伊莉討論區

標題: 最小連比?(已解決) [打印本頁]
作者: weirdococo    時間: 2017-6-4 03:03 PM     標題: 最小連比?(已解決)

本帖最後由 weirdococo 於 2017-6-4 10:52 PM 編輯

作業題目是這樣，輸入一個用逗號分隔的連比，取之最小連比，
譬如輸入8 , 28 , 64 , -128 , -256，輸出為2, 7, 16, -32, -64。
我的一貫作風，先用script language 先寫一遍
  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 ;
複製代碼
，執行結果

[attach]119026838[/attach]
然後想說怎麼用純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不能相加，所以一樣要轉型!
作者: coal511464    時間: 2017-6-4 07:47 PM

語言只是實現演算法的工具 並不會有什麼太特殊的地方
只是根據資料怎麼處理 寫法會有不同
作者: weirdococo    時間: 2017-6-4 08:14 PM

本帖最後由 weirdococo 於 2017-6-4 08:29 PM 編輯
coal511464 發表於 2017-6-4 07:47 PM
語言只是實現演算法的工具 並不會有什麼太特殊的地方
只是根據資料怎麼處理 寫法會有不同 ...

題外話，學了一個語言，會碰到不同東西，然後會見到不同演算法，就像是我只用C語言的話，我就不會知道lamda function的意義，因為C語言不鼓勵，也就是說語言會影響演算法，進而引想我的思維，然而我的思維有被一些非主流語言控制住的嫌疑，所以我會想看看主流的作法。
單然我可以用C++語言把上面的寫法照樣刻上去(因該要用到boost)，但是要用C有一點困難，也就是說我被一寫思維困住，現在還慢慢再想解決的方法。

補充內容 (2017-6-4 08:16 PM):
還有作業真的是要求用C語言寫，也就是說我真的寫不出來。
作者: ren1244    時間: 2017-6-4 08:58 PM

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

想一下C語言的基本型態
最接近 list 的應該是 array
而我們可以用動態宣告來達成可變長度的 array
如果裝滿了，那麼我們必須重新要一塊更大空間的記憶體
再把原本的資料 copy 過去
並釋放舊有的空間

你現在需要訓練的是類似這樣低階的思維
如果依賴外部的函式庫
那麼還是一樣無法感受到寫C語言的感覺
只是把一切你熟悉的東西換個名字罷了

我想先從簡單的開始吧：
1. 用scanf 輸入字串
2. 將字串解析成整數陣列
3. 寫一個函數，可以將整數陣列約分到不能再約分

先完成這些，再來想可變長度陣列的事情
此外，若要實作 regex 應該不是那麼簡單可以完成的。

補充內容 (2017-6-4 09:05 PM):
也可以想想：C++ STL 中，vector 跟 list 的差別是甚麼？插入、移除、存取第N個元素，分別是哪一種效率高？
函式的差別，不只是他給予的介面。
作者: caoh    時間: 2017-6-4 09:07 PM

人換個情景、語言，寫不出來事很正常的。
你只是需要練習 C 的撰寫方式，不是非得函數式的思維，畢竟 C 不擅長。
更何況要做出 zip, map, fold 難道不能自己刻嗎？
只是 C 不擅長函數組合的模式，硬要寫比較憋扭吧
C 必有其長處，否則早被淘汰了
  
  
  
作者: weirdococo    時間: 2017-6-4 09:52 PM

本帖最後由 weirdococo 於 2017-6-4 10:23 PM 編輯
ren1244 發表於 2017-6-4 08:58 PM
我覺得這是好事情，經過這樣的練習才程式語言的背後幫我們做了甚麼事情。
prompt、split、grep、map、…
這 ...

3. 寫一個函數，可以將整數陣列約分到不能再約分
就是這個想不出來，如果有限時解題的話，我一定自己刻一個fold/reduce去寫，
還沒想透，可能用兩個loop再加一個變數去完成fold的感覺，但是我在想這樣對嗎?
感覺像這樣
  1. int64_t gcd ( int64_t a, int64_t b ) {
  2.   int64_t c;
  3.   while ( a != 0 ) {
  4.      c = a; a = b%a;  b = c;
  5.   }
  6.   return b;
  7. }

  9. int64 buffer = array[0];
  10. while( true ) {
  11. //會有指標退化的問題  不能作為sub
  12.     if (buffer == 1 )
  13.         break;
  14.     for(uint64_t i =1; i <= sizeof(array); i++) {
  15.         buffer  = gcd( array[i],buffer  );
  16.     }
  17.     for(uint64_t i =1; i <= sizeof(array); i++) {
  18.         array[i] = array[i]/ buffer ;
  19.     }
  20.    
  21. }
複製代碼


