一个余数问题的思考

2024-05-29 02:08
文章标签 问题 思考 余数

本文主要是介绍一个余数问题的思考,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

刚刚在贴吧上看到一个很简单的算法小问题,顺便看到了很多人不同的思路。我觉得很有意思,所以也来研究一下。

问题如下:

一筐鸡蛋:
1个1个拿,正好拿完。
2个2个拿,还剩1个。
3个3个拿,正好拿完。
4个4个拿,还剩1个。
5个5个拿,还差1个。
6个6个拿,还剩3个。
7个7个拿,正好拿完。
8个8个拿,还剩1个。
9个9个拿,正好拿完。
问:筐里最少有几个鸡蛋?

题目很简单,我们可以直接用暴力穷举法。这当然是最简单的办法, 下面是这种方法的Kotlin代码。运行之后,得到结果为1449。

fun answer1() {var n = 0while (true) {if (n % 2 == 1 && n % 4 == 1 && n % 5 == 4 && n % 6 == 3 && n % 7 == 0 && n % 8 == 1 && n % 9 == 0) {break}n++}println(n)
}

当然暴力穷举虽然简单,但是效率并不是很高,对于这个问题来说,循环运行了1449次。我们可以分析题目特点,简化循环的运行次数。

首先来看看题目,很明显第一句是废话,因为任何正整数都可以被1整除。然后是第二句,这表明这个数是一个奇数。第三句和第九句明显重复,可以被9整除,那么必然也可以被3整除,所以只看第九句就可以了。还有第五句需要注意一下,因为这里是被5除还差1个,所以是还剩4个。我看贴吧里有些人审题不严,导致做了一个错误答案。

经过一番分析,上面的题目就变成了下面这样的。

奇数
能被9整除
除以4余1
除以5余4
除以6余3
能被7整除
除以8余1

注意到7和9互质,所以答案必然是63的倍数,而且还是个奇数,所以是奇数倍。所以我们的代码可以改进一下。代码中的count用于统计循环次数,这次结果和上次一样,但是循环次数仅为12次,每次要判断的条件也减少了很多。

fun answer2() {var n = 63var count = 0while (true) {count++if (n % 4 == 1 && n % 5 == 4 && n % 6 == 3 && n % 8 == 1) {break}n += 63 * 2}println("n=$n,count=$count")}

当然还可以进一步优化。由于这个数除以5余4,可以想到该数的个位数字不是4就是9,但是由于是奇数,那么个位数必然是9,而且这个数是63的倍数。而除以4余1除以8余1这两个条件可以简化为除以8余1。所以最后代码就变成了这样,循环仅仅循环了3次。

fun answer3() {var n = 63 * 3var count = 0while (true) {count++if (n % 8 == 1) {break}n += 630}println("n=$n,count=$count")
}

我还看到贴吧上有人说用同余定理算,但是我比较笨,没理解怎么用同余定理来计算。不过以前我倒是遇到过类似的题目,所以最后来介绍一下。

我遇到的题目类似下面这样:

一个数除以2余1,除以3余2,除以4余3,这个数最小是几?

这个问题倒是有一个简便方法,由于余数恰好和除数只差1,所以如果在被除数上加1,那么它就可以同时被2、3、4整除,所以这个数最小应该是2、3、4的最小公倍数再减1,所以应该是23 。

回到我们这道题目来说,由于余数每次都不一样,所以没办法这么做。不过我想了想,能不能通过加一个数,让余数都变得相同。由于我数学不好,也不懂数论这些专业知识,所以直接用代码模拟一下,发现确实可以得到一个数,让答案加上这个数以后,所有余数都相同。这个数是1071,这时候余数都是0 。Kotlin代码如下。

fun cal() {val numbers = hashMapOf(2 to 1,3 to 0,4 to 1,5 to 4,6 to 3,7 to 0,8 to 1,9 to 0)var n = 0while (true) {n++for (k in numbers.keys) {val old = numbers[k]numbers[k] = (old!! + 1) % k}val set = numbers.values.toSet()if (set.size == 1) {break}}println("这个数是:$n")
}

有了这个数,我们就可以用上面的方法来计算结果了。答案加上1071之后,可以被2-9的所有数整除,所以2-9的最小公倍数再减去1071,就是我们要求的答案。而2-9的最小公倍数也就是5-9的最小公倍数,是2520,再减去前面的1071,正好就是最一开始我们得到的答案1449!

如果大家有更好的思路,也可以告诉我,让我们互相学习,共同进步!

这篇关于一个余数问题的思考的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1012339

相关文章

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

Springboot如何正确使用AOP问题

《Springboot如何正确使用AOP问题》:本文主要介绍Springboot如何正确使用AOP问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录​一、AOP概念二、切点表达式​execution表达式案例三、AOP通知四、springboot中使用AOP导出

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题

《解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题》:本文主要介绍解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4... 目录未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘打开pom.XM

IDEA Maven提示:未解析的依赖项的问题及解决

《IDEAMaven提示:未解析的依赖项的问题及解决》:本文主要介绍IDEAMaven提示:未解析的依赖项的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录IDEA Maven提示:未解析的依编程赖项例如总结IDEA Maven提示:未解析的依赖项例如

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题?(与哨兵模

SpringBoot+Redis防止接口重复提交问题

《SpringBoot+Redis防止接口重复提交问题》:本文主要介绍SpringBoot+Redis防止接口重复提交问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录前言实现思路代码示例测试总结前言在项目的使用使用过程中,经常会出现某些操作在短时间内频繁提交。例