Skip to main content
位置変更
ソース リンク
Liamovwv
  • 177
  • 2
  • 9

解答のソースコードのイメージを教えて欲しいという質問だと解釈したので、ソースコードにコメントを付ける形で書きます。
ざっくりいうと、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段進めて小問題に分割してるイメージです。

解答のソースコードのイメージを教えて欲しいという質問だと解釈したので、ソースコードにコメントを付ける形で書きます。

//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段進めて小問題に分割してるイメージです。

解答のソースコードのイメージを教えて欲しいという質問だと解釈したので、ソースコードにコメントを付ける形で書きます。
ざっくりいうと、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個以下の高さまで積める
        }
    }
ソース リンク
Liamovwv
  • 177
  • 2
  • 9

解答のソースコードのイメージを教えて欲しいという質問だと解釈したので、ソースコードにコメントを付ける形で書きます。

//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段進めて小問題に分割してるイメージです。