猴子吃桃问题:
有一堆桃子不知数目,猴子第一天吃掉一半,觉得不过瘾,又多吃了一只,第二天照此办理,吃掉剩下桃子的一半另加一个,天天如此,到第十天早上,猴子发现只剩一只桃子了,问这堆桃子原来有多少个?
模型:
用\(a_i\)表示第\(i\)天的桃子数量。
- 第一天桃子数为:\(a_1\)
- 。。。
- 第\(i\)天的桃子数\(a_i\)
- 第\(i+1\)天的桃子数\(a_{i+1}=a_i/2-1\)
- 。。。
- 第\(10\)天的桃子数\(a_{10} = 1\),
则问题为:\(a_1=?\),如果\(a_{10} = 1\)。
钓鱼问题:
A 、 B 、 C 、 D 、 E 五人夜间合伙捕鱼,凌晨时都疲倦不堪,各自在河边的树丛中找地方睡着了。日上三竿, A 第一个醒来,他将鱼分作五份,把多余的一条扔回河中,拿自己的一份回家去了。 B 第二个醒来,也将鱼分作五份,扔掉多余的一条,拿走自己的一份,接着 C 、 D 、 E 依次醒来,也都按同样的办法分鱼,问五人至少合伙捕了多少条鱼?试编程序算出。
模型:
直接用A 、 B 、 C 、 D 、 E变量的值表示他们所看到的鱼的数量。
则:
- \(B = 4 * (A - 1) / 5\)
- \(C = 4 * (B - 1) / 5\)
- \(D = 4 * (C - 1) / 5\)
- \(E = 4 * (D - 1) / 5\)
E把数量为\(E\)的鱼分成5份,还多一条鱼。所以
- \(E \mod 5 = 1\)
常识告诉我们,\(E=6, 11, 16,...\)。
同时,上面的递推关系也表示了下列关系
- \(D \mod 5 = 1\)
- \(C \mod 5 = 1\)
- \(B \mod 5 = 1\)
- \(A \mod 5 = 1\)
分析题面描述“问五人‘至少’合伙捕了多少条鱼?”,所以,我们可以按最小值进行求解。
从\(E=6\)开始,不断迭代,尝试下列除法正好都能除尽,即上面的同余式均成立。
- \(D=5*E/4+1\)
- \(C=5*D/4+1\)
- \(B=5*C/4+1\)
- \(A=5*B/4+1\)