1

## 【已交】學校C++作業，快還能不能更快?

(所以每個寶藏有個別的代號(1、2、3...)和價值)

Sample input/output:
Welcome to NCU-EE Mediation Committee
Please enter the number of treasures or -1 to end the program: 10
Please enter the size of backpack: 4
Treasure 1 (\$): 1
Treasure 2 (\$): 2
Treasure 3 (\$): 3
Treasure 4 (\$): 4
Treasure 5 (\$): 5
Treasure 6 (\$): 6
Treasure 7 (\$): 7
Treasure 8 (\$): 8
Treasure 9 (\$): 9
Treasure 10 (\$): 0
……Distribution……Distribution……Distribution……
YES
People 1 : Treasure 1 Treasure 5 Treasure 9
People 2 : Treasure 3 Treasure 4 Treasure 8 Treasure 10
People 3 : Treasure 2 Treasure 6 Treasure 7
Thanks and Come Again
Welcome to NCU-EE Mediation Committee
Please enter the number of treasures or -1 to end the program: 4
Please enter the size of backpack: 1
Treasure 1 (\$): 2
Treasure 2 (\$): 2
Treasure 3 (\$): 4
Treasure 4 (\$): 4
……Distribution……Distribution……Distribution……
NO
Thanks and Come Again
Welcome to NCU-EE Mediation Committee
Please enter the number of treasures or -1 to end the program: -1
Bye-Bye

``````#include <iostream>

using namespace std;

int nums,siz;

bool toequal(int [],int);
int average(int [],int);
bool compare(int [],int,int);
bool distribute(int [],int,int,int,int,int,int [],int [],int [],int);

int main()
{
str:cout << "***Welcome to NCU-EE Mediation Committee***" << endl;
cout << "Please enter the number of treasures or -1 to end the program: ";
cin >> nums;
cout << "Please enter the size of backpack: ";
cin >> siz;

int treasurevalue[nums],treasuresum=0,avg,one[nums],two[nums],three[nums];

for(int i=0;i<nums;i++)
{
cout << "Treasure " << i+1 << "(\$): ";
cin >> treasurevalue[i];
}
cout << "……Distribution……Distribution……Distribution……" << endl;

for(int i=0;i<nums;i++)
{
treasuresum += treasurevalue[i];
}

if(!toequal(treasurevalue,nums))
{
cout << "NO" << endl;
goto str;
}
else
{
avg=average(treasurevalue,nums);

if(!compare(treasurevalue,nums,avg))
{
cout << "NO" << endl;
goto str;
}
}
if(distribute(treasurevalue,1,0,0,0,0,one,two,three,avg))
{
goto str;
}
else if(distribute(treasurevalue,2,0,0,0,0,one,two,three,avg))
{
goto str;
}
else if(distribute(treasurevalue,3,0,0,0,0,one,two,three,avg))
{
goto str;
}
else
{
cout << "NO" << endl;
goto str;
}
}
bool toequal(int treasure[],int nums)
{
int sum=0;
for(int i=0;i<nums;i++)
{
sum+=treasure[i];
}
if(sum%3!=0)
{
return false;
}
else
{
return true;
}
}
int average(int treasure[],int nums)
{
int sum=0;
for(int i=0;i<nums;i++)
{
sum+=treasure[i];
}
return sum/3;
}

