python分苹果问题_给大家分享一个「Python算法题」分苹果

python分苹果问题_给大家分享一个「Python算法题」分苹果今天刷到一道算法题,分享一下果园里有堆苹果,N(1<N<9)只熊来分。第一只熊把这堆苹果平均分为N份,多了一个,它把多的一个扔了,拿走了一份。第二只熊把剩下的苹果又平均分成N份,又多了一个,它同样把多的一个扔了,拿走了一份,第三、第四直到第N只熊都是这么做的,问果园里原来最少有多少个苹果?可以先尝试一下再往下看(N=5的时候,答案是3121)。先简单分析一下这道题目,假设当第k个熊取完之后还有M个…

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

Jetbrains全系列IDE稳定放心使用

今天刷到一道算法题,分享一下

果园里有堆苹果,N(1<N<9)只熊来分。第一只熊把这堆苹果平均分为N份,多了一个,它把多的一个扔了,拿走了一份。第二只熊把剩下的苹果又平均分成N份,又多了一个,它同样把多的一个扔了,拿走了一份,第三、第四直到第N只熊都是这么做的,问果园里原来最少有多少个苹果?

可以先尝试一下再往下看(N=5的时候,答案是3121)。

先简单分析一下这道题目,假设当第k个熊取完之后还有M个苹果,按照题目的意思,M除以N的余数恰好是1,那么第k+1只熊可以拿到(M-1)/N个苹果,第k只熊取之前有MN/(N-1)+1个苹果。 换句话说,这堆苹果满足一个性质,对于每一只熊,取之前取之后的苹果数除以N都余1,取之后的苹果数整除(N-1)*。

这样考虑的话,我们可以从最后一只熊开始向前倒推总的苹果数num,最后一只熊取走了N份苹果中的1份,所以剩下的苹果一定为N-1的倍数,所以num初始值一定为N-1的倍数。

把num初值为 N-1之后,开始倒推,上一只熊取之前的苹果数为num = num + num/(N-1)+1,再判断这个数字能否被N-1整除,若可以,继续向前倒推,若不能,说明num不满足条件,将num初值更新为2(N – 1),重复上述过程,若nun不满足条件,再设置为3(N-1),依次类推,直到循环中的num都能被N-1整除,这时候的num为满足条件的最小值,可能说的不是很清楚,直接看代码

8595f7f7840f

给大家分享一个「Python算法题」分苹果

再仔细分析一下这个题目,如果把每只熊取之前的苹果数记做一个序列

8595f7f7840f

给大家分享一个「Python算法题」分苹果

根据之前的分析,倒数第k次取之前的苹果数是倒数k+1次取之前的苹果扔掉一个再取走一份后剩下的,所以有关系式:

8595f7f7840f

给大家分享一个「Python算法题」分苹果

同时倒数第一只熊取之前的苹果数满足条件:

8595f7f7840f

给大家分享一个「Python算法题」分苹果

这里|表示整除,因为它需要扔掉一个然后分成N份。换种表示方式可以写成

8595f7f7840f

给大家分享一个「Python算法题」分苹果

综合到一起,所有的条件可以描述为

8595f7f7840f

给大家分享一个「Python算法题」分苹果

有没有感觉很熟悉,这不就是高中的数列递推公式?把通项公式求出来就完事了,根据上面的递推式,有

8595f7f7840f

给大家分享一个「Python算法题」分苹果

最后得到

8595f7f7840f

给大家分享一个「Python算法题」分苹果

因为xN必须是整数,所以m取值不能任意,有一定的限制,实际上已经非常明确了,要使得xN是整数,只要让m的取值恰好可以消掉中式子的分母就可以了,最终可以得到

8595f7f7840f

给大家分享一个「Python算法题」分苹果

其中

8595f7f7840f

给大家分享一个「Python算法题」分苹果

这样我们实际上求出了所有满足条件的苹果数量,如果只要最小数量,让t=1就可以啦,最终得到

8595f7f7840f

给大家分享一个「Python算法题」分苹果

这样代码就变得非常非常非常简单。

8595f7f7840f

给大家分享一个「Python算法题」分苹果

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/183461.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 一些蛮好的题目,学习

    一些蛮好的题目,学习

  • PLSQL 使用教程

    PLSQL 使用教程1打开表打开PLSQL点击Objects在下拉列表中选中Myobjects找到Table下级目录中都是数据库的表2查看表的数据选中表,右击点击-查看数据/querydata弹出sql窗口,可以查看数据3查看表结构选中表,右击点击-查看/View…

  • 报文学习四(LLDP协议)「建议收藏」

    报文学习四(LLDP协议)「建议收藏」1.LLDP出现的原因随着网络技术的发展,接入网络的设备的种类越来越多,配置越来越复杂,来自不同设备厂商的设备也往往会增加自己特有的功能,这就导致在一个网络中往往会有很多具有不同特性的、来自不同厂商的设备,为了方便对这样的网络进行管理,就需要使得不同厂商的设备能够在网络中相互发现并交互各自的系统及配置信息。LLDP(LinkLayerDiscoveryProtocol,链路层发现协议)就是用于这个目的的协议。当一个设备从网络中接收到其它设备的这些信息时,它就将…

  • navicat premium 15 J激活码_在线激活[通俗易懂]

    (navicat premium 15 J激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • idea查看激活码-激活码分享[通俗易懂]

    (idea查看激活码)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

发表回复

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

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