计算数据中 1 的个数

 给定一个十进制正整数N,计算从1开始到N的所有整数中，一共有多少个“1”？
拓展：1. 写一个函数F（N）， 返回“1”的个数
         2.在32位整数范围中，满足条件F(N) = N 的最大的 N 是多少？


思路一：
     统计每一个数字中“1”的个数，然后遍历1～N范围的所有数，并把没个数中“1"的个数加起来
这是最简单也是最容易想到的方法。


思路二：
      将所有的数字都转换成字符串，然后计算字符串中出现的“1”的个数。
 理由：1.string类型的变量对字符串有加的操作
          2.C++语言中本身库中有将数字转换成字符串的函数 itoa()


思路三：
     寻找数字中的规律，这是最难的一种方法。


算法伪代码：
  思路一: 初始化 sum = 0, k = 0, 
              step1: k<--- k+1;
              step2: if k <= N
                           sum <----- sum + count(k);
                         goto step1;
 long count( int k)
{
    int iNum = 0;
    while(k != 0)
    {
        iNum += ( k % 10 == 1 ) ? 1: 0;
        k /= 10;
     }
     return iNum;
}
算法分析：先计算k的位数([lgk] + 1)，乘法和除法记作一次运算，加法和减法不计. 对于K共计 2（[lgk] + 1）次运算
从1～N 共计运算次数是：2∑（[lgk] + 1） (k = 1 ~ N ) 大约是2（[lgn!] + n)次


思路二：
   假设系统是32位定义一个char str[32] 用来存储要转换后的字符串 
   int main()
   {
       string s;
       char str[32];
       for( int i = 1; i < N; ++i)
       {
            itoa( i, str, 10);
            s.append( str );
        }
        cout << count( s.begin(), s.end(), '1' ) << endl;
}


思路三：(可能会有误）
假设N = abcde 分析如下：
     step1：e = 1, （a,、b、c、d） 都有10中选择
     step2: d = 1, 其余的位上也都有10个选择
     .................
     step5: a = 1, 其余的位上也都有10个选择
  共计有：5 × 10×10×10×10 个选择
总结：。
      如果N是正整数，则N的位数是 （[lgN] + 1）,则这么多位总共有1的个数是[lgN] × 10^[lgN]。
这样的话，程序问题就转换成计算成函数 F[N] = [lgN] × 10^[lgN]的问题，但是F[N]多计算了N ～10^([lgN] + 1) - 1 之间1的个数。
举例说明一下：
     N = 123， F[127] = lg[123]  × 10 ^[lg123] 得到 1 ～ 999中所有的 1 的个数。这样我们要减去 123 ～ 999 之间 1 的个数，因为127 和999
都是3位的，这样计算1的个数就方便了。
  个位为1：100×i + 10×j + 1 , i<1-9> ,j<3-9>  63
  十位为1：100×i + 10 + j , i<2-9> ,j<0-9> 80
F[127] - 143 = 57 

最后

以上就是繁荣秋天为你收集整理的计算数据中 1 的个数的全部内容，希望文章能够帮你解决计算数据中 1 的个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。