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

fly231

这是我的代码，来献献丑，比楼主的算法慢多了，惭愧
#include <iostream>

using namespace std;

int main()
{
        cout << "input max number to find" << endl;
        long long maxnum;
        cin >> maxnum;
        cout << maxnum << endl;

        long long totalonecnt = 0;
        long long curonecnt = 0;
        long long lastdigit = 0;
        long long left=0;

        for (long long l=1; l<=maxnum; l++)
        {
                lastdigit = l-1;
                left = lastdigit%10;
                while ( left==9 )
                {
                        lastdigit = lastdigit/10;
                        left = lastdigit%10;
                }
                if ( left==0 )
                        curonecnt++;
                else if ( left==1 )
                        curonecnt--;

                totalonecnt = totalonecnt + curonecnt;
                if (totalonecnt==l)
                        cout << l << endl;
        }

        return 0;
}

suek

我觉得这个问题的关键不在于计算哪些数整数n，而在于考虑n的最大范围。

10^0<=n<10^1, min f(n)=1
10^1<=n<10^2, min f(n)=1*10^0 +1
10^2<=n<10^3, min f(n)=2*10^1+1
10^3<=n<10^4, min f(n)=3*10^2+1

依次类推(这个是排列组合问题，大家应该都会算)，
当n为等于11位时,min f(n)=10*10^9+1=10^10+1
当n为等于12位时,min f(n)=11*10^10+1=10^11+10^10+1>10^11

所以n的范围应该是1<=n<10^11
(不知道各位能否有更好的办法把n范围缩小到更小，比如10^10)

写程序就是很容易的事情了，不管算法怎样，只要结果正确就可以了。

[ 本帖最后由 suek 于 2006-3-30 15:03 编辑 ]

zhangjiakouzf

原帖由 suek 于 2006-3-30 13:58 发表
我觉得这个问题的关键不在于计算哪些数整数n，而在于考虑n的最大范围。

10^0<=n<10^1, min f(n)=1
10^1<=n<10^2, min f(n)=1*10^0 +1
10^2<=n<10^3, min f(n)=2*10^1+1
10^3<= ...

我觉得这个思想非常正确，一般求解如果无法得出精确值的话，在范围上面趋近是通用做法
但算法好像有点问题，正在考虑一般表达式:em11:

suek

原帖由 zhangjiakouzf 于 2006-3-30 14:36 发表


我觉得这个思想非常正确，一般求解如果无法得出精确值的话，在范围上面趋近是通用做法
但算法好像有点问题，正在考虑一般表达式:em11:

嗯，是我想错了一下。这样算的话，范围还是太大，看来只有看看别的办法了。

zhangjiakouzf

原帖由 zhangjiakouzf 于 2006-3-30 14:36 发表


我觉得这个思想非常正确，一般求解如果无法得出精确值的话，在范围上面趋近是通用做法
但算法好像有点问题，正在考虑一般表达式:em11:

这个是10^n内含1数字的个数

[ 本帖最后由 zhangjiakouzf 于 2006-3-30 15:26 编辑 ]

zhangjiakouzf

看看这个对吗
10^1  n=1  f(n)=1
10^2  n=2  f(n)=20

sdeven.lee

google的题？不会吧。不是一直都是考算法题和开放题吗？
这不像啊

没见过，google一年都懒的换次题，不知道这是哪年的

lmatt

我想了好久,才想出来.但结果出来的非常慢.
下面是我的,献丑了.请大家多多指教.
#include<stdio.h>
#include<string.h>
#include<math.h>
main()
{
        long long m;
        for(m=1;m<=1000000000;m++)
        fun(m);
        getch();
}
fun(long long m)
{
        char a[100];
        int n,i;
        long long k=0,x=m;
        sprintf(a,"%lld",m);
        n=strlen(a);
        for(i=0;i<n;i++)
        {
                x-=(a-4*pow10(n-i-1);
                if(i!=0&&i!=n-1)
                {
                if(a==49) k+=x+1+(n-1-i)*pow10(n-2-i);
                else if(a!=4 k+=(a-4*(n-1-i)*pow10(n-2-i)+pow10(n-1-i);
                else k+=0;
                }
                if(i==n-1) k+=a==48?0:1;
                if(i==0)
                {
                        if(a[0]!=49) k+=pow10(n-1)+(a[0]-4*(n-1)*pow10(n-2);
                        else k+=1+(n-1)*pow10(n-2)+x;
                }
                if(a[0]==4 k=0;
                else if(n==1) k=1;
        }
        if(k==m) printf("%lld\n",k);

}

[ 本帖最后由 lmatt 于 2006-3-31 10:20 编辑 ]

2eye

这个问题很早以前在Python的列表里讨论过，用排列组合非常快就可以出来了。我去找找，把程序也给贴上来。前面用公式证明的那个，可能就是用的排列组合。

def f(n):
   """f(n) = Sum{g(k)}, k=1..n
   where g(k) = number of '1's in decimal presentation of k
   """
   m = 1; r = 0
   # In the i-th loop, we sum No. of '1' showed in the i-th position
   # (start from the RIGHT) of all k's decimal presentation, k=1..n.
   # m == 10**(i-1), i.e. the order of i-th digit.
   while m <= n:
       head = n / (m *10) * (m * 10)   # digits to the left of digit_i
       digit_i = n / m % 10            # the i-th digit
       tail = n % m                    # digits to the right of digit_i
       # Example: for n=23456 and m=100, head=23000,digit_i=4,tail=56

       # This many '1's showed on the i-th position of k, for k=1..head-1.
       r += head / 10
       if digit_i == 1:
           r += tail + 1   # No. of '1's showed on i-th position for
k=head..n
       elif digit_i > 1:
           r += m          # same as above, but diff. calculation
       # Select the (i+1)-th position.
       m *= 10

   return r

#import pdb
#pdb.set_trace()

#look for some n2 satisfying f(n2) >= n2
n = 1; loops = 0
while n < 10**100:
   loops += 1
   F = f(n)
   if F == n:
       print "f(" + str(n) + ") = " + str(F) + ", loop " + str(loops)
       n += 1
   elif F < n:
       # find the order of n
       m = 10; d = 1   # m = 10**d holds
       while m <= n:
           m *= 10; d += 1
       # now d == No. of digits in str(n)

       # this jump will never be "too long", since there is no more than
       # n-F '1's between n+1 and n+jump. (f(n+jump) equals n+jump only
when
       # each number between n+1 and n+jump has d '1's
       jump = (n - F) / d
       if jump > 0:
           n += jump
       else:
           n += 1
   else:   # F > n
       # this is equivalent to new_n = n+(F-n),
       # and f(new_n) == f(n+(F-n)) >= f(n) == F == n+(F-n) == new_n
       n = F
   #print "not satisfied: f(" + str(n) + ") = " + str(F)

Skily

using System;

namespace ConsoleApplication1
{
       
        class Class1
        {
                [STAThread]
                static void Main(string[] args)
                {
                        long n = 0;
                        long sum = 0;
                        while(true)
                        {                               
                                long m = n;
                                while(m>0)
                                {
                                        int k =(int) m%10;
                                        if(k == 1)
                                        {
                                                sum++;
                                        }
                                        m = (long) m/10;
                                }
                                if(sum == n)
                                {
                                        Console.WriteLine(n);
                                }
                                n++;
                        }
                }
        }
}