bool compare(int treasure[],int nums,int avg)
{
int themax=treasure[0];
for(int i=1;i<nums;i++)
{
if(treasure[i]>themax)
{
themax=treasure[i];
}
}
if(themax<=avg)
{
return true;
}
return false;
}
bool distribute(int treasurevalue[],int man,int treasure,int counter1,int counter2,int counter3,int one[],int two[],int three[],int avg)
{
if(counter1>siz)
{
return false;
}
else if(counter2>siz)
{
return false;
}
else if(counter3>siz)
{
return false;
}

if(treasure == nums)
{
int  value1=0,value2=0,value3=0;
for(int i=0;i<counter1;i++)
{
value1 += treasurevalue[one[i]];
}
if(value1>avg)
{
return false;
}
for(int i=0;i<counter2;i++)
{
value2 += treasurevalue[two[i]];
}
if(value2>avg)
{
return false;
}
for(int i=0;i<counter3;i++)
{
value3 += treasurevalue[three[i]];
}
if(value3>avg)
{
return false;
}
if(value1 == value2&&value2 == value3)
{
cout << "People 1: ";
for(int i=0;i<counter1;i++)
{
cout << one[i]+1 << " ";
}
cout << endl;
cout << "People 2: ";
for(int i=0;i<counter2;i++)
{
cout << two[i]+1 << " ";
}
cout << endl;
cout << "People 3: ";
for(int i=0;i<counter3;i++)
{
cout << three[i]+1 << " ";
}
cout << endl;
return true;
}
}
if(man==1)
{
one[counter1] = treasure;
counter1++;
}
if(man==2)
{
two[counter2] = treasure;
counter2++;
}
if(man==3)
{
three[counter3] = treasure;
counter3++;
}
if(distribute(treasurevalue, 1 ,treasure+1,counter1,counter2,counter3,one,two,three,avg))
{
return true;
}
else if(distribute(treasurevalue, 2 ,treasure+1,counter1,counter2,counter3,one,two,three,avg))
{
return true;
}
else if(distribute(treasurevalue, 3 ,treasure+1,counter1,counter2,counter3,one,two,three,avg))
{
return true;
}
}
``````
``````#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

//Set these two variable as global variable because they will use in main function and others one
int nums, siz; //Nums to get how many treasure there,siz to get how many treasure their backpacks can carry
//Set function
bool toequal(int [], int);//To decide whether those treasure can be equal
int average(int [], int);//Get the average of the value of those treasures
bool compare(int [], int, int);//To decide whether the value of the most valuable treasure is more than the average
bool distribute(int [], int, int, int, int, int [], int [], int [], int);//To distribute those treasures into their backpacks

int main()
{
str:cout << "***Welcome to NCU-EE Mediation Committee***" << endl;
cout << "Please enter the number of treasures or -1 to end the program: ";
cin >> nums;
cout << "Please enter the size of backpack: ";
cin >> siz;

int treasurevalue[nums], treasuresum = 0, avg, one[nums], two[nums], three[nums];

for(int i=0; i<nums; i++)
{
cout << "Treasure " << i+1 << "(\$): ";
cin >> treasurevalue[i]; //Input the value of treasures into array
}
cout << "......Distribution......Distribution......Distribution......" << endl;

//Use toequal and compare function to decide whether those treasures are we want
for(int i=0; i<nums; i++)
{
treasuresum += treasurevalue[i];
}
if(!toequal(treasurevalue, nums))
{
cout << "NO" << endl;
goto str;//Can't be equal, goto the start
}
else
{
avg = average(treasurevalue, nums);//Get average
if(!compare(treasurevalue, nums, avg))
{
cout << "NO" << endl;
goto str;//The value of the most valuable treasure is more than average, goto the start
}
}

for(int result=0; result < pow(3,nums); result++)//There are at most 3^(the number of treasures) results, to try every result
{
//Initialize their backpacks
one[nums] = {0};
two[nums] = {0};
three[nums] = {0};

if(distribute(treasurevalue, result, 0, 0, 0, one, two, three, avg))
{
goto str; //Those treasures have been distribute, stop the loop and goto the start
}
}

}
//------------------------------------------------------function's body----------------------------------------------------------//
bool toequal(int treasure[], int nums)
{
int sum = 0;
for(int i=0; i<nums; i++)
{
sum += treasure[i];//Add up all the value of treasures
}
if(sum % 3 != 0)
{
return false; //The value of treasures can't be equal because it can't be divisible
}
else
{
return true;
}
}
//------------------------------------------------------function's body----------------------------------------------------------//
int average(int treasure[], int nums)
{
int sum = 0;
for(int i=0; i<nums; i++)
{
sum += treasure[i];
}
return sum / 3; //Return average into variable avg
}
//------------------------------------------------------function's body----------------------------------------------------------//
bool compare(int treasure[], int nums, int avg)
{
int themax = treasure[0];
for(int i=1; i<nums; i++)
{
if(treasure[i] > themax)//Compare the value of treasures respectively, choose the most variable one
{
themax = treasure[i];
}
}
if(themax <= avg)
{
return true;
}
return false;//The value of the most variable one is more than average
}
//------------------------------------------------------function's body----------------------------------------------------------//
bool distribute(int treasurevalue[], int result, int counter1, int counter2, int counter3, int one[], int two[], int three[], int avg)
{
//Set value1 as the value sum of people1's treasures, value2 for people2, value3 for people3
int value1=0, value2=0, value3=0;
//Covert the variable "result" into ternary number system as 10-digits that every digit corresponds to the number of treasures
for(int i=0; i<nums; i++)
{
if(result % 3 == 0)//The number of digit "0" corresponds to people1
{
one[counter1++] = i;//Put treasure j into people1's backpacks
}
if(result % 3 == 1)//The number of digit "1" corresponds to people2
{
two[counter2++] = i;//Put treasure j into people2's backpacks
}
if(result % 3 == 2)//The number of digit "2" corresponds to people3
{
three[counter3++] = i;//Put treasure j into people3's backpacks
}
result /= 3; //To next digit which corresponds to treasure
}
//To add up all the value of people1's treasure
for(int i=0; i<counter1; i++)
{
value1 += treasurevalue[one[i]];
}
if(value1 > avg)
{
return false;//All the value of people1's treasure is more than average
}
//To add up all the value of people2's treasure
for(int i=0; i<counter2; i++)
{
value2 += treasurevalue[two[i]];
}
if(value2 > avg)
{
return false;//All the value of people2's treasure is more than average
}
//To add up all the value of people3's treasure
for(int i=0; i<counter3; i++)
{
value3 += treasurevalue[three[i]];
}
if(value3 > avg)
{
return false;//All the value of people3's treasure is more than average
}
if(value1 == value2 && value2 == value3)//If the value of their treasures is equal respectively, print the result and return true
{
cout << "YES" << endl;
cout << "People 1: ";
for(int i=0; i<counter1; i++)
{
cout << "Tresure " << setw(2) << one[i] + 1 << " ";
}
cout << endl << "People 2: ";
for(int i=0; i<counter2; i++)
{
cout << "Tresure " << setw(2) << two[i] + 1 << " ";
}
cout << endl << "People 3: ";
for(int i=0; i<counter3; i++)
{
cout << "Tresure " << setw(2) << three[i] + 1 << " ";
}
cout << endl;
return true;
}
}
``````

