T130870 找出次品
題目背景
題目描述
給定一串小球，其中有一個是次品（次品會輕一些），正常小球用1表示，次品小球用0表示，要求將次品小球的編號找出（編號從11開始） 要求：
- 需定義一個天平函式int balance(bool *a, int a_count, bool *b, int b_count)，a和b均為小球陣列，a_count、b_count為兩陣列所含小球的數量，若a重，則回傳1；b重，則回傳-1；a,b等重，回傳0，
- 利用天平函式，設計遞回演算法來進行題目給出的小球次品的尋找，
輸入格式
第一行一個整數n，表示小球的數量，
第二行n個整數，其中1個為0，其余n-1個為1，請找出次品的編號，
輸出格式
一個整數(1…n)，表示次品的位置，
輸入輸出樣例
輸入 #1
5
1 1 1 0 1
輸出 #1
4
說明/提示
1≤n≤1,000
參考解答：
#include<iostream>
using namespace std;
int find(int* weight, int left, int right) {//首次傳入的left為陣列最左邊的一個下標，首次傳入的right為陣列最右邊的一個下標，回傳值為次品所對應的陣列下標
if (left + 1 == right) {//如果僅有兩個球 或 遞回演算法進行到僅剩兩個球的時候
return weight[left] < weight[right] ? left : right;
}
int mid = left + (right - left) / 2;//中間位置的小球
int Lsum = 0, Rsum = 0;//Lsum表示左側天平所有小球的質量，Rsum表示右側天平所有小球的質量
if ((right - left + 1) % 2 == 0) {//如果有（大于2的)偶數個球
for (int i = left; i <= mid; ++i) {
Lsum += weight[i];
}
for (int i = mid + 1; i <= right; ++i) {
Rsum += weight[i];
}
return Lsum < Rsum ? find(weight, left, mid) : find(weight, mid + 1, right);//回傳質量較輕的一組進行遞回
}
else {//如果有（大于1的）奇數個球
for (int i = left; i <= mid-1; ++i) {
Lsum += weight[i];
}
for (int i = mid + 1; i <= right; ++i) {
Rsum += weight[i];
}
//此時表示將中間小球拿出,剩下偶數個小球,Lsum為mid左側所有小球的質量，Rsum為mid右側所有小球的質量
if (Lsum == Rsum)return mid;//如果左右兩側小球的質量相同，回傳中間位置小球的下標
else return Lsum < Rsum ? find(weight, left, mid-1) : find(weight, mid + 1, right);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int* weight = new int[n];
for (int i = 0; i < n; ++i) {
cin >> weight[i];
}
if (n == 1) {
cout << 1;//如果僅有一個球，默認此球即為次品
}
else cout << find(weight, 0, n - 1) + 1 << endl;
delete[]weight;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/266197.html
標籤：C++