小练习 20170515 考察“跳跃数”的密度

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

                               
登录/注册后可看大图

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成，即5.8 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

----回帖需写明解题思路，鼓励在程序中加上注释


一些鱼油反映题目有些过难，为此略过一部分偏难的题目。



题目：

如果一个数的每一位都大于等于前一位，则称其为递增数，例如 134468。

类似的，如果一个数的每一位都小于等于前一位，则称其为递减数，例如 66420。

如果一个正整数既不是递增数也不是递减数，则称其为一个“跳跃数”，例如 155349。

显然 100 以下不存在任何跳跃数，但是 1000 以下的数中一半以上（525）个是跳跃数。事实上，跳跃数比例首次超过 50% 的数是 538。

令人惊奇的是，跳跃数的数量越来越多，到 21780 时跳跃数的比例已经达到 90%。

求使得跳跃数比例恰好等于 99% 的最小的数。

WelanceLee

1. def nonskip(a):
   
2.     b = list(str(a))
   
3.     b.sort()
   
4.     c = ''.join(b)
   
5.     b.sort(reverse = True)
   
6.     d =''.join(b)
   
7.     if int(d) == a or int(c) == a:
   
8.         return True
   
9.     return False
   
10.    
    
11. i = 1
    
12. n = 0
    
13. while True:
    
14.     if nonskip(i):
    
15.         n += 1
    
16.     if n/i == 0.01:
    
17.         print(i)
    
18.         break
    
19.     i += 1

复制代码

答案是1587000

lovesword

1. #!/usr/bin/env python
   
2. # coding=utf-8
   
3. # python 2.7
   
4. import time
   
5. start = time.time()
   
6. n,t,bl=1,[],0.0
   
7. while bl<>0.99:
   
8.         if reduce(lambda x,y:[False,y][x<=y and x<>False],str(n)) :
   
9.                 pass
   
10.         elif reduce(lambda x,y:[False,y][x>=y and x<>False],str(n)):
    
11.                 pass
    
12.         else:
    
13.                 t.append(n)
    
14.         bl = float(len(t))/n
    
15.         n=n+1
    
16. print 'sec:',time.time()-start
    
17. print 'res:',n-1

复制代码

sec: 6.24860095978
res: 1587000

jerryxjr1220

思路就是先定义一个判断跳跃数的函数，然后用穷举法依次测试，直到跳跃数与总数的比值是0.99.

1. def isjump(n):
   
2.         if n<100:
   
3.                 return False
   
4.         else:
   
5.                 flagup, flagdown = 1, 1
   
6.                 t1, m1 = n% 10, n//10
   
7.                 while m1:
   
8.                         if m1%10<=t1:
   
9.                                 t1, m1 = m1%10, m1//10
   
10.                         else:
    
11.                                 flagup = 0
    
12.                                 break
    
13.                 t2, m2 = n% 10, n//10
    
14.                 while m2:
    
15.                         if m2%10>=t2:
    
16.                                 t2, m2 = m2%10, m2//10
    
17.                         else:
    
18.                                 flagdown = 0
    
19.                                 break
    
20.                 if flagup == 0 and flagdown == 0:
    
21.                         return True
    
22.                 else:
    
23.                         return False
    
24. 
    
25. count = 0
    
26. index = 0
    
27. while True:
    
28.         index += 1
    
29.         if isjump(index):
    
30.                 count += 1
    
31.         if count/index == 0.99:
    
32.                 print(index)
    
33.                 break

复制代码

输出：
1587000
[Finished in 2.5s]

另外，一种是变成字符串来判断，但是运算时间相对会长一点。

1. def is_jump(n):
   
2.     if n < 100:
   
3.         return False
   
4.     up_flag, down_flag = 0, 0
   
5.     l = len(str(n))
   
6.     n0 = int(str(n)[0])
   
7.     for i in range(1, l):
   
8.         n1 = int(str(n)[i])
   
9.         if n1 > n0:
   
10.             up_flag = 1
    
11.         if n1 < n0:
    
12.             down_flag = 1
    
13.         if up_flag == 1 and down_flag == 1:
    
