問題タブ [puzzle]

0 と 1 を持つ NxN 行列が与えられます。a を含むすべての行をすべての に設定し、a0を含むすべての列をすべての0に設定します。00

例えば

結果は

Microsoft のエンジニアが、余分なメモリを必要とせず、2 つのブール変数と 1 つのパスだけを使用するソリューションがあると教えてくれたので、その答えを探しています。

ところで、それがビットマトリックスであると想像してください。したがって、マトリックスに含めることができるのは1と0だけです。

このコードが 14 を出力する理由を誰かに説明してもらえますか? 他の学生から質問されたのですが、よくわかりませんでした。

私の問題は、8 クイーンズ パズルに非常によく似ています。

たとえば、次のような 2 次元配列 (N x N) があります。

水平、垂直、斜めに 1 の出現をチェックしています

「1」の（x、y）位置のみをリストに保存することを考えています

それを数学的に解き、「1」のすべての位置を別の (x1,y1)<->(x2,y2) でチェックし、

x1 == x2チェックするかどうy1 == y2 we have a collision!か：

(???)

ここで、z は +/- です( x1+z in 0..N ) and ( y1+z in 0..N ) .......

私の問題は、斜めの衝突をチェックすることです。それを行うより良い方法はありますか???

以下に示す 1 つのテーブルの設計を考えると、次のクエリをどのように実行するのが最善でしょうか?

• 民族 ID が与えられた大家族の集合
• 2 つの民俗 ID が与えられた共通の祖先のセット
• 民族 ID が与えられた子孫の集合

*ボーナス最初のいとこ、民族IDを指定して2回削除

テーブルフォーク

私が宝くじの数字を推測したとしましょう：

1689年

宝くじのしくみは、数字が実際の当選番号の数字と 1:1 で一致する限り、数字の順序は関係ありません。

したがって、番号 1689 は次の場合の当選番号になります。

1896年、1698年、9816年など.

あなたの推測の各数字がターゲット番号に存在する限り、宝くじに当選します。

これを行うことができる数学的な方法はありますか？

この問題は、O(N^2) ループで各桁を宝くじの当選番号の各桁と照合してチェックすることで解決しました (モジュラスで区切ります)。それは問題ありませんが、うまくいきますが、私にできるきちんとした数学のトリックがあるかどうか知りたいです.

たとえば、最初は... 両方の数字の各桁の和と積を取り、それらが一致すれば勝てると思っていました。

↑それでいいと思いますか？

しかし、宝くじの推測を見つけたとき、すぐにこれを反証しました。222 と 124 は数字は異なりますが、積と和は同じです。

順序に関係なく num1 の数字が num2 の数字と一致するかどうかをすばやく判断するために使用できる数学のトリックを知っている人はいますか?

コーヒーを飲みすぎたのかもしれませんし、長時間働きすぎたのかもしれませんが、とにかく、この方法が何をするのか、またはなぜ、どのようにそれを行うのかについて、誰かが私に光を当てることができますか? ? ネクストカラーとは？

アップデート

皆様、ご回答ありがとうございます。プログラム内のメソッドのコンテキストを見ると、それらの意図が、既存の色のセットから「最も離れた」新しい色を返すことであったことは明らかです。

この質問へのフォローアップを提示してくれたSparrに感謝します.あなたのアドバイスを念頭に置いて上記を間違いなく書き直します.

私はRGBカラースケールに精通していません。上記のメソッドの意図を知ることは、「無料？」を検索することです。色を既存の色のセットに置き換えた場合、1で提供された解決策は実際に、色をどのように知覚するかという意味で補完的になりますか? セットを補完する色を選択する簡単な方法はありますか、それとも RGB コンポーネントの数値解析によって実際に適切な色が得られるのでしょうか?

有効な浮動小数点数のセットを乗算ベースの演算の下でグループに強制するためのトリックとテクニックに精通している人はいますか？

つまり、任意の2つの浮動小数点数（ "double a、b"）が与えられた場合、乗算を含むどの操作シーケンスがこれを別の有効な浮動小数点数に変換しますか？（有効な浮動小数点数は、NaN、非正規化数、および-0.0を除いて、1-正規化されたものです）。

この大まかなコードを置くには：

NaNがあるため、乗算だけでは機能しません。理想的には、これは直線的なアプローチです（「Xを超える場合は、Yで割る」定式化を回避します）。

これがすべての有効な浮動小数点数に対して機能しない場合、そのような操作が利用できるサブセットはありますか？

（私が探しているモデルは、Cでの整数の乗算に似ています。2つの整数が乗算されても、常に整数が返されます）。

私はこれに単純化したクラスを持っています：

このことの配列をソートしたいと思います。だから私は簡単なcopmaratorを作成しました：

次に、の2つの引数形式を使用しますArrays.sort。

これは私のテストケースでは問題なく機能しますが、配列が奇妙で繰り返し可能な順序で終わることがあり、すべてがうまくいかないことがあります。どうすればいいの？

除算と剰余演算を連続してカウントするルーチンを考えてみましょう。

64 ビットの被除数から始めて、ルーチンは定数除数で除算します。
余りが 0 の場合、ルーチンは戻ります。
それ以外の場合、剰余に 2^32 を掛けて整数商を加算することにより、新しい被除数が作成されます。

コード内:

任意の除数を使用して、目的のカウントを取得するために必要な Dividend を計算するための非反復方法はありますか?
多くの最初の配当では、これはすぐに「アサート」状態になるようです。いくつかの配当により、これは永遠にループしますか?

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

配送車は、一連の配送 (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)) と比較すると、.

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