1

再帰の理解に問題があり、次の問題を解決できませんでした。

入力: オブジェクト (fe フィールド) と整数 n

望ましい出力: n フィールドのリスト

単純なオブジェクトを 2 つの部分に分割するメソッドを作成しましたが、正常に動作します。しかし、再帰を処理できませんでした。

createFields(field, 5) の最小限の例:

Input:
**********************************
*                                *
*                                *
*                                *
**********************************
1st iteration (after divide(field))
**********************************
*                *               *                
*                *               *
*                *               *
**********************************
2nd iteration 
**********************************
*                *               *                
**********************************
*                *               *
**********************************
3rd last iteration 
**********************************
*       *        *               *                
**********************************
*                *               *
**********************************

これで私を助けてもらえますか？

ありがとうございました！

4

3 に答える 3

0

現在の関数を繰り返し使用できるはずです。1つのフィールドから始めて、2つのフィールドのリストを提供する関数を呼び出します。それらを一時リストに追加します。次に、これらのフィールドでsplit関数を呼び出します。特定のサイズのフィールドが不足したら、小さなフィールドを分割することから始めます。

以下のコードは、サイズxおよびx / 2のn個のフィールド（およびに格納されている）を提供するはずですfields。fields2

Field startField=...
ArrayList<Field> fields=new ArrayList<Field>();
ArrayList<Field> fields2=new ArrayList<Field>();
fields.add(startField);
nrFields=1;
outerlabel:
while(nrFields<n){
    while((!fields.isEmpty()){
        Field fieldToSplit = fields.remove(0);
        List<Field> splitFields=splitt(fieldToSplit);
        fields2.addAll(splitFields);
        nrFields++;
        if(nrFields==n)break outerlabel;
    }
    fields=fields2;
    fields2=new ArrayList<Field>();

}
于 2013-03-14T22:07:59.193 に答える
0

私のコメントの 1 つに続いて、非再帰的なソリューションの提案を (疑似コードで) 示します。

split(field, n) {
    queue = new Queue()
    queue.addLast(field)
    while (queue.size() < n) {
        f = queue.removeFirst()
        pair = f.split()
        queue.addLast(pair.a)
        queue.addLast(pair.b)
    }
    return queue

}

于 2013-03-14T22:19:55.233 に答える
0

アルゴリズムの高レベルの説明は次のようになります。

divide_recursively (fields, n)
args:
    input/output fields : List of fields
    input n : integer (number of fields)
precondition:
    head of list is largest available field
body:
    if (fields.size() == n) return
    f = fields.front()
    fields.pop_front()
    fsplit[] = split_field(f)
    fields.push_back(fsplit[0])
    fields.push_back(fsplit[1])
    divide_recursively(fields, n)

このアルゴリズムではsplit_field、 が入力を正確に半分に分割する限り、前提条件は常に満たされます。

アルゴリズムは、質問のタグの 1 つであるため、再帰を使用して提示されます。これは末尾再帰を使用します。多くのコンパイラ/インタプリタは、末尾呼び出しの最適化の特殊なケースとして通常のループに変換します。

上記のアルゴリズムは貪欲なアプローチを使用しています。以下は、分割統治法を使用する代替アルゴリズムです。

divide_recursively (fields, n)
precondition:
    fields contains exactly one element
body:
    if (n == 1) return
    f = fields.front()
    fields.pop_front()
    fpslit[] = split_field(f)
    subfields1 = new list + fsplit[0]
    subfields2 = new list + fsplit[1]
    divide_recursively(subfields1, n/2)
    divide recursively(subfields2, n - n/2)
    fields = subfields1 + subfields2
于 2013-03-14T22:04:40.503 に答える