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)


相关推荐

  • 字符0的ascii码值是多少_码值是什么

    字符0的ascii码值是多少_码值是什么\0的ASCII码值是多少

  • java二维数组随机赋值_java 二维数组随机赋值

    java二维数组随机赋值_java 二维数组随机赋值java二维数组随机赋值[2021-01-3100:08:55]简介:目的:使用二维数组打印一个10行杨辉三角。(视频教程推荐:java课程)思路:1.第一行有1个元素,第n行有n个元素;2.每一行的第一个元素和最后一个元素都是1;3.从第三行开始php修改二维数组中值的方法:1、通过【for($i=0;$i<count(Array());++…

  • ArrayList底层实现原理「建议收藏」

    ArrayList底层实现原理「建议收藏」ArrayList简介ArrayList是我们开发中非常常用的数据存储容器之一,其底层是数组实现的,我们可以在集合中存储任意类型的数据,ArrayList是线程不安全的,非常适合用于对元素进行查找,效率非常高。源码分析创建了一个大小为0的数组,在后面会用到。声明了一个数组。ArrayList的无参构造方法,将前面声明创建的大小为0的数组赋给elementData数组。这是ArrayList的有参构造方法,传入一个int类型的变量,相当于我们在使用arrayList的时候指定list的大小

  • 手机修改ntp服务器地址,修改手机ntp服务器ip地址[通俗易懂]

    手机修改ntp服务器地址,修改手机ntp服务器ip地址[通俗易懂]修改手机ntp服务器ip地址内容精选换一换本文介绍使用云手机服务时需要了解的基本概念。云手机是一台包含原生安卓操作系统,具有虚拟手机功能的云服务器,简单来说,云手机=云服务器+AndroidOS。您可以远程实时控制云手机,实现安卓APP的云端运行;也可以基于云手机的基础算力,高效搭建应用,如云游戏、移动办公、直播互娱等场景。服务器是用来提供云手机的物理服务器。云手机目前以服务器您可以直接修改虚…

  • Python爬虫系列:爬取小说并写入txt文件

    Python爬虫系列:爬取小说并写入txt文件Python爬虫系列——爬取小说并写入txt文件文章介绍了如何从网站中爬取小说并写入txt文件中,实现了单章节写取,整本写取,多线程多本写取。爬虫使用的python版本为python3,有些系统使用python指令运行本脚本,可能出现错误,此时可以试一试使用python3运行本脚本。本文是一个教程,一步步介绍了如何爬取批量小说内容以及存储这是txt文件中,以下是项目源码地址。

  • 集成学习-stacking算法

    众所周知,集成学习算法,它将多个弱分类器集成起来,以达到较高的分类准确率。常见的集成学习方法:boosting bagging stacking今天主要讲stacking.Stacking的基本思想将个体学习器结合在一起的时候使用的方法叫做结合策略。对于分类问题,我们可以使用投票法来选择输出最多的类。对于回归问题,我们可以将分类器输出的结果求平均值。…

发表回复

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

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