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

猴子分苹果问题递归算法_猴子分苹果递推公式试题算法训练猴子分苹果题目描述:资源限制时间限制:1.0s内存限制:256.0MB问题描述  秋天到了,n只猴子采摘了一大堆苹果放到山洞里,约定第二天平分。这些猴子很崇拜猴王孙悟空,所以都想给他留一些苹果。第一只猴子悄悄来到山洞,把苹果平均分成n份,把剩下的m个苹果吃了,然后藏起来一份,最后把剩下的苹果重新合在一起。这些猴子依次悄悄来到山洞,都做同样的操作,恰好每次都剩下了m个…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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账号...

(0)


相关推荐

  • Delphi 语言「建议收藏」

    Delphi 语言「建议收藏」自1995年Borland公司发布Delphi1.0以来,Delphi受到很多开发者的亲睐,到1999年发布Delphi5,Delphi以其开发快捷、控件丰富、易于上手等优势吸引了众多的开发者,用户

  • 荣耀路由2 虚拟服务器,2019年性价比之王旗舰路由器—荣耀路由PRO2评测「建议收藏」

    大家好我是搞机大表姐,今天大表姐给大家带来的是和荣耀V20一起发布的全新旗舰路由器—荣耀路由PRO2,时隔三年终于迎来了荣耀路由器PRO的升级版,相比上一代荣耀路由器PRO2带来了“六”大技术的升级,更是支持30天用不爽就退,且明哥还在发布会发下战书“600元内路由器任意挑战”的狠话让这次发布的路由PRO2带来了更足的底气,那么具体的实际表现如何呢,请看下面大表姐为大家带来的评测。按照国际惯…

  • 在图形管理工具mysql workbench窗口_sqlite可视化工具

    在图形管理工具mysql workbench窗口_sqlite可视化工具可视化数据库管理工具MySQLWorkbench的安装配置及使用MySQLWorkbench是为数据库管理员、程序开发者和系统规划师提供可视化的Sql开发、数据库建模、以及数据库管理功能的工具。1.下载官网下载地址:https://dev.mysql.com/downloads/workbench/这里下载的版本是:community,为社区版,非商用,可以免费使用。2.安装安装过程就不多说了,双击安装,根据提示进行,非常简单。3.打开安装完成后,双击桌面图标即可打开,界

  • JMH 测试「建议收藏」

    JMH 测试「建议收藏」JHM测试框架

  • 判断图同构大杀器—nauty算法

    判断两图是否同构是一个经典问题。nauty算法作为时下较为流行的主流算法,具有效率高,剪枝力度强等优势。当然,在某些特殊情况会失灵。虽然该算法的概念在上世纪80年代就提出来了,但发展至今,仍然是不可忽略的一种方法。本人翻遍了中文互联网,没找到详细相关介绍,在stackoverflow上边找到了一个问答,顺着帖子的回复找到了算法原作者自建的网站,如获至宝。再结合离散数学,看懂了这个算法的大致流程。总结如下:nauty算法:判断两个图是否同构。思路:①设置一套编号系统,给两个图进行编号,如果两个

  • Pytest(11)allure报告「建议收藏」

    Pytest(11)allure报告「建议收藏」前言allure是一个report框架,支持java的Junit/testng等框架,当然也可以支持python的pytest框架,也可以集成到Jenkins上展示高大上的报告界面。mac环境:

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号