Skip to main content
誤字の修正
ソース リンク
cubick
  • 2.1万
  • 5
  • 27
  • 64

再帰関数を持ちい用いて回答するこの問題についての実装が理解できておりません。
再帰関数自体の理解は概要と簡単なフィボナッチ数列を求めるなどの実装は理解できている程度の状態です。
コードを注意深く読むと理解できるような当たり前のことなのかもしれませんが下記再帰関数がイメージできておりません。
※コード途中でデバックのような値の出力を試してみたりはしてみました。

再帰関数を持ちいて回答するこの問題についての実装が理解できておりません。
再帰関数自体の理解は概要と簡単なフィボナッチ数列を求めるなどの実装は理解できている程度の状態です。
コードを注意深く読むと理解できるような当たり前のことなのかもしれませんが下記再帰関数がイメージできておりません。
※コード途中でデバックのような値の出力を試してみたりはしてみました。

再帰関数を用いて回答するこの問題についての実装が理解できておりません。
再帰関数自体の理解は概要と簡単なフィボナッチ数列を求めるなどの実装は理解できている程度の状態です。
コードを注意深く読むと理解できるような当たり前のことなのかもしれませんが下記再帰関数がイメージできておりません。
※コード途中でデバックのような値の出力を試してみたりはしてみました。

Improve format
ソース リンク
PicoSushi
  • 4,959
  • 1
  • 10
  • 28

▼関数の実装例(java)
void dfs(int k, int res, int left) {
if (res < 0) return;
if (res == 0) {
for (int i = 0; i < k-1;i++) {
System.out.print(a[i]+ " ");
}
System.out.println(a[k-1]);
return;
}
for (int i=left; i >=1; i--) {
a[k] = i;
dfs(k+1, res-i, i);
}
}

void dfs(int k, int res, int left) {
        if (res < 0) return;
        if (res == 0) {
            for (int i = 0; i < k-1;i++) {
                System.out.print(a[i]+ " ");
            }
            System.out.println(a[k-1]);
            return;
        }
        for (int i=left; i >=1; i--) {
            a[k] = i;
            dfs(k+1, res-i, i);
        }
    }

▼呼び出し例
dfs(0, n, n);
※n

dfs(0, n, n); 

※nは5などの入力値

(5) (4, 1) (3, 2) (3, 1, 1) (2, 2, 1) (2, 1, 1, 1) (1, 1, 1, 1, 1)

(5) (4, 1) (3, 2) (3, 1, 1) (2, 2, 1) (2, 1, 1, 1) (1, 1, 1, 1, 1)
入力例1
5
 
出力例1
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

入力例1
5

出力例1
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
入力入力
入力は複数のデータセットからなる.n が 0 のとき入力が終了する.データセットの数は 5 を超えない.

入力例
5
5
0
出力例
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

入力例
5
5
0
出力例
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

▼関数の実装例(java)
void dfs(int k, int res, int left) {
if (res < 0) return;
if (res == 0) {
for (int i = 0; i < k-1;i++) {
System.out.print(a[i]+ " ");
}
System.out.println(a[k-1]);
return;
}
for (int i=left; i >=1; i--) {
a[k] = i;
dfs(k+1, res-i, i);
}
}

▼呼び出し例
dfs(0, n, n);
※nは5などの入力値

(5) (4, 1) (3, 2) (3, 1, 1) (2, 2, 1) (2, 1, 1, 1) (1, 1, 1, 1, 1)

入力例1
5

出力例1
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
入力
入力は複数のデータセットからなる.n が 0 のとき入力が終了する.データセットの数は 5 を超えない.

入力例
5
5
0
出力例
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

▼関数の実装例(java)

void dfs(int k, int res, int left) {
        if (res < 0) return;
        if (res == 0) {
            for (int i = 0; i < k-1;i++) {
                System.out.print(a[i]+ " ");
            }
            System.out.println(a[k-1]);
            return;
        }
        for (int i=left; i >=1; i--) {
            a[k] = i;
            dfs(k+1, res-i, i);
        }
    }

▼呼び出し例

dfs(0, n, n); 

※nは5などの入力値

(5) (4, 1) (3, 2) (3, 1, 1) (2, 2, 1) (2, 1, 1, 1) (1, 1, 1, 1, 1)
入力例1
5
 
出力例1
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

入力
入力は複数のデータセットからなる.n が 0 のとき入力が終了する.データセットの数は 5 を超えない.

入力例
5
5
0
出力例
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
ソース リンク

再帰関数について

再帰関数を持ちいて回答するこの問題についての実装が理解できておりません。
再帰関数自体の理解は概要と簡単なフィボナッチ数列を求めるなどの実装は理解できている程度の状態です。
コードを注意深く読むと理解できるような当たり前のことなのかもしれませんが下記再帰関数がイメージできておりません。
※コード途中でデバックのような値の出力を試してみたりはしてみました。

お手数ですが噛み砕いて解説いただければ幸いです。

また、再帰関数を用いる問題はどれも理解が難しく感じることが多いです。
再帰関数を分かる、実装できるようになるためにするとよいことなどあればご教示いただけると助かります。

▼関数の実装例(java)
void dfs(int k, int res, int left) {
if (res < 0) return;
if (res == 0) {
for (int i = 0; i < k-1;i++) {
System.out.print(a[i]+ " ");
}
System.out.println(a[k-1]);
return;
}
for (int i=left; i >=1; i--) {
a[k] = i;
dfs(k+1, res-i, i);
}
}

▼呼び出し例
dfs(0, n, n);
※nは5などの入力値

▼問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0507

同じ大きさの正方形の紙が n 枚ある.これらの紙の下部を水平に揃えて何列かに並べる.ただし,隣り合う列は左側が右側より低くならないように並べなければならない.例えば, n = 5 のときは,次のような 7 通りの並べ方が可能である.

これらを,各列に並んだ正方形の個数の列で表すことにする.例えば, n = 5 の ときは,それぞれ,

(5) (4, 1) (3, 2) (3, 1, 1) (2, 2, 1) (2, 1, 1, 1) (1, 1, 1, 1, 1)

と表わされる.

n を入力したとき, 辞書式順序で全て出力するプログラムを作成せよ.n ≤30 とする.ただし, 辞書式順序とは2つの並べ方 (a1, a2 , ..., as) が並べ方 (b1, b2, ..., bt ) に対して, a1 > b1 または, ある整数 i > 1 が存在して a1 = b1 , ..., ai-1 = bi-1 かつ ai > bi が成り立つとき (a1, a2, ..., as) が (b1 , b2, ..., bt) より先に出力されるように並べることである.

入力データ は 1 行からなり,1 行目に n が書かれている.

出力には並べ方を辞書式順序で 1 行に1通りずつ書き最後に改行を入れること. 並べ方は (a1, a2, ..., as) の出力は整数 a1, a2, . . . , as をこの順番に空白で区切って出力すること.

入力例1
5

出力例1
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
入力
入力は複数のデータセットからなる.n が 0 のとき入力が終了する.データセットの数は 5 を超えない.

出力
データセットごとに、辞書式順序で全て出力する.

入力例
5
5
0
出力例
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

参照:AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/