7-2 解答

• 利用遞迴，一次填一個符號
• 每次填完N個符號才輸出一個運算式

提示

#include<iostream>
using namespace std;

int N;
int num[100]; //0~N-1
char op[100];  //1~N-1

void dfs( int now )
{
    /* TODO

    if 做到最後一個數字{
        印出這個組合的結果,ex:3 +2 +4 +1 +7
    } else {
        針對每個符號進行下一步的計算，以+號為例
        op[now] = '+';
        dfs( now+1 );

        -號 與 *號 的部分請自行完成...
    }

    */    
}

int main()
{
    int i;

    cin >> N;
    for( i=0 ; i<N ; i++ )
        cin >> num[i];

    dfs( 1 ); //從第1個數字開始

    return 0;
}

解答

#include<iostream>
using namespace std;

int N;
int num[100]; //0~N-1
char op[100];  //1~N-1

void dfs( int now )
{
    // 做到最後一個數字
    if( now >= N )
    {
        int i;
        cout << num[0];
        for( i=1 ; i<N ; i++ )
            cout << " " << op[i] << num[i];
        cout << endl;
    }
    else
    {
        // 用遞迴的方式實作DFS
        op[now] = '+';
        dfs( now+1 );

        op[now] = '-';
        dfs( now+1 );

        op[now] = '*';
        dfs( now+1 );
    }
}

int main()
{
    int i;

    cin >> N;
    for( i=0 ; i<N ; i++ )
        cin >> num[i];

    dfs( 1 ); //從第1個數字開始

    return 0;
}