大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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为满足条件的最小值,可能说的不是很清楚,直接看代码
给大家分享一个「Python算法题」分苹果
再仔细分析一下这个题目,如果把每只熊取之前的苹果数记做一个序列
给大家分享一个「Python算法题」分苹果
根据之前的分析,倒数第k次取之前的苹果数是倒数k+1次取之前的苹果扔掉一个再取走一份后剩下的,所以有关系式:
给大家分享一个「Python算法题」分苹果
同时倒数第一只熊取之前的苹果数满足条件:
给大家分享一个「Python算法题」分苹果
这里|表示整除,因为它需要扔掉一个然后分成N份。换种表示方式可以写成
给大家分享一个「Python算法题」分苹果
综合到一起,所有的条件可以描述为
给大家分享一个「Python算法题」分苹果
有没有感觉很熟悉,这不就是高中的数列递推公式?把通项公式求出来就完事了,根据上面的递推式,有
给大家分享一个「Python算法题」分苹果
最后得到
给大家分享一个「Python算法题」分苹果
因为xN必须是整数,所以m取值不能任意,有一定的限制,实际上已经非常明确了,要使得xN是整数,只要让m的取值恰好可以消掉中式子的分母就可以了,最终可以得到
给大家分享一个「Python算法题」分苹果
其中
给大家分享一个「Python算法题」分苹果
这样我们实际上求出了所有满足条件的苹果数量,如果只要最小数量,让t=1就可以啦,最终得到
给大家分享一个「Python算法题」分苹果
这样代码就变得非常非常非常简单。
给大家分享一个「Python算法题」分苹果
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/183461.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...