問題タブ [proof]

私は、オペランドと演算子が後置表記で書かれた文字の配列を読み取るコンピュータープログラムを持っています。次に、プログラムは配列をスキャンして、次のようにスタックを使用して結果を計算します。

このプログラムが後置式を正しく評価することを帰納法によって証明するにはどうすればよいですか? (演習 4.16 Java のアルゴリズム (Sedgewick 2003) から取得)

Tがn個の要素を持つ平衡BSTであり、Lが左側のサブツリー、Rが右側のサブツリーである場合、その深さが2log（n）+1以下であることをどのように証明できますか？

私が持っている帰納法による証拠がありますが、私はそれを取得していません。

（stackoverflowは主にプログラミング指向であることを理解していますが、バイナリ検索ツリーに関するいくつかの質問を見つけて試してみることにしました。うまくいかないことを願っています。:)）

まず第一に、これは副作用のないアルゴリズムでのみ可能ですか?

第二に、このプロセス、良い本、記事などについてどこで学べますか?

この式は、バブル ソート アルゴリズムのデータ構造の本から取得しました。

(n-1) * (n 回) であることはわかっていますが、なぜ 2 で割るのか?

誰か私にこれを説明するか、詳細な証拠を教えてください。

ありがとうございました

これがプログラミングに直接関係していないことは知っていますが、次の証明に正規言語の反復補題を適用する方法を誰かが知っているかどうか疑問に思いました。

L = {（a ^ n）（b ^ n）（c ^ m）：n！=m}が文脈自由言語ではないことを示す

私はポンピング補題を適用することにかなり自信がありますが、これは本当に私を苛立たせています。どう思いますか？

私は古いアルゴリズムのメモを確認していて、この証拠に出くわしました。それは私が持っていた課題からのものであり、私はそれを正しく理解しましたが、確かに証拠が不足していると感じています。

問題はprove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.

私の証明は次のようになります：

矛盾による証明。まず、d値'i'でQから頂点をプルするとします。次回は、d値が「j」の頂点をプルします。iを引いたとき、d値を確定し、開始頂点sからiまでの最短経路を計算しました。正のエッジウェイトがあるため、パスに頂点を追加するときにd値を縮小することはできません。Qからiを引いた後、より小さなd値でjを引く場合、jを介してiに到達できる可能性があるため、iへの最短経路がない可能性があります。ただし、iへの最短経路はすでに計算されています。可能なパスは確認しませんでした。保証されたパスはもうありません。矛盾。

この証明をどのように改善できますか？またはさらに良いことに、別のアプローチがありますか？かなり弱いようです:)

編集：申し訳ありませんが、この場合、私の優先キューは最小ヒープで実装されています

プロジェクトオイラーの問題50を解決しようとしています。私に答えを与えたり、私のためにそれを解決したりしないでください。この特定の質問に答えてみてください。

目標は、100万未満の素数に追加される連続する素数の最長の合計を見つけることです。n以下の素数をすべて見つけるためにふるいを書き、それが正しいことを確認しました。次に、次の方法を使用して、連続する素数の各サブセットの合計を確認します。

空のリストがありますsums。素数ごとに、の各要素に追加しsumsて新しい合計を確認してから、に素数を追加しますsums。

これはPythonです

check()100万未満の2つ以上の連続する素数のすべての合計を要求したかどうかを知りたい

問題は、21個の連続する素数の合計として書くことができる素数953があることを示していますが、私はそれを見つけていません。