補充內容 (2017-6-4 10:08 PM):
vector 跟 list 的差別老師有考! 幾本上就是記憶體連不連續讓我有沒有辦法指定第N個元素，list 沒辦法，所以他只能都跑一遍。
作者: weirdococo    時間: 2017-6-4 10:05 PM

caoh 發表於 2017-6-4 09:07 PM
人換個情景、語言，寫不出來事很正常的。
你只是需要練習 C 的撰寫方式，不是非得函數式的思維，畢竟 C 不 ...

就是想不出非得函數式的思維，所以當我的資料是一個連續的sequence的時候就想不出來了!
像是這題，我寫不出來不用fold概念的'將整數陣列約分到不能再約分'的function!
作者: weirdococo    時間: 2017-6-4 10:49 PM

weirdococo 發表於 2017-6-4 10:05 PM
就是想不出非得函數式的思維，所以當我的資料是一個連續的sequence的時候就想不出來了!
像是這題， ...

找到問題了，我發覺我perl也錯了，不需要那個while。
所以就perl因該是這樣，
  1. my Int constant  @data = prompt("input continue ratio\n").split(',').grep(/\d/).map({ $_.Int });
  2. say  @data «/» [gcd] @data;
複製代碼
作者: chevylin0802    時間: 2017-6-4 10:50 PM

本帖最後由 chevylin0802 於 2017-6-5 11:12 AM 編輯
weirdococo 發表於 2017-6-4 10:05 PM
就是想不出非得函數式的思維，所以當我的資料是一個連續的sequence的時候就想不出來了!
像是這題， ...

先將8拆分
可以得到1，2，4，8
拆分方式你應該會
反正就是用for迴圈找出來
1不用算
然後由高而低作為除數
依次帶進去其他數字取餘數
只要一個不能整除，也就是餘數不為零
就換下一個數字當除數
找出最大公因數之後
就不必再帶下一個數字去當除數
而是每一個輸入的數字去除這個最大公因數
這就是演算法
演算法其實非常重要
資料結構一半以上的核心都在這個部份
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <unistd.h>

  5. int input_array[] = { 8 , 28 , 64 , -128 , -256 };
  6. int output_array[6];
  7. int parts[6];

  9. int main(int argc, char** argv)
  10. {

  12.         int i, j, k;
  13.         int flag;

  15.         /* 求出8的因數 */
  16.         for (i=2, j=0; i < input_array[0]/2 ; i++) {
  17.                 if (input_array[0] % i == 0) {
  18.                         parts[j] = i;
  19.                         j++;
  20.                 }
  21.         }
  22.         /* 8本身也可以被自己整除 */
  23.         parts[j] = input_array[0];

  25.         /* 除數陣列的迴圈, 數值從高而低 */
  26.         for (i = j; i >= 0; i--) {
  27.                 for(k = 1; k < 5; k++) {
  28.                         if( input_array[k] % parts[i] != 0) {
  29.                                 /* 不能被整除時, 跳出內層迴圈 */
  30.                                 flag = 0;
  31.                                 break;
  32.                         } else {
  33.                                 /* 能被整除時, 將input_array整除之後寫到output_array裏 */
  34.                                 flag = 1;
  35.                                 output_array[k] = input_array[k]/parts[i];
  36.                         }
  37.                 }
  38.                 /* 所有input_array的迴圈都可以被整除時, 表示已找到最大公因數 */
  39.                 if(flag == 1) {
  40.                         /* 由於8沒有進行迴圈整除測試, 所以在此補上整除後的結果寫到output_array裏 */
  41.                         output_array[0] = input_array[0]/parts[i];
  42.                         /* 跳出外層迴圈 */
  43.                         break;
  44.                 }
  45.         } /* for (i = j; i >=0; i--) */

  47.         print_f("Outputs : ");
  48.         for (i = 0; i < 5; i++) {
  49.                 print_f(" %d,", output_array[i]);
  50.         }
  51.         print_f("\n");

  53.         exit(0);
  54. }
複製代碼
這是範例程式, 已測試！
作者: weirdococo    時間: 2017-6-4 11:58 PM

本帖最後由 weirdococo 於 2017-6-4 11:59 PM 編輯
chevylin0802 發表於 2017-6-4 10:50 PM
先將8拆分
可以得到1，2，4，8
拆分方式你應該會

這感覺是一個較少花費的解決方案，我對演算法的概念是如何更有效率做出解果，
通常不直觀，其實我有想過找本演算法來看，但後來還是作罷，
因為我才大一學了一學期的程式設計，一般來說演算法是大三大四的課程，
也就是說我有很多依賴還沒學好，再者程式就算不走最短路徑也會有結果，
也就是說還沒有優化的打算，這也是我可以接受script language這種慢速的東西的原因，
就算我學了演算法寫程式，如果不是遇到效率問題，我想我也會到最後才把沒
有效率的地方改寫吧。
作者: weirdococo    時間: 2017-6-5 12:04 AM

