Posted on 2006-09-08 13:05
chenger 阅读(1749)
评论(13) 编辑 收藏 引用 所属分类:
Programming Stuff
从同学那儿听说了一个传说是Google面试题的题目：找出所有的正整数N，使得小于N的所有正整数的各位数字中所有的'1'的数目和N相等。
我的解法：
#include <iostream>
#include <limits>
#include <cstddef>
using namespace std;
size_t calc_ones(size_t n)
{
const size_t save = n;
size_t sum = 0,ten = 1,cnt = 1;
if(n%10 > 1)
sum = 1;
n /= 10;
for(;n;n /= 10)
{
size_t r = n%10;
if(r == 1)
sum += save + (r*cnt - 10*n)*ten;
else if(r != 0)
sum += (10 + r*cnt)*ten;
ten *= 10;
++cnt;
}
return sum;
}
void solve()
{
size_t max = numeric_limits<size_t>::max();
for(size_t i = 1;i < max;++i)
if(calc_ones(i) == i)
cout << i << "\n";
}
int main()
{
solve();
return 0;
}在VS2005下编译运行，输出结果为：
199992 199993 199994 199995 199996 199997 199998 199999 200000 1599992 1599993 1599994 1599995 1599996 1599997 1599998 1599999 1600000 1600001 2600000 13200000 13200001 35000000 35199992 35199993 35199994 35199995 35199996 35199997 35199998 35199999 35200000 117463827 500000000 500199992 500199993 500199994 500199995 500199996 500199997 500199998 500199999 500200000 501599992 501599993 501599994 501599995 501599996 501599997 501599998 501599999 501600000 501600001 502600000 513200000 513200001 535000000 535199992 535199993 535199994 535199995 535199996 535199997 535199998 535199999 535200000
可以证明，再往上就没有了。跑得比较慢，需要好几分钟。我考虑过进一步缩小检索的范围，应该是可以做到的，不过没有实现。
Update：上面的算法有很大的改进余地，主要来自张沈鹏同学给出的程序，我专门写了一篇文章来讨论，
这里。或者可以直接看
张沈鹏同学的文章。