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

yipeiwu_com6年前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中定制类的比较运算实例

Python中的比较运算有几种:小于、小于等于、等于、大于等于、大于、不等于等。如果我们的数据对象具有明确的物理含义,比如说数值是带有数字与物理单位的字符串组合,那么进行大小比较的时候就...

深入Python解释器理解Python中的字节码

深入Python解释器理解Python中的字节码

我最近在参与Python字节码相关的工作,想与大家分享一些这方面的经验。更准确的说,我正在参与2.6到2.7版本的CPython解释器字节码的工作。 Python是一门动态语言,在命令行...

Python定义函数功能与用法实例详解

本文实例讲述了Python定义函数功能与用法。分享给大家供大家参考,具体如下: 1.函数的意义 一般数学上的函数是,一个或者几个自变量,通过某种计算方式,得出一个因变量。 y = f(...

Python利用全连接神经网络求解MNIST问题详解

Python利用全连接神经网络求解MNIST问题详解

本文实例讲述了Python利用全连接神经网络求解MNIST问题。分享给大家供大家参考,具体如下: 1、单隐藏层神经网络 人类的神经元在树突接受刺激信息后,经过细胞体处理,判断如果达到阈值...

教你如何编写、保存与运行Python程序的方法

教你如何编写、保存与运行Python程序的方法

第一步 接下来我们将看见如何在 Python 中运行一个传统的“Hello World”程序。Python教程本章将会教你如何编写、保存与运行 Python 程序。 通过 Python...