14.             return True
    
15.         n0 = n1
    
16.     return False
    
17. 
    
18. jumps = 0
    
19. n = 100
    
20. while jumps / n != 0.99:
    
21.     if is_jump(n):
    
22.         jumps += 1
    
23.     n += 1
    
24. print(n)

复制代码

输出：
1587000
[Finished in 5.1s]

ooxx7788

1. def ep112():
   
2.     flag = 0
   
3.     total = 0
   
4.     n = 100
   
5.     check = lambda s : 0 if ''.join(sorted(s)) in [s, s[::-1]] else 1
   
6.     while flag != 0.99:
   
7.         total += check(str(n))
   
8.         flag = total / n
   
9.         n += 1
   
10.     print(n-1)

复制代码

但是我认为这不算解题。

1. %timeit ep112()
   
2. 1587000
   
3. 1587000
   
4. 1587000
   
5. 1587000
   
6. 1 loop, best of 3: 3.25 s per loop

复制代码

小Q学Python

思路：这题的核心是如何效率的判断一个数是否为跳跃数
1.最开始，用sorted来正序、逆序排列后比较，虽然写法相当简单，但效率不高。数字位数越大，这种方式的效率就降了下来。
2.按照最基本的想法，如果能从前几位就判断是否跳跃数，效率就提高很多

1. def isTY(number):
   
2.         if number < 100:
   
3.                 return False
   
4.         a = str(number)
   
5.         flag = 0
   
6.         for i in range(len(a)-1):
   
7.                 a1,a2 = int(a[i]),int(a[i+1])
   
8.                 if flag == 0:
   
9.                         if a1 > a2:
   
10.                                 flag = 1
    
11.                                 continue
    
12.                         if a1 < a2:
    
13.                                 flag = 2
    
14.                                 continue
    
15.                 if flag == 1:
    
16.                         if a1 < a2:
    
17.                                 return True
    
18.                 if flag == 2:
    
19.                         if a1 > a2:
    
20.                                 return True
    
21.         return False
    
22. 
    
23. 
    
24. def getnumber(pct):
    
25.         number = 1
    
26.         counts = 0
    
27.         while True:
    
28.                 if isTY(number):
    
29.                         counts+=1
    
30.                 if counts/number >= pct:
    
31.                         break
    
32.                 number += 1
    
33.         return number

复制代码

In [36]: %time getnumber(0.99)
Wall time: 6.19 s
Out[36]: 1587000

余欲渔

1. i,t=0,0
   
2. while True:
   
3.     i+=1
   
4.     stri=list(str(i))
   
5.     seti=sorted(set(stri))
   
6.     if stri[0]==seti[0]:
   
7.         1
   
8.     elif stri[0]==seti[-1]:
   
9.         seti.reverse()
   
10.     else:
    
11.         t+=1
    
12.         if t/i>=0.99:break
    
13.         continue
    
14.     stric=[stri[0]]
    
15.     for x in stri :
    
16.         if x != stric[-1]:
    
17.             stric.append(x)
    
18.     if stric != seti :
    
19.         t+=1        
    
20.         if t/i>=0.99:break
    
21. print(i,t)

复制代码

1.   RESTART: C:\Users\Administrator\AppData\Local\Programs\Python\Python35-32\test.py
   
2. 1587000 1571130

复制代码

zahi

# -*- coding:utf-8 -*-

total = 100                        #查找起始
count = 0                          #查找到跳跃数
dis = 0             #上次查找了几位
com = '100'         #上次已比较的数字

while 1:
        num = str(total)

        if num[0:dis] == com:                # 如果前面几位为跳跃数,则一定为跳跃数 如 1430为跳跃数  1431 也为跳跃数
                count += 1
        else:
                flg = 0         #0 相等 1 递减 -1 递增
                com = b = num[0:1]               
                dis = 1
               
                for a in num[1:]:
                        a, b = b, a
                        dis += 1                   #记录计较位数
                        com += b        #记录已计较的数值

                        if a == b:                #相等进行进行下次比较
                                continue
                        elif a < b:
                                tmp = -1
                        elif a > b:
                                tmp = 1

                        if flg == 0:        #如果上次比较结果为空, 记录这次比较结果
                                flg = tmp
                        elif flg != tmp:        # 上次比较结果和这次不行等,即为跳跃数
                                count += 1
                                break

        if count / total >= 0.99:        # 满足条件, 跳出循环
                print(total)
                break

        total += 1

