google笔试题,进来看看,解决方法

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;