题目:海滩上有一堆桃子,五只猴子来分。第一只猴子把这堆桃子凭据分为五份,多了一个,这只猴子把多的一个扔入海中,拿走了一份。第二只猴子把剩下的桃子又平均分成五份,又多了一个,它同样把多的一个扔入海中,拿走了一份,第三、第四、第五只猴子都是这样做的,问海滩上原来最少有多少个桃子?
程序有现成的:https://blog.csdn.net/a542214712/article/details/8122871 (我假设这个程序是对的,如果不对,请指出)
我主要是想告诉你,任何程序,只要你能用循环写出来,都可以无脑改写成递归(反过来不一定。不借助堆栈未必能把递归写成循环)
public class Tao {
public static void main(String[] args) {
int monkey=1;//要分桃的猴子数
int peaches=1;//桃的总数
int peach=1;//每次分桃的总数
//循环进行给每个猴子分桃
while(monkey<=5)
{
//如果成功分桃
if(peach%5==1&&peach/5!=0)
{
//可分桃的总数为现在的4/5
peach=(peach/5)*4;
//换下一个猴子
monkey++;
}
//如果失败,重新分桃这时可分桃数量加1
else
{
peaches++;
peach=peaches;
monkey=1;
}
}
System.out.println("桃的最小总数为:"+peaches);
}
}
桃的最小总数为:3121
任何循环都可以改写成递归。关键是要搞清楚改写的技巧,把局部变量提升为参数,把循环变成if和递归调用:
class Untitled {
public static void main(String[] args) {
foo(0, 1, 1);
}
public static void foo(int monkey, int peaches, int peach)
{
//循环进行给每个猴子分桃
if(monkey<=5)
{
//如果成功分桃
if(peach%5==1&&peach/5!=0)
{
//可分桃的总数为现在的4/5
peach=(peach/5)*4;
//换下一个猴子
monkey++;
}
//如果失败,重新分桃这时可分桃数量加1
else
{
peaches++;
peach=peaches;
monkey=1;
}
foo(monkey, peaches, peach);
return;
}
System.out.println("桃的最小总数为:"+peaches);
}
}
这个程序也许有点复杂,你可以动手试试看自己来把下面的程序改写成递归:
public class HelloWorld {
public static void main(String []args) {
int i = 1;
int sum = 0;
for (i = 1; i <= 100; i++)
sum += i;
System.out.println(sum);
}
}
参考答案:
public class HelloWorld {
public static void main(String []args) {
foo(1, 0);
}
public static void foo(int i, int sum)
{
if (i <= 100)
{
sum += i;
i++;
foo(i, sum);
return;
}
System.out.println(sum);
}
}
这题目是不是错了 5个猴子 都分5份,扔了一个,那么一共扔了5个桃子,为什么这5个桃子没在第一个猴子分的时候给分成5份,每份增加1个