marlin12 iT邦研究生 5 級 ‧ 2020-12-07 17:50:29 檢舉

aa232399 iT邦新手 5 級 ‧ 2020-12-08 20:45:43 檢舉
To marlin12:先謝謝您花時間看我的code，也感謝您的回覆，然後因為struct和class還未學習，所以也無法用在此次作業中，不過我會繼續精進的，感謝!!!

### 2 個回答

4

iT邦研究生 2 級 ‧ 2020-12-07 11:57:03

bool toequal(int [],int);
int average(int [],int);
bool compare(int [],int,int);

``````for(int i=0;i<nums;i++) {
cout << "Treasure " << i+1 << "(\$): ";
cin >> treasurevalue[i];
treasuresum += treasurevalue[i]; //順便算總和
if(maxVal < treasurevalue[i]) { //順便取最大值
maxVal = treasurevalue[i];
}
}
avg=treasuresum/3; //算平均
if(
treasuresum % 3 == 0 || //檢查平均值是否為整數
maxVal > avg //單一寶物最大值不能大於平均值
) {
cout << "NO" << endl;
goto str; //現在不推薦用 goto 了，不過還沒看完就先照原本放著
}
``````

#### 後續補充

distribute 函式中，直到 `if(treasure == nums)` 才開始計算每個人分別拿到多少價值的寶藏。

``````if(man==1)
{
oneSum += treasurevalue[treasure]; //直接計算已取得總價值
if(oneSum > avg) {
oneSum -= treasurevalue[treasure]; //還原
return false; //中斷後面繼續分配
} else {
one[counter1] = treasure;
counter1++;
}
}
//後面 man==2 跟 man==3 一樣這樣處理
``````

（細節你再自己調整）

aa232399 iT邦新手 5 級 ‧ 2020-12-08 20:46:05 檢舉

0
marlin12
iT邦研究生 5 級 ‧ 2020-12-08 22:44:37