Re: [問題] 演算法...

看板C_and_CPP (C/C++)作者yauhh (喲)時間16年前 (2009/06/07 18:48)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串2/2 (看更多)

※ 引述《meteor1211 (小希)》之銘言： : Counterfeit Coin的問題， : 以下是問題 : Write a pseudocode for the divide-into-three algorithm for : the fake-coin problem.(make sure that your algorithm handles : properly all values of n,not only that are multiples of 3). : 每次都知道他應該要怎麼做... : 可是遇到要寫成程式相關的東西就腦袋卡住了... : 想請問有人可以解救嗎>< : 謝謝大家!!! 1. 先有個稱重函數. 呼叫 weigh(array, count_of_array) 可計算 array 的重量總和. 參考程式碼: int weigh(int *a, int n) { int i, sum = 0; for (i=0; i<n; i++) sum += a[i]; return sum; } 2. 然後把任何幣值資料分成三份,找包含偽幣的陣列: 令有陣列為 a[][] = {{1,1,1}, {1,2,1}, {1,1}}, 呼叫 array_counterfeit(a, 3) 可取得包含偽幣陣列的位置, 0或1或2. 第二個參數是前二份數量相同硬幣的各自數量. 參考程式碼: //輸入三個陣列,指出哪個陣列有偽幣 int array_counterfeit(int **a, int n2) { int w0 = weigh((*a)[0], n2); int w1 = weigh((*a)[1], n2); if (w0 == w1) return 2; else if(w0 > w2) return 1; else return 0; } 3. 找偽幣程式中,將所有幣值資料整理成三份,第一份跟第二份相等量,第三份比其他二份不是少一項就是少兩項. 找偽幣程式是遞迴程式,找到其中一份包含偽幣,就用同樣的方法找那一份中的偽幣. 最後傳回偽幣所在位置. 令有幣值陣列 d = {1, 1, 1, 1, 1, 1, 2}, 呼叫 counterfeit(a, 7, 0) 可取得偽幣在陣列 a 的位置. 第三個參數是遞迴要用的,指第一個參數 a 陣列對全域幣值陣列 d 陣列的偏移位置. 參考程式碼: int counterfeit(int *a, int n, int offset) { int (*a)[3]; int n2 = n, i; int cai, ci; while (n2 % 3 != 0) n2++; n2 = n2 / 3; (*a)[0] = (int*)malloc(sizeof(int)*n2); (*a)[1] = (int*)malloc(sizeof(int)*n2); (*a)[2] = (int*)malloc(sizeof(int)*(count_inputs % n2)); for (i=0; i<n2; i++) { a0[i] = inputs[i]; a1[i] = inputs[n2+i]; } for (i=0; i<(count_inputs % n2); i++) a2[i] = inputs[n2+n2+i]; cai = array_counterfeit(&(*a), n2); for (i=0; i<3; i++) if (cai != i) free((*a)[i]); if (cai == 2) { if (count_inputs % n2 == 1) ci = 0; else ci = counterfeit((*a)[cai], count_inputs % n2, n2 + n2); } else if (cai == 1) { if (n2 == 1) ci = 0; else ci = counterfeit((*a)[cai], n2, n2); } else { if (n2 == 1) ci = 0; else ci = counterfeit((*a)[cai], n2, 0); } free((*a)[cai]); return (offset + ci); } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.231.65.57 ※ 編輯: yauhh 來自: 61.231.65.57 (06/07 18:51)