python分苹果问题_给大家分享一个「Python算法题」分苹果
把num初值为 N-1之后，开始倒推，上一只熊取之前的苹果数为num = num + num/(N-1)+1，再判断这个数字能否被N-1整除，若可以，继续向前倒推，若不能，说明num不满足条件，将num初值更新为2*(N - 1),重复上述过程，若nun不满足条件，再设置为3*(N-1),依次类推，直到循环中的num都能被N-1整除，这时候的num为满足条件的最小值，可能说的不是很清楚，直接看代码
![Image 1][]
再仔细分析一下这个题目，如果把每只熊取之前的苹果数记做一个序列
![Image 1][]
根据之前的分析，倒数第k次取之前的苹果数是倒数k+1次取之前的苹果扔掉一个再取走一份后剩下的，所以有关系式：
![Image 1][]
同时倒数第一只熊取之前的苹果数满足条件：
![Image 1][]
这里|表示整除，因为它需要扔掉一个然后分成N份。换种表示方式可以写成
![Image 1][]
综合到一起，所有的条件可以描述为
![Image 1][]
有没有感觉很熟悉，这不就是高中的数列递推公式？把通项公式求出来就完事了，根据上面的递推式，有
![Image 1][]
最后得到
![Image 1][]
因为xN必须是整数，所以m取值不能任意，有一定的限制，实际上已经非常明确了，要使得xN是整数，只要让m的取值恰好可以消掉中式子的分母就可以了，最终可以得到
![Image 1][]
其中
![Image 1][]
这样我们实际上求出了所有满足条件的苹果数量，如果只要最小数量，让t=1就可以啦，最终得到
![Image 1][]
这样代码就变得非常非常非常简单。
![Image 1][]
[Image 1]:
骑猪看日落
红太狼
àì夳堔傛蜴生んèń
小灰灰
水深无声
小鱼儿
还没有评论，来说两句吧...