其他
【Python算法题】分苹果
作者：量化小白H
个人公众号：量化小白上分记
今天刷到一道算法题，分享一下
果园里有堆苹果，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为满足条件的最小值，可能说的不是很清楚，直接看代码
def getnum(n):
j = 1
num = n-1
i = 0
while(i < n):
if num%(n-1) != 0:
i =0
j += 1
num = (n-1)*j
else:
i += 1
num += 1 + num/(n-1)
return num
再仔细分析一下这个题目，如果把每只熊取之前的苹果数记做一个序列
根据之前的分析，倒数第k次取之前的苹果数是倒数k+1次取之前的苹果扔掉一个再取走一份后剩下的，所以有关系式：
同时倒数第一只熊取之前的苹果数满足条件：
这里|表示整除，因为它需要扔掉一个然后分成N份。换种表示方式可以写成
综合到一起，所有的条件可以描述为
有没有感觉很熟悉，这不就是高中的数列递推公式？把通项公式求出来就完事了，根据上面的递推式，有
最后得到
因为xN必须是整数，所以m取值不能任意，有一定的限制，实际上已经非常明确了，要使得xN是整数，只要让m的取值恰好可以消掉中式子的分母就可以了，最终可以得到
其中
这样我们实际上求出了所有满足条件的苹果数量，如果只要最小数量，让t=1就可以啦，最终得到
这样代码就变得非常非常非常简单。
def getnum1(n):
return n**n +1-n
Python的爱好者社区历史文章大合集：
关注后在公众号内回复“ 课程 ”即可获取：
小编的转行入职数据科学（数据分析挖掘/机器学习方向）【最新免费】
小编的Python的入门免费视频课程！
小编的Python的快速上手matplotlib可视化库！
崔老师爬虫实战案例免费学习视频。
陈老师数据分析报告扩展制作免费学习视频。
玩转大数据分析！Spark2.X + Python精华实战课程免费学习视频。