4

最近、プログラミングの授業で、任意の言語でプログラムを作成するという課題が与えられました。このプログラムは、nが与えられた場合、すべての i に対してp [i] != i: 0 となるような、サイズnの配列pに対して可能なすべての乱れを生成します。 <= i < n. イテレータを使用する必要がありました。yield

例: n=3、[0, 1, 2] は乱れではありませんが、[2, 0, 1] は [1, 2, 0] と同様です。

動作する疑似コード ソリューションを思いつきましたが、問題はパワー ループ (つまり、nが実行時にのみ認識されるn個のネストされたループ) が必要なことでした。これを行うために、文字列内の Ruby コードでn 個のネストされたループを生成し、文字列をeval編集しました。私の解決策はうまくいきましたが、私の教授は、goto動的コード生成よりも数個の s を使用する方が良い解決策 (少なくとも読みやすい) であると考えました。

goto私はいつも悪い選択だったという印象を受けました。動的に生成されたコードの実行時評価が、なぜより悪い選択になるのgotoでしょうか? 生成されたコードはクリーンでシンプルで、与えられた問題に対してかなり効率的です。コード生成が依存する唯一のユーザー入力はnであり、事前に整数値であることを確認するためにチェックされます。当然yieldのことながら、それは唯一の混乱です。

私は自分のプログラミング課題の解決策を求めているのではなく、goto過剰な動的コード評価を使用する理由、またはその逆の使用の背後にある理由を知りたいだけです。

編集： 明確にするために、割り当てには反復子を使用したプログラムと再帰を使用した別のプログラムの作成が含まれていたため、反復バージョンは必ずしも効率的であるとは限りませんでした。

4

11 に答える 11

6

GOTO とコード生成はどちらも、この問題 IMO に対する洗練されていないソリューションです。おそらくここで正しい答えである再帰アルゴリズムがあります。

于 2009-09-11T18:42:55.750 に答える
2

あなたのコードを見なければ、私は教授の側に立つ傾向があります。GoTo と動的コードのどちらかを選択する場合、私は前者に傾倒します。GoTo は必ずしも悪い選択ではありません。

于 2009-09-11T18:46:11.983 に答える
2

GoTos を使用しなくても、ほとんどすべての問題を解決できます。特にループでは、break ステートメントと continue ステートメントを使用して、コード標準を維持したまま goto を暗黙的に使用できます。

nネストされたループは悪い計画のように聞こえますが、代わりに再帰関数を検討することをお勧めします。nループを実行する必要があるたびに、常に再帰を考える必要があります。

于 2009-09-11T18:46:25.630 に答える
2

動的コードはコンパイル時にチェックできません。つまり、エラーは実行時まで検出されません。それらを見つけにくくする可能性があります。ruby の場合、これは、IDE またはエディタのどちらを使用していても、構文エラーが検出されないことを意味します。それは後藤を選ぶプラスです。

この場合、決定を下すには両方を見る必要があると思います。私はコードを見たことがありませんが、動的コードや goto を使用しない優れたソリューションがあることは間違いありません。goto は必ずしも悪いわけではありませんが、使用を検討している場合は、おそらくこれまでに最適な設計上の決定を下しておらず、ソリューションを再検討したいと考えているでしょう。

于 2009-09-11T18:49:08.183 に答える
2

これは非常に興味深い質問です。決定的な答えがあるかどうかはわかりません。

goto の問題は、構造化されていない方法での使用です。goto は「大規模なランダムな飛躍」であるため、一般的な例では、ジャンプの後、どこから来たのかがわかりません。デバッグと保守性、そして - コードの「正しさ」を証明するより正式な意味で。もちろん、コードに構造を課す時点でオプションがない言語もあります (私はしばらく使用していました)。肝心なのは、GOTO が悪いということではなく、goto が使用される (および悪用される) 方法が悪いということであり、それが危険な構造を利用できるようにするということです。

コード生成を使用して結果を評価するのは賢いです:)しかし、「賢い」ことは常に良いことではなく、それを解決策として使用することの問題の一部は、意図したとおりに実際に問題に対処していないことだと思います。それはある意味で「ごまかし」かもしれません-少なくともあなたの教授に関する限り-あなたのソリューションを無効にすることはありませんが、それを「洗練されていない」ものにする可能性があります。コードに関しては、デバッグと保守の問題も発生します。

再帰的な解決策は、特に (約 25 年前に) 再帰をループに巻き戻すことができると教えられたことを漠然と覚えているので、おそらく最もエレガントです。

間違いなく興味深い質問です！

于 2009-09-11T19:10:01.860 に答える
0

再帰的な解決策-これは早期の剪定を伴う解決策です。私の唯一の質問は列挙に関するものです。彼は、呼び出しが成功するたびにリスト内の次の項目を生成する列挙子を作成することを望んでいましたか？これはおそらく、このプログラムのラムダバージョンを作成することで最も簡単に実装できます-私は、プロローグインタープリタースタイルのクエリを実行するときに質問に対する次の回答を生成するクエリジェネレーターを作成するときに、常にlispでこれを実行していました。

Option Strict On Option Explicit On

モジュールModule1

Private Sub printGeneratedList(ByVal generatedList As List(Of Integer))
    For Each el In generatedList
        Console.Write(el & " ")
    Next
    Console.WriteLine()
End Sub

Private Sub generateAux(ByVal i As Integer, ByVal n As Integer, _
                    ByVal generatedList As List(Of Integer))
    If i >= n Then
        printGeneratedList(generatedList)
        Return
    End If
    For j As Integer = 0 To n - 1
        If Not j = i Then
            If Not generatedList.Contains(j) Then
                generatedList.Add(j)
                generateAux(i + 1, n, generatedList)
                generatedList.Remove(j)
            End If
        End If
    Next
End Sub

Private Sub generate(ByVal n As Integer)
    Console.WriteLine("Generating for n = " & n.ToString())
    Dim l As List(Of Integer) = New List(Of Integer)
    If n < 0 Then
        Throw New Exception("n must be >= 0")
    End If
    generateAux(0, n, l)
End Sub

Sub Main()
     generate(0)

    Console.ReadLine()
    generate(1)

    Console.ReadLine()
    generate(2)

    Console.ReadLine()
    generate(3)

    Console.ReadLine()
    generate(4)

    Console.ReadLine()

End Sub

エンドモジュール

于 2009-09-11T21:33:31.000 に答える
0

後藤はきれいではありません。しかし、高性能が必要な場合は、これらのコーディング ルールの一部を破る必要がある場合もあります...

速度が本当に重要な問題である場合、たとえば、ライブラリやコードを書きたい場合は、goto を使用することを検討してください。確かに、すべてがうまくいくように注意する必要があります。

コメント: 最後に、実行中の CPU は単純なジャンプ以外は何もしません。プログラミング言語/コンパイラがそれらを作成するだけです。注意して使用し、それを台無しにしないでください。

于 2009-09-11T18:45:06.930 に答える