3

アルゴリズムに関する知識を向上させるために、オンラインでいくつかのパズルを見回していました...

私は以下の質問に出くわしました：

「スペースが削除され、文字の順序がシャッフルされた単語がいくつかある文があります。辞書があります。スペースと通常の文字の順序の単語で文を生成するアルゴリズムを記述してください。」

これを解決する良い方法がわかりません。

私はアルゴリズムに不慣れですが、問題を見るだけで、プログラムに知的精神が行うことを実行させると思います。

これが私が考えることができるものです：

-まず、「is」、「the」、「if」などの辞書から手動で一般的な短い英語の単語を見つけて、dataset-1に入れます。

-次に、dataset1の単語の順列（「si」、「eht」、「eth」、「fi」など）を見つけて、dataset-2に入れ

ます。-次に、入力センテンスから、dataset2の単語に一致する文字シーケンスを見つけて入れます。それらをdataset-3に挿入し、見つかったものの代わりに入力文にスペースを挿入します。

-残りの単語については、辞書から単語を見つけるために順列を実行します。

私はアルゴリズムの初心者です...それは悪い解決策ですか？

4

2 に答える 2

1

これは完全に良い解決策のようです、

一般に、アルゴリズムを判断するための2つのパラメーターがあります。

  1. 正しさ-アルゴリズムは正しい答えを提供しますか？

  2. リソース-回答を提供するために必要な時間またはストレージサイズ。

通常、これら2つのパラメーターの間にはトレードオフがあります。

たとえば、辞書のサイズによって、再構築できるスクランブル文が決まり、より多くの入力に対して正しい答えが得られますが、検索プロセス全体に時間がかかり、より多くのストレージが必要になります。

あなたが提示した問題の難しい部分は、順列を計算する必要があるという事実であり、それらはたくさんあります。

したがって、すべてをチェックするのは費用がかかります。提案したことを実行し、一般的に使用される単語の小さなサブセットを作成して最初にチェックすることをお勧めします。そうすれば、平均的なケースの方が適しています。

注：順列/検索をチェックすると言っても大丈夫ですが、最終的にはそれを行う正確な方法を指定する必要があります。

現在、あなたが書いたのはアルゴリズムのアイデアですが、与えられた入力を取得して機械的に出力を計算することはできません。

于 2012-12-24T07:44:42.820 に答える
0

実際には、単語の長さで辞書を分割することから始めるのが賢明かもしれません。

次に、最小の単語を見つけるのではなく、使用可能な文字を使用して作成できる最大の単語を見つけてください。短い単語がより一般的であるため、絞り込むのが難しくなります。IE：それは本当に「もし」なのか「イチジク」なのか。

次に、単語の長さwごとに、一度にw文字ずつ進めることができます。

有効な単語を見つけたからといって、それが正しい単語であるとは限りませんが、まだ多くの可能な組み合わせがあります。すべての部分文字列を確認したら、O（c ^ 4 * d）のようなものがあります。ここで、dは辞書の単語数、cは文の文字数です。実際には、辞書を単語の長さで並べ替えると、それよりもかなり少なくなります。次に、有効な単語を取得し、すべての文字が使用されるように機能する順序を理解する必要があります。複数の解決策があるかもしれません。

于 2012-12-24T12:06:54.830 に答える