(Cpp) 5矮人分果

// from http://www.cppblog.com/mythma/archive/2007/06/25/26923.html
/**题：
 * 话说有五个小矮人上山摘野果,摘回来后平均分,可是怎么也分不下去.因为分不平均.
 * 到了晚上,一个小矮人爬起来,从里面扔了一个, 刚好能平均分成五份.然后他把自己的那份藏起来,就睡觉去了.
 * 第二个小矮个也爬了起来,也把果子扔了一个后刚好分成5份,他也把自己那份藏了起来.然后睡觉,
 * 余下3 个小矮人都是这样做的,过程完全一样. 请问,最初这堆果子至少有多少个?
 */
/**解：
 * 设共有total个野果；
 * 第1个矮人拿走 (total-1)/5 个野果，此时剩下 (total - 1)/5*4 个野果；
 * 第2个矮人拿走 ((total-1)/5*4 - 1)/5 个野果，剩下 ((total-1)/5*4 - 1)/5*4 个野果；
 * 以此类推...
 */
#include <iostream>
using namespace std;

int getTotal(){
    int total = 1; // 设初始野果总数1个
    while (true){
        int _t = total;
        for (int i = 1; i <= 5; i++){
            if ((_t - 1) % 5 == 0){ // 条件：扔掉1个能够5等分
                _t = (_t - 1) / 5 * 4; // 第i个矮人拿走1/5后剩下的继续循环
                if (i == 5){ // 如果5个矮人都拿到野果
                    return total;
                }
            }
        }
        total ++; // 不满足则野果总数加1
    }
}

int main(){
    cout << getTotal() << endl;
    return 0;
}
 

输出：3121