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程序设计有所帮助。

赞 (0)

相关推荐

  • python实现八大排序算法（2）

    python实现八大排序算法（2）

    本文接上一篇博客python实现的八大排序算法part1,将继续使用python实现八大排序算法中的剩余四个:快速排序.堆排序.归并排序.基数排序 5.快速排序 快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的. 算法思想: 已知一组无序数据a[1].a[2].--a[n],需将其按升序排列.首先任取数据a[x]作为基准.比较a[x]与其它数据并排序,使a[x]排在数据的第k位,并且使a[1]~a[k-1]中的每一个数据<a[x],a[k+1]~a[n]中的每一个数

  • Python计算斗牛游戏概率算法实例分析

    本文实例讲述了Python计算斗牛游戏概率算法.分享给大家供大家参考,具体如下: 过年回家,都会约上亲朋好友聚聚会,会上经常会打麻将,斗地主,斗牛.在这些游戏中,斗牛是最受欢迎的,因为可以很多人一起玩,而且没有技术含量,都是看运气(专业术语是概率). 斗牛的玩法是: 1. 把牌中的JQK都拿出来 2. 每个人发5张牌 3. 如果5张牌中任意三张加在一起是10的 倍数,就是有牛.剩下两张牌的和的10的余数就是牛数. 牌的大小: 4条 > 3条 > 牛十 > 牛九 > -- >

  • python编程羊车门问题代码示例

    问题: 有3扇关闭的门,一扇门后面停着汽车,其余门后是山羊,只有主持人知道每扇门后面是什么.参赛者可以选择一扇门,在开启它之前,主持人会开启另外一扇门,露出门后的山羊,然后允许参赛者更换自己的选择. 请问: 1.按照你的第一感觉回答,你觉得不换选择能有更高的几率获得汽车,还是换选择能有更高的几率获得汽车?或几率没有发生变化? 答:第一感觉换与不换获奖几率没有发生变化. 2.请自己认真分析一下"不换选择能有更高的几率获得汽车,还是换选择能有更高的几率获得汽车?或几率没有发生变化?" 写出

  • Python基于分水岭算法解决走迷宫游戏示例

    本文实例讲述了Python基于分水岭算法解决走迷宫游戏.分享给大家供大家参考,具体如下: #Solving maze with morphological transformation """ usage:Solving maze with morphological transformation needed module:cv2/numpy/sys ref: 1.http://www.mazegenerator.net/ 2.http://blog.leanote.com

  • 用Python实现随机森林算法的示例

    拥有高方差使得决策树(secision tress)在处理特定训练数据集时其结果显得相对脆弱.bagging(bootstrap aggregating 的缩写)算法从训练数据的样本中建立复合模型,可以有效降低决策树的方差,但树与树之间有高度关联(并不是理想的树的状态). 随机森林算法(Random forest algorithm)是对 bagging 算法的扩展.除了仍然根据从训练数据样本建立复合模型之外,随机森林对用做构建树(tree)的数据特征做了一定限制,使得生成的决策树之间没有关联,

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

    本文实例讲述了Python实现的中国剩余定理算法.分享给大家供大家参考,具体如下: 中国剩余定理(Chinese Remainder Theorem-CRT):又称孙子定理,是数论中的一个定理.即如果一个人知道了一个数n被多个整数相除得到的余数,当这些除数两两互质的情况下,这个人就可以唯一的确定被这些个整数乘积除n所得的余数. 维基百科上wiki:The Chinese remainder theorem is a theorem of number theory, which states t

  • python实现简单中文词频统计示例

    python实现简单中文词频统计示例

    本文介绍了python实现简单中文词频统计示例,分享给大家,具体如下: 任务 简单统计一个小说中哪些个汉字出现的频率最高 知识点 1.文件操作 2.字典 3.排序 4.lambda 代码 import codecs import matplotlib.pyplot as plt from pylab import mpl mpl.rcParams['font.sans-serif'] = ['FangSong'] # 指定默认字体 mpl.rcParams['axes.unicode_minus

  • python opencv肤色检测的实现示例

    python opencv肤色检测的实现示例

    1 椭圆肤色检测模型 原理:将RGB图像转换到YCRCB空间,肤色像素点会聚集到一个椭圆区域.先定义一个椭圆模型,然后将每个RGB像素点转换到YCRCB空间比对是否再椭圆区域,是的话判断为皮肤. YCRCB颜色空间 椭圆模型 代码 def ellipse_detect(image): """ :param image: 图片路径 :return: None """ img = cv2.imread(image,cv2.IMREAD_COLOR)

  • python 窃取摄像头照片的实现示例

    python 窃取摄像头照片的实现示例

    python窃取摄像头照片源码+获取授权码方法+py打包成exe 教你用python做一个属于自己的窃取摄像头照片的软件. 需要安装python3.5以上版本,在官网下载即可. 然后安装库opencv-python,安装方式为打开终端输入命令行. 可以在使用pip的时候加参数-i https://pypi.tuna.tsinghua.edu.cn/simple,这样就会从清华这边的镜像去安装需要的库,会快很多. pip install opencv-python -i https://pypi.

  • Python实现七大查找算法的示例代码

    Python实现七大查找算法的示例代码

    查找算法 -- 简介 查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素.     查找表(Search Table):由同一类型的数据元素构成的集合     关键字(Key):数据元素中某个数据项的值,又称为键值     主键(Primary Key):可唯一的标识某个数据元素或记录的关键字 查找表按照操作方式可分为:         1.静态查找表(Static Search Table):只做查找操作的查找表.它的主要操作是:         ①

  • Python基本运算几何运算处理数字图像示例

    Python基本运算几何运算处理数字图像示例

    目录 平移 镜像 水平镜像 垂直镜像 旋转 以图像左上角为旋转中心 以图像中心为旋转中心 缩放 插值算法 最近邻插值算法 双线性插值算法 三次内插法 改变图像中物体对象(像素)之间的空间关系. 平移 # 定义平移矩阵,需要是numpy的float32类型# x轴平移50,y轴平移80, 2*3矩阵 M = np.array([[1, 0, 50], [0, 1, 80]], dtype=np.float32) # 用仿射变换实现平移 new_image = cv2.warpAffine(imag

  • Python图像分割之均匀性度量法分析

    Python图像分割之均匀性度量法分析

    均匀性度量图像分割是图像像素分割的一种方法,当然还有其他很多的方法.这里简单的介绍下其原理和实现代码[有源码] 其流程大概分为一下几步 1.确定一个阈值 2.计算阈值两边的像素个数.占比.以及方差 3.将两边的方差和占比想乘再相加 4.循环1~3的步骤 下面以这个例子为示例做一个演示 计算公式: 阈值为: 1 阈值左边值为: [1, 1, 0, 0, 0] 均值: 0.08 阈值右边值为: [3, 9, 9, 8, 2, 3, 7, 3, 3, 6, 6, 4, 6, 8, 2, 5, 2, 9

  • Python实现炸金花游戏的示例代码

    今天的第二个作品,哈哈哈哈,搞起来感觉还挺有意思的,不过代码里纸牌J,Q,K,A几个数字被我替换成了11,12,13,14......主要是没有想到简单的办法让其比较,索性都用数字了,我太菜了,希望有大佬指点一下. 代码如下: import random   #导入随机数函数 def puke():     """     生成一副52张的扑克牌(除去大小王)     :return:     """     list1 = ['黑桃', '红桃

  • Python实现识别花卉种类的示例代码

    Python实现识别花卉种类的示例代码

    目录 百度图像识别 读取照片文件 整理分类照片 大家好,我是小五 “无穷小亮的科普日常”经常会发布一些鉴定网络热门生物视频,既科普了生物知识,又满足观众们的猎奇心理.今天我们也来鉴定一下网络热门植物!最近春天很多花都开了,我正好趁着清明假期到户外踏青并拍摄了不少花卉的照片. 由于对很多花不是特别熟悉,所以我们需要借助软件来识别究竟是什么花的种类.市面上的识花软件有很多,比如花伴侣.形色.百度等等,我测试后发现百度的识别效果最为优秀.于是我就有了一个想法,能不能批量调用百度的接口,对花卉照片进行识

  • Python实现解析ini配置文件的示例详解

    Python实现解析ini配置文件的示例详解

    目录 楔子 ini 文件 特殊格式 小结 楔子 在开发过程中,配置文件是少不了的,只不过我们有时会将 py 文件作为配置文件(config.py),然后在其它的模块中直接导入.这样做是一个好主意,不过配置文件是有专门的格式的,比如:ini, yaml, toml 等等. 而对于 Python 而言,也都有相应的库来解析相应格式的文件,下面我们来看看 ini 文件要如何解析. ini 文件 先来了解一下 ini 文件的格式: [satori] name = 古明地觉 age = 16 where 

随机推荐