VFP 愛用者社區

Watermelon · 註冊時間: 2005-01-22 文章: 204 第 1 樓

請教各位前輩，最大公約數、最小公倍數的算法。
請問有沒有這樣的函數?

小賴 · 註冊時間: 2004-12-27 文章: 476 第 2 樓

? GCD(45, 36)
LCM = 45 * 36 / GCD(45, 36)
? LCM

FUNCTION GCD
LPARAMETERS A, B
LOCAL A1, A2, A3
A1 = MIN(A, B)
A2 = MAX(A, B)
DO WHILE .T.
A3 = MOD(A2, A1)
IF A3 = 0
RETURN A1
ELSE
A2 = A1
A1 = A3
ENDIF
ENDDO

GCD(A, B)為A, B的最大公因數, 最小公倍數為 A*B/GCD(A, B)
如為 A, B, C 三數其最大公因數 = GCD(GCD(A,B), C)
最小公倍數為 A*B*C/GCD(A, B)^2
依此類推 ...不懂時; 問問以前的數學老師吧!

行者孙 · 註冊時間: 2006-03-11 文章: 43 第 3 樓

*求兩個數的最大公約數
*以下是我根據欧几里德算法來寫的
m=2
n=5
do while .t.
if mod(max(m,n),min(m,n))=0
r=min(m,n)&&r值最后就是最大公約數
exit
else
r=mod(max(m,n),min(m,n))
m=min(m,n)
n=r
r=min(m,n)
endi
endd
*上麵的代碼就可以求得m,n得最大公約數

*求最小公倍數
*原理m*n=兩者得最大公約數*兩者得最小公倍數
m=2
n=4
F=m*n
do while .t.
if mod(max(m,n),min(m,n))=0
r=min(m,n)&&r值最后就是最大公約數
exit
else
r=mod(max(m,n),min(m,n))
m=min(m,n)
n=r
r=min(m,n)
endi
endd
T=F/r&&T就是兩者得最小公倍數暸

*上麵得代碼我自己也沒測試，不過應該沒問題

Watermelon · 註冊時間: 2005-01-22 文章: 204 第 4 樓

感謝兩位前輩指點，我是有一堆數字約127個，想求這127個數的最小公倍數，我會用兩位前輩的方法試試看!
謝謝指點!

小賴 · 註冊時間: 2004-12-27 文章: 476 第 5 樓

127個整數的公倍數?
你該不會是玩我們吧 ! 不知你有沒有評估, 127個不同整數相乖, 這種天文數字
應該會有多大 ? 就算倍精度型態的變數, 也恐難應付 !
如果你沒弄錯的話 ; 這個數你可能要用一個相當大的陣列來存放, 陣列每一元素只存
放 0-9的數代表公倍數的每一位數值, 例如 123 就用
a[1] = 3, a[2] = 2, a[3] = 1 否則一定會數值溢位.

syntech · 發表於: 星期三三月 22, 2006 9:07 am 文章主題:

worst case 就是 127 個整數都是質數,
所以其最小公倍數就是 127 個數字相乘.

看你要讓這些整數的範圍到哪,
沒有範圍的話,
算到溢位也是正常的.

小賴 · 註冊時間: 2004-12-27 文章: 476 第 7 樓

>worst case 就是 127 個整數都是質數,
>所以其最小公倍數就是 127 個數字相乘.

先兩兩比較, 如有因數, 倍數關係時, 可去掉因數那一個數;
這樣可能少一點, 如果還是127個, 那麼至少有127個相異質數
相乖是正常的, 只會多, 不會少, 所以正常是比Syntech兄的Worst Case
還要Worst.

syntech · 發表於: 星期三三月 22, 2006 11:21 am 文章主題:

看不懂?

如果有127個數字找最小公倍數,
最壞情況是"至少有127個相異質數".

最多也只有127個數字,
全為相異質數,也是"最多127個相異質數"
除了最小公倍數之外,
哪來第128個數字? Shocked

還是我漏掉"相異"會有誤解? Very Happy

小賴 · 註冊時間: 2004-12-27 文章: 476 第 9 樓

先把127個整數化為質因數連乖積, 取出共有之質數相乖謂之"最大公因數"
剩餘全部相乖再乘最大公因數謂之"最少公倍數"
如果127個都是質數, 當然是只有127個質數相乘, 但是如果127個合數, 化為"質因數連乖積"
就會有N個質數, 且N > 127

......我是不是應該沒有誤解才對 ?

行者孙 · 註冊時間: 2006-03-11 文章: 43 第 10 樓

既然是用编程的思路去解决问题，就不要心存幻想，老老实实的结合上面已经提供的求两个数的最大公约数的方法去做个循环两两累算，最后再求出最小公倍数。
回答问题的人最好自己能把问题先考虑好再回答，不要误导问问题的人！

行者孙 · 註冊時間: 2006-03-11 文章: 43 第 11 樓

欢迎广大台湾省狐友加入我的VFP应用程式算法群,QQ群号：12787940

syntech · 發表於: 星期三三月 22, 2006 1:44 pm 文章主題:

問題好玩的地方在於解答通常不會只有一個,

兩兩求最小公倍數,遞迴到所有數字是一個方法,
一次分解所有數字,求最大公因數,再找出最小公倍數也是一個方法,
應該也還有許多不同的方法可以辦到.

最重要的是,問這個問題,明擺著就是學校作業.
不對別人的家庭作業作認真回答就是我的忍道. XD

Watermelon · 註冊時間: 2005-01-22 文章: 204 第 13 樓

感謝各位前輩指點!
最近幾天因比較忙，所以沒上網。
很抱歉的是上次沒把問題描述清楚，我的問題是127筆資料全是分數如：
12/87,34/100,24/174,64/200,10/123,20/246......其中分母也有很多是相同的
我的答案是要把這127個加起的和。
感謝各位前輩提供這麼多方法。

catjoke · 發表於: 星期六三月 25, 2006 11:38 am 文章主題:

我想說的是, 使用小數點吧...

告知計算答案是 12382309498523080984023984092384832/232398472389749823798238423890382320932 會有意義嗎!?

還是告知 0.656399293 => 0.6564 算吧.

Watermelon · 註冊時間: 2005-01-22 文章: 204 第 15 樓

感謝各位大哥指點，我用小賴前輩的方法得到我要的答案，代碼如下：
SELE 0
USE c:\aa
GO top
n1=1
DO while !eof()
nAt=at('/',p1)+1
n2=val(subs(p1,nAt))
IF n2>0
LCM = n1 * n2 / GCD(n1, n2)
REPL p2 with n2&&原分母
REPL p4 with val(left(p1,nAt-1))&&分子)
ENDIF
Skip
ENDDO
REPL p3 with LCM/p2*p4 all&&約分後分子
? LCM&&公分母