海盗分椰⼦c语⾔编程,⽔⼿分椰⼦——迭代法、递归解题（⽰
例代码）
题⽬内容：
n(1< n <=5)个⽔⼿在岛上发现⼀堆椰⼦，先由第1个⽔⼿把椰⼦分为等量的n堆，还剩下1个给了猴⼦，⾃⼰藏起1堆。然后，第2个⽔⼿把剩下的n-1堆混合后重新分为等量的n堆，还剩下1个给了猴⼦，⾃⼰藏起1堆。以后第3、4个⽔⼿依次按此⽅法处理。最后，第n个⽔⼿把剩下的椰⼦分为等量的n堆后，同样剩下1个给了猴⼦。请⽤迭代法编程计算并输出原来这堆椰⼦⾄少有多少个,n的值要求从键盘输⼊。若输⼊的n值超出要求的范围，程序输出”Error!”。
提⽰：分成的等量的堆数应该与⽔⼿的数量⼀致.
程序运⾏结果⽰例1：
Input n(1 < n <= 5):
5↙
y=3121.
程序运⾏结果⽰例2：
Input n (1 < n <= 5):
7↙
Error!
输⼊提⽰信息： “Input n(1 < n <= 5):
”
输⼊格式: “%d”
输出格式：”y=%d
”
输⼊错误提⽰信息：”Error!
”
这是⼀道著名的数学问题，解题通式为:
y=a(a/m)n-1 －db/c
y ── 被分的椰⼦的总个数.
a ── 每次分的份数,
n ── 总共分的次数.
b ── 每次分a份后的余数.
c ── 每次分a份后拿⾛的份数.
d ── 每次分a份后拿⾛c份后，剩下再分的份数.
编程递归函数
m── (a/d)的最⼤公约数.
迭代法实现
思路：
假设现在有五个⼈分⼀堆椰⼦，那么每个⼈都会分⼀次椰⼦，我们可以得知⼈数就是分椰⼦的次数
假设第⼀个⼈还没分的时候椰⼦总共有y1个，那么第⼀个⼈分了之后，椰⼦总数y2=(y1-1)*(4/5)；如果已知y2求y1，那么y1=
(y2*5)/4+1。
我们知道椰⼦都是⼀个⼀个的，这就说明椰⼦数量是整数，判断⼀个数是否是符合条件，我们仅需要判断每次它被分之后是不是整数就ok。
为减少时间复杂度，我们选择还原数量的⽅式迭代，设⼀个循环，循环变量为分了n次之后每⼀份的椰⼦数量，向上还原，判断还原n层的过程中每次椰⼦的数量仍然是否是整数，如果不是，继续外层循环，直到到⼀个数能够进⾏n次内层循环为⽌。
程序代码(C语⾔)：
#include
int main()
{
int i, j, total, n;
printf("Input n(1
");
scanf("%d", &n);
if (n <= 1 || n > 5)
{
printf("Error!
");
}
else
{
i = 1;
while(1)
{
total = i;
for(j = 0; j < n; j++)
{
total = total * 5;
if(total % 4 != 0)
{
break;
}
total = total / 4;
total += 1;
}
if(j == n)
{
break;
}
i++;
}
printf("y=%d
", total);
}
return 0;
}
递归实现
思路：
写⼀个函数模拟分椰⼦操作，传⼊分的椰⼦数量和分的⼈数，判断椰⼦数量是否⾜够⽀持到最后⼀个⼈分完，如果能返回⼀个真值，如果不能返回⼀个假值。
程序代码(C语⾔)：
#include
int divide(int n, int m);
static int people;
int main()
{
int i;
int n;
printf("Input n(1
");
scanf("%d", &n);
people = n;
if (n <= 1 || n > 5)
{
printf("Error!
");
}
else
{
for (i = 1; ; i++)
{
if (divide(i, n))
{
printf("y=%d
", i);
break;
}
}
}
return 0;
}
int divide(int n, int m)
{
if (n / people == 0 || n % people != 1) return 0;
if (m == 1)
return 1;
return divide(n - n / people - 1, m - 1); }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。