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)。这样就能大大提高速度了。