weirdococo 發表於 2017-6-4 10:49 PM
找到問題了，我發覺我perl也錯了，不需要那個while。
所以就perl因該是這樣， ...

問題已解
找機會再用python寫寫看，題外話，最近python也能定型(Type Hints)，好像越來越少Duck typing的程式語言了。
作者: chevylin0802    時間: 2017-6-5 12:31 AM

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

不對，演算法的基礎就是資料結構
資料結構一般都是大一下學期的必修課程
沒道理改到大三才學
演算法確實不太直觀
但是它卻是有必要性

另外一點
script language腳本語言
跟直譯式程式語言還是有差別的
腳本語言只能算是直譯式語言的子集
但不能視為相同

事實上
只要是程序導向的程式語言
當有人根據它做出直譯器時
都可以稱它叫做直譯式程式語言
哪怕是C或者是Pascal
PC版最早的Basic就是直譯式語言
但是它並不能稱為腳本語言

然而為何直譯式程式語言在現在卻是越來越普及
其實最主要的兩大原因所導致
第一個原因是現在的電腦的速度越來越快
已經足夠擔負起直譯式語言的執行效率差的問題
而第二個原因則是比如C/C++的程式
常常因為人為疏失而導致記億體的配置與釋放動作不完整
造成已配置的記憶體經常在程式結束之後仍然不得釋出
這也就導致現在越來越多工程師喜歡使用例如Python之類的程式語言來開發
因為直譯式程式語言自行管理著記億體的配置
可以確保不發生memory leak的問題

作者: a333221    時間: 2017-6-5 10:55 PM

chevylin0802 發表於 2017-6-4 10:50 PM
先將8拆分
可以得到1，2，4，8
拆分方式你應該會

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

可是你 sample 用的方法似乎只針對  8 , 28 , 64 , -128 , -256 這例子在做，

沒就一般情況進行處理
作者: chevylin0802    時間: 2017-6-6 05:39 AM

本帖最後由 chevylin0802 於 2017-6-6 05:48 AM 編輯
a333221 發表於 2017-6-5 10:55 PM
大大，人家的 8 , 28 , 64 , -128 , -256 只是舉例，要的是一般情況也能處理，

可是你 sample 用的方法 ...


那是他的作業，我不可能給他完整版的程式。
所以只給一個sample。
至於他如果要手動輸入數值
他就要自己去改
演算法都有給他了
剩下來的事應該由他自己去做
至於如果他的數值個數要可變動
那就再用link list的方式做
C的link list網路上一堆範例
總不需要我再提供吧？
反正就是做一個struct而已
再加上幾個function
比如，size，add，remove，next, head，tail，等自己動手做
作者: a333221    時間: 2017-6-6 11:18 PM

本帖最後由 a333221 於 2017-6-6 11:34 PM 編輯
chevylin0802 發表於 2017-6-6 05:39 AM
那是他的作業，我不可能給他完整版的程式。
所以只給一個sample。
至於他如果要手動輸入數值

作業當然是自己做。
昨天沒看仔細，誤以為大大直接假設已知 8 的所有非 1 因數為 2 4 8，
所以誤認為大大的演算法只針對題目給的例子在做。

大大 8 的所有因數是讓程式自己算的，這演算法一定會比原發問者的來得有效率嗎？
還有，要算因數，要講究演算法的話，迴圈的終止條件要用開根號，用迴圈算出一半的因數，
另一半用除的得出。大大用的是除以 2，除以 2 可以用一個迴圈完成，但運算量會多不少。
作者: chevylin0802    時間: 2017-6-6 11:34 PM

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


不可能比較費時
gcd的算法反而才是最費時的
因為gcd有迭代的反覆運算
而且還是兩兩計算一次gcd
然後還要再用gcd再計算出gcd
反覆處理
不信的話
你代入一組不同於樓主提供的數字
12， 16， 24， 56， 72
你可以去比看看走了多少次迴圈

千萬別以為兩兩一組的gcd迴圈
就能得到同樣的gcd數值
萬一不是的時候，
還得再一次對每一組的gcd重新求出gcd
作者: a333221    時間: 2017-6-6 11:46 PM

chevylin0802 發表於 2017-6-6 11:34 PM
不可能比較費時
gcd的算法反而才是最費時的
因為gcd有迭代的反覆運算

就大大給的例子「12， 18， 24， 30， 48」，
估算，僅考慮除法個數