朝暾

从1开始以步长为1进行递增，每到一个数就记录当前跳跃数以及总数，计算比例，满足比例就结束。
程序结果：使得跳跃数比例恰好等于 99% 的最小的数是1587000。

1. def is_tiaoyue(num): #判断是否是跳跃数
   
2.     return not (is_dizeng(num) or is_dijian(num))
   
3. 
   
4. def is_dizeng(num): #判断是否是递增数
   
5.     string = str(num) #数字转换成字符串以便进行每一位的遍历及计算
   
6.     length = len(string)
   
7.     if length == 1: #个位数按照题意既是递增数又是递减数
   
8.         return True
   
9.     for i in range(length-1):
   
10.         if int(string[i+1]) - int(string[i]) >= 0:
    
11.             continue
    
12.         else: #有一位不符合条件即为假
    
13.             return False
    
14.     return True #循环顺利结束，所有位都满足条件，为真
    
15. 
    
16. def is_dijian(num): #判断是否是递减数，与递增数判断几乎一模一样，只需改一下判断条件
    
17.     string = str(num)
    
18.     length = len(string)
    
19.     if length == 1:
    
20.         return True
    
21.     for i in range(length-1):
    
22.         if int(string[i+1]) - int(string[i]) <= 0:
    
23.             continue
    
24.         else:
    
25.             return False
    
26.     return True
    
27. 
    
28. def shu(): #生成器，不断返回一个整数
    
29.     i = 1
    
30.     while True:
    
31.         yield i
    
32.         i += 1
    
33. 
    
34. count = 0 #记录跳跃数数目
    
35. total = 0 #记录总数
    
36. for i in shu(): #不断计算，直到达到要求的比例
    
37.     if is_tiaoyue(i):
    
38.         count += 1
    
39.     total += 1
    
40.     if count / total == 0.99:
    
41.         break
    
42. 
    
43. print('使得跳跃数比例恰好等于 99% 的最小的数是{}'.format(total))
    

复制代码

当回首遇上转身

1. def jump_num():
   
2.     count = 0
   
3.     num = 0
   
4.     while 1:
   
5.         flag1,flag2 = 0,0
   
6.         num_temp = num
   
7.         while num_temp//10 > 0:
   
8.             temp = num_temp // 10
   
9.             a = num_temp % 10
   
10.             b = temp % 10
    
11.             if a > b:
    
12.                 flag1 = 1
    
13.             if a < b:
    
14.                 flag2 = 1
    
15.             if flag1 == 1 and flag2 == 1:
    
16.                 count += 1
    
17.                 break
    
18.             num_temp = temp  
    
19.         num += 1
    
20.         if count*100 == num*99:
    
21.             return(num)
    

复制代码

shigure_takimi

lovesword 发表于 2017-5-15 10:20
sec: 6.24860095978
res: 1587000

1. import time
   
2. 
   
3. t1 = time.time()
   
4. 
   
5. def isJumpNumber(n):
   
6.     if n <= 100:
   
7.         return False
   
8.     else:
   
9.         strN = str(n)
   
10.         minN = ''.join(sorted(strN))
    
11.         maxN = minN[::-1]
    
12.         if strN not in (minN, maxN):
    
13.             return True
    
14.         else:
    
15.             return False
    
16. 
    
17. n = 1
    
18. count = 0
    
19. while True:
    
20.     if isJumpNumber(n):
    
21.         count += 1
    
22.     if count/n >= 0.99:
    
23.         break
    
24.     n += 1
    
25. print(n)
    
26.    
    
27. t2 = time.time()
    
28. print(t2- t1)
    
29. 
    
30. #  1587000
    
31. #  耗时6.0秒
    

复制代码