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

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

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

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

先简单分析一下这道题目,假设当第k个熊取完之后还有M个苹果,按照题目的意思,M除以N的余数恰好是1,那么第k+1只熊可以拿到(M-1)/N个苹果,第k只熊取之前有M*N/(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为满足条件的最小值,可能说的不是很清楚,直接看代码

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

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

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

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

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

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

最后得到

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

其中

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

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181227A1J2DB00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券