以下是引用jj369258在2012-8-27 13:52:28的发言：

Description
给定一个十进制正整数N,写下从1开始，到N的所有整数，然后统计一下其中出现的所有的“1”的个数。例如： N=2,写下1 ，2。这样只出现了1个“1”. N=12,我们会写下1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，10 ，11 ，12。这样，1的个数是5。那么，给定已知的正整数N，你是否能给出N以内所有正整数中出现1的总数。
Input
首先输入一个正整数T（1<=T<=1000），表示一共有T组测试样例，接下来有T行输入，每行输入一个正整数N（1<=N<2147483647）。
Output
针对每个测试用例，输出N以内所有正整数出现1的总数，相邻的总数结果用一个回车分隔。
Sample Input
4
1
11
15
99
Sample Output
1
4
8
20

HINT
结果值可能超出基本整形表示范围，需要用到64位的整型。
C语言中，64位的整型有两种：
第一种：用于gcc编译环境下的long long 型，其输入输出格式控制符为%lld。“lld”意为long long decimal。例如：
long long a;
scanf("%lld",&a);
printf("%lld",a);
第二种：用于Mircrosoft Visual C++编译环境的__int64。“__”为双下划线，其 输入输出格式控制符为%I64d, 其中“I64d”表示，Integer 64 decimal。例如：
__int64 a;
scanf("%I64d",&a);
printf("%I64d",a);

由于电脑被人拿去用了 代码还未验证  还请 坛子里面的人帮忙

00   01   02  03  04  05  06  07 08 09           1
10   11   12  13  14  15  16  17 18 19           11
20   21                                          1
30   31                                          1
40   41                                          1   
50   51                                          1
60   61                                          1
70   71                                          1
80   81                                          1
90   91                              99          1

1    11   1   1   1    1   1    1   1  1=20  这个里面有20个

在大于 100 的进行一个排列
100   101   102  103  104  105  106  107 108 109        
110   111   112  113  114  115  116  117 118 119  
120   121
130   131
140   141
150   151
160   161
170   171
180   181
190   191                                      199
你吧这100以上的数字百位数的1给拿掉   你会发现排序是和 99内的数字是1样的的
所以100-199这100个数字的含1的个数 是100+20=120   100 是从100到199数字个数来的 他们都带了1的，20 是从上一个99内数字统计出的带1的个数

再看看200-299的数字  你把百位数上的2拿掉 你会同样发现 排列是和 99内的数字是1样的  但是200起头的百位是不含有1的。所以 就只有20个数字了 对不对

同理从300-999都是这么个情形了。 归纳法  呵呵

现在我们再来看看1000-1999的数字 ，跟分析1000-999的数字方法一样 取掉千位上的数字1 你就看到了 100位的排序，再拿走百位上的数字 你是不是看到了 99内的排序呢
是不是呢 所以1000-1999的数字 含1的数字的个数  出来了 1000+100+20
2000-9999的我就不说了，（100+20=120）*8=？ 我算不出来   

归纳法可以去推 10000+上的数字   10000+1000+100+20



[ 本帖最后由 zhu224039 于 2012-8-29 19:32 编辑 ]

凌晨解答，脑袋不是很灵光，当中推理方面说的含糊了点

现在找出了事物的特性了，那么我们就可以来写算法了

算法注意点 11    111 1111   11111  这个地方初步判断  他比较特别，统计下来 就是因为他才有了不同的个数  个数的不同看上面99 的数字排序

这个数 NUM 被输入进来了  首先判断数的位数 用j=0 计数  还有1件事情就是记下数的个 十百 千位上的数字吧 用数组啊a[MAXNUM],看情况是要给MAXNUM 搞个很大的值才行
i=num;
for(i=i/10;i>0;i=i/10 ){
   a[j]=i%10;                     
    j++;                            %是不是求余啊 搞忘记了  反正这个地方是求余的地方，5/10的余数是不是为5呢？ 脑袋晃悠了 弄不楚              
                                         
}
a[j]=i%10;

现在知道j的 取值了，就得分情况了
跟上面的推论挂钩，先写个 100以内的函数，j<=1 代表100以内，判断数的取值在那个段 a[j]是10位数字的 大家可以看我给出的表格最左边的数竖着看 就能对应上第几行了。 a[j-1]代表的各位，大家就横着点 就可以定位这个数在哪了，位置分三等 1-9，为一等，10-19为一等，20-99为一等 区别对待。 算法如下：
int jishu(int a[],int num,int j)
{
  int num1;
  if(num>=1&&num<9)
     num1=1;
  if(num=0)
     num1=0;
  if(a[j]==1){
     if(a[j-1]>=1)
     num1=a[j-1]+2;
     else
     num1=1;
     num1+=1;
   }
   else if(a[j]>=1){
      if(a[j-1]>=1)
      num1=1;
      else
      num1=0;
      num1+=a[j]-1+11;
    }
return num1
}

100以上的  j=2 1000 j=3
那么当是100或者是1000以上的
这个就可以用递归来求解了

