Description

有一座五層的數字塔，第一層有 1 個數字，第二層有 2 個數字，以此類推
整座塔呈現三角形，每個數字只和下一個距離最近的兩個數字有樓梯連結
而且只能往下走，如下圖:

    1
   4 6
  6 9 3
 6 3 7 1
2 6 3 1 8

第二層的 4 只可以走到第三層的 6、9
第二層的 6 只可以走到第三層的 9、3

從第一層開始往下走
要如何讓經過的數字加起來等於指定的值
並且經過的層數是最少的
請將層數印出

 

hint:

#include 

#define INF 2147483647
#define SIZE 5

int Value;    /* 指定的數 */
int NoSolution;
int min;

/* 傳入即將進入第幾層、第幾個位置以及目前為止的加總 */
void goThroughTower(int tower[SIZE][SIZE], int level, int index, int sum)
{
    if (level + 1 > min || level + 1 > SIZE) {
        return;
    }
    else {
        /*
            ???
        */
    }
}

int main()
{
    int tower[SIZE][SIZE];
    int i, j;

    while (scanf("%d", &Value) != EOF) {
        NoSolution = 1;
        min = INF;

        for (i = 0; i < SIZE; ++i) {
            for (j = 0; j <= i; ++j)
                scanf("%d", &tower[i][j]);
        }

        goThroughTower(tower, 0, 0, 0);

        if (NoSolution == 1)
            printf("No solution\n");
        else
            printf("%d\n", min);
    }

    return 0;
}

Input

指定的數₁

塔₁

...

指定的數_N

塔_N

 

註: 塔內的數以及指定的數均為 1~2³¹-1 的正整數

N 為小於20的正整數

Output

層數₁

...

層數_N

 

註: 若無解則印 "No solution"

最後須加上換行

Sample Input  Download

Sample Output  Download

Tags

Discuss