算法分析与设计 狼吃兔子问题 07 级计算机科学与技术3 班王尤峰算法演示 cave5 cave0 cave4 cave2 cave3 cave1 Wolf N=6 M=4问题分析 我们先做一个假设，你围着400 米的环形跑道跑步，分多 次（整数次）跑，每次跑150 米，如果你想回到原出发点 ，那么毫无疑问你跑的最短总路程为400 米的整数倍同时 也是150 米的整数倍并且为最小公倍数1200 米，需要经过 1200/150=8 次奔跑。 经过以上分析，我想你已经明白了狼找兔子经过的最小总 山洞数目为n 、m 的最小公倍数，假设该公倍数为k，那么 狼搜索过的山洞为k/m 个。如果完成整个过程狼搜索过的 山洞为n ，那么兔子便无处藏身（即k/m=n 亦即k=m*n ）。 在数学中我们已经知道(m*n)/ （m ，n 的最大公约数）=k ， 由此可知当最大公约数为1 时刚好满足兔子无藏身之地， 同时我们也可以知道m 、n 的最大公约数不为1 时兔子有藏 身之地。公约数法 void main() int n,m,result; scanf(%d, scanf(%d, result=check
