孫子演算法例題

1. 孫子演算法

我們首先需要先求出三個數：
第一個數能同時被3和5整除，但除以7餘1，即15；
第二個數能同時被3和7整除，但除以5餘1，即21；
第三個數能同時被5和7整除，但除以3餘1，即70；
然後將這三個數分別乘以被7、5、3除的余數再相加，即：15×2+21×3+70×2=233．
最後，再減去3、5、7最小公倍數的整數倍，可得：233-105×2=23．或105k+23（k為正整數）．
由於物數量在100至200之間，故當k=1時，105+23=128
故答案為：128

2. 寫5條關於《孫子算經》中的題目及答案

《孫子算經》里的孫子問題
在我國古代數學名著《孫子算經》的下卷中，記載有這樣一個問題：「今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何?」(答曰：二十三)這就是聞名於世的「孫子問題」。《孫子算經》中給出了它的一般解法：「術日：三三數之剩二，置一百四十；五五數之剩三，置六十三；七七數之剩二，置三十；並之，得二百三十三，以二百一十減之即得。凡三三數之剩一，則置七十；五五數之剩一，則置二十一；七七數之剩一，則置十五。一百六以上，以一百五減之，即得。」明朝數學家程大位在所著《演算法統宗》中把這一解法概括為四句歌訣：「三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，除百零五便得知。」具體到本題的結果，由70×2+21×3+15×2—2×105=23得所求物為23個，一般地說，所求物個數是23+105n(n=0，1，2，3……)。它的解答要用到不定方程的知識或同餘的知識。
《孫子算經》對於「孫子問題」的解答暗示了一般途徑，由它作出的理論概括，被西方譽為「中國剩餘定理」。孫子問題的演算法還有其他一些名稱，如「鬼谷算」、「隔牆算」、「秦王暗點兵」和「韓信點兵」等。其中「韓信點兵」也指這樣的問題：有兵一隊，若列成五行縱隊，則末行一人；成六行縱隊，則末行五人；成七行縱隊，則末行四人；成十一行縱隊，則末行十人，求兵數。下面給出它的一個算術解法：(1)在6、7、11的公倍數中找一個被5除餘1的數，如3×462；(2)在5、7、11的公倍數中找一個被6除餘5的數，如5×385；(3)在5、6、11公倍數中找一個被7除餘4的數，如4~330；(4)在5、6、7的公倍數中找一個被ll除餘1O的數，如10×210；(5)3×462+5×385+4×330+lO×210=6731，則6731是滿足條件的一個數，它比5、6、7、11的最小公倍數2310大，若求滿足條件的最小正數，則應從6731中減去2310的兩倍，得211l，由此所求兵數的一般結果是2111+2310 n(n=0，1，2，……)。這種算術解法也適用於「孫子問題」。
《孫子算經》中的中國剩餘定理
最早提出並記敘這個數學問題的，是南北朝時期的數學《孫子算經》著作中的「物不知數」題目。這道「物不知數」的題目是這樣的：
「今有一些物不知其數量。如果三個三個地去數它，則最後還剩二個；如果五個五個地去數它，則最後還剩三個；如果七個七個地去數它，則最後也剩二個。問：這些物一共有多少？」用簡練的數學語言來表述就是：求這樣一個數，使它被3除餘2，被5除餘3，被7除餘2。
《孫子算經》給出了這道題目的解法和答案，用算式表示即為：
70×2＋21×3＋15×2－105×2＝23
後來的數學家把這種解法編成了如下的一首詩歌以便於記誦：
「三人同行七十（70）稀，
五樹梅花二一（21）枝。
七子團圓正半月（15），
除百零五（105）便得知。
為什麼被3除的余數要乘70，而被5除的余數乘21，被7除的余數乘15呢？仔細研究不難發現：
5×7×2≡1（mod3），3×7≡1（mod5），3×5≡1（mod7），
這就是中國南宋數學家秦九韶在他的《數書九章》中提出的「大衍求一術」的理論，通俗地說，就是求「一個數的多少倍除以另一個數，所得的余數為一」。該理論在西方數學史著作中正式被稱為「中國剩餘定理」。
如何運用中國剩餘定理解題呢？
例1 除以3餘1，除以5餘2，除以7餘4的最小三位數是多少？
這類題目可以直接運用上述的詩歌內容來解答，即用被3除的余數去乘70，用被5除的余數去乘21，用被7除的余數去乘15，再根據要求找出最小的三位數：
1×70＋2×21＋4×15＝70＋42＋60＝172
由於172減去105的差為67，是兩位數，所以最小的三位數是172。
例2 一個數除以5餘3，除以7餘4，除以9餘5，這個數最少是多少？
此題由於出現「除以9餘5」，因此，如果照搬上述的方法顯然是行不通的，但仍可以運用上述的思維方式進行解答。
7×9≡3（mod5），余數同題中所要求的「一個數除以5餘3」相同。
5×9≡3（mod7），而題中要求「一個數除以7餘4」，因此，只有將5×9的積擴大一定倍數，讓其積被7除餘4才可，即：5×9×6≡270≡4（mod7）。
同理，5×7≡8（mod9），只有5×7×4≡140≡5（mod9）。
因此，這個數的解法為：
7×9＋5×9×6＋5×7×4－5×7×9
=63＋270＋140－315
=473－315
=158
所以，這個數最少是158。
在這題的解法中，有一個值得探討的問題是：在5×9≡3（mod7），余數與題中要求的「一個數除以7餘4」不符時，為什麼一定要將5×9的積擴大6倍，使其積被7除餘4呢？這是因為這樣的數就滿足了能被5和9整除，同時被7除餘4的要求，即5×9×6≡4（mod7）≡0（mod5）≡0（mod9）。同理，7×9≡3（mod5）≡0（mod7）≡0（mod9），5×7×4≡5（mod9）≡0（mod5）≡0（mod7）。所以，（5×9×6＋7×9＋5×7×4）≡473≡4（mod7）≡3（mod5）≡5（mod9）。
孫子算經
〈四庫全書．孫子算經．提要〉：
臣等謹案〈隋．經籍志〉有《孫子算經》二卷，不著其名，亦不著其時代，〈唐．藝文志〉稱李淳風注甄鸞《孫子算經》三卷於孫子上冠以甄鸞，蓋如淳風之注《周髀算經》因鸞所注，更加辨論也。《隋書》審度引《孫子算術》：「蠶所生吐絲為忽，十忽為秒，十秒為毫，十毫為氂，十氂為分。」本書乃作：「十忽為一絲，十絲為一毫。」又論嘉量，引《孫子算術》：「六粟為圭，十圭為抄，十抄為撮，十撮為勺，十勺為合。」本書乃作：「十圭為一撮，十撮為一抄，十抄為一勺。」考之《夏侯陽算經》引田曹、倉曹亦如本書，而《隋書》中所引與史傳往往多合，蓋古書傳本不一，校訂之儒各有據證，無妨參
差互見也。唐之選舉，算學凡十書，《孫子》《五曹》共限一歲習肄，於後來諸算術中，特為近古，第不知孫子何許人，《朱彝尊集》〈五曹算經．跋〉：「相傳其法出於孫武，然孫子別有算經，考古者存其說可爾。」又有〈孫子算經．跋〉雲：「首言度量，所起合乎兵法：『地生度，度生量，量生數』之文，次言乘除之法，設為之數，十三篇中所雲：
『廓地分利、委積、遠輸貴賣、兵役、分數』比之《九章》〈方田〉、〈粟米〉、〈差分〉、〈商功〉、〈均輸〉、〈盈不足〉之目，往往相符，而要在『得算多，多算勝』以是知此編非偽托也。」彝尊之意，蓋以為確出於孫武。今考書內設問有雲：「長安、洛陽相去九百里」又雲：「佛書二十九章，章六十三字。」則後漢明帝以後人語。孫武，春秋末人，安有是語乎！舊本久佚，今從《永樂大典》所載□集編次，仍為三卷，冠以〈原序〉，其甄、李二家之注，則不可復考，是則姚廣孝等割裂刊削之過矣。乾隆四十三年七月，恭校上。
總纂官：臣紀昀、臣陸錫熊、臣孫士毅。
總校官：臣陸費墀。
〈原序〉
孫子曰：夫算者：天地之經緯，群生之元首，五常之本末，陰陽之父母，星辰之建號，三光之表裡，五行之准平，四時之終始，萬物之祖宗，六藝之綱紀。稽群倫之聚散，考二氣之降升，推寒暑之迭運，步遠近之殊同，觀天道精微之兆基，察地理從橫之長短，采神祇之所在，極成敗之符驗。窮道德之理，究性命之情。立規矩，准方圓，謹法度，約尺丈，立權衡，平重輕，剖毫釐，析泰絫。歷億載而不朽，施八極而無疆。散之者，富有餘；背之者，貧且寠。心開者，幼沖而即悟；意閉者，皓首而難精。夫欲學之者，必務量能揆己，志在所專，如是，則焉有不成者哉！
〈卷上〉
度之所起，起於忽。欲知其忽，蠶吐絲為忽，十忽為一絲，十絲為一毫，十毫為一氂，十氂為一分，十分為一寸，十寸為一尺，十尺為一丈，十丈為一引，五十引為一端，四十尺為一匹，六尺為一步，二百四十步為一畝，三百步為一里。
稱之所起，起於黍。十黍為一絫，十絫為一銖，二十四銖為一兩，十六兩為一斤，三十斤為一鈞，四鈞為一石。
量之所起，起於粟。六粟為一圭，十圭為一撮，十撮為一抄，十抄為一勺，十勺為一合，十合為一升，十升為一斗，十斗為一斛，十斛得六千萬粟。所以得知者，六粟為一圭，十圭六十粟為一撮，十撮六百粟為一抄，十抄六千粟為一勺，十勺六萬粟為一合，十合六十萬粟為一升，十升六百萬粟為一斗，十斗六千萬粟為一斛，十斛六億粟百，斛六兆粟，千斛六京粟，萬斛六陔粟，十萬斛六秭粟，百萬斛六穰粟，千萬斛六溝粟，萬萬斛為一億六澗粟，十億斛六正粟，百億斛六載粟。
凡大數之法：萬萬曰億，萬萬億曰兆，萬萬兆曰京，萬萬京曰陔，萬萬陔曰秭，萬萬秭曰穰，萬萬穰曰溝，萬萬溝曰澗，萬萬澗曰正，萬萬正曰載。
周三，徑一，方五，邪七。見邪求方，五之，七而一；見方求邪，七之，五而一。
白銀方寸重一十四兩。
玉方寸重一十兩。
銅方寸重七兩半。
鉛方寸重九兩半。
鐵方寸重七兩。
石方寸重三兩。
凡算之法：先識其位，一從十橫，百立千僵，千十相望，萬百相當。（案：萬百原本訛作百萬，今據《夏侯陽算經》改正。）
凡乘之法：重置其位，上下相觀，頭位有十步，至十有百步，至百有千步，至千以上命下所得之數列於中。言十即過，不滿，自如頭位。乘訖者，先去之下位；乘訖者，則俱退之。六不積，五不只。上下相乘，至盡則已。
凡除之法：與乘正異乘得在中央，除得在上方，假令六為法，百為實，以六除百，當進之二等，令在正百下。以六除一，則法多而實少，不可除，故當退就十位，以法除實，言一六而折百為四十，故可除。若實多法少，自當百之，不當復退，故或步法十者，置於十百位（頭位有空絕者，法退二位。）余法皆如乘時，實有餘者，以法命之，以法為母，實余為子。
以粟求糲米，三之，五而一。
以糲米求粟，五之，三而一。
以糲米求飯，五之，二而一。
以粟米求糲飯，六之，四而一。
以糲飯求糲米，二之，五而一。
以□米求飯，八之，四而一。
十分減一者，以二乘二十除；減二者，以四乘二十除；減三者，以六乘二十除；減四者，以八乘二十除；減五者，以十乘二十除；減六者，以十二乘二十除；減七者，以十四乘二十除；減八者，以十六乘二十除；減九者，以十八乘二十除。
九分減一者，以二乘十八除。
八分減一者，以二乘十六除。
七分減一者，以二乘十四除。
六分減一者，以二乘十二除。
五分減一者，以二乘十除。
九九八十一，自相乘得幾何？答曰：六千五百六十一。
術曰：重置其位，以上八呼下八，八八六十四即下，六千四百於中位；以上八呼下一，一八如八，即於中位下八十，退下位一等，收上頭位八十（案：原本脫「上」字，今補。）以上位一（案：上位原本訛作「頭位」，今改正。）呼下八，一八如八，即於中位，下八十；以上一呼下一，一一如一，即於中位下一，上下位俱收中位，即得六千五百六十一。
六千五百六十一，九人分之。問：人得幾何？答曰：七百二十九。
術曰：先置六千五百六十一於中位，為實，下列九人為法，頭位置七百（案：原本脫上字，今補。），以上七呼下九，七九六十三，即除中位六千三百，退下位一等，即上位，置二十（案：上位原本訛作頭位，今改正。），以上二呼下九，二九一十八，即除中位一百八十，又更退下位一等，即上位，更置九（案：上位原本亦訛作頭位，今改正。），即以上九呼下九，九九八十一，即除中位八十一，中位並盡，收下位，頭位所得即人之所得，自八八六十四至一一如一，並准此。
八九七十二，自相乘，得五千一百八十四，八人分之，人得六百四十八。
七九六十三，自相乘，得三千九百六十九，七人分之，人得五百六十七。
六九五十四，自相乘，得二千九百一十六，六人分之，人得四百八十六。
五九四十五，自相乘，得二千二十五，五人分之，人得四百五。
四九三十六，自相乘，得一千二百九十六，四人分之，人得三百二十四。
三九二十七，自相乘，得七百二十九，三人分之，人得二百四十三。
二九一十八，自相乘，得三百二十四，二人分之，人得一百六十二。
一九如九，自相乘，得八十一，一人得八十一。
右九九一條，得四百五，自相乘，得一十六萬四千二十五，九人分之，人得八千二百二十五。
八八六十四，自相乘，得四千九十六，八人分之，人得五百一十二。
七八五十六，自相乘，得三千一百三十六，七人分之，人得四百四十八。
六八四十八，自相乘，得二千三百四，六人分之，人得三百八十四。
五八四十，自相乘，得一千六百，五人分之，人得三百二十。
四八三十二，自相乘，得一千二十四，四人分之，人得二百五十六。
三八二十四，自相乘，得五百七十六，三人分之，人得一百九十二。
二八十六，自相乘，得二百五十六，二人分之，人得一百二十八。
一八如八，自相乘，得六十四，一人得六十四。
右八八一條，得二百八十八，自相乘，得八萬二千九百四十四，八人分之，人得一萬三百六十八。
七七四十九，自相乘，得二千四百一，七人分之，人得三百四十三。
六七四十二，自相乘，得一千七百六十四，六人分之，人得二百九十四。
五七三十五，自相乘，得一千二百二十五，五人分之，人得二百四十五。
四七二十八，自相乘，得七百八十四，四人分之，人得一百九十六。
三七二十一，自相乘，得四百四十一，三人分之，人得一百四十七。
二七一十四，自相乘，得一百九十六，二人分之，人得九十八。
一七如七，自相乘，得四十九，一人得四十九。
右七七一條，得一百九十六，自相乘，得三萬八千四百一十六，七人分之，人得五千四百八十八。
六六三十六，自相乘，得一千二百九十六，六人分之，人得二百一十六。
五六三十，自相乘，得九百，五人分之，人得一百八十。
四六二十四，自相乘，得五百七十六，四人分之，人得一百四十四。
三六一十八，自相乘，得三百二十四，三人分之，人得一百八。
二六一十二，自相乘，得一百四十四，二人分之，人得七十二。
一六如六，自相乘，得三十六，一人得三十六。
右六六一條，得一百二十六，自相乘，得一萬五千八百七十六，六人分之，人得二千六百四十六。
五五二十五，自相乘，得六百二十五，五人分之，人得一百二十五。
四五二十，自相乘，得四百，四人分之，人得一百。
三五一十五，自相乘，得二百二十五，三人分之，人得七十五。
二五一十，自相乘，得一百，二人分之，得五十。
一五如五，自相乘，得二十五，一人得二十五。
右五五一條，得七十五，自相乘，得五千六百二十五，五人分之，人得一千一百二十五。
四四一十六，自相乘，得二百五十六，四人分之，人得六十四。
三四一十二，自相乘，得一百四十四，三人分之，人得四十八。
二四如八，自相乘，得六十四，二人分之，人得三十二。
一四如四，自相乘，得一十六，一人得一十六。
右四四一條，得四十，自相乘，得一千六百，四人分之，人得四百。
三三如九，自相乘，得八十一，三人分之，人得二十七。
二三如六，自相乘，得三十六，二人分之，人得一十八。
一三如三，自相乘，得九，一人得九。
右三三一條，得一十八，自相乘，得三百二十四，三人分之，人得一百八。
二二如四，自相乘，得一十六，二人分之，人得八。
一二如二，自相乘，得四，一人得四。
右二二一條，得六，自相乘，得三十六，二人分之，人得一十八。
一一如一，自相乘，得一，一乘不長。
右從九九至一一，總成一千一百五十五，自相乘，得一百三十三萬四千二十五，九人分之，人得一十四萬八千二百二十五。
以九乘一十二，得一百八，六人分之，人得一十八。
以二十七乘三十六，得九百七十二，一十八人分之，人得五十四。
以八十一乘一百八，得八千七百四十八，五十四人分之，人得六十二。
以二百四十三乘三百二十四，得七萬八千七百三十二，一百六十二人分之，人得四百八十六。
以七百二十九乘九百七十二，得七十萬八千五百八十八，四百八十六人分之，人得一千四百五十八。
以二千一百八十七乘二千九百一十六，得六百三十七萬七千二百九十二，一千四百五十八人分之，得四千三百七十四。
以六千五百六十一乘八千七百四十八，得五千七百三十九萬五千六百二十八，四千三百七十四人分之，人得一萬三千一百二十二。
以一萬九千六百八十三乘二萬六千二百四十四，得五億一千六百五十六萬六百五十二，一萬三千一百二十二人分之，人得三萬九千三百六十六。
以五萬九千四十九乘七萬八千七百三十二，得四十六億四千九百四萬五千八百六十八，三萬九千三百六十六人分之，人得一十一萬八千九十八。
以一十七萬七千一百四十七乘二十三萬六千一百九十六，得四百一十八億四千一百四十一萬二千八百一十二，一十一萬八千九十八人分之，得三十五萬四千二百九十四。
以五十三萬一千四百四十一乘七十萬八千五百八十八，得三千七百六十五億七千二百七十一萬五千三百八，三十五萬四千二百九十四人分之，人得一百六萬二千八百八十二。
〈卷中〉
今有一十八分之一十二。問：約之得幾何？答曰：三分之二。
術曰：置十八分在下，一十二分在上，副置二位以少減多，等數得六為法，約之即得。
今有三分之一、五分之二。問：合之二得幾何？答曰：一十五分之十一。
術曰：置三分五分在右方，之一之二在左方，母互乘子，五分之二得六，三分之一得五，並之，得一十一為實；又方二母相乘，得一十五為法。不滿法，以法命之，即得。
今有九分之八，減其五分之一。問：余幾何？答曰：四十五分之三十一。
術曰：置九分五分在右方，之八之一在左方，母互乘子，五分之一得九，九分之八得四十，以少減多，餘三十一，為實；母相乘，得四十五，為法。不滿法，以法命之，即得。
今有三分之一，三分之二，四分之三。問：減多益少，幾何而平？答曰：減四分之三者二，減三分之二者一，並以益三分之一，而各平於一十二分之七。

