0

どうすれば手配できますか。数の...配置から形成された各新しい数が前の最大値から最大で1の差を持つように。

たとえば、入力がk = 1の場合、出力は1になります

k = 2の場合、出力は次のようになります。11、12 2,1は間違っています。これは、左端が常に1である必要があるためです。

k = 3の場合、出力は111、112、121、122、123です。

k = 4の場合：1111,1112,1121,1122,1123,1212,1211,1213,1223,1221、1222、1233、1234

1423は間違ったdiffb/w1と4は3です。1243は間違ったdiffb/w2と4は2です。

可能であれば、DPを使用してこれを行うにはどうすればよいですか？

これは上記の質問に対する解決策の1つです...誰かが私がこのコードを理解するのを手伝ってくれますか...事前に感謝します...

public class MaxOneDiff {

    public static void main(String[] args) {
        int k = 4;
        getList(k);
    }

    public static void getList(int k) {
        int arr[] = new int[k];
        int index = 0;
        printRecList(k, arr, index, k);
    }

    public static void printRecList(int k, int arr[], int index, int range) {
        if (k == 0) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]);
            }
            System.out.println();
        } else {
            for (int i = 1; i <= range; i++) {
                if (index == 0) {
                    arr[index] = i;
                    printRecList(k - 1, arr, index + 1, range);
                } else {
                    int t = arr[index-1]-i;
                    t = t > 0 ? t : -t;
                    if (t < 2) {
                        arr[index] = i;
                        printRecList(k - 1, arr, index + 1, range);
                    }
                }
            }
        }
    }
}
4

1 に答える 1

0

簡単な部分から始めましょう：

public static void getList(int k) {
    int arr[] = new int[k];
    int index = 0;
    printRecList(k, arr, index, k);
}

これは、再帰リストの印刷機能のヘルパーであり、初期のものを設定するだけです。

public static void printRecList(int k, int arr[], int index, int range) {

これは再帰関数であり、2つの主要な部分が含まれている必要があります（実際に含まれています）。

  1. 基本ケース（ここでは、k == 0の場合）
  2. 何かを行い、問題をより小さな問題に減らし、再発する非基本的なケース。

規範事例：

    if (k == 0) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println();

k == 0の場合、配列内の数値を左から右に出力し、最後に改行を入れます。

非ベースケース:(より複雑な部分）

    else {
        for (int i = 1; i <= range; i++) {
            if (index == 0) {
                arr[index] = i;
                printRecList(k - 1, arr, index + 1, range);
            } else {
                int t = arr[index-1]-i;
                t = t > 0 ? t : -t;
                if (t < 2) {
                    arr[index] = i;
                    printRecList(k - 1, arr, index + 1, range);
                }
            }
        }
    }

「i」は1から範囲になります。

ヘルパー関数はこれをindex=0で呼び出すため、再帰の最初/最上位レベルは、配列の最初の要素（要素0）をiに設定し、再帰メソッドを呼び出すことで構成されます。

再帰呼び出しでインデックス==0になることは二度とないので、else句に注意を向けます。

ここでは、値iを次の要素に割り当てることができるかどうかを知りたいので、elementToLeftからiを引いた絶対値が2以上であるかどうかを確認します。

'i'がその位置に割り当てるのに有効である場合（つまり、左側の値とは1または0だけ異なり、'i'はforループからの範囲までしか取得できません）。

次にそれを割り当て、次の位置を確認します。

これは、配列の最後の要素に到達したときに終了します。

于 2012-07-27T04:59:53.167 に答える