求高手给出这个google题目算法的思路
还是google的面试题,在网上找了一个算法,但是里面有个看不明白
下面是题目
有这样一个函数f(n)，对于任意正整数n，它表示从 0 到 n 之间出现“1”的个数，
比如 f(1) = 1, f(13) = 6,请列出从 1 到 1234567890 中所有的 f(n) = n 的 n, 要求准确快速.
现在f(n)我求出来了.这个题目的考点是后者,怎么列出那些n呢
我现在找出一个算法,可以在1ms内列出这些n
但是我有语句话没看明白
我贴在下面,大家帮我看看,
void display(MyLong number)
{
MyLong i = 0 ;//从0开始 "假遍历 "
MyLong OneCount = 0 ;
while( i < number )
{
//调用函数来求得1的个数
OneCount = Get1Count(i) ;
//下面开始分情况处理
if( OneCount == i )//直接输出
{
printf( "%d\n ",i) ;
i++ ;//加到下一个数,下一个数可能是要找的
}
else if ( i > OneCount ) //这里的else不能少.也没有else的话走了上面一句后很可能会走到这里的一句,造成输出结果丢失.因为不加else时如果走到了这一步,i +1但是这里的onecount 却还是原来上一个i得出的值,所以造成漏输
{
if ( ( i - OneCount ) / 10 > 0 )//两数之间的差是否大于1位数,因为在个位数上0到9只有1个1
{
i += ( i - OneCount ) / 10 ;
}
else //当他们的差是一位数的情况时
{
i++ ; // 这是正常情况下的+1 ,因为加1的情况下再次判断时是有可能成为结果的.
//比如199980不是目标,但199981就是目标了,所以这里不要加多了
}
}
else if( i < OneCount )//这种情况下直接跳过,不用再考虑了.
//即使i += 1 ,也 <=OneCount 比如i = 199991,count = 199998
{
i = OneCount ;
}
}
}
我不明白的地方是( i - OneCount ) / 10 > 0,为什么这么写
为什么下面i += ( i - OneCount ) / 10 ;呢
其他的我都看懂了,就是这句实在看不懂,
请大家帮我解释解释
谢谢
[解决办法]
f(13) = 6 ？？？？？
---
f(13) = 5
------------
#include <iostream.h>
#include <string>
using namespace std;
int main()
{
const char *t = "1 ";//比较字符
int input;//循环终值
int step = 0;//含有1的数字的个数
cin> > input;
for (int j=0; j <=input; j++)
{
char *p = new char(10);
sprintf(p, "%d ", j);
string s(p);
if (s.find(t) == 0)//包含字符
{
step++;
}
}
cout < <step < <endl;
return 0;
}
[解决办法]
楼主的算法不是穷举的,是变步长的
我不明白的地方是( i - OneCount ) / 10 > 0,为什么这么写
为什么下面i += ( i - OneCount ) / 10 ;呢
=============================================
因为最大的数是10位，所以一个数最多10个 '1 '，如果( i - OneCount ) / 10 > 0
则i加上( i - OneCount ) / 10 后，OneCount不会超过i，就是说i到i+( i - OneCount ) / 10之间不可能有满足条件的数。
[解决办法]
> > 我不明白的地方是( i - OneCount ) / 10 > 0,为什么这么写
> > 为什么下面i += ( i - OneCount ) / 10 ;呢
这个不难理解. (i-OneCount> /10 > 0 的情况表示i比f(1)大很多的情况下(至少大于等于10的情况下), 这种情况下, 步子要迈大一点, 而不是要象小脚娘娘那样, 一次只加1.
至于为什么步子是 (i-OneCount)/10, 即i += (i-OneCount)/10;呢? 那是因为考虑到一种极端情况下, 譬如下一个i是1111111111的情况, 那时候, i的步子只能是1, 因为这种情况下, OneCount增加的是10, 其他情况下, 对于i每增加1, OneCount增加的数目都不会超过10的, 所以说, i += (i-OneCount)/10; 是一种极端保守的步子. 当然如果步子迈大一点, 在极端情况下, 是有可能有漏网之鱼的.
LZ的这种算法, 效率其实是不大高的.
[解决办法]
酱紫可以不...
ul c1( ul x )
{
static const ul pr[] ={0,1,20,300,4000,50000,600000,7000000,80000000,900000000};
ul d , r = 0 , m = 1000000000 , w=9;
for( ;w; m/=10,--w )
{
d=(x/m)%10; x%=m;
if(d)r += d * pr[w] + (d> 1?m:(x+1));
}
return r+(x> 0);
}
[解决办法]
if ( ( i - OneCount ) / 10 > 0 )//两数之间的差是否大于1位
如果你的i只比onecout多一位数，那么可能i ++ 就有可能找到
满足条件的数。
但是如果i比onecount多了两位数了。
步长就没有必要+1了。浪费子弹。
所以直接加上多的这个两位数。
如果是30就加30，如果是40就加40。
因为在此段区间中。OneCount的值了不起就是加上 (i - OneCount ) / 10这么多
次个位上出现1的机会。所以步长就可以跳
[解决办法]
f(13) = 6 ？？？？？
---
f(13) = 5
//01 02 03 04 05 06 07 08 09 10 11 12 13
6个
[解决办法]
http://community.csdn.net/Expert/topic/5416/5416154.xml?temp=.117779
[解决办法]
OO给出的程序
对于这个不理解
if(ncount > (number + (n-1)) ) //ncount number+(n-1)比较
{
return maxcount;
}
if(maxcount < number) //maxcount number比较
{
return maxcount;
}
能不能解释一二，多谢
[解决办法]
mark一下以后看
[解决办法]
强人多！
[解决办法]
f(13) = 6 ？？？？？
