iT邦幫忙

1

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

題目是這樣的:
有三個人要分寶藏,我要寫程式幫他們判斷寶藏能不能平均分給他們,
程式一開始要先依序輸入寶藏個數,再輸入背包大小,再個別輸入每個寶藏的價值。
(所以每個寶藏有個別的代號(1、2、3...)和價值)
如果不能平分,或平分完有人超過背包大小,就顯示"NO",否則就顯示"YES",並列出三個人包包塞了哪幾個寶藏。
然後重複執行直到在輸入寶藏那邊打上-1,停止程式。
要求:
用iteration的方式和recursion的方式各寫一次。

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

我解開了recursion的部分了! (更新:也解開iteration的部分了)
用窮舉法來解,現在在想有沒有方法可以讓這程式跑得更快速?
目前有用"如果該背包放超過平均數就return false來讓程式跳過該次選擇"。

#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 檢舉
除了用上cin和cout以外,基本上這是C程式,而不是C++程式

這種方法有點[土炮],如果多幾個寶藏和人去分,怎麽辦?

為何不用struct或者class去把相關的變數和函式組合起來?
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 一樣這樣處理

以上只是描述概念,實際使用可能要連帶調整一些地方,例如 distribute 最後面可能要加上 return false;
(細節你再自己調整)

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

謝謝您看完整篇code,感激不盡!! 我下意識把判斷超過平均的放在分完寶藏那裏,沒發現這邊可以做更改,真的幫大忙了!還有前面的總和那邊您的寫法真的簡化很多空間,我會多學學的!

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

我要發表回答

立即登入回答