递归公式出来了
已知 1<=a<=99 ,j={0,1}  f(j)=a
求 x>=100的问题 即j>1  的时候
对于 以1为最高位的
f(2)=(（x+1）%100)+f(j) 此时的a=x%100  按照我上述算法推出
f(3)=(（x+1）%10x10x10)+f(2)  此时的a=x%1000；
对于1不是最高位的
f(2)=f(j)
f(3)=f(2)
这个鸟毛的递归调用就是要靠什么 表达式推理要正确，俺是个数学白痴份子，推到这 还请各位考究
这个只是计算出了 数在区域0-99 a[j]00-a[j]99  a[j]000-a[j]999 区间的数字带1的总数  还得加上前面的数才对，我的天 睡着了，突然想到 我的推理的范围在哪
还得加上块外的数据才对快外 假如 1个数是1500  上面的算法就只能计算出1000-1500范围内的个数  1000以下的并未计算在内，所以俺得接着推
1000以下的函数，两者相加 才能满足要求。
0-99 数是20 100-199 数是100+20=120 200-299 20 300-399 20  知道了  除了100-199的数据是得  用100-999={100+20，20，20，20，20，20，20，20,20,20}
这个地方怎么那么像 咱们给出的 表 0-99 和 100-19   也就是20*10+100 =300  
1000-1999  1000+300 2000-2999  300  3000-3999 300   1 2 3 4 5 6 7 8 9 ={1000+300,300,300,300,300,300，300,300,300}
1000+300*10=4000
这样就很清楚了
已知f(1)=20   f(1)=jisuan(99)=20
f(2)=10*f(1)+10*10   
f(3)=10*f(2)+10*10*10
归纳出
f(n)=f(n-1)*10+10的N次方
由于计算是计算出了他当前的块中的个数 那么就的把那个块给不算在内，数最高的位决定块 所以
n=j-1
这个递归函数位置 不够了 我在下一个版面给补上 取名为 int jishu2(int n，int m) 这个函数是计算低1位的个数  比如 现在要求的是1500 那么这个函数计算的个数就是0-999的
如果是2500 或者3500  那么还剩下1部分没加上去 那么就是 a[j]-1>1&&j>=2 满足这个要求才能进行计算  睡不着啊 接着改 这部分值很好求 f(n)=f(n-1)*10+10的N次方的
10 改成个a[j]-1  就可以了。大家重新看 F(1) F(2) f(3)的算法 其实他们就单个来说只有个9个数相加 第10个数是加了他上一层得dao de数据
所以  a[j]此时 用公式  （f(n)-10的N次方）*(a[j]-1)/10 +10的N 次方 可以计算得到。
公式计算怎么来的
f(n)-10的n次方 =f(n-1)*10
把10换成a[j]-1  只需要将他乘以(a[j]-1)/10 就可以了


[ 本帖最后由 zhu224039 于 2012-8-29 19:26 编辑 ]

int jishu2(int n)
{
   int num1,i,num2=1,num3;
   if(n==1)
   num1=20;
   else{
    for(i=n;i>0;i--)
    num2=10*num2;
    num1=10*jishu2(n-1)+num2;
   }
ruturn (num1);
}

int jishu(int num)
{
int num1,i,j,n,n1=1;
  i=num;
  for(i=i/10;i>0;i=i/10 ){
    a[j]=i%10;           %是不是求余啊 搞忘记了  反正这个地方是求余的地方，5/10的余数是不是为5呢？ 脑袋晃悠了 弄不楚               
    j++;                   用 j 记下 数有个位  位 说的是个十百千万                                                      
  }
  a[j]=i%10;               因为最后一个余数在循环体内是取不到的
if(j<=1)                   j={0,1} 为0 代表只有各位数 1代表10位，这个判定的就是0-99的数值了 总共是100个
{
    if(num>=1&&num<9)                当他为各位的时候 NUM1是为各位的情况了的

     {                  
     num1=1;
          }              
  if(num=0)                          这个是用在大数求解的情况的 假如数字是 100呢 就完蛋了 没这个就完蛋
    {
     num1=0;
          }     
  if(a[j]==1){                     a[j]的值存放的是数的十位  对应的是 10-19 这个部分的
     if(a[j-1]>=1)
     num1=a[j-1]+2;
     else
     num1=1;
     num1+=1;
   }
   else if(a[j]>=1){               这个对应的是 20-99部分的
      if(a[j-1]>=1)
      num1=1;
      else
      num1=0;
      num1+=a[j]-1+11;
    }
}
else
{
      for(n=j;n>0;n--)       这个是为了计算 10*10*10的
      n1=10*n1;
    if(a[j]==1)
      num1=(num+1)%n1+jishu((num1+1)%n1);    递归函数了 照着推理上面的函数套用就可以了，递归求解问题都是什么  F(X)=F(X的表达式)+。。。。。什么类型的
   else
      num1=jishu((num1+1)%n1);
  }
    if(j>1)                                   这个是计算余下的块，有个疑问 毕竟自己只是看了一遍C  就是 递归会不会像进程一样吧我这个块也给我运行了 求解
   {                                           我是觉得不太可能，不管了 反正也是给大家一个思路
    num3=jishu2(j-1);
    num1=num1+num3;
    }
  if(a[j]-1>1&&j>2)
   {
    num4=((nun3-n1）/10)*(a[i]-1))/10+n1;
   num1=num1+num4;
    }   

    return num1;
}




[ 本帖最后由 zhu224039 于 2012-8-29 19:28 编辑 ]

辛苦了，给点颜色你瞧瞧！

我的代码是臭的，别人发的 一大堆 回答的，  我的代码虽然没有上机测试，但是整套思想写上去了，木有人看        换了颜色也是木有人看，伤心的很

没人看的原因也许是解释太长了。如果想写又难又长的东西，就要做好没人看的准备。
而且你确实是没上机运行过，连有汉字的地方前面也不加点 // 之类的。这样想直接拷贝你的代码去研究一下的机会都没有。

另外这个问题前一阵子论坛里讨论过了，经常来坛子里逛的人可能对那次讨论印象还很深，所以现在对这个题的兴趣不是很浓了。


[ 本帖最后由 pangding 于 2012-8-30 10:13 编辑 ]

jj... 的那个帖子里我也给了链接，楼主难道没有兴趣看看吗？
https://bbs.bccn.net/thread-371905-1-1.html

我觉得看看还是能学到不少东西的。