Posted on 2006-09-08 13:05
chenger 閱讀(1765)
評論(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：上面的算法有很大的改進余地，主要來自張沈鵬同學給出的程序，我專門寫了一篇文章來討論，
這里?；蛘呖梢灾苯涌?a href="/zuroc/archive/2006/09/16/12540.html">張沈鵬同學的文章。