google笔试题,进来看看,
有这样一个函数f(n)，对于任意正整数n，它表示从 0 到 n 之间出现“1”的个数，
比如 f(1) = 1, f(13) = 6,请列出从 1 到 1234567890 中所有的 f(n) = n 的 n, 要求准确快速.
[解决办法]
int f(int n)
{
int m,k,count;
if(n==1)
{printf( "%d/n ",1);return 1;}
m=n;
while(m> 0)
{
k=m%10;
if(k==1)
count++;
m=m/10;
}
count=count+f(n-1);
if(count==n)
printf( "%d/n ",n);
return count;
}
[解决办法]
#include <stdio.h>
#include <conio.h>
#define LEN 20
void f(char *str) {
char a[LEN],ai=0,*fnt=str,*now,*end;
while (*++fnt);
end=fnt;
while (--fnt> =str)
if (*fnt== ' ') {
now=fnt+1;
while (now <end)a[ai++]=*now++;
a[ai++]= ' ';
end=fnt;
}
while (++fnt <end)a[ai++]=*fnt;
a[ai++]=0;
printf(a);
}
void main() {
char *str= "I am a student ";
f(str);
getch();
}
[解决办法]
f(13) = 6
1、10、11、12、13
^ ^ ^^ ^ ^
有点意思，标记一下
---------------------------------
呵呵，11可是两个1呀！
[解决办法]
int Count1( int n )
{
//这个函数计算给定数字n中1的个数
int iRet = 0;
int m = n;
while(m> 0)
{
if( 1 == m % 10 )
++iRet;
m /= 10;
}
return iRet;
}
int Calc( int n )
{
if( n == 1 )
{
cout < < "num: " < < n < < "\tcount: " < < 1 < < "\n ";
return 1;
}
int iRet = Count1( n ) + Calc( n - 1 );
cout < < "num: " < < n < < "\tcount: " < < iRet < < "\n ";
return iRet;
}
int main()
{
Calc( 123 );
}
挺有意思的，不过到底是不是google的面试题呢。。。
[解决办法]
1,2,3,4,5,6,7,8,9,0和1234567890
有很大的差距.不要只考虑到10.
还有要考虑怎么做的程序更小,更简单.
N是任意整数不是吗?是的.
这题不是很难,难是在于怎么简化他.
[解决办法]
cy2005abc的可以得出答案，但效率是不是低了点
应该还有好一点的方法
我想应该有一种数学方法可以来做
但一时想不起来了
[解决办法]
我知道 google 是怎么做的，
先建立数组
number[1000] ;
也可以定义
//define MAX 10000
init()
{
number[0] = 0;
number[1] = 1;
number[2] = 0;
number[3] = 0;
number[999] = 0;
}
int Get1Count(int n)
{
int nCount =0 ;
for(; n > 0 ;)
{
nCount += number[n % 1000 ]
n = n /1000;
}
return nCount;
}
[解决办法]
Hylas(羽心) ( ) 信誉：100 Blog 加为好友 2007-04-23 17:53:18 得分: 0
我知道 google 是怎么做的，
先建立数组
number[1000] ;
也可以定义
//define MAX 10000
init()
{
number[0] = 0;
number[1] = 1;
number[2] = 0;
number[3] = 0;
number[999] = 0;
}
int Get1Count(int n)
{
int nCount =0 ;
for(; n > 0 ;)
{
nCount += number[n % 1000 ]
n = n /1000;
}
return nCount;
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
很无语
[解决办法]
用指针来计算不知道速度能不能快点？
/**********************************************/
#include <stdlib.h>
#include <stdio.h>
int main(void)
{
long int number,i,count=0;
char *p;
char string[10];
printf( "PLZ input the number:\n ");
scanf( "%ld ",&number);
for(i=1;i <=number;i++)
{
itoa(i, string, 10);
p=&string;
while(*p!= '\0 ')
{
if(*p== '1 ') count++;
p++;
}
}
printf( "%ld\n ", count);
}
/*******************************************************/
输入：11 输出：4
输入：10000 输出：4001
输入：10000000 输出：7279141
输入：100000000 输出：72808170
输入：10 0000 0000 输出：（等了3分钟，没有出结果，偶的CPU 1.8G的，速度太慢了。）
[解决办法]
y = strlen(x);
if (y == 1) f(x) =1;
if (x/(10^y)> 1) f(x) = 10^y + (x/(10^y)-1)*f(10^y-1) + f(x%10);
else
f(x) = f(x%10)+x - 10^y +1;
如果最高位x/(10^y)是1,如10369 则是f(10369) = f(9999) + 10369-10000+1 //else部分
如果不是最高位大于1(if 部分) 则f(20369) = 10^5 + 1*f(9999) + f(369)
其中10^5是10000-20000之间的数,
1*f(9999)指9999内的数据(如果是30369就是2*f(9999),0-9999和20000-30000之间含有1的数目一样多)
f(369)是20000-20369之间的数
只是想法,没有实现过,无责任猜想
[解决办法]
搞错了,还以为11只算一个呢
改进一下算法
y = strlen(x);
if (y == 1) f(x) =1;
if (x/(10^y)> 1) f(x) = 10^y + (x/(10^y))*f(10^y-1) + f(x%10);
else
f(x) =f(10^y-1) + f(x%10)+(x - 10^y +1);
还是无责任猜想
上面的else 部分也写错了,应该是f(x) = f(10^y-1)+x - 10^y +1;
[解决办法]
一个位 ：[?]
0-9 种可能， 为1 的是 1 种情况。
二个位 ：[?][?]
0-99 种可能， 为1 的是:
当个位为1时，十位有：10个结果。
当十位为1是，个位有：10个结果。
所以是 10 + 10 = 20 种情况。
三个位 ：[?][?][?]
0-999 种可能， 为1 的是:
当个位为1时，十位,百位有：10*10 = 100个结果。
当十位为1是，个位,百位有：10*10 = 100个结果。
当百位为1是，个位,十位有：10*10 = 100个结果。
所以是 100 + 100 + 100 = 300 种情况。
类推：
0-9999 4000 种情况。
0-99999 50000 种情况。
----------------------------------
ps:
1 的话 就是 0 + 1 = 1情况. ==> 0 * 10^(0-1) + 1
10 的话 就是 9 + 1 = 2情况. ==> 1 * 10^(1-1) + 1
100 的话 就是 99 + 1 = 21情况. ==> 2 * 10^(2-1) + 1
1000 的话 就是 999 + 1 = 301情况. ==> 3 * 10^(3-1) + 1
--------------------------------
(假设置位数是n) : 得:
f(n) = n * 10^(n-1) + 1
所以：
1234567890 = 1 * (10 * 10^(10-1) + 1) +
2 * ( 9 * 10^( 9-1) + 1) +
...
9 * ( 2 * 10^( 2-1) + 1) +
0 * ( 1 * 10^( 0-1) + 1)
[解决办法]
faint..
错了。 。。。。
比如说 :
90 : [?][?] ==> 十位为1， 10种情况。 各位为1， 9种情况。 所以是 19个结果。。
800 : [?][?][?] ==> 10 * 10 + 10 * 8 + 10 * 8 = 260.
7000 : ===> 10 * 10 * 10 + 10 * 10 * 7 + 10 * 10 * 7 + 10 * 10 * 7 = 3100
===================================================
也就是说，如果是针对与 n个9 的或是 1,n个0 的。是我最初的结果。
9, 99,999,9999,...
0,10,100,1000,10000....
如果是n,m个0的。（这里假如首位是n，其中有m个0）
2,3000,4000,500....
================================================
有关系：
f(n,m) = 10^m + m*7*10^(m-1)
================================================真理啊。。。
[解决办法]
本题的关键问题是求f(n)=n的n值列表，故必须对f(n)进行优化，
从题目的定义可知，f(n)函数事实上是求一个BCD码(8421)累加值
并求得每个累加值中1的个数和问题，因此可以将该问题分解为
从1开始的递推累加过程，每个过程分为四个步骤：
（1）求当前值加1后的BCD码(8421)的值。
（2）求当前累加值BCD码中1的个数。
（3）将当前值中1的个数与之前1的个数进行求和。
（4）检查当前n值与累计1的值是否相同，相同则输出n。
由于本题要求是快速准确，而求BCD码的累加值最好的方法是使用
硬件电路，如果使用软件实现，可使用hash真值表的方法。
我在这里采用64K空间的BCD码累加真值表和64K空间的BCD码求1个
数真值表来计算步骤1和步骤2，以达到最佳速度，下面是源代码和
输出结果：
#include "stdafx.h "
#include <windows.h>
int inc1_arr[65536] = {
0X000001,0X000002,0X000003,0X000004,0X000005,0X000006,0X000007,0X000008,0X000009,0X000010,
0xFFFFFF,0xFFFFFF,0xFFFFFF,0xFFFFFF,0xFFFFFF,0xFFFFFF,0X000011,0X000012,0X000013,0X000014,
0X000015,0X000016,0X000017,0X000018,0X000019,0X000020,0xFFFFFF,0xFFFFFF,0xFFFFFF,0xFFFFFF,
......//数量较多省略(其中下标为0x9999的值为0x010000，值为0xFFFFFF表示BCD码无效)
};
char count1_arr[65536] = {
0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,
......//数量较多省略
};
int main(int argc, char* argv[])
{
unsigned short usBCD[3] = {0, 0, 0};
int i, k;
int iSum = 0;
DWORD dwTick = GetTickCount();
for(i = 1; i <= 1234567890; i ++) {
k = inc1_arr[usBCD[0]];
usBCD[0] = k & 0xffff;
if(k & 0x00ff0000) {
k = inc1_arr[usBCD[1]];
usBCD[1] = k & 0xffff;
if(k & 0x00ff0000) {
k = inc1_arr[usBCD[2]];
usBCD[2] = k & 0xffff;
}
}
iSum += count1_arr[usBCD[0]] + count1_arr[usBCD[1]] + count1_arr[usBCD[2]];
if(iSum == i) {
printf( "%d\n ", i);
}
}
printf( "\nTime Used: %d mSec\n ", GetTickCount() - dwTick);
return 0;
}
VC++ 6.0下编译通过，在Pentium M 1.4GHz笔记本上的运行结果(不到20秒)：
1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
200000
200001
1599981
1599982
1599983
1599984
1599985
1599986
1599987
1599988
1599989
1599990
2600000
2600001
13199998
35000000
35000001
35199981
35199982
35199983
35199984
35199985
35199986
35199987
35199988
35199989
35199990
35200000
35200001
117463825
500000000
500000001
500199981
500199982
500199983
500199984
500199985
500199986
500199987
500199988
500199989
500199990
500200000
500200001
501599981
501599982
501599983
501599984
501599985
501599986
501599987
501599988
501599989
501599990
502600000
502600001
513199998
535000000
535000001
535199981
535199982
535199983
535199984
535199985
535199986
535199987
535199988
535199989
535199990
535200000
535200001
1111111110
Time Used: 19838 mSec
[解决办法]
何必如此复杂：
int f(unsigned int n)
{
int ncount = 0;
while(n)
{
++ncount;
n = n & (n - 1);
}
return ncount;
}
int main(int argc, char *argv[])
{
std::cout < <f(1) < <std::endl;
std::cout < <f(0xff) < <std::endl;
}
[解决办法]
总结：我用TC和DEV-c++测试了一下：发现只有 fohonet(不得与将兮,使我沦亡！) 和以前 ：
http://topic.csdn.net/t/20050816/12/4211591.html 的 oo(为了名副其实，努力学习oo技术ing) ( ) 的方法是正确的，其他人总出现些莫名其妙的错误，要么就是结果不对。
不过在数值大于1 0000 0000 时候，oo(为了名副其实，努力学习oo技术ing) ( )说的只要1MS的计算时间，有点不可能吧！
##############oo(为了名副其实，努力学习oo技术ing) c++版的############################
#include <iostream>
#include <windows.h>
#include <ctime>
using namespace std;
unsigned long const len = 10000000;
int main()
{
char buffer[20];
unsigned long counts = 0 , i, stringLength, j;
string s = " ";
DWORD start, end, usetime;
start = GetTickCount();
for(i=1; i <=len; i++)
{
s = _itoa(i, buffer,10);
stringLength = s.length();
for(j=0; j <stringLength; j++)
{
if(s[j] == '1 ')
counts++;
}
}
cout < < "The counts of number 1 is : " < <counts < <endl;
end = GetTickCount();
usetime = start - end;
cout < < "use " < <usetime < < "milliseconds " < <endl;
}
[解决办法]
设N为原始值
表示为：N = ...a[k+2]a[k+1]a[k]...a[1]a[0]
[]表示下标
下面计算a[k]位1的个数：
1.当a[k]> 1时
只有前面的数（记为N[前]）决定，即：（N[前]+1）×10^k
2.当a[k]=0时
也只有前面的数（记为N[前]）决定，即：（N[前]）×10^k
3.当a[k]=1时
只有前面和后面的数共同决定（记为N[前]和N[后]）决定，即：（N[前]）×10^k+N[后]+1
其中：N[前] = N / (10^(k+1)) = ...a[k+2]a[k+1]
N[后] = N % (10^k) = a[k-1]a[k-2]...a[0]
说明：k = 0 或 最大值 也成立
由以上分析可以写出程序get1Count()
得出的结果是：
1429355270
程序是在tc2.0下调试通过
#include <stdio.h>
#include <math.h>
#include <conio.h>
long get1Count(long N)
{
long tempN = N;
long before;
long after;
long tempCount = 0;
long count = 0;
int a;
int k;
int m;
for(m=0; ; m++)
{
if( N / (long)pow(10,m+1) == 0 )
{
break;
}
}
for(k=0; k <m+1; k++)
{
a = (int)(tempN % 10);
tempN = tempN / 10;
before = N /(long) pow(10,k+1);
after = N % (long)pow(10,k);
if (a > 1)
{
tempCount = (before + 1)*(long)pow(10,k);
}
else if (a == 0)
{
tempCount = before*(long)pow(10,k);
}
else if (a == 1)
{
tempCount = before*(long)pow(10,k) + after + 1;
}
printf( "\na = %d, tempCount = %ld\n ",a,tempCount);
count = count + tempCount;
}
return count;
}
void assertEqual(long l,long r)
{
if(l != r)
{
printf( "\nassert error! %ld != %ld\n ",l,r);
}
else
{
printf( "\ncongratulation!\n ");
}
}
int main()
{
long targetValue = 1234567890;
long count = get1Count(10);
assertEqual(count, 2);
count = get1Count(11);
assertEqual(count, 4);
count = get1Count(12);
assertEqual(count,5);
count = get1Count(100);
assertEqual(count,21);
count = get1Count(200);
assertEqual(count,20+20+100);
count = get1Count(targetValue);
printf( "\nthere are %ld 1 in number %ld\n ", count, targetValue);
printf( "press Enter to Exit\n ");
getch();
return 0;
}
[解决办法]
回复人：Hylas(羽心) ( 一级(初级)) 信誉：100 2007-4-23 17:53:19 得分:0
?
我知道 google 是怎么做的，
先建立数组
number[1000] ;
也可以定义
//define MAX 10000
init()
{
number[0] = 0;
number[1] = 1;
number[2] = 0;
number[3] = 0;
number[999] = 0;
}
int Get1Count(int n)
{
int nCount =0 ;
for(; n > 0 ;)
{
nCount += number[n % 1000 ]
n = n /1000;
}
return nCount;
}
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
这个绝对是错误的！
[解决办法]
> > To: oo(为了名副其实，努力学习oo技术ing)
> > 那个c++版的是你写的，计算时间的我没有注意，我只看了结果是对的。
##########################################################
不好意思 上面我 说错了！！！！！！！！！！！！
重新更正:
To: oo(为了名副其实，努力学习oo技术ing)
那个c++版的是 zhouhuahai（道号 "虚无 "） 写的，计算时间的我没有注意，我只看了结果是对的。
##############################################################
总结：我用TC和DEV-c++测试了一下：发现只有 fohonet(不得与将兮,使我沦亡！) 和以前 ：
http://topic.csdn.net/t/20050816/12/4211591.html 的 zhouhuahai（道号 "虚无 "） 的方法是正确的，其他人总出现些莫名其妙的错误，要么就是结果不对。
不过在数值大于1 0000 0000 时候，oo(为了名副其实，努力学习oo技术ing) ( )说的只要1MS的计算时间，有点不可能吧！
##############zhouhuahai（道号 "虚无 "） c++版的############################
#include <iostream>
#include <windows.h>
#include <ctime>
using namespace std;
unsigned long const len = 10000000;
int main()
{
char buffer[20];
unsigned long counts = 0 , i, stringLength, j;
string s = " ";
DWORD start, end, usetime;
start = GetTickCount();
for(i=1; i <=len; i++)
{
s = _itoa(i, buffer,10);
stringLength = s.length();
for(j=0; j <stringLength; j++)
{
if(s[j] == '1 ')
counts++;
}
}
cout < < "The counts of number 1 is : " < <counts < <endl;
end = GetTickCount();
usetime = start - end;
cout < < "use " < <usetime < < "milliseconds " < <endl;
}
[解决办法]
耗时应该在ms级别：
#include <stdlib.h>
#include <stdio.h>
int power(int n)
{
int i, sum;
sum = 1;
for (i = 0; i <n; i++)
sum *=10;
return sum;
}
int getx(int n)
{
int i = 0;
while (1)
{
if (n/power(i++) == 0)
break;
}
return i-1;
}
int f(int n)
{
int x99;
if (n <=9)
return 1;
x99 = power(getx(n)-1);
if (n> =2*x99)
return x99 + f(x99-1)*(n/x99) + f(n%x99);
else
return f(x99-1) + f(n%x99) + n%x99 + 1;
}
void main(void)
{
printf( "ret:%d\n ",f(1234567890));
return;
}