Python实现的中国剩余定理算法示例,python定理算法示例
Python实现的中国剩余定理算法示例,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 Socket实现简单TCP Server/client功能示例,pythonclient
- Python基于Socket实现的简单聊天程序示例,pythonsocket
- Python实现抓取网页生成Excel文件的方法示例,
- Python实现将Excel转换为json的方法示例,pythonjson
- Python实现读取邮箱中的邮件功能示例【含文本及附件】
- python中 chr unichr ord函数的实例详解,unichrord
- python的多重继承的理解,python继承
- python扫描proxy并获取可用代理ip的实例,pythonproxy
- Python实现读写sqlite3数据库并将统计数据写入Excel的方法
- Python读取sqlite数据库文件的方法分析,
评论关闭