kyiimno asked in 科學數學 · 1 decade ago

Part II 韓信點兵,尋找一次就OK的公式。給20 點

請看完看清楚整個內容,謝謝。

Part II 尋找一次就OK的公式

我不會在乎點數的,所以給最多的20 點代表我的誠意。

有疑問的大大請在意見欄中發表疑問。

( 有人對於發問人只給五 點,隨便選最佳答案就可獲得十點感到不滿。我也看的出來有人是在亂問的,所以我有一個想法。針對 "選最佳答案就可獲得十點" 除非取消,不然絕對不要回答,也不要回答答案在意見欄,頂多給個方向即可。點數在10點以上的才回答,這樣就應該可以先消除純粹賺點數的發問心態。畢竟這是求知的地方,我很喜歡這裡,雖然我能力有限。有大大願意響應我嗎? )

題目:

韓信點兵

一群人(非質數)列隊,總人數 4437。

每列101人剩94人(101*43...94)

每列100人剩37人(100*44...37)

每列 99人剩81人(99*44...81)

若要形成完整的隊伍,則有多少種(長方形)的隊伍?

( 總數是亂取的兩數相乘 51 * 87 ,非質數,所以一定有解。)

觀念:

我知道只要列出4437 的公因數即可,公因數的數量就等於有多少種的隊伍。

總人數是質數就只能排成很長的一行,所以質數在這題裡沒有意義。

(質數的公因數只有1和自己 )

對我來說,找公因數的步驟也要算不少的算式(尤其是值越大)。

其實是讓程式在跑,但是時間越短,爽度就越高。

既然已知(101*43...94)(100*44...37)等等,何不就 "將計就計",使用(101*43...94)(100*44...37)等條件。

想法:

已知每列101人剩94人(101*43...94)的條件。

少一列就成了100列,剩下的人數是94人加上第101列的43人等於137人。

137人比100列還多,所以多了37人,變成(100*44...37)。

想像一下畫面,最後一排多出了37人。

總人數不是質數,則一定有整除的時候。只是隊伍不知道會有多長。

實驗:

假設沒有多餘的人的時候,而且隊伍是正方形。

一顆圍棋當成一人,照我想法排列。