12, 18 ==> 12, 6 ==> 0, 6  ==> 兩次除法得 gcd  6
6, 24   ==>   6, 0                ==> 一次除法得 gcd  6
6, 30   ==>   6, 0                ==> 一次除法得 gcd  6
6, 48   ==>   6, 0                ==> 一次除法得 gcd  6

共 5 次除法

大大求 12 的所有非 1 因數 2 3 4 6 12  ==>  四次除法
用這些因數再和其它數比，一定超過 5 次除法

我給一例 10000, 10, 200, 25, 2，這例子會差更多
作者: chevylin0802    時間: 2017-6-6 11:51 PM

本帖最後由 chevylin0802 於 2017-6-6 11:53 PM 編輯
a333221 發表於 2017-6-6 11:46 PM
就大大給的例子「12， 18， 24， 30， 48」，
估算，僅考慮除法個數



你錯了，求因數時一定是用最小數去求因數，哪裡會拿1000去計算
所以差更多是差再哪裡？
當我傻到拿1000去求因數嗎？
作者: a333221    時間: 2017-6-6 11:57 PM

chevylin0802 發表於 2017-6-6 11:51 PM
你錯了，求因數時一定是用最小數去求因數，哪裡會拿1000去計算
所以差更多是差再哪裡？
當我傻到拿1000去 ...

那就是要再做排序的意思，那我再給一例 10000, 9009, 9999, 8888, 7777
只要數字大一點，就算是排序了，也沒有用啊，
而且這種演算法會有忽快忽慢、不穩定的問題　
作者: weirdococo    時間: 2017-6-7 12:10 AM

a333221 發表於 2017-6-6 11:57 PM
那就是要再做排序的意思，那我再給一例 10000, 9009, 9999, 8888, 7777
只要數字大一點，就算是排序了， ...

有就是說，還需要一個loop找出序列最小質（不需要sort)，在比較一下複雜度才是！
作者: weirdococo    時間: 2017-6-7 12:14 AM

本帖最後由 weirdococo 於 2017-6-7 12:26 AM 編輯
a333221 發表於 2017-6-6 11:57 PM
那就是要再做排序的意思，那我再給一例 10000, 9009, 9999, 8888, 7777
只要數字大一點，就算是排序了， ...

不要在吵了，我有空用一個count去比較複雜度就是了，去比較一下什麼時候（多少元素，數字大小範圍），那一個比較複雜就是了！
作者: ren1244    時間: 2017-6-7 01:53 AM

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

此外，要找出一個數的所有因數，光是這件事情就要跑很多迴圈。
而輾轉相除法卻能很快的找到最大公因數
找a,b的最大公因數：
輾轉相除法不會進行超過O(h)次除法，其中h是較小數b在十進位下的位數。

--  維基百科：輾轉相除法


作者: chevylin0802    時間: 2017-6-8 09:43 AM

本帖最後由 chevylin0802 於 2017-6-8 09:58 AM 編輯
ren1244 發表於 2017-6-7 01:53 AM
最小值未必是最少因數的數字
例如960跟991，雖然960比較小，但是因數卻很多

你告訴我
2跟32767的gcd的輾轉相除法需要跑多少次迴圈？
3跟32767用gcd的輾轉相除法需要跑多少次迴圈？
同樣的還有5, 7, 11
你是不是可以告訴我
輾轉相除法真的所向無敵？

要舉極端例子
大家都會找
不是只有你會而已

再來一點
輾轉相除法所得到的gcd是兩個數兩個數一組
如果這個數列有n個數列
第一個數字與之後的數列數字所求出來的gcd就會有n-1個gcd值
你告訴我這n-1個gcd值如果在最差的狀況下可不可能都完全相異？
這個時候你跟我講這n-1個gcd裏面到底哪一個才是n個數組裏的最大公因數？
另外這n-1個gcd數組有沒有可能還有最大公因數存在而且還不屬於這n-1個數組裏的數字？

不是我愛說
輾轉相除法看起來好像比較快
可是問題是它也很有可能需要經過數次的gcd求取過程
每一個都需要一次迴圈
它就會無限逼近於3階的Order
而不是表面上所得到的兩階
作者: ren1244    時間: 2017-6-8 02:40 PM

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

這是最差狀況了

另外，開版的作法不是分別兩兩去求最大公因數，再看這些公因數是不是一樣
而是利用：n+1個數字的gcd必為[(前n個數字的gcd)與(第n+1個數)的gcd]
例如，拿 5,7,11,13 來算
開版不是用
gcd(5,7)
gcd(7,11)
gcd(11,13)
然後再去看是不是一樣
他的作法是
gcd(gcd(gcd(5,7),11),13)
所以不會有你提到的相異或相同的問題



歡迎光臨 伊莉討論區 (http://a401.file-static.com/) Powered by Discuz!