未加星标

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

字体大小 | |
[开发(python) 所属分类 开发(python) | 发布者 店小二04 | 时间 | 作者 红领巾 ] 0人收藏点击收藏

本文实例讲述了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)相关术语:python基础教程 python多线程 web开发工程师 软件开发工程师 软件开发流程

tags: Python,除余,定理,整数,theorem,remainder,division,integers,Chinese,算法
分页:12
转载请注明
本文标题:Python实现的中国剩余定理算法示例
本站链接:http://www.codesec.net/view/561010.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 开发(python) | 评论(0) | 阅读(56)