(由第一個發問的題目所得到的解答。http://tw.knowledge.yahoo.com/question/index?qid=1... )

邊長為六,則可以得2*18,3*12,4*9。

至於會要求N 的最小值則是隊伍會看起來最寬(或最長)。

第一個發問的題目公式就是這樣來的。

公式:

長和寬為A和X,

推出的公式為

( A * N B ) / ( A - N ) = X...0。

我認為X 還是沒有意義,因為總人數已知,求N 即可。

還是我推導的公式一開始就有錯誤?

閒話:

這不是我的作業,我也不是學生,也不是工作上遇到的問題之ㄧ。

只是看到 "韓信點兵" 的題目的異想天開。

其中一句是 "「三三數之剩二,五五數之剩三,七七數之剩二,問物幾何?」"

現在的話:除3餘2,除5餘3,除7餘2,總數為?

我只是多了一句 "除某數餘零",則某數為?

所以不想用找公因數的方法,想將計就計。不知可行?

感謝:

上一個題目是:( A * N ) / ( A - N ) = X...0。

則結論就是找出A^2中比A小的最大因數t,然後 n=A-t。

我也有學到另一種思維。

特別感謝 "小曄" 大大的智慧及付出,其他人也辛苦了。

對話:

"小曄" 大大,我出個送分題由你回答。讓妳該得的點數還是要拿的,好嗎?

Update:

[ 其他 ] dd ( 研究生 4 級 ) 2005-10-27 08:44:39 發表 [ 檢舉 ]

除了因數分解還可能有更快的方法?!

現在的我相信是有有更快的方法的

Update 2:

回 答 者: The Proud Cat ( 初學者 5 級 ) [ 檢舉 ]

回答時間: 2005-10-26 23:01:35

12種長方形

視公因數而定

我不知道怎麼用一個公式解噎!!

抱歉!!

對不起,讓妳誤會了。

我這裡的公式指的是一串連續的步驟,並不是一個算式就可解決的意思。

Update 3:

to 小曄

我也是看到有趣的題目,才會點進來看。

==========

我想都不如用 n-=[√4437],這樣一次遞減 1,然後試 4437(mod n)是否為 0來試

找 4437 的所有因數 n,會不會來得快一點?

就是這個方法啦,雖然在理論上也可以算是找 "因數" 的方法。

不過對設計程式來說差很多。

公因數,是不是因數的筆誤呢?

我沒學過正規的數學,應該是我的錯。我只知道是個可以整除的數。

"除" 應該改成 "除以" 。因為這兩個差滿多的~

我不管是那個,都是第一個數當分子。

Update 4:

我解釋一下 A=n^2 + n 的由來

A=n^2 + n 可以等於 A = n(n+1)

有一串數字的規律為1+2+3+4+...+n,則總和為 (1+n)*n/2。(梯形公式拿來算三角形和長方形也可以用)

假設一個數字 A=32,√A=5.xxxxx(取整數就好)。

想像一個畫面,有一個5*5 棋子排成的正方體,和剩7 顆的一行。

Update 5:

步驟

1. 圖形為

。。。。。

。。。。。

。。。。。

。。。。。

。。。。。

,,,,,,,

2. 砍掉,變為

。。。。。

。。。。。

。。。。。

。。。。。

。。。。。

,,,,,

,,

3. 拿掉一行,變成

。。。。

。。。。

。。。。

。。。。

。。。。

。。。。

。。,,,,,,

4. 重複2~3

。。。。

。。。。

。。。。

。。。。

。。。。

。。。。

。。,,

,,,,

剛好到第四步驟就是長方形

Update 6:

5.

。。。

。。。

。。。

。。。

。。。

。。。

。。。

。。。

,,,,,,,,

6.

。。。

。。。

。。。

。。。

。。。

。。。

。。。

。。。

,,,

,,,

,,

7.

。。。

。。。

。。。

。。。

。。。

。。。

。。。

。。。

。。。

。。。

。。

8.

。。

。。

。。

。。

。。

。。

。。

。。

。。

。。

。。

,,,,,,,,,,

Update 7:

9.

。。

。。

。。

。。

。。

。。

。。

。。

。。

。。

。。

,,

,,

,,

,,

,,

也是長方形

所以32有兩個長方形

用數字來看,每一次都是移下一行

每移一次長和寬的關係是差 2,4,6,8.....

總和是 2+4+6+8+...+n = (1+n)*n。

設餘數 = r ,長=p和寬=q,q不考慮。

n=1

p=4

r=2+2=p

Update 8:

n=2

p=3

r=0+2

n=3

p=2

r=2+2 = 2p

應該是沒有必要試 (mod n)是否為 0 的動作,因為我看到圖形,

只要餘數可以等同其中一邊長或寬就可以說是整除,

跟(mod n)是否為 0 的原理應該是相同的。

雖然對電腦來說都是一樣的動作,對人來說應該比較輕鬆。

Update 9:

這就是我所謂的 "將計就計" 。

可是把√A 每次減一,跟把A "除以" 1,2,3 等等。

根本是半斤(√A 每次減一)八兩(A "除以" 1,2,3 ...)的次數。

所以我認為應該有個"某步驟"存在。

Update 10:

to dd

二個很大的質數的乘積 ?

不會那麼剛好吧?

Update 11:

to dd

如果原數是二個很大的質數的乘積

還是得要用因數分解的方法嗎?

Update 12:

我的國小數學題,

應用題

1. 繩子長40公尺,圍出最大面積。

A: 當時最正確的答案是10*10。(最大面積當然是正圓)

2. 有一面牆可當一邊,繩子長40公尺,圍出最大面積。

A: 當時最正確的答案是20*10。(最大面積會是半正圓嗎?我不確定)

如果繩子增加?或用面積要求繩子長?

可能會需要不一樣觀念吧。

這題的觀念應該可以多少套用到這裡吧。

5 Answers

Rating
  • 1 decade ago
    Favorite Answer

    首先謝謝你~

    看得出來你滿介意目前知識加算點數的方式。

    我個人是覺得,這個就好像法律定了之後,總是有遊走於法律邊緣的人一樣~

    在不能改變環境的時候,就改變自己的作法或是心態 ^^

    我也滿喜歡知識加這樣的原始善意,只是跟你一樣,發現有好多人有不好的

    習慣,以致於原本滿熱衷於這裡的,現在變成只在這邊找到一些還可用的資源~

    兩個做法,一個是看見別人有問題,自己能夠的就給點意見的,

    或是上來看有沒有有趣的題目供我們討論、交換心得或是彼此學習。

    =============================================================

    就這一題的討論,其實如果是交給電腦來找的話,我也想不出一個個漸進

    的數值來去試之外還有什麼好方法。

    所謂的小於A的最大因數,這個找因數的方法,讓人腦來算好算,

    交給電腦的話,我大概也只能用小於√A的數字,每次減 1然後往下試~

    不過這題你數次打到公因數,是不是因數的筆誤呢?

    公因數是存在兩者以上的數才有公因數的。

    而找因數的時候,如果讓電腦先用 4437=101*43 + 94,

    再試 4437=100*43 + 43+94 = 100*44 + 37,光是這一步,就比原來使用函數

    4437 = 100 * [4437/100] + 4437(mod 100)來的複雜吧?

    再往下去試 99,98這樣試下去,來找 4437 的 兩數乘法,

    我想都不如用 n-=[√4437],這樣一次遞減 1,然後試 4437(mod n)是否為 0來試

    找 4437 的所有因數 n,會不會來得快一點?

    ============================================================

    還有真的很對不起的就是,我一直想不出來這些跟 A=n^2 + n,

    還有 (A*n) / (A-n) = X .... 0 的關係是?

    以 4437 的例子來看, 4437 = 101*43 + 94,

    那應該表成 A = p*q + r 。

    以邊長為 6 的例子,那也是 6^2 = 36 = 2*18 = 3*12 = 4*9,

    也看不出這跟 A=n^2 + n 還有 (A*n) / (A-n) = X .... 0 的關係。

    致於下面一句話:

    『其中一句是 "「三三數之剩二,五五數之剩三,七七數之剩二,問物幾何?」"

    現在的話:除3餘2,除5餘3,除7餘2,總數為?』

    "除" 應該改成 "除以" 。因為這兩個差滿多的~

    18÷3 = 6 ,我們可以唸成 18除以3等於6,或是 3 除18 等於 6。

    而除以某數餘零,我想,沒有比標準分解式來找因數的個數還好用的方法了~

    而且,因為中小學的數學,通常學的都是簡單答案的題目,所以如果合條件的

    解答有多個的話,最常見的是要問說有幾個答案,而不是問說是哪幾個~

    ===============================================================

    另外,我原本也在猜想你的原題是不是跟矩形的邊長還有面積有關,

    一個邊長為 X 的正方形,從一邊截 b 長的的矩形接在側邊的話,

    那會有一塊長 (X+b) ,寬 (X-b) 的矩形,可是另外一塊邊長為 b的正方形就沒算到了。也不知該挪到哪去。

    又想到,A*n=X * (A-n),一邊是 A長減去 n長,那 A*n 就是原來是一邊長為 A,

    另一邊寬為 n。這樣,會有(A-n)的情況,就是截去一個邊長為 n 的正方形,

    然後,不知道它要怎麼跟 一個長寬 n 跟 (A-n) 的矩形接在一起~

    最後呢,說到韓信點兵的題目,我現在只記得中國剩餘定理的作法,

    XX數之餘 x,YY數之餘 y,ZZ數之餘 z。(X、Y、Z要互質,不然可能出現無解)

    我的做法:

    就是先找 YZ× p 除以 X 餘 x 的 p值 ( 1≦p≦ x-1,除非 x=0,不然 p不為0);

    再找 XZ× q 除以 Y 餘 y 的 q 值 ( 1≦q≦ y-1);

    最後找 XY× r 除以 Z 餘 z 的 r 值 ( 1≦r≦ z-1)。

    數字不大的話,這樣找起來是滿快的~ 加上如果有 mod 的運算觀念的話,

    找 p,q,r 的值應該就快的很了~

    ============================================================

    我之前也曾經想過,如果沒有學過珠心算,如果用心算快速算一些數值

    的近似值呢?例如 1/19,

    我就用 1/20 + 1/400 + 1/8000 + .... 的觀念,先算 1/20,然後加上這個數的 1/20,

    再加上剛那數值的 1/20,這樣加個兩三次後,看要精確到小數點以下幾位~

    如果要算的是 7/19,一樣先算出 7/20= 0.35,然後加上 0.0175,再加上 0.000875

    那如果要算的是 5/21呢?就先算出 5/20= 0.25,然後減去它的 1/20,就是 0.0125,然後再加上0.000625。這樣下來,我發現這樣是對的,可是呢~

    這樣不如我直接用小學學的除法來算,可能還比較快呢 @@~

    2005-10-28 16:19:17 補充:

    請教dd一下:

    (看來你對電腦好熟哦~)

    如果真的乘法運算是加法的十倍的話~

    那麼,當p值越來越小,q值越來越大的時候,例如p=2時的回圈時,次回圈要做六百多次以上的運算,而這回圈中的運算,r要做一次減法,q要做一次加法,也就是說,一個回圈中要做上千次的運算,

    有沒有計算過,平均這樣寫出來的程式,跟直接用mod的方法來計算的時間比呢?是會大於十倍,還是小於十倍呢?

    還有,當有A=4437出來之後,第一個p值要如何去取,也是取[√4437]嗎?

  • Anonymous
    6 years ago

    到下面的網址看看吧

    ▶▶http://qoozoo09260.pixnet.net/blog

  • 1 decade ago

    有看到 n^2+n 嗎?

  • dd
    Lv 6
    1 decade ago

    除了因數分解還可能有更快的方法?!

    2005-10-27 11:10:03 補充:

    就算是用之前那題的東西

    也是得因數分解阿

    2005-10-28 10:42:20 補充:

    p=101 q=43 r=94

    while (r大於0) {

    .....p--;

    .....r+=q;

    .....while (r大於等於p) {

    ..........r-=p;

    ..........q++;

    .....}

    }

    2005-10-28 10:50:09 補充:

    因為電腦做加.減會比乘.除.MOD來得快很多很多

    所以上面的方法可以很快地找出4437的二個因數87*51

    但是現在的電腦都已經很好了

    就算是用乘.除.MOD也很快

    例如

    以前的電腦做一個加法要0.1秒

    乘法要10秒

    那相對之下少用乘法是來的重要的多

    但是現在的電腦做一個加法要0.0000001秒

    乘法要0.00001秒

    這樣子的情況下就沒什麼必要去要求要做到最少的乘法

    2005-10-28 10:57:03 補充:

    當然如果原數是二個很大的質數的乘積

    那這個方法是有很好的效率來找因數

    但是最終要解這個問題還是得要因數分解呀

    2005-10-28 12:36:57 補充:

    我是指要算有幾種隊伍時得因數分解後再算是比較快的

    至於找因數是可以用你所說的方法

    也就是我上面說的演算法

    當然找到N=A*B後

    再遞迴地找A的因數(以及B的)

    最後就可以把N因數分解完

    (其實小質因數可以用簡單的辦別法先提出來)

    最後就用因數個數就可以知道解了

    2005-10-28 18:54:44 補充:

    其實我對電腦不是很熟啦

    我是math畢業又不是cs畢業的

    不過倒是可以寫程式來計算時間

    像是用for跑10000000次加.乘.mod

    看分別花了多久的時間

  • How do you think about the answers? You can sign in to vote the answer.
  • 1 decade ago

    12種長方形

    視公因數而定

    我不知道怎麼用一個公式解噎!!

    抱歉!!

    Source(s): 自己
Still have questions? Get your answers by asking now.