题目112：考察“跳跃数”的密度
Bouncy numbersWorking 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;
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;
}; 迷雾少年 发表于 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 思路就是先定义一个函数判别是否是跳跃数，然后从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))
for i in range(1, l):
n1 = int(str(n))
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
jerryxjr1220 发表于 2017-5-15 17:09
思路就是先定义一个函数判别是否是跳跃数，然后从100开始穷举，直到跳跃数/总数=0.99为止。
输出：
兄，我的答案也是1587100，但是正确答案是1587000，奇怪了 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 本帖最后由 永恒的蓝色梦想 于 2021-1-27 16:00 编辑
def isBouncy(n):
n =
r = range(1, len(n))
for i in r: # increasing
if n > n:
break # 如果不是递增数退出
else:
return False # 如果没有退出返回False
for i in r: # decreasing
if n < n:
break # 如果不是递减数退出
else:
return False # 如果没有退出返回False
return True
bouncyCount = 0
count = 100
while bouncyCount * 100 - count * 99:
bouncyCount += isBouncy(count)
count += 1
print(count) 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;
}
页:
[1]