Python實(shí)現(xiàn)的中國(guó)剩余定理算法示例
本文實(shí)例講述了Python實(shí)現(xiàn)的中國(guó)剩余定理算法。分享給大家供大家參考，具體如下：
中國(guó)剩余定理（Chinese Remainder Theorem-CRT）:又稱(chēng)孫子定理，是數(shù)論中的一個(gè)定理。即如果一個(gè)人知道了一個(gè)數(shù)n被多個(gè)整數(shù)相除得到的余數(shù)，當(dāng)這些除數(shù)兩兩互質(zhì)的情況下，這個(gè)人就可以唯一的確定被這些個(gè)整數(shù)乘積除n所得的余數(shù)。
維基百科上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.
有一數(shù)n，被2除余1，被3除余2，被5除余4，被6除余5，正好被7整除，求該數(shù)n.
分析：n被2除余1，說(shuō)明概述最小為1，之后該條件一直滿足，所以需要加上的數(shù)一定是2的倍數(shù)。被3除余2，即（1+2*i）%3=2，其中i為正整數(shù)。之后該條件一直滿足，所以需要加上的數(shù)一定是3的倍數(shù)，又因?yàn)榍耙粋€(gè)條件的限制，所以是2和3的最小公倍數(shù)的整數(shù)倍。一次類(lèi)推，知道找到被7整除的數(shù)。
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
最終結(jié)果為119。
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門(mén)與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
python?yaml文件數(shù)據(jù)按原有的數(shù)據(jù)順序dump問(wèn)題小結(jié)
這篇文章主要介紹了python?yaml文件數(shù)據(jù)按原有的數(shù)據(jù)順序dump,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2023-11-11
這篇文章主要介紹了微信公眾號(hào)接入ChatGPT機(jī)器人的方法,不難，總共可以分為兩步，一是在云服務(wù)器上部署自定義消息處理服務(wù)，二是微信公眾號(hào)配置自己的消息處理服務(wù)器，本文給大家講解的非常詳細(xì)，需要的朋友可以參考下2023-02-02
本文記錄一些 Python 日常編程中的小妙招，并使用 IPython 進(jìn)行交互測(cè)試，讓我們更好的了解和學(xué)習(xí) Python 的一些特性，對(duì)大家的學(xué)習(xí)或工作具有一定的價(jià)值，需要的朋友可以參考下2021-09-09
python?tkinter實(shí)現(xiàn)彈窗的輸入輸出
這篇文章主要為大家詳細(xì)介紹了python?tkinter實(shí)現(xiàn)彈窗的輸入輸出，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02
這篇文章主要介紹了Python中的ctime()方法使用教程,是Python入門(mén)學(xué)習(xí)的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-05-05
PyTorch之nn.ReLU與F.ReLU的區(qū)別介紹
這篇文章主要介紹了PyTorch之nn.ReLU與F.ReLU的區(qū)別介紹，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-06-06
Python新版極驗(yàn)驗(yàn)證碼識(shí)別驗(yàn)證碼教程詳解
這篇文章主要介紹了Python新版極驗(yàn)驗(yàn)證碼識(shí)別驗(yàn)證碼，極驗(yàn)驗(yàn)證是一種在計(jì)算機(jī)領(lǐng)域用于區(qū)分自然人和機(jī)器人的，通過(guò)簡(jiǎn)單集成的方式，為開(kāi)發(fā)者提供安全、便捷的云端驗(yàn)證服務(wù)2023-02-02
Python3中FuzzyWuzzy庫(kù)實(shí)例用法
在本篇文章中小編給各位整理了關(guān)于Python3z中FuzzyWuzzy庫(kù)實(shí)例用法及相關(guān)代碼，有興趣的朋友們可以參考下。2020-11-11
python中字典和列表的使用，在數(shù)據(jù)處理中應(yīng)該是最常用的，今天通過(guò)多種場(chǎng)景給大家分享python 字典和列表嵌套用法，感興趣的朋友一起看看吧2021-06-06
這篇文章主要介紹了Python實(shí)現(xiàn)粒子群算法的示例，幫助大家更好的理解和使用Python，感興趣的朋友可以了解下2021-02-02