※ 引述《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)