这么坚定地相信你的理解是对的么？为什么不提交一下小曹的代码试试呢？

#include <stdio.h>
#define M 9999
int main(void)
{
    int c[M+1];//存储1~N里面1的个数
    int num[M];//存储输入的数
    int i,j,k=0,d,n;
    for(i=1,d=0;i<=M;i++)
    {
        for(j=1;i/j;j*=10)
        {
            c[i]=d;
            if(i/j%10==1)
               c[i]=++d;
        }
    }//算出所以的数
    printf("Input:\n");
    while(scanf("%d",&n),n)
    {
        num[k]=n;
        k++;
    }
    printf("\nOutput:\n");
    for(i=0;i<k;i++)
    {
        printf("%d\n",c[(num[i])]);//输出1~已输入数n里面1的个数
    }
    return 0;
}

额  楼主 不得不说 你的算法是有问题的   很简单  1~11 里面有4个1  你这个输出的是3  1~111里面有36个1  你这个输出的是31  这里面你忽略了高位上原有的1
我顺着你的思路 把你的代码改了下 然后我把我对题目的要求的理解也写进了代码 你就知道 那个输入 输出的要求 是什么意思了

好吧 原来楼主是理解错了题目的意思 = =  题目意思应该是出现1的个数 而不是含有1的整数的个数

我明白我错在什么地方了，少判断了当n为0的情况，应当加一句 if(n==0) return 0;
#include <stdio.h>

// 递归方法
int recursion( int n )
{
    int base = 1;
    if( n == 0 )
        return 0;
    if( n < 10 )
        return 1;
    for( ; n>=base*10; base*=10 );

    return n/base*recursion(base-1) + ( n/base==1 ? n%base+1 : base ) + recursion(n%base);
}

int main()
{
    int n;
    for( ; scanf("%d",&n)==1 && n!=0; )
        printf( "%d\n", recursion(n) );

    return 0;
}

楼主错啦。楼主看看它给的例子。“N=10，1，2.....10中包含两个数字1”。你改成求1的个数去oj试试吧。反正又不麻烦，

#include"stdio.h"
int main()
{
    int x[9999],i,j,d,N;
    for(i=0,d=0;i<9999;i++)
    {
        for(j=1;i/j;j*=10)
        {
            if(i/j%10==1)
            {x[d]=i;
            if(x[d]==x[d-1])
            x[d-1]==-1;
            //printf("%d d=%d ",x[d],d);
            d++;
            }
        }
    }
    while(scanf("%d",&N),N)
    {
        for(i=0;i<9999;i++)
        {
            if(N>=9991){printf("4000\n");break;}
            if(x[i]<=N&&x[i+1]>N)
            {
                if(x[i]==-1)
                continue;
                else
                printf("%d\n",i+1);break;}
        }
    }
    return 0;
}

自己AC后的代码
是我理解错了
我太年轻了

---------1到N所有整数包含1的个数程序--------

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int i,m=0,x,y,z,n,k;
    printf("请输入正整数n(1<=n<=9999)：\n");
    scanf("%d",&n);
    for(i=0;i<=n;i++)
    {
                    x=i/1000;
                    if(x==1)
                       m++;
                    y=i/100%10;
                    if(y==1)
                      m++;
                    z=i%100/10;
                    if(z==1)
                       m++;
                    k=i%10;
                    if(k==1)
                       m++;
      }
    printf("\n1到%d的所有整数包含1的个数为：%d\n",n,m);
  system("pause");
}
---------1到N所有整数包含1的个数程序--------
--------1到N所有整数包含1的整数个数程序------
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int i,m=0,x,y,z,n,k;
    printf("请输入正整数n(1<=n<=9999)：\n");
    scanf("%d",&n);
    for(i=0;i<=n;i++)
    {
                    x=i/1000;                    
                    y=i/100%10;                    
                    z=i%100/10;                    
                    k=i%10;
                    if(x==1||y==1||z==1||k==1)
                       m++;
      }
    printf("\n1到%d的所有整数包含1的整数个数为：%d\n",n,m);
  system("pause");
}

--------1到N所有整数包含1的整数个数程序------

#include "stdio.h"
int main()
{
    int x[9999],i,j,d,N;

    int xx[9999] = {0};
    int i_count = 0;

    for(i=0,d=0;i<9999;i++)
    {
        for(j=1;i/j;j*=10)
        {
            if(i/j%10==1)
            {
                x[d]=i;
            //printf("%d d=%d ",x[d],d);
            d++;
            break;}
        }
    }

    while(scanf("%d",&N),N)
    {
        for(i=0;i<9999;i++)
        {
            if(N>=9991)
            {
                printf("3439\n");
                break;
            }
            if(x[i]<=N&&x[i+1]>N)
            {
                //printf("%d\n",i+1);
                xx[i_count++] = i+1;
                break;
            }
        }
    }

    for(i= 0;i <i_count;i++ )
    {
        printf("%d\n",xx[i]);

    }
    return 0;
}

自诩时间复杂度为O(1)的算法，求喷。
思路：将一个整数自最高位拆分为两部分 如[0 - 5234]=[0 - 499]+[5000 - 5234],[x - y]表示x-y间1的个数
[0-499]为5*[0-99]+100,100是[100-199]多出的100个
[5000-5234]=[0-234]，递归求解即可，其中如果高位是1 需加上多出的1 如[1000-1234]=[0-234]+235
运算过程中，将[0-9,99,999]的个数保存起来 只计算一次 则函数执行的时间只取决于整数的位数 而与其大小无关 可视为常量时间复杂度

int num_1_rec(int n)
{
    static int num_base[4] = {0, 0, 0, 1};  //分别存放0-9,99,999,9999中出现的1的个数 
    
    //个位数直接退出
    if(n == 0) return 0;
    else if(n < 10) return 1;
    
    int base = 1, basepos = -1, i, nH, nL; 
    
    //求解n(>=10)的数基（Exp. 50的数基为10），以及其对应的num_base的下标位置 
    while((i = n/base) >= 10){
        base *= 10;
        basepos++;
    }
    
    //最高位产生的1的个数(Exp. 2523, 0-1999中1的个数) 
    nH = num_base[basepos] != 0 ? num_base[basepos] : num_1_rec(base-1);
    nH *= i;
    if(i > 1) nH += base;
    else nH += n%base + 1;  //最高位为1的情况的特殊处理 
    
    //低位产生的1的个数(Exp. 2523, 2000-2523[0-253]中1的个数) 
    nL = num_1_rec(n%base);
    
    //保存已经计算过的0-9,99...中1的个数 
    if(n+1 == base*10) num_base[basepos+1] = nH+nL;
    
    return nH+nL;            
}