猴子分苹果问题递归算法_猴子分苹果递推公式

全栈程序员-用户IM • 2022年10月12日下午5:46 • 未分类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

试题算法训练猴子分苹果

题目描述：

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　秋天到了，n只猴子采摘了一大堆苹果放到山洞里，约定第二天平分。这些猴子很崇拜猴王孙悟空，所以都想给他留一些苹果。第一只猴子悄悄来到山洞，把苹果平均分成n份，把剩下的m个苹果吃了,然后藏起来一份，最后把剩下的苹果重新合在一起。这些猴子依次悄悄来到山洞，都做同样的操作，恰好每次都剩下了m个苹果。第二天，这些猴子来到山洞，把剩下的苹果分成n分，巧了，还是剩下了m个。问，原来这些猴子至少采了多少个苹果。
输入格式
　　两个整数，n m
输出格式
　　一个整数，表示原来苹果的数目
样例输入
5 1
样例输出
15621
数据规模和约定
　　0<m<n<9
　　
题意：

该题简化为这样，n个猴子，每个猴子将所看到的苹果均分为n份，多余m个苹果。拿走m个以及一份。求原来苹果的个数。

思路：

假设某一次猴子操作之前的苹果个数为sum2，操作之后的苹果个数为sum1，每一份苹果个数为num（中间变量）。那么
①sum2=n*num+m；
由①可知：（sum2-m）刚好是n整份（没有余数）的苹果；
②sum1=sum2-num-m（拿走m个以及一份）
由②可知：sum1=（sum2-m）-num【（sum2-m）是n整份，再减去num，就是（n-1）份的苹果】，所以sum1就是（n-1）份的苹果，每一份的个数为num。
所以sum1与sum2个关系为：
sum1×n/(n-1)=sum2-m；可以推出：sum1×n/(n-1)+m=sum2；

注意：

（1）确定一个值，即第n只猴子操作完（拿了m个苹果，又藏了一份苹果）之后苹果的个数。
（2）该题是蓝桥杯的题，但是我觉得有一个问题，那就是题目第一个测试数据出错，第二天猴子们把苹果分成n份时，一份至少1个，所以本题不是百分之百正确。

有bug的测试数据如下：

2 1

7
（这样的话，就意味着第n只猴子操作完只剩下1个苹果啦，没办法再分成2份啦，所以我觉得蓝桥杯该题存在的一个问题，但是不影响大家学习，这道题）
这个测试数据正确的答案应该是15

代码：

#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
int sum[10];
int main()
{ 
   	
	int n,m,flag,i,temp=0;
	cin>>n>>m;
	memset(sum,0,sizeof(sum));
	int num;//第n只猴子操作结束后分成 n份，每一份的个数 
	for(num=1;;num++)//注意这里，最好不要限制num的最大值，算出最后的答案结束即可 
	{ 
   
		sum[1]=n*num+m;//最后一只猴子操作完之后的苹果个数 
		if(((sum[1]-m)%n==0)&&(sum[1]%(n-1)==0))
		{ 
   
			for(i=2;i<=n+1;i++)//操作n次（因为有n只猴子） 
			{ 
   
				flag=0;
				if(sum[i-1]%(n-1)==0&&(sum[i-1]-m)%n==0)
				{ 
   
					sum[i]=sum[i-1]*n/(n-1)+m;//计算结果如上面思路中所写 
					if(sum[n+1])//算出来原来的苹果数就输出，且结束 
					{ 
   
						cout<<sum[n+1]<<endl;
						return 0;
					}
				}
				else
				{ 
   
					flag=1;//计算过程中，某次操作中，苹果的个数不符合要求 
					break;//要求((sum[1]-m)%n==0)&&(sum[1]%(n-1)==0) 
				}
			}
			if(flag)//继续寻找最后一只猴子操作完的苹果个数 
				continue;
		}
	}
	return 0; 
}