問題タブ [puzzle]

これまでの私のベストショット：

配送車は、一連の配送 (d ₁、d ₂、...d _n ) を行う必要があり、任意の順序で配送できます。つまり、集合 D = {d ₁、 d ₂ ,...d _n } は有効なソリューションですが、特定のソリューションは、ルートの一端にある基地局を出る前に決定する必要があります (たとえば、パッケージを車両の LIFO に積み込む必要があると想像してください)。 ）。

さらに、さまざまな順列のコストは同じではありません。_{これは、d i-1}と d _iの間を移動した距離の 2 乗の合計として計算できます。ここで、d ₀は基地局と見なされます。ただし、方向の変更を伴うセグメントには 3 倍の費用がかかることに注意してください。 (これが鉄道または気送管で行われており、後退すると他の交通が妨げられると想像してください)。

D基地局からの距離 (つまり、abs(d_i -d_jは 2 つの配送間の距離) として表される配送のセットと、各順列を連続して生成)するイテレーターpermutations(D)が与えられた場合、コストが任意の順列以下の順列を見つけます。その他の順列。

ここで、この説明から直接実装すると、次のようなコードになる可能性があります。

これは O(n*n!^2) です。たとえば、かなりひどいものです。特に、洞察力のある人が D を並べ替えるだけで見つけられる O(n log(n)) と比較すると、.

私の質問: もっともらしい問題の説明を思いつくことができますか?それは、不注意な人をより悪い(または別の方法でひどい) ソート アルゴリズムの実装に自然に導くようなものです。

Douglas Hofstader による Godel, Escher, Bach の第 8 章で、読者はこれら 2 つのステートメントを TNT に翻訳するように求められます。

「b は 2 の累乗です」

と

「b は 10 のべき乗です」

次の答えは正しいですか?:

(「∃」が「数値が存在する」という意味であると仮定すると):

∃x:(xx = b)

つまり、「x に x を掛けると b に等しい数 'x' が存在する」

それが正しければ、次のものも同様に簡単です。

∃x:(xxxxxxxxxx = b)

著者は、それらはトリッキーであり、2 つ目の問題は解決に数時間かかると述べているため、私は混乱しています。ここで明らかな何かを見逃したに違いありませんが、見えません!

次を使用せずに、C で数値 (1 から 10 まで) の階乗を見つけるにはどうすればよいですか?

• for、while、do while などのループ ステートメント。
• if や case などの条件演算子。と
• + 、 − 、 * 、 % 、 /、++、 −−? などの算術演算子

参考までに: この質問は C aptitude で見つけました。

サイズXxYのパネルがあります。このパネルに、ランダムなサイズの最大N個の長方形を配置したいのですが、どの長方形も重ならないようにします。これらの長方形のX、Y位置を知る必要があります。

アルゴリズム、誰か？

編集：N個の長方形はすべて最初からわかっており、任意の順序で選択できます。それは手順を変更しますか？

最近はiPhoneでスクランブルというゲームをやっています。このゲームを Boggle として知っている人もいるかもしれません。基本的に、ゲームが開始すると、次のような文字のマトリックスが表示されます。

このゲームの目的は、文字をつなげてできる単語をできるだけ多く見つけることです。任意の文字から始めることができ、それを囲むすべての文字は公正なゲームであり、次の文字に移ると、その文字を囲むすべての文字は、以前に使用された文字を除いて公正なゲームです. たとえば、上のグリッドでは、、、、、などの単語を思いつくことができます。単語LOBは、少なくとも 3 文字で、NxN 文字以下である必要があります。このゲームでは 16 文字ですが、実装によっては異なる場合があります。 . このゲームは楽しくて中毒性がありますが、私はどうやらそれが得意ではないようで、可能な限り最高の単語 (単語が長いほど、より多くのポイントを獲得できる) を提供するプログラムを作成して、少しごまかしたかったのです。TUXSEAFAME

_{（出典：boggled.org）}

残念ながら、私はアルゴリズムやその効率などについてあまり得意ではありません。私の最初の試みは、このような辞書(~2.3MB) を使用して、組み合わせを辞書エントリと一致させようとする線形検索を行います。これは、可能な単語を見つけるのに非常に長い時間がかかります。また、ラウンドごとに 2 分しか与えられないため、単純に不十分です。

Stackoverflowers がより効率的なソリューションを思い付くことができるかどうかを確認することに興味があります。Python、PHP、Perl のビッグ 3 P を使用したソリューションを主に探していますが、速度が不可欠であるため、Java や C++ を使用するものもクールです。

現在のソリューション:

• Adam Rosenfield、パイソン、20 代まで
• John Fouhy、Python、~3 秒
• Kent Fredric、Perl、~1 秒
• Darius Bacon、パイソン、~1 秒
• rvarcher、VB.NET、~1 秒
• Paolo Bergantino、PHP (ライブ リンク)、~5 秒 (ローカルで~2 秒)

最近、就職の面接でプログラミングのパズルを解くように頼まれました。Excel の列の文字を実際の数字に変換することについてです。思い出すと、Excel はその列に A から Z までの文字で名前を付け、そのシーケンスは AA、AB、AC... AZ、BA、BB などになります。

文字列をパラメーターとして受け入れ（「AABCCE」など）、実際の列番号を返す関数を作成する必要があります。

ソリューションはどの言語でもかまいません。

わかりました、例による目標:これを行うコマンドラインアプリ:

カウントダウン.exe 7

プリント 7 6 5 4 3 2 1

減算 (マイナス記号の使用を含む) や文字列の反転は一切許可されていません。

どうやら簡単すぎます:-)答えの概要（少なくとも原則）

1. 追加と再帰によって
2. モジュロを使用して
3. 押したり弾いたりして、(おそらく最も明白な?)
4. オーバーフローを利用して
5. 試行錯誤を使用して (おそらく最も明白ではないでしょうか?)

私はこの課題をstackoverflowコミュニティの注目を集めたかったのです。元の問題と答えはここにあります。ところで、あなたが以前にそれをフォローしていなかったなら、あなたはエリックのブログを読むことを試みるべきです、それは純粋な知恵です。

概要：

null以外のIEnumerableを受け取り、次の特性を持つ文字列を返す関数を記述します。

1. シーケンスが空の場合、結果の文字列は「{}」です。
2. シーケンスが単一アイテム「ABC」の場合、結果の文字列は「{ABC}」になります。
3. シーケンスが2項目シーケンス「ABC」、「DEF」の場合、結果の文字列は「{ABCandDEF}」になります。
4. シーケンスに「ABC」、「DEF」、「G」、「H」などの3つ以上の項目がある場合、結果の文字列は「{ABC、DEF、G、およびH}」になります。（注：オックスフォードコンマはありません！）

ご覧のとおり、私たち自身のJon Skeet（はい、同時に2つの場所にいることができることはよく知られています）が解決策を投稿しましたが、彼の（IMHO）は最もエレガントではありませんが、おそらくあなたはそれを打ち負かすことはできませんパフォーマンス。

どう思いますか？そこにはかなり良いオプションがあります。私は、（Fernando Nicoletの）selectメソッドとaggregateメソッドを含むソリューションの1つが本当に好きです。Linqは非常に強力であり、このような課題に時間を割くことで多くのことを学ぶことができます。私はそれを少しひねったので、それはもう少しパフォーマンスが高く、明確です（カウントを使用し、リバースを回避することによって）：