据说是google的面试题，看谁的快

marinekiller

可以证明楼主是对的
但我算到3500001就算不下去了，太慢
期待正解
#include <iostream.h>
#include "conio.h"
long exp(int m,int k)
{
        int n=1;
        if( k == 0 )
                n = 1;
        else
                for(int i=1;i<=k;i++)
                        n *=m;
        return n;
}
int main()
{
        int n;
        cout<<"Input n:";
        cin>>n;
        int m = 0;
        for (int i=1;i<=n;i++)
        {
            for(int j=1;exp(10,j-1)<=i;j++)
            {
                if(i%exp(10,j)/exp(10,j-1)==1)
                   m++;

            }
            if(m == i)
                cout<<m<<endl;

        }
        //cout<<m<<endl;
       _getch();
}

chen_gxing

高手呀,我真是佩服的五体投地了.
说算法我不懂,说数学我不精.看来我也只有默默的灌水了.请大家谅解.

爱随柳飘

原帖由 bleem1998 于 2006-3-29 12:14 发表
写了个伪的
大伙指正
[code]
//计算一个整数里还有多少个1，有几个返回几
int num_a_int(int papapa)
{
        //这个函数对谁来说都easy吧
        return 0;
}

//这个函数就是题目里要求的那个函数 ...

有见的。不错，用的是函数递归吧。

markcarmen

构造一个函数 num(int x),此函数返回数字x中所含“1”的个数。
那么当n>1时根据定义有
f(n) = f(n-1)+num(n) ；


y=0;
for(i=1;i<=n;i++)
  y+=num(i);

程序的时间复杂度为O(n);空间复杂度为O(1);

marinekiller

#include <iostream.h>
#include <conio.h>
void main()
{
       int n = 1 , b = 9 , m = 1 , p = 10 , x = 0 , k = 0;        // m是n的位数，p是10的m次方
       for( ; n < 9999999999; n++ )
       {
              if( b = 0 )              // b=0时，n恰好为10的整数倍，算得n中1的个数为k，则n+1中有 K+1 个1......
              {                                                                    //  n+2,n+3.....n+9 中各有 k 个1
                    if( n == p )                                              // 如果n等于p,位数m加1，相应的p值改变
                    {
                           m++; p *= 10;
                    }      
                    k = 0;
                    int ln = n / 10, lp = p;
                    for( ; m > 0 ; m-- )
                    {
                           if(ln % lp / ( lp / 10 ) == 1 )
                           k++;
                           lp /= 10;
                    }
             }
              else
              {
                    if( b = 9 )  { x += k+1;  b-- }
                    x += k; b--;
              }
              if( x == n )   { cout << n << endl; }
       }
}

c++ builder 环境下运行，没有调试过，不知道速度怎样！
不过应该不错吧，哈哈，昨天想了一个晚上，哪位兄弟在机子上运行下帮我看看啊！

[ 本帖最后由 marinekiller 于 2006-4-8 22:47 编辑 ]

wobushiwo

再次思考中。。。

[ 本帖最后由 wobushiwo 于 2006-4-8 20:34 编辑 ]

gaoas

#include <cstdlib>
#include <iostream>
using namespace std;

int incone( int n)
{
    int i=0;
    do
    {
          if ( n%10 == 1 )
              {i++;}
           n=n / 10;
    }
    while ( n > 0);
//    cout << i <<endl;
    return i;
}

int main(int argc, char *argv[])
{
    int i=1,m,n=2;
    while (i != n )
    {
        i+=incone(n);
        n++;           
    }
    printf("%d\n", i);
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

gaoas

do
    {
        i+=incone(n);
    }while (i != n++ );

marinekiller

#include <iostream.h>
#include <conio.h>
void main()
{
       int n = 1 , b = 9 , x = 0 , k = 0;        // m是n的位数，p是10的m次方
       for( ; n < 9999999999; n++ )
       {
              if( b = 0 )              // b=0时，n恰好为10的整数倍，算得n中1的个数为k，则n+1中有 K+1 个1......
              {                                                                    //  n+2,n+3.....n+9 中各有 k 个1
                                       
                    k = 0;
                    int ln = n , lp = p;
                    for( ; ln > 0 ;  )
                    {
                           if(ln % 10 ) == 1 )
                           k++;
                           ln /= 10;
                    }
             }
              else
              {
                    if( b = 9 )  { x += k+1;  b-- }
                    x += k; b--;
              }
              if( x == n )   { cout << n << endl; }
       }
}

c++ builder 环境下运行，没有调试过，不知道速度怎样！
不过应该不错吧，哈哈，昨天想了一个晚上，哪位兄弟在机子上运行下帮我看看啊！

jinni0411

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>

static int dig_1 =0;

int my_fun(const int i)
{
    char a[100];
    int len;

    memset(a,0x00,100);
    itoa(i,a,10);

    len = strlen(a);
    while(len>=0)
    {
       if(a[--len]=='1')
          dig_1++;
    }
    return dig_1;
}

void main()
{
    int n=1;
    while(1)
    {
        if(my_fun(n) == n)
            printf("%d  \n",n);
        n++;
    }
}