Yet Another Programmer

上次寫了一篇關于google面試題的文章。我給的算法跑得很慢，后面張沈鵬同學用python寫了一個算法，速度很快（再次感覺python的性能不像想象中那么壞，當然和算法有關），看了一下他的代碼，函數count(i)用來計算小于i的1的個數，和我寫的calc_ones算法基本相同，只不過count(i)用了遞歸，看上去更清楚一些。主要的速度差別在little(i)函數上，這個函數避免了很多迭代：

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++版本。主循環也要略微改變一下：

void solve()
{
??? size_t max = 10000000000;
??? for(size_t i = max;i > 0;i = little(i));
}

可以看到，現在循環從大到小。little函數找到下一個可能滿足題目約束的i。在little函數中，首先計算小于i的1的個數ones，如果ones和i相等，就將i輸出（這就是題目要求干的事）。如果i小于ones，那么就要在小于i的自然數中找下一個可能滿足條件的數。因為搜索的范圍不超過10^10，所以一個數中至多含有9個1，按照這種極端情況，也必須將i減少(ones-i)/8才有可能滿足條件(這里之所以是8，因為同時i也減少了）。如果i大于ones，考慮一個小于i的數i'，可以考慮一下calc_ones(i')的取值，極端情況，[i',i)的范圍內的整數沒有一個包含1，也就是說當i減少到i'時1的個數沒有損失，那么calc_ones(i') = calc_ones(i)，如果i'>calc_ones(i)，則就有i'>calc_ones(i')，直到i'=calc_ones(i)，因此下一個需要查看的數就是calc_ones(i)。其實上面這一段討論可以用一個式子來概括：對i'<i,calc_ones(i)-9*(i-i') <= calc_ones(i') <= calc_ones(i)。這樣就能大大提高速度了。