大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/182725.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...