猴子分桃

monkey_div_peach.c

#include <stdio.h>
/*
 * 海滩上有一堆桃子，五只猴子来分，第一只猴子把这堆桃子平均分为五份，多了一个，
 * 这只猴子把多的一个扔到了海里，拿走了一份，第二只猴子把剩下的桃子又平均分成
 * 五份，又多了一个，它同样把多的一个扔到了海里，拿走了一份，第三只，第四只，第
 * 五只都是这样做的，问海滩上原来最少有多少桃子。使用递归编程求解。
 */
#define MONKEY 5

// 由当前猴子数和最终剩下的桃数求出总桃数
int re_div(int monkey, int peach_last) {
    int next;
    if (monkey == 0)
        return peach_last;
    next = re_div(monkey - 1, peach_last);
    if( next % 4 != 0)
        return -1;
    return (next/4*5 + 1);
}

int main(int argc, const char *argv[]) {
    int i;
    int result;

    for (i = 1; ; i++) {
        if ((result = re_div(MONKEY, i*4)) > 0) {
            printf("monkey:%d, last_peach:%d, all_peach:%d\n", MONKEY, i*4, result);
            break;
        }
    }
    return 0;
}

monkey_div_peach2.c

#include <stdio.h>
/*
 * 海滩上有一堆桃子，五只猴子来分，第一只猴子把这堆桃子平均分为五份，多了一个，
 * 这只猴子把多的一个扔到了海里，拿走了一份，第二只猴子把剩下的桃子又平均分成
 * 五份，又多了一个，它同样把多的一个扔到了海里，拿走了一份，第三只，第四只，第
 * 五只都是这样做的，问海滩上原来最少有多少桃子。使用递归编程求解。
 */
#define MONKEY 5

// 判断monkey和peach是否可能，可能返回1，不能返回0
int is(int monkey, int peach) {
    if(monkey == 0)
        return 1;
    if(peach % 5 != 1)
        return 0;
    return is(monkey-1, (peach-1)/5*4);
}

int main(int argc, const char *argv[]) {
    int i;

    for (i = 1; ; i++) {
        if ((is(MONKEY, 5*i+1) == 1)) {
            printf("monkey:%d, all_peach:%d\n", monkey, 5*i + 1);
            break;
        }
    }
    return 0;
}