私のソフトウェアエンジニアリングコースでは、スタックの次の特性が私に凝縮されました。完全公理バージョンI Uled here。
自然に生まれたトロールなので、私はすぐにトロールスタックを考案しました。既に1つ以上の要素がある場合、その要素をランダムに並べ替えます。このナンセンスの実装が実際に公理に違反しているかどうか、すぐに私は講演者と議論をしました。私はいいえ、最高の要素はそれがどこにとどまると言った。彼らははい、何とかあなたは再帰的にプッシュポップの公理を適用して「より深く」得ることができると言った。それは私には見えない。誰が正しい？スタック実装Trollfaceの方法
違反公理はpop(push(s,x)) = sです。スタックsをn > 1の別個のエントリに置きます。 push(s,x)がであり、s'xであり、s'のランダム置換がsである場合、popが関数なので、問題があります。random_permutation()はどのように逆転しますかpop(push(s,x)) = s？ s'のプリイメージは、の順列のいずれかであった可能性があり、どちらにマップするかにかかわらず、n! - 1 > 0他の元の順列s''の場合はpop(push(s'',x)) != s''です。
恐らく私の問題は公理が反復されるかどうかです。 x ... mmmhの公理をもう一度挿入すれば、今私はそれを見ると思う。 –
@HaukeReddmann私が見る限り、反復は必要ありません。 1つの 'pop（push（）） 'の後でさえ、あなたはあなたが始めたものとは異なるスタックを持つ可能性が非常に高いでしょう（もし置換が確定的に行われるならば、' pop （push（）） '）。 –
誰もが見ることが非常に簡単な（このように "トロール"という言葉を使用している）このような場合、常に紙の上に "プログラム"を実行するのに役立ちます。
何回かプッシュしてポップすると何が起こるかを書き留めてください。
また、それらの公理がスタックの実際の動作に非常に密接に対応しているかどうかを確認する必要があります。彼らは楽しいためだけに存在するのではありませんが、深く（単語の複数の意味で）、そのメソッドでデータ構造を指定します。あなたは、それらをスタックのイン・アウトを記述する「正式なシステム」とみなすことさえできます。
あなたが懐疑的であることはまだ良いことに注意してください。これはa）より良い洞察と、b）あなたの上司が行うエラーの検出につながります。この場合、彼らは正しいですが、それはあなたに多くの時間を節約することができるケースがあります（例えば、 "Gödel、Escher、Bach"の "MU"おもう）。
そうです。 –
違反公理は 'pop（push（s、x））= s'です。 –