Python实现的中国剩余定理算法示例

yipeiwu_com7年前Python基础

本文实例讲述了Python实现的中国剩余定理算法。分享给大家供大家参考,具体如下:

中国剩余定理(Chinese Remainder Theorem-CRT):又称孙子定理,是数论中的一个定理。即如果一个人知道了一个数n被多个整数相除得到的余数,当这些除数两两互质的情况下,这个人就可以唯一的确定被这些个整数乘积除n所得的余数。

维基百科上wiki:The Chinese remainder theorem is a theorem of number theory, which states that, if one knows the remainders of the division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

有一数n,被2除余1,被3除余2,被5除余4,被6除余5,正好被7整除,求该数n.

分析:n被2除余1,说明概述最小为1,之后该条件一直满足,所以需要加上的数一定是2的倍数。被3除余2,即(1+2*i)%3=2,其中i为正整数。之后该条件一直满足,所以需要加上的数一定是3的倍数,又因为前一个条件的限制,所以是2和3的最小公倍数的整数倍。一次类推,知道找到被7整除的数。

n=1
while(n%3 != 2):
  n += 2
while(n%5 != 4):
  n += 6
while(n%6 != 5):
  n += 30
while(n%7 != 0):
  n += 30

最终结果为119。

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

相关文章

Python os模块介绍

os.getcwd() 获取当前工作目录,即当前python脚本工作的目录路径 os.chdir("dirname") 改变当前脚本工作目录;相当于shell下cd os.cur...

给大家整理了19个pythonic的编程习惯(小结)

Python最大的优点之一就是语法简洁,好的代码就像伪代码一样,干净、整洁、一目了然。 要写出 Pythonic(优雅的、地道的、整洁的)代码,需要多看多学大牛们写的代码,github...

python使用BeautifulSoup分页网页中超链接的方法

本文实例讲述了python使用BeautifulSoup分页网页中超链接的方法。分享给大家供大家参考。具体如下: python通过BeautifulSoup分页网页中的超级链接,这段py...

Python绘制正余弦函数图像的方法

Python绘制正余弦函数图像的方法

今天打算通过绘制正弦和余弦函数,从默认的设置开始,一步一步地调整改进,让它变得好看,变成我们初高中学习过的图象那样。通过这个过程来学习如何进行对图表的一些元素的进行调整。 01. 简单绘...

Python实现pdf文档转txt的方法示例

本文实例讲述了Python实现pdf文档转txt的方法。分享给大家供大家参考,具体如下: 首先,这是一个比较粗糙的版本,因为已经够用了,而且对pdf的格式不熟悉,所以暂时没有进一步优化。...