[原]从1到n的正数中1出现的次数

时间：2011-03-13 来源：喃易

直接贴代码

class Program

{ static void Main(string[] args) { Console.WriteLine("请输入一个整数."); int num = 0; string numStr = Console.ReadLine(); do { while (!int.TryParse(numStr, out num)) { Console.WriteLine("输入的数据不正确，请重新输入一个整数！"); numStr = Console.ReadLine(); } numStr = 计算(num); } while (1 == 1); } private static string 计算(int num) { int count = 0; Number numC = new Number(num); System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); Console.WriteLine("开始"); sw.Start(); count = numC.CountByDivisionShow(); sw.Stop(); Console.WriteLine("整数{0},包含{1}个1，用时：{2}ms", num, count, sw.ElapsedMilliseconds); Console.WriteLine("开始2"); sw.Reset(); sw.Restart(); count = numC.CountByStringShow(); sw.Stop(); Console.WriteLine("整数{0},包含{1}个1，用时：{2}ms", num, count, sw.ElapsedMilliseconds); Console.WriteLine("开始3"); sw.Reset(); sw.Restart(); count = numC.CountByBit(); sw.Stop(); Console.WriteLine("整数{0},包含{1}个1，用时：{2}ms", num, count, sw.ElapsedMilliseconds); return Console.ReadLine(); } } class Number { //各位上的数值索引上升依次为个十百千... private int[] numArray; //各位上幂值如1 10 100 等.. private Dictionary<int, int> powerValue; //此数的长度 private int numLength = 0; private int num; public Number(int num) { this.num = num; numArray = (from a in num.ToString().ToArray() select Convert.ToInt32(a.ToString())).ToArray(); numLength = numArray.Length; powerValue = new Dictionary<int, int>(numLength); for (int i = 0; i < numLength; i++) { powerValue.Add(i, Convert.ToInt32("1".PadRight(i + 1, '0'))); //调换数值为个位开始的顺序 if (i < numLength / 2) { ExChange(ref numArray[i], ref numArray[numLength - i - 1]); } } } public int CountByDivisionShow() { int count = 0; for (int i = 0; i <= num; i++) { CountByDivision(i, ref count); } return count; } public int CountByStringShow() { int count = 0; for (int i = 0; i <= num; i++) { CountByString(i.ToString(), ref count); } return count; } public int CountByBit() { //计数器 int count = 0; //第一部分（此位之前的数对其的影响） int part1 = 0; //第二部分（此位之后的数对其的影响） int part2 = 0; for (int j = 0; j < numLength; j++) { //位前的影响基数 int temp = num / (powerValue[j]*10); if (j == 0)//计算个位上出现的次数 { part1 = temp; part2 = numArray[j] > 0 ? 1 : 0; } else if (j == numLength - 1)//计算首位上出现的次数 { part1 = 0; part2 = numArray[j] > 1 ? powerValue[j] : num % powerValue[j] + 1; } else//其它位上出现的次数 { part1 = temp * powerValue[j]; if (numArray[j] == 1)//此位上为1时，受后面的值的影响 { part2 = num % (powerValue[j] / 10) + 1; } else if (numArray[j] > 1)//此位大于1时，受影响为此位的幂值 { part2 = powerValue[j]; } else//此位为0时，影响为0 { part2 = 0; } } count = count + part1 + part2; } return count; } private void CountByString(string num,ref int count) { count+= num.ToCharArray().Count(a=> a=='1'); } private void CountByDivision(int num, ref int count) { if (num % 10 == 1) count++; int temp = num / 10; if (temp > 0) { CountByDivision(temp, ref count); } } //调换数值 private void ExChange(ref int a, ref int b) { a = a ^ b; b = a ^ b; a = a ^ b; } }

不同方法，效率相差还是很大的。（本人cpu 比较烂算得比较慢）

图1：