题目112：考察“跳跃数”的密度

欧拉计划

Bouncy numbers

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.

Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.

Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.

题目：

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

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

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

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

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

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

迷雾少年

1-1587002跳跃数有:1571132个比例:0.99
请按任意键继续. . .

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <string>
   
4. #include <stdlib.h>
   
5. using namespace std;
   
6. //判断是否为跳跃数
   
7. bool isz(int ma)
   
8. {
   
9.         string a;
   
10.         char buf[20];
    
11.         itoa(ma,buf,10);
    
12.         string A(buf);
    
13.         string B,C;
    
14.         B=A;
    
15.         C=A;
    
16.         sort(B.begin(),B.end());
    
17.         if(B==A)  return false;
    
18.         reverse(C.begin(),C.end());
    
19.         sort(C.begin(),C.end());
    
20.         reverse(C.begin(),C.end());
    
21.         if(C==A)  return false;
    
22.        
    
23.         return true;
    
24. }
    
25. int main()
    
26. {
    
27.         int m = 0;
    
28.         double k;
    
29.         for (int i = 1; i <10000000; i++)
    
30.         {
    
31.                 //跳跃数增加
    
32.                 if(isz(i)) m++;
    
33.                 //std::cout<<"1-"<<i<<"跳跃数有:"<<m<<"个";
    
34.                 k=((double)m)/((double)i);
    
35.         //        std::cout<<"比例:"<<k <<endl;
    
36.                 if(k>=0.99f)
    
37.                 {
    
38.                         std::cout<<"1-"<<i<<"跳跃数有:"<<m<<"个";
    
39.                         std::cout<<"比例:"<<k <<endl;
    
40.                 system("pause");
    
41.                 }
    
42.         }
    
43.         return 0;
    
44. };

复制代码

jerryxjr1220

迷雾少年 发表于 2016-8-31 17:28
1-1587002跳跃数有:1571132个比例:0.99
请按任意键继续. . .

这题答案应该是1587000

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

复制代码

jerryxjr1220

思路就是先定义一个函数判别是否是跳跃数，然后从100开始穷举，直到跳跃数/总数=0.99为止。

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)

复制代码

输出：
1587100
[Finished in 5.1s]

gunjang

jerryxjr1220 发表于 2017-5-15 17:09
思路就是先定义一个函数判别是否是跳跃数，然后从100开始穷举，直到跳跃数/总数=0.99为止。

输出：

兄，我的答案也是1587100，但是正确答案是1587000，奇怪了

gunjang

1. import time
   
2. st = time.time()
   
3. def getBouncyNumtype(n):
   
4.         if n < 10:
   
5.                 return 3 #same
   
6.         upflag,downflag = False, False
   
7.         x, n = n%10, n//10
   
8.         while n > 0:
   
9.                 if n%10 < x: #increasing
   
10.                         upflag = True
    
11.                 elif n%10 > x: #decreasing
    
12.                         downflag = True
    
13.                 if upflag and downflag:
    
14.                         return 0               
    
15.                 x, n = n%10, n//10
    
16.         if upflag:
    
17.                 return 1
    
18.         if downflag:
    
19.                 return 2
    
20.         return 3 #same
    
21. 
    
22. n = 100
    
23. cnt = 0
    
24. while n//100 != n-cnt:               
    
25.         t = getBouncyNumtype(n//100)
    
26.         firstDigit = n//100 % 10
    
27.         if t==1: #increasing
    
28.                 cnt += 100 - (10-firstDigit+1)*(10-firstDigit)//2               
    
29.         elif t==2: #decreasing
    
30.                 cnt += 100 - (firstDigit+1+1)*(firstDigit+1)//2
    
31.         elif t==0: #bouncy
    
32.                 cnt += 100
    
33.         else: # all same digit
    
34.                 cnt += (10+firstDigit+2)*(9-firstDigit)//2 + (10+11-firstDigit)*firstDigit//2 - 9
    
35.         n += 100
    
36.         #if n==21800: break
    
37. 
    
38. print(n, cnt, cnt/n) #1587100 1571229 0.99 #why 1587000
    
39. print(time.time()-st) #0.031200170516967773

复制代码

永恒的蓝色梦想

1. def isBouncy(n):
   
2.     n = [int(i)for i in str(n)]
   
3.     r = range(1, len(n))
   
4. 
   
5.     for i in r:    # increasing
   
6.         if n[i-1] > n[i]:
   
7.             break    # 如果不是递增数退出
   
8.     else:
   
9.         return False    # 如果没有退出返回False
   
10. 
    
11.     for i in r:    # decreasing
    
12.         if n[i-1] < n[i]:
    
13.             break    # 如果不是递减数退出
    
14.     else:
    
15.         return False    # 如果没有退出返回False
    
16. 
    
17.     return True
    
18. 
    
19. 
    
20. bouncyCount = 0
    
21. count = 100
    
22. 
    
23. while bouncyCount * 100 - count * 99:
    
24.     bouncyCount += isBouncy(count)
    
25.     count += 1
    
26. 
    
27. print(count)

复制代码

debuggerzh

1587000

Process returned 0 (0x0)   execution time : 0.082 s
Press any key to continue.
这浮点精度怎么就这么迷……

1. #include<iostream>
   
2. #include<cstdio>
   
3. using namespace std;
   
4. 
   
5. const int M = 2e6;
   
6. const double EPS = 1e-15;
   
7. 
   
8. bool is_incr(int x){
   
9.   int curr,next = x % 10;
   
10.   x /= 10;
    
11. 
    
12.   while(x){
    
13.     curr = x % 10;
    
14.     if (next < curr)  return false;
    
15.     next = curr;
    
16.     x /= 10;
    
17.   }
    
18.   return true;
    
19. }
    
20. 
    
21. bool is_decr(int x){
    
22.   int curr,next = x % 10;
    
23.   x /= 10;
    
24. 
    
25.   while(x){
    
26.     curr = x % 10;
    
27.     if (next > curr)  return false;
    
28.     next = curr;
    
29.     x /= 10;
    
30.   }
    
31.   return true;
    
32. }
    
33. 
    
34. 
    
35. int main(){
    
36.   int cnt = 0;
    
37.   for (int i = 1; ;i++){
    
38.     if (is_incr(i) || is_decr(i) )  continue;
    
39.     cnt++;
    
40. 
    
41.     if (cnt / (double)(i) > 0.99) {cout << i << endl; break;}
    
42.   }
    
43.   //cout << cnt << endl;
    
44.   return 0;
    
45. }
    

复制代码