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/

3 件の回答 3

2

文章題がうだうだ長いですが要するに 「左≧右」 を満たすような数列を得るという課題ですよね。

再帰は次のように考えていくと理解しやすいと思います。

1.再帰の途中
・今この状態である→次はどうする

2.再帰の終了
・この条件が成立したら終了

提示例題を簡単に説明するなら

再帰の途中:
・今注目中の位置より左側は確定済みなので、考慮不要
・今注目中の位置にn個を置いた→題意上、次はn個以下1個以上が置けるので、置いて1つ右に行く操作を再帰で実施
再帰の終了:
・置けなかったら表示せず終了 (res<0 はこれ:残り数が足らない)
・正しく置ききったら表示して終了 (res==0 はこれ:残0)
・1個を置いたらその次は終了 (for が終わる)

オイラが再帰を「自分のものにした」と確信したのは二分探索木の通り掛け順表示を理解したときでした。まあ当時だから struct を使って実装していたわけですが

再帰の途中:
・左を表示
・自分を表示
・右を表示
と再帰すると「左を表示」は自動的に「左要素をすべて表示」になる(右も同様)。二分探索木の性質からこれだけで昇順表示となる。

再帰の終了:
・自分自身が null

この通り掛け順表示は簡単にはループに変換できない点でも再帰の題材としてよいと思います。

数学的帰納法が理解できれば再帰も理解できるでしょう(帰納法の場合は「最初」を証明する点が異なります)。

2

解答のソースコードのイメージを教えて欲しいという質問だと解釈したので、ソースコードにコメントを付ける形で書きます。
ざっくりいうと、k番目に何個置くかを決定して、それ以降の並べ方はk+1番目以降に丸投げして、残りがちょうど0個になったときに出力するイメージです。

//k:ブロック列の長さ
//res:残りのブロックの数
//left:1つ前の場所に積み上げたブロック数(=これ以降の場所で積み上げられるブロックの高さの最大数)
//a[]:今のブロックの並べ方が入る配列。a[i]にはi番目の場所の積み上げた高さが入る。

void dfs(int k, int res, int left) {
        if (res < 0) return;//残ったブロックの数が0未満なら何も出来ないので終了
        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;//k番目にi個のブロックを積む
            dfs(k+1, res-i, i);//k+1番目はres-i個のブロックが残り、i個以下の高さまで積める
        }
    }
1

このように書くと分かりやすいですか?paiza.ioで実行させています。restは「残り」という意味で、posは「位置」です。

import java.util.*;

public class Main {

    private int a[]; // 並べ方(a1, ..., as)

    public Main(int size) {
        a = new int[size+1]; // a0はダミー。a1 ... asを使用する
        a[0] = size;
    }

    public void dfs(int rest, int pos) {
        // 残りの正方形の数が0のとき、現在の並べ方を表示する
        if (rest == 0) {
            for (int i = 1; i < pos - 1; i++)
                System.out.print(Integer.toString(a[i]) + " ");
            System.out.println(Integer.toString(a[pos - 1]));
            return;
        }
        // そうでなければ、正方形を現在の位置に積み上げて右の位置に移る
        for (int i = Math.min(rest, a[pos-1]); i >= 1; i--) {
            a[pos] = i;
            dfs(rest - i, pos + 1);
        }
    }

    public static void main(String[] args) throws Exception {
        // Your code here!

        (new Main(5)).dfs(5, 1);
    }
}

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。