Posted on 2006-09-16 15:35
chenger 閱讀(895)
評(píng)論(4) 編輯 收藏 引用 所屬分類:
Programming Stuff
上次寫(xiě)了一篇關(guān)于google面試題的
文章。我給的算法跑得很慢，后面張沈鵬同學(xué)用python寫(xiě)了一個(gè)
算法，速度很快（再次感覺(jué)python的性能不像想象中那么壞，當(dāng)然和算法有關(guān)），看了一下他的代碼，函數(shù)count(i)用來(lái)計(jì)算小于i的1的個(gè)數(shù)，和我寫(xiě)的calc_ones算法基本相同，只不過(guò)count(i)用了遞歸，看上去更清楚一些。主要的速度差別在little(i)函數(shù)上，這個(gè)函數(shù)避免了很多迭代：
size_t little(size_t i)
{
??? size_t ones = calc_ones(i);
??? if(ones == i)
??????? cout << i << "\n";
??? if(i < ones)
??????? if((ones - i)/9 > 1)
??????????? return i - (ones - i)/8;
??? if(i > ones)
??????? return ones;
??? return i - 1;
}這是C++版本。主循環(huán)也要略微改變一下：
void solve()
{
??? size_t max = 10000000000;
??? for(size_t i = max;i > 0;i = little(i));
}可以看到，現(xiàn)在循環(huán)從大到小。little函數(shù)找到下一個(gè)可能滿足題目約束的i。在little函數(shù)中，首先計(jì)算小于i的1的個(gè)數(shù)ones，如果ones和i相等，就將i輸出（這就是題目要求干的事）。如果i小于ones，那么就要在小于i的自然數(shù)中找下一個(gè)可能滿足條件的數(shù)。因?yàn)樗阉鞯姆秶怀^(guò)10^10，所以一個(gè)數(shù)中至多含有9個(gè)1，按照這種極端情況，也必須將i減少(ones-i)/8才有可能滿足條件(這里之所以是8，因?yàn)橥瑫r(shí)i也減少了）。如果i大于ones，考慮一個(gè)小于i的數(shù)i'，可以考慮一下calc_ones(i')的取值，極端情況，[i',i)的范圍內(nèi)的整數(shù)沒(méi)有一個(gè)包含1，也就是說(shuō)當(dāng)i減少到i'時(shí)1的個(gè)數(shù)沒(méi)有損失，那么calc_ones(i') = calc_ones(i)，如果i'>calc_ones(i)，則就有i'>calc_ones(i')，直到i'=calc_ones(i)，因此下一個(gè)需要查看的數(shù)就是calc_ones(i)。其實(shí)上面這一段討論可以用一個(gè)式子來(lái)概括：對(duì)i'<i,calc_ones(i)-9*(i-i') <= calc_ones(i') <= calc_ones(i)。這樣就能大大提高速度了。