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);

唔 不断对其用10求余，直至商为0，中间有余数为1时就计数？
我的想法大概是这样的，不过比较麻烦就是了。
手里没编译环境也就没写代码验证了，不知道楼主问题是不是这个意思。

这样的话耗时比较多！运行结果是对的，但是会超时，有没有可以改进的方案！缩小时间复杂度！

#include<stdio.h>   
int main()
{
    int n,k,i,r,count,j;
    long m;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        count=0;
        scanf("%ld",&m);
        for(j=1;j<=m;j++)
        {
             k=j;
             while(k>0)
             {
                 r=k%10;
                 if(r==1)
                     count++;
                 k=k/10;
             }
        }
        printf("%d\n",count);
    }
    return 0;
}

以前论坛里有讨论过类似的问题，建议去看看：https://bbs.bccn.net/thread-371905-1-1.html
之后你就能知道 0 到 9999 这样的数之间有几个 1。我把这些答案记在 a[10] 里。

对于任意 n 的话，我想了个方法：
随便输个数，比如 1234，那么可以分段计算有几个1，比如按这样分段：
0-4， 5-34， 35-234， 235-1234
就可以用递归来算一共有几个1。do_conut 用来数 n 以内有几个 1, k 用于表示它是个几位数。

235 到 1234 之间有几个 1 呢？
对于千位，1000 到 1234 这 235 个数共有 235 个 1。这是语句  (h == 1 ? n%tenp+1 : tenp) 的作用。如果 h 比 1 大的话，1000 个 1 都能用全，否则是234+1个1。
对于 235 到 1234 之间后三位的一，按这个顺序看：1000 到 1234，235 到 999，由于不用数千位的1 ，它和和 0 到 999 的 1 的个数是一样的。如果是 3234 的话，这个循环就能跑 3 遍。语句 h * a[k] 是这个作用。
当然还得处理一些比较特殊的，比如 1034 这样的，do_count 的第二次数参数其实是 do_count(034, 3) 这种由于百位一个1都没有，直接跳掉数 34 里还有几个1就行了。

试了几个数好像是对的，主要也是为了展示个思路，不对你再自己改改吧。

#include <stdio.h>
#include <math.h>

int a[10] = {
    0,
    1,
    20,
    300,
    4000,
    50000,
    600000,
    7000000,
    80000000,
    900000000,
};

int do_count(int n, int k)
{
    if (--k == 0) return n > 0;

    int tenp = pow(10, k), h = n/tenp;

    return do_count(n%tenp, k)
        + (h == 0 ? 0 : h * a[k] + (h == 1 ? n%tenp+1 : tenp));
}

int count(int n)
{
    int k, t = 1;
    for(k = 0; n/t; t *= 10, k++);
    return do_count(n, k);
}

int main()
{
    int n;
    scanf("%d", &n);

    printf("%d\n", count(n));

    return 0;
}

唔 对算法表示压力山大。。。
最近闲的没事儿也翻了翻《算法导论》
不过我高中肄业的数学水平看着很吃力
希望看完能多少有些帮助吧，学学数据结构也好。。。

我学了数据结构责骂感觉用不上啊？？？有什么提高程序运行效率的没！！我那个代码运行严重超时啊！求改进！求算法！

学点基本的算法知识，然后得多想多练。
我楼上说的想法你想清楚了吗？亏我解释得那么详细，要不仔细看我可受伤了。

这个我可以告诉你了，要用到统计方面的知识 还有归纳法 还有个忘记了。具体算法的正确归纳方法如下
0    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 13:02 编辑 ]

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

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

算法注意点 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以上的
这个就可以用递归来求解了


   







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