题目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
请按任意键继续. . .

#include <iostream>
#include <algorithm>
#include <string>
#include <stdlib.h>
using namespace std;
//判断是否为跳跃数
bool isz(int ma)
{
        string a;
        char buf[20];
        itoa(ma,buf,10);
        string A(buf);
        string B,C;
        B=A;
        C=A;
        sort(B.begin(),B.end());
        if(B==A)  return false;
        reverse(C.begin(),C.end());
        sort(C.begin(),C.end());
        reverse(C.begin(),C.end());
        if(C==A)  return false;
        
        return true;
}
int main()
{
        int m = 0;
        double k;
        for (int i = 1; i <10000000; i++)
        {
                //跳跃数增加
                if(isz(i)) m++;
                //std::cout<<"1-"<<i<<"跳跃数有:"<<m<<"个";
                k=((double)m)/((double)i);
        //        std::cout<<"比例:"<<k <<endl;
                if(k>=0.99f)
                {
                        std::cout<<"1-"<<i<<"跳跃数有:"<<m<<"个";
                        std::cout<<"比例:"<<k <<endl;
                system("pause");
                }
        }
        return 0;
};

jerryxjr1220

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

这题答案应该是1587000

def isjump(n):
        if n<100:
                return False
        else:
                flagup, flagdown = 1, 1
                t1, m1 = n% 10, n//10
                while m1:
                        if m1%10<=t1:
                                t1, m1 = m1%10, m1//10
                        else:
                                flagup = 0
                                break
                t2, m2 = n% 10, n//10
                while m2:
                        if m2%10>=t2:
                                t2, m2 = m2%10, m2//10
                        else:
                                flagdown = 0
                                break
                if flagup == 0 and flagdown == 0:
                        return True
                else:
                        return False

count = 0
index = 0
while True:
        index += 1
        if isjump(index):
                count += 1
        if count/index == 0.99:
                print(index)
                break

jerryxjr1220

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

def is_jump(n):
    if n < 100:
        return False
    up_flag, down_flag = 0, 0
    l = len(str(n))
    n0 = int(str(n)[0])
    for i in range(1, l):
        n1 = int(str(n)[i])
        if n1 > n0:
            up_flag = 1
        if n1 < n0:
            down_flag = 1
        if up_flag == 1 and down_flag == 1:
            return True
        n0 = n1
    return False

jumps = 0
n = 100
while jumps / n != 0.99:
    if is_jump(n):
        jumps += 1
    n += 1
print(n)

输出：
1587100
[Finished in 5.1s]

gunjang

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

输出：

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

gunjang

import time
st = time.time()
def getBouncyNumtype(n):
        if n < 10:
                return 3 #same
        upflag,downflag = False, False
        x, n = n%10, n//10
        while n > 0:
                if n%10 < x: #increasing
                        upflag = True
                elif n%10 > x: #decreasing
                        downflag = True
                if upflag and downflag:
                        return 0                
                x, n = n%10, n//10
        if upflag:
                return 1
        if downflag:
                return 2
        return 3 #same

n = 100
cnt = 0
while n//100 != n-cnt:                
        t = getBouncyNumtype(n//100)
        firstDigit = n//100 % 10
        if t==1: #increasing
                cnt += 100 - (10-firstDigit+1)*(10-firstDigit)//2                
        elif t==2: #decreasing
                cnt += 100 - (firstDigit+1+1)*(firstDigit+1)//2 
        elif t==0: #bouncy
                cnt += 100
        else: # all same digit
                cnt += (10+firstDigit+2)*(9-firstDigit)//2 + (10+11-firstDigit)*firstDigit//2 - 9
        n += 100
        #if n==21800: break

print(n, cnt, cnt/n) #1587100 1571229 0.99 #why 1587000
print(time.time()-st) #0.031200170516967773

永恒的蓝色梦想

def isBouncy(n):
    n = [int(i)for i in str(n)]
    r = range(1, len(n))

    for i in r:    # increasing
        if n[i-1] > n[i]:
            break    # 如果不是递增数退出
    else:
        return False    # 如果没有退出返回False

    for i in r:    # decreasing
        if n[i-1] < n[i]:
            break    # 如果不是递减数退出
    else:
        return False    # 如果没有退出返回False

    return True


bouncyCount = 0
count = 100

while bouncyCount * 100 - count * 99:
    bouncyCount += isBouncy(count)
    count += 1

print(count)

debuggerzh

1587000

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

#include<iostream>
#include<cstdio>
using namespace std;

const int M = 2e6;
const double EPS = 1e-15;

bool is_incr(int x){
  int curr,next = x % 10;
  x /= 10;

  while(x){
    curr = x % 10;
    if (next < curr)  return false;
    next = curr;
    x /= 10;
  }
  return true;
}

bool is_decr(int x){
  int curr,next = x % 10;
  x /= 10;

  while(x){
    curr = x % 10;
    if (next > curr)  return false;
    next = curr;
    x /= 10;
  }
  return true;
}


int main(){
  int cnt = 0;
  for (int i = 1; ;i++){
    if (is_incr(i) || is_decr(i) )  continue;
    cnt++;

    if (cnt / (double)(i) > 0.99) {cout << i << endl; break;}
  }
  //cout << cnt << endl;
  return 0;
}