6

私はこのコードで立ち往生しています：

問題: 子供は一度に n 段の階段を 1 段、2 段、または 3 段飛び越えることができます。n の値を与えて、彼が階段を上ることができる順序のすべての順列を出力してください。

これは私のコードです:

    public class HoppingLad
    {
        int count;
        void hop(int n,int present)
        {
            if(n==present)
            {
                count++;
                System.out.println("\nFinished type "+count+" climbing.\n");
            }
            else
            {
                if((n-present)>=1)
                {
                    System.out.print("\nClimbed 1 step.\nReached "+(present+1)+"   ");
                    hop(n,present+1);
                }
                if((n-present)>=2)
                {
                    System.out.print("\nClimbed 2 step. \nReached "+(present+2)+"   ");
                    hop(n,present+2);
                }
                if((n-present)>=3)
                {
                    System.out.print("\nClimbed 3 step. \nReached "+(present+3)+"   ");
                    hop(n,present+3);
                }


            }

        }

        public static void main(String [] args)
        {
            HoppingLad hl=new HoppingLad();
            hl.hop(3, 0);
            System.out.println("There are "+hl.count+" ways to climb.");
        }
    }

出力は次のとおりです。

 Climbed 1 step.  
 Reached 1  
 Climbed 1 step.  
 Reached 2  
 Climbed 1 step.  
 Reached 3   
 Finished type 1 climbing.


 Climbed 2 step. 
 Reached 3   
 Finished type 2 climbing.


 Climbed 2 step. 
 Reached 2   
 Climbed 1 step.
 Reached 3   
 Finished type 3 climbing.


 Climbed 3 step. 
 Reached 3   
 Finished type 4 climbing.

 There are 4 ways to climb.

私が得た出力は、部分的に正しく、部分的に不完全です。階段の上り方の数は正しいのですが、お気づきのように、

登った 2
到達した 3

出力の一部がそのまま来ています

登った 1
到達した 1

その前に来る部分。私は再帰ツリーを描画しましたが、ツリーは最初の部分が出力にないことを示唆しています。

ただし、ユーザーは地上から指示を受ける必要があります。私は多くのことを試しましたが、役に立ちませんでした。誰でも私のためにこれを修正できますか?

4

4 に答える 4

1

ソリューションを部分的な結果として出力しているため、その部分的なソリューションに基づいて新しいソリューションを取得しても、それらは繰り返されません。

言い換えれば、あなたはそうします（n = 3の場合）

        --> state 0
hop(1)  --> state 1 --> print "1"
hop(1)  --> state 2 --> print "1"
hop(1)  --> state 3 --> print "1" --> print "solution";

次に、状態 2 (これ以上の解決策はありません) に戻り、状態 1 に戻ります。

hop(2) --> state 3 --> print "2" --> print "solution"

状態1に到達できる「1」を出力せずに

解決策は、実際の状態に到達するために必要なステップのリストを渡し、解決策に到達したときにすべてのリストを出力することです。もちろん、これには配列またはリストを使用するため、前の状態に戻るときにそれらのステップを削除する必要があります。

更新: 代替 (出力の変更に基づく) は、必要なステップ数に基づいて回答を集計することです。つまり、出力は次のようになります (上記と同じソリューションの場合)。

Climbed 1
          -> Climbed 1
                       -> Climbed 1. Solution Found!
          -> Climbed 2. Solution Found!

これにより、ユーザーは自分でパスを再構築できます。繰り返しになりますが、現在のステップ数を知るには新しいパラメーターが必要です。

配列/リストのバージョンは必要だがアイテムを削除したくない場合は、リストを複製してコピーを次の関数呼び出しに渡すことができますが、それは非効率的です。

于 2012-07-03T21:48:30.717 に答える
1

このソリューションを実装しました。あなたが宿題を終えた場合にのみ、私はあなたにメールします。

できることは、 aStringを維持し、実行された現在のステップを連結し続けることです。条件に達したら、全体Stringを出力し、個々のステップを出力しません。そうすれば、再帰ステップごとに解にどれだけ近づいているかをチェックするオーバーヘッドを減らすことができます。現在のステップが解決策につながる場合にのみ、パスが出力されることを確認してください。

例 (n=3 と仮定)

3,0,"" -> 3,1,"1" -> 3,2,"11" -> 3,3,"111"(1 つのソリューション オーバー、"111" を出力)

しきい値に到達するために一連のステップを実行する必要があるこの種の問題 (一般的に) では、最も効率的な解決策 (一般的に) は、ステップのリストを保存してから、個々のステップを印刷するのではなく、ソリューション全体を印刷することです。そうすれば、すべての解決策を確実にカバーできることがわかり、現在のステップが解決策につながらない場合は印刷されません。

于 2012-07-11T10:35:12.333 に答える
0

あなたの問題-私が質問を正しく理解していれば-たとえば、ステップ0からステップ1への上昇から始まる可能性を考慮すると、「0から1への上昇」を1回出力してから表示するだけです。ステップ 1 から始まるすべての可能性。

代わりに、再帰を通過するときに完全なルートを追跡し、階段の最上部に到達したらルート全体を出力するように手配する必要があります。

HoppingLadたとえば、の呼び出しの開始時にhop(n,k)、若者がどのようにして をステップしたかを説明する配列をクラスに与えることで、これを行うことができますk。次に、そのn==present場合、その配列を調べて、少年が 0 から に到達した方法の完全な説明を出力できますn。

これを整理するにはいくつかの方法があり、問題はかなり宿題のように見えるので、あまり詳細を記入したくありません。それにもかかわらず、上記が役立つことを願っています。

于 2012-07-03T21:46:32.100 に答える
0

だからここに私の解決策があります、それはjavascriptを使用しますが、ES6を使用します（配列で動作するスプレッド、デフォルトパラメータ、これはFirefoxの現在のバージョンで正常に動作します、私はFirefox 50でこれを行いました）：

function getHopPathsCnt(totalsteps, maxhopability, curstep = 0, taken = [], total={count:0}) {
  if (totalsteps === curstep) {
    total.count++;
    console.log('A possible hop path:', taken.join(' '));
  } else {
    for (let hopped = 1; hopped <= maxhopability; hopped++) {
      if (totalsteps - curstep >= hopped)
        getHopPathsCnt(totalsteps, maxhopability, curstep + hopped, [...taken, hopped], total);
    }
  }
  if (curstep === 0) {
    console.error('Total ways to climb', totalsteps, 'steps with up to', maxhopability, 'hops at a time:', total.count);
    return total.count;
  }
}

使用するには:

getHopPathsCnt(3, 3);

出力:

可能なホップ パス: 1 1 1

可能なホップ パス: 1 2

可能なホップ パス: 2 1

可能なホップパス: 3

一度に最大 3 ホップで 3 段を登る方法の合計: 4

4

上記のガレスとは異なり、完全なソリューションを提供した理由

この問題は宿題のように見えるので、共有したいと思います。宿題は、新しい地平を開くためのものです。そのため、解決策がない場合は、「現在のスキル/精神」でそれを強要し続けることがあります。最終的に解決策を見て逆に作業すると、私の「スキル/精神」に新しい側面が追加されただけです。そのため、「宿題のように見えるので、あまり詳細を記入しません」という解決策を見るのが嫌いです。それが学習の唯一の方法につながるので、問題を間違えて、愚かな採点システムが私たちに悪い成績を与え、「私たちの過ちから学ぶ」. 避けられるのであれば、間違いから学ぶのは嫌いです。また、特に努力すれば、グレードとして「間違った」/「F」のカーストに分類されることはありません。

于 2016-12-10T22:52:49.103 に答える