1 #include "stdio.h" 2 #include "iostream" 3 #define MAXNUM 30 4 5 int FalseCoin(int coin[], int low, int heigh) 6 { 7 int i, sum1, sum2, sum3; 8 int re; 9 10 sum1 = sum2 = sum3 = 0; 11 if (low + 1 == heigh) 12 { 13 if (coin[low] < coin[heigh]) 14 { 15 re = low + 1; 16 return re; 17 } 18 else 19 { 20 re = heigh + 1; 21 return re; 22 } 23 } 24 if ((heigh - low + 1) % 2 == 0) //n是偶数 25 { 26 for (i = low; i < low+(heigh - low) / 2; i++) 27 { 28 sum1 = sum1 + coin[i]; 29 } 30 for (i = low + (heigh - low) / 2 + 1; i < heigh; i++) 31 { 32 sum2 = sum2 + coin[i]; 33 } 34 if (sum1 > sum2) 35 { 36 re = FalseCoin(coin, low + (heigh - low) / 2 + 1, heigh); 37 return re; 38 } 39 else 40 { 41 } 42 } 43 else 44 { 45 for (i = low; i < low+(heigh - low) / 2 - 1; i++) 46 { 47 sum1 = sum1 + coin[i]; 48 } 49 for (i = low + (heigh - low) / 2 + 1; i < heigh; i++) 50 { 51 sum2 = sum2 + coin[i]; 52 } 53 sum3 = coin[low + (heigh - low) / 2]; 54 if (sum1 > sum2) 55 { 56 re = FalseCoin(coin, low + (heigh - low) / 2 + 1, heigh); 57 return re; 58 } 59 else if (sum1 < sum2) 60 { 61 re = FalseCoin(coin, low, low + (heigh - low) / 2 - 1); 62 return re; 63 } 64 else 65 { 66 } 67 if (sum1 + sum3 == sum2 + sum3) 68 { 69 re = low + (heigh - low) / 2 + 1; 70 return re; 71 } 72 } 73 } 74 75 int main() 76 { 77 int coin[MAXNUM]; 78 int i, n; 79 int weizhi; 80 scanf("%d",&n); 81 for (i = 0; i < n; i++) 82 { 83 scanf("%d",coin[i]); 84 } 85 weizhi = FalseCoin(coin, 0, n - 1); 86 printf("在上述%d个银币中,第 %d 个银币是假的!\n",n,weizhi); 87 system("pause"); 88 return 0; 89 }