| 查看: 219 | 回复: 0 | |||
| 当前主题已经存档。 | |||
[交流]
一道google面试题 n=f(n) 我算出的最大值为1111111110
|
|||
|
有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？ 原题的意思好像是这样的，前几天是在我们校园网上发现这个问题的，发帖的人说让写出计算机在5分钟内得到的最大值，本人经过一段时间思考，写出一个算法，在10秒之内得到了一个最大值，并且证明这就是 n=f(n) 的最大值！ 现在把自己的想法拿出来，供大家讨论！ 本人得出的最大值是：n=1111111110.000000 基本思路是： 1：先得到n=f(n)中n最大值存在的大范围（int CompareFun()做的工作） 原理： 设：FunctionNum(Num)为长度为1到长度Num的最大数之间所有数中1的总个数（例：Num=3则NUM(3)为1到999中的1的总数） FunctionMax(Num)为Num个9,如FuntionMax(3)=999，即公式FunctionMax(Num)=10^Num-1； 则由题意知：FunctionNum(1)=1; (1) FunctionNum(Num)=10^(Num-1)+10*FunctionNum(Num-1); (2) 由(1)(2)得：FunctionNum(Num)=Num*10^(Num-1); 现在就是要看看FunctionMax(Num)=10^Num-1; 与FunctionNum(Num)=len*10^(Num-1); 在Num属于自然数且趋于无穷时有没有交点了; 很明显FunctionNum(Num)增长的快，且FunctionMax(1)>FunctionNum(1); 所以FunctionNum(Num)与FunctionMax(Num)在实数范围当Num>1时一定有交点； 由 int CompareFun(); 计算出此数存在的范围为999999999.000000到 9999999999.000000 2：从999999999.000000＋1开始 计算此数存在的小范围（ 程序把这个范围缩小到了2000以内，是为了说明问题方便，其实范围可了再小到两位数甚至个位数） 原理： 因为当n 在最高位是1到2之间时候f(n)是增长相对最快的，如：10－－20,100000－200000等； 所以最可能出现在这个范围之内，因此用以下代码加以筛选： double n=FunctionMax(CopmareFun()-1)+1; double ncopy=n; int len=GetNumLen(n)-2; int i=1; while(len>2) { if( (n-f(n)) >=1000 ) { n=n+Get10Square(len--); ncopy=n; } else { n=ncopy; } } double k=n+1001.0; 3：最后用 double f(double Num); 一个一个判断 结果存在xx.txt和yy.txt之中。 关于f()函数的几点说明： 任意数计算其中1的个数 1.从这个数Num最高位算起，先算出这个数一共多少位bitnum 2.如果这个数只有一位，且不为0，总数加1,to end;这个数为0，则不加，to end 3.如果这个数的位数bitnum不为1，计算S=S+FunctionNum(bitnum-1)*head; 其中head为这个数的最高位 4.如果最高位为1，则计算S=S+DropHead(Num)+1；DropHead(Num)为这个数Num去掉最高位余下的部分 5.否则计算S=S+Get10Square(bitnum-1)；其中Get10Square(bitnum-1)为10＾(bitnum-1) 6.去掉这个数的最高位，返回1。 7.end 关于n=1111111110.000000 是n=f(n)的最大值的证明： 因为当n 在最高位是1到2之间时候f(n)是增长最快的，如：10－20,100000－200000等； 当n=999..999时f(n)达到n 进位(n=100..00)之前达到最大； 证明过程： 因为：f(9999999999.0)=10000000000.0; 所以：f(10000000000.0)=10000000001.0; 知:在 n=10000000000.0到19999999999.0中 f(n)恒>n 且 f(19999999999.0)(已经)远远 > 19999999999.0; (0) 又因为：f(9999999999.0)>9999999999.0; (1) 所以在 20000000000.0到29999999999.0 30000000000.0到39999999999.0 ....... 90000000000.0到99999999999.0 等等的这各9999999999.0+1个数之间 都会出现 f(29999999999.0)-f(20000000000.0)=f(9999999999.0); (2) 29999999999.0-20000000000.0=9999999999.0; (3) 由(0)(1)(2)(3)得: f(29999999999.0)远远 > 29999999999.0 同理可证 f(39999999999.0)远远 > 39999999999.0 f(49999999999.0)远远 > 49999999999.0 .... f(99999999999.0)远远 > 99999999999.0 当99999999999.0变成99999999999.0+1=10000000000.0时 在f(10000000000.0) 当然仍远远 > 10000000000.0 然后n 在 10000000000.0 到 20000000000.0 之间时 f(n)会长的更快 依些类推，可知 n> 1111111110.00000 后 n 的增长速度远远小于f(n)的增长速度！ 证毕！ 附程序C语言代码： #include "stdio.h" int GetNumLen(double Num); double Get10Square(int Num);//10^Num double FunctionMax(int Num);//10^Num-1 double FunctionNum(int Num);//Num*10^(Num-1) double DropHead(double Num); int GetHead(double Num); int CompareFun(); double f(double Num); main() { FILE* fp; FILE* savefp; fp=fopen("xx.txt","w"  ;savefp=fopen("yy.txt","w" ;double n=FunctionMax(CopmareFun()-1)+1; double ncopy=n; int len=GetNumLen(n)-2; int i=1; while(len>2) { if( (n-f(n)) >=1000 ) { n=n+Get10Square(len--); ncopy=n; } else { n=ncopy; } } double k=n+1001.0; while(n<=k) { double fn=f(n); printf("%f",n); printf(" %f",fn); if(n==fn) printf(" %f",n); printf("\n" ;fprintf(fp,"%f",n); fprintf(fp," %f",fn); if(n==fn) { fprintf(fp," %f",n); fprintf(savefp,"%f\n",n); } fprintf(fp,"\n" ;n++; } printf("game over\n" ;fclose(fp); fclose(savefp); return true; } int GetNumLen(double Num) { int len=1; while((Num=Num/10)>=1) { len++; } return len; } double Get10Square(int Num) { double return_value=1; for(int i=0;i return return_value; } double FunctionNum(int Num) { return Num*Get10Square(Num-1); } double FunctionMax(int Num) { return Get10Square(Num)-1; } int CompareFun() { int i=1; while(FunctionMax(i)>FunctionNum(i)) i++; return i; } double DropHead(double Num) { int len=GetNumLen(Num); if(len==1) return 0; else { double HeadUnit=Get10Square(len-1); while(Num>=HeadUnit) { Num-=HeadUnit; } return Num; } } int GetHead(double Num) { double HeadUnit=Get10Square(GetNumLen(Num)-1); return (int)(Num/HeadUnit); } double f(double Num) { double S=0; int bitnum; bitnum=GetNumLen(Num); int interrupt=1; while(interrupt) { if(bitnum==1) { if(Num!=0) S++; else { } interrupt=0; } else { int head=GetHead(Num); S=S+FunctionNum(bitnum-1)*head; if(head==1) { S=S+DropHead(Num)+1; } else { S=S+Get10Square(bitnum-1); } } Num=DropHead(Num); bitnum=GetNumLen(Num); } return S; } 另附n=f(n)的所有值(均由 double f(double Num) 得出)： 0 1 199981.000000 199982.000000 199983.000000 199984.000000 199985.000000 199986.000000 199987.000000 199988.000000 199989.000000 199990.000000 200000.000000 200001.000000 1599981.000000 1599982.000000 1599983.000000 1599984.000000 1599985.000000 1599986.000000 1599987.000000 1599988.000000 1599989.000000 1599990.000000 2600000.000000 2600001.000000 13199998.000000 35000000.000000 35000001.000000 35199981.000000 35199982.000000 35199983.000000 35199984.000000 35199985.000000 35199986.000000 35199987.000000 35199988.000000 35199989.000000 35199990.000000 35200000.000000 35200001.000000 117463825.000000 500000000.000000 500000001.000000 1111111110.000000 [ Last edited by beast_me on 2006-10-16 at 18:36 ] |
回复此楼» 猜你喜欢
327求调剂
已经有16人回复
-
085600材料与化工329分求调剂
已经有16人回复
-
考研调剂
已经有8人回复
-
279学硕食品专业求调剂院校
已经有23人回复
-
各位老师好，求调剂，本科211，一志愿天津大学生物与医药学硕，差两名录取。
已经有8人回复
-
288求调剂，一志愿华南理工大学071005
已经有21人回复
-
化学070300 求调剂
已经有19人回复
-
B区0809 ，数一英一，290 求调剂
已经有4人回复
-
290求调剂
已经有16人回复
-
274求调剂
已经有8人回复
