google的那道数1的面试题，欢迎大家讨论。可以加分

Question

有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？为什么f(13)=6, 因为1,2,3,4,5,6,7,8,9,10,11,12,13.数数1的个数，正好是6.请大家写出自己的算法，并统计一些在你机器上计算出1111111110的时间。为了不影响大家的思路，我最后贴上我的程序。语言不限，随便了。原贴http://community.csdn.net/expert/topic/4211/4211591.xml对于用字符串s表示的整数z，小于等于它的数中包含多少个1可以简单的分析s的各个位上的数值来表示出来。方法如下：
取字符串为a0a1a2a3a4a5，数字表示下标，简要举6位作为示例。比如a3位，它右边a4a5，我的算法只考虑该位对于它右边各位的影响。
定义一个递归函数int CountOne（string s）求结果
若a3＝0，则对右面的贡献为CountOne（a4a5）； 若a3＝1，则对右面的贡献为：a4a5的值＋1＋CountOne（a4a5）＋CountOne（a3位的权值－1）。上式中a4a5的值＋1表示从100－1a4a5这些数在a3所在的百位的1的个数，CountOne（a4a5）表示从100－1a4a5这些数中a3右边各位中1的个数，CountOne（a3位的权值－1）的值表示从000－099这些数中a3右边各位中含有的1的个数。 若a3>＝2则对右边的贡献为：a3本位权值＋CountOne（a4a5），＋CountOne（a3位的权值－1）×a3的值。上式中本位权值表示从100－199这个100个数，CountOne（a4a5）表示从a300－a3a4a5这些数中a3右边各位中1的个数，CountOne（a3位的权值－1）×a3的值表示从000－（a300－1）这些数中a3右边各位中含有的1的个数。例如a3＝4，则表示从000－099，100－199，200－299，300－399这400个数中各位和十位包含的1的个数。例如求54321中千位4对右边各位的影响，则是case3，1000＋CountOne（321）＋CountOne（999）×4，结果我没有算，估计正确。我测试原题中1111111110，结果正确，时间为0.012秒，硬件为p43.0,512M内存,硬件较好，不过我觉得我的算法也不麻烦，大家评议。欢迎批评，qq83508052，msn：[email protected]代码：
using System;
using System.IO;
using System.Xml;
using System.Xml.XPath;
using System.Threading;
using System.Timers;public class Sample
{
static void Main()
{
// Application.Run(new PagingSample());
string s="";
System.Console.Write("Input N:");
s = System.Console.ReadLine(); DateTime dt1 = DateTime.Now;

int count = CountOne(s);
System.Console.WriteLine("f("+s+")={0}",count); DateTime dt2 = DateTime.Now;
TimeSpan ts = dt2.Subtract(dt1);
System.Console.WriteLine("{0:d}",ts.ToString());
System.Console.ReadLine();
} public static void OnTimer(Object source, ElapsedEventArgs e)
{
Console.WriteLine("Hello World!");
}
public static int CountOne( string s )
{
s= TrimZeroAHead(s);
char[] array = s.ToCharArray();
int i=0,length=array.Length ;
int n = int.Parse(s); if(n==0)
return 0;
if(n<10&&n>0)
return 1;

char c=array[length-1];
string sub=""; int count=0; i=0;
sub=s.Substring(i+1);
c = array[i];
if(c=='0')
{
count+=CountOne(sub);
return 0;
}
else
{
if(c=='1')
{
int a = (int)Math.Pow(10,length-i-1)-1;
string temp = a.ToString();
count += 1+int.Parse(sub)+CountOne(sub)+CountOne(temp);
//return count;

}
else
{//c>=2
int multi = int.Parse(c.ToString());
int a = (int)Math.Pow(10,length-i-1)-1;
string temp = a.ToString();
count += (a+1)+CountOne(sub)+CountOne(temp)*multi;
//return count;
}
}
return count;
} public static string TrimZeroAHead(string s)
{
int i=0;
for(i=0;i<s.Length-1;i++)
if(s[i]!='0')
break;
return s.Substring(i);
}
}

Answer 1

oo(为了名副其实，努力学习oo技术ing) ,c#的效率低于c和c＋＋，所以时间只是一个参考。求出最大数的问题其实没有比求数这个数之前有多少个1麻烦，因为求出最大数一定要求你要从1开始遍历，每一次都加上本次被遍历数中包含多少1，加在以前的基础上就ok了。而针对一个数求出之前的1的个数，遍历在思想上就落后了很多了。大家讨论。

Answer 2

对于第一个问题，我的想法如下：
    可以每次将1到N的一个数取出来，用itoa（）（即将INT类型转换成ASCII码形式）进行转换，然后将存入一个字符串数组，然后将数组中的每位与1的ASCII码进行比较，统计出现次数即可。

Answer 3

时间计算语句顺序变为
DateTime dt1 = DateTime.Now;

int count = CountOne(s);
DateTime dt2 = DateTime.Now;
TimeSpan ts = dt2.Subtract(dt1);

System.Console.WriteLine("f("+s+")={0}",count);时间0了，我用毫微秒也为0。

Answer 4

拿着C#的代码跑到C语言来，倒版么？送回C#去……

Answer 5

回复人： antijpn(antijpn) ( ) 信誉：100  2005-10-10 13:45:12  得分: 0  
 
 
   
拿着C#的代码跑到C语言来，倒版么？送回C#去……
--------------------------------大米干的~~~
呵呵~~~
  
 

Answer 6

我的运行结果：
1000000000000的运行时间为：156毫秒
计算f(n) =n的时间是：29.406秒
我的机器：P4 2.6  512 内存