3. 關於孫子問題的演算法C++ 求個能通過的演算法

這個題目就是孫子定理（中國剩餘定理）中的結論，是數論中的基礎定理之一。

對於

M=p1*b1+p2*b2+...+pn*bn

能滿足M除以a1的余數也是p1，M除以a2的余數也是p2……M除以an的余數也是pn。則

bimodai=1

bimodaj=0(i!=j)

這樣的解可以通過如下方式構造

C=a1*a2*...*an

ci=C/ai

bi=ti*ci且bimodai=1

這個構造的方法依賴於正整數a1,a2,...an是互質的，如果它們不是互質，不存在對於任意的N都成立的解。

程序如下：

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
usingnamespacestd;
intmain()
{
intN=0;
intTemp=0;
intB=1;
cin>>N;
if(N<=0||N>=11)
exit(1);
vector<int>pAn;
for(inti=0;i<N+1;i++)
{
cin>>Temp;
if(Temp>0&&Temp<=50)
pAn.push_back(Temp);
}
sort(pAn.begin(),pAn.end());
for(inti=0;pAn[i]<pAn[N-1]/2;i++)
{
for(intj=i+1;j<N;j++)
{
if(pAn[j]%pAn[i]==0)
{
cout<<"NO"<<endl;
return0;
}
}
}
for(inti=0;i<N;i++)
B*=pAn[i];
int*pBn=newint[N];
int*pCn=newint[N];
for(inti=0;i<N;i++)
{
pBn[i]=B/pAn[i];
pCn[i]=pBn[i];
}
for(inti=0;i<N;i++)
{
while(pBn[i]%pAn[i]!=1)
pBn[i]+=pCn[i];
}
for(inti=0;i<N;i++)
cout<<pBn[i]<<'';
return0;
}