Posted on 2006-09-08 13:05
chenger 閱讀(1782)
評(píng)論(13) 編輯 收藏 引用 所屬分類:
Programming Stuff
從同學(xué)那兒聽(tīng)說(shuō)了一個(gè)傳說(shuō)是Google面試題的題目：找出所有的正整數(shù)N，使得小于N的所有正整數(shù)的各位數(shù)字中所有的'1'的數(shù)目和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下編譯運(yùn)行，輸出結(jié)果為：
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
可以證明，再往上就沒(méi)有了。跑得比較慢，需要好幾分鐘。我考慮過(guò)進(jìn)一步縮小檢索的范圍，應(yīng)該是可以做到的，不過(guò)沒(méi)有實(shí)現(xiàn)。
Update：上面的算法有很大的改進(jìn)余地，主要來(lái)自張沈鵬同學(xué)給出的程序，我專門寫了一篇文章來(lái)討論，
這里?；蛘呖梢灾苯涌?a href="/zuroc/archive/2006/09/16/12540.html">張沈鵬同學(xué)的文章。