最小連比?(已解決)

weirdococo

作業題目是這樣，輸入一個用逗號分隔的連比，取之最小連比，
譬如輸入8 , 28 , 64 , -128 , -256，輸出為2, 7, 16, -32, -64。
我的一貫作風，先用

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

先寫一遍

1. use v6;
   
2. my Int constant  @data = prompt("input continue ratio\n").split(',').grep(/\d/).map({ $_.Int });
   
3. say  @data «/» [gcd] @data unless [gcd] @data <= 0 ;

複製代碼

，執行結果


然後想說怎麼用純C語言寫出來，目前不知道怎麼用C語言(不是C++)寫出folder/reduce 或是
zip還有可延伸的list，一般是怎麼處理的??



補充內容 (2017-6-4 03:06 PM):
雖然不是作業內容但是也想問用C++一般是怎麼處理的?我是自己寫個zip或reduce和hyper operator。

補充內容 (2017-6-4 03:22 PM):
題外話，最小連比的英文是甚麼阿?

補充內容 (2017-6-4 03:34 PM):
其實我很想知道，道地的C/C++語言起家的人，會用甚麼想法(演算)來解決這個問題，並增加自己的思考方法。

補充內容 (2017-6-4 05:16 PM):
題外話2，其實現在perl的型態很硬，兩個string不能相加，所以一樣要轉型!...

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

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在十進位下的位數。

這是最差狀況了

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

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

chevylin0802

ren1244 發表於 2017-6-7 01:53 AM

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

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

...

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

ren1244

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

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

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

--  維基百科：

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

...

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

weirdococo

a333221 發表於 2017-6-6 11:57 PM

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

那就是要再做排序的意思，那我再給一例 10000, 9009, 9999, 8888, 7777
只要數字大一點，就算是排序了， ...

...

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

weirdococo

a333221 發表於 2017-6-6 11:57 PM

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

那就是要再做排序的意思，那我再給一例 10000, 9009, 9999, 8888, 7777
只要數字大一點，就算是排序了， ...

有就是說，還需要一個loop找出序列最小質（不需要sort)，在比較一下複雜度才是！...

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

a333221

chevylin0802 發表於 2017-6-6 11:51 PM

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

你錯了，求因數時一定是用最小數去求因數，哪裡會拿1000去計算
所以差更多是差再哪裡？
當我傻到拿1000去 ...

...

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

chevylin0802

a333221 發表於 2017-6-6 11:46 PM
就大大給的例子「12， 18， 24， 30， 48」，
估算，僅考慮除法個數

你錯了，求因數時一定是用最小數去求因數，哪裡會拿1000去計算
所以差更多是差再哪裡？
當我傻到拿1000去求因數嗎？...

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

a333221

chevylin0802 發表於 2017-6-6 11:34 PM

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

不可能比較費時
gcd的算法反而才是最費時的
因為gcd有迭代的反覆運算

就大大給的例子「12， 18， 24， 30， 48」，
...

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

chevylin0802

a333221 發表於 2017-6-6 11:18 PM
作業當然是自己做。
昨天沒看仔細，誤以為大大直接假設已知 8 的所有非 1 因數為 2 4 8，
所以誤認為大大 ...

不可能比較費時
gcd的算法反而才是最費時的
因為gcd有迭代的反覆運算
...

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

a333221

chevylin0802 發表於 2017-6-6 05:39 AM

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

那是他的作業，我不可能給他完整版的程式。
所以只給一個sample。
至於他如果要手動輸入數值

...

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

chevylin0802

a333221 發表於 2017-6-5 10:55 PM
大大，人家的 8 , 28 , 64 , -128 , -256 只是舉例，要的是一般情況也能處理，

可是你 sample 用的方法 ...

那是他的作業，我不可能給他完整版的程式。
所以只給一個sample。
...

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

a333221

chevylin0802 發表於 2017-6-4 10:50 PM

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

先將8拆分
可以得到1，2，4，8
拆分方式你應該會

大大，人家的 8 , 28 , 64 , -128 , -256 只是舉例，要的是一般情況也能處理，
...

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

chevylin0802

weirdococo 發表於 2017-6-4 11:58 PM
這感覺是一個較少花費的解決方案，我對演算法的概念是如何更有效率做出解果，
通常不直觀，其實我有想過找 ...

不對，演算法的基礎就是資料結構
資料結構一般都是大一下學期的必修課程
...

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

weirdococo

weirdococo 發表於 2017-6-4 10:49 PM

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

找到問題了，我發覺我perl也錯了，不需要那個while。
所以就perl因該是這樣， ...

問題已解...

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