最小連比?(已解決)

ren1244

我覺得這是好事情，經過這樣的練習才程式語言的背後幫我們做了甚麼事情。
prompt、split、grep、map、…
這些東西必須自己來實現
(不過一開始還是簡單些，先滿足此題需求就好，不求那麼泛用)

想一下C語言的基本型態
最接近 list 的應該是 array
而我們可以用動態宣告來達成可變長度的 array
如果裝滿了，那麼我們必須重新要一塊更大空間的記憶體
...

瀏覽完整內容，請先 註冊 或 登入會員

ren1244

最小值未必是最少因數的數字
例如960跟991，雖然960比較小，但是因數卻很多

此外，要找出一個數的所有因數，光是這件事情就要跑很多迴圈。
而輾轉相除法卻能很快的找到最大公因數
找a,b的最大公因數：

輾轉相除法不會進行超過O(h)次除法，其中h是較小數b在十進位下的位數。

--  維基百科：

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

...

瀏覽完整內容，請先 註冊 或 登入會員

ren1244

2跟32767跑2次迴圈，計算如下：
32767%2=1
2%1=0
得最大公因數為1

3跟32767跑2次迴圈，計算如下：
32767%3=1
2%1=0

對 a>b>0

輾轉相除法不會進行超過O(h)次除法，其中h是較小數b在十進位下的位數。

這是最差狀況了

另外，開版的作法不是分別兩兩去求最大公因數，再看這些公因數是不是一樣
...

瀏覽完整內容，請先 註冊 或 登入會員