🧑🏿‍🤝‍🧑🏼 🕓 👆🏻 一回で 🎏 🧕🏾 🎅🏼

プログラミングタスクの中で、同じような要素のシーケンス（通常は数字）が与えられ、1つのパスでいくつかの特性を見つける必要があります（標準偏差、最小要素の数、最大合計の連続セクション...）シーケンスは非常に長くなる可能性があり、メモリに収まりません。通常、シーケンスの要素には他の制限はありません。

これらのタスクにより、すべてが多かれ少なかれ明確になります。MSU機構モジュールで目的の関数の「誘導拡張」と呼ばれるものを見つけて、その計算を実装する必要があります。見つからない場合（必要なメモリ量が大きすぎる）、問題は解決しません。

しかし、他のタスクがあります。集約内のシーケンスの要素には追加の制限があり、これらの制限はソリューションで実質的に使用する必要があります（チェックする必要はありません）。最も単純なこのようなタスクは次のようになります。

問題1.シーケンスには1からNまでの整数がランダムな順序で含まれていますが、数字の1つがスキップされます（残りは1回だけ検出されます）。 Nは事前にはわかりません。 不在番号の特定

解決策は明らかです：数値を見て、その数値Kと合計Sを見つけます。条件により、N = K + 1、つまり1からNまでの数値の合計は（K + 1）*（K + 2）/ 2であり、不足している数値（K + 1）*（K + 2）/ 2-Sに等しい何らかの理由でオーバーフローが心配な場合は、符号なしの数値を使用してください（オーバーフローはひどいものではありませんが、（K + 1）*（K + 2）/ 2 :)を計算するときは注意してください）、または合計ではなく、すべての数値のXORを探します。

問題2.整数がシーケンスに書き込まれます。 数字の1つは正確に1回、残りは2回です。 一度発生する番号を見つけます。

ここでも、すべてが単純です。すべての数値のXORを見つけます-それが答えになります。実際、目的の数の一部のビットがゼロに等しい場合、シーケンス全体では偶数の要素で1に等しくなり、XORの値はゼロに等しくなります。それ以外の場合、同様に、XORの値は1です。または、より単純には、合計すると同じ要素が破棄されます。

タスクを少し複雑にしましょう：

問題3.整数がシーケンスに書き込まれます。 数字Xは1回または2回、残りの数字は3回出現します。 数値Xを見つけます。簡単にするために、数値は負でないと仮定します。

非表示のテキスト

前の問題と同様に進めます。各数値を3進法に変換します。b = b [0] + 3 * b [1] +3 ² * b [2] + ...各桁について、3を法とする値の合計を求めます（合計s [0]、s [1]、s [2]、...）。さらに、数値自体を計算します。

シーケンス内の数値が3 * k + 1の場合、Xは1回満たされ、その値はs [0] + 3 * s [1] +3 ² * s [2] + ...数値が3 * k +の場合2、セットs [i]で単位を2に置き換える必要があり、その逆も同様です。x[i] =（3-s [i]）％3、X = x [0] + 3 * x [1] +3 ² * x [2] + ...

そして、あなたが別の一歩を踏み出すと？

問題4.整数がシーケンスに書き込まれます。 Xの数は1.2または3回、残りの数は4回です。 番号Xを見つけます。

非表示のテキスト

以前のアプローチはここでは機能しません：基数4の数値システムを使用してビット単位の量を見つけると、Xが1回または3回出会った場合、すべてがうまくいきます。しかし、Xが2回出会った場合、次の桁が0であったか2であったかを調べることはできません。両方のケースでこの放電の合計siの値はゼロになります。どうする

実際、私があなたを欺いた最後の時。 3進システムをいじる必要はまったくありませんでした。各2進数のビットの合計を計算するだけで十分であり、3で除算すると、対応するビットのXの数はゼロになりました。そうでない場合は、1つ。

この問題では、まったく同じことを行いますが、4で割り切れることを確認します。たとえば、これらのタスクは次のように解決できます。

static int FindNotThree(IEnumerable<int> seq) { int a=0,b=0; foreach(int c in seq) { a^=~b&c; b^=~a&c; } return a|b; } static int FindNotFour(IEnumerable<int> seq) { int a=0,b=0; foreach(int c in seq) { a^=b&c; b^=c; } return a|b; }

タスク5.長い列に人がいます。 彼らのそれぞれについて、最後を除いて、彼らは彼の名前と彼の後ろの名前を書き留めました。 結果のレコードは混合され、ファイルに記録されました。 1回のファイルスキャンで最初と最後の人の名前を特定する必要があります。 これらの名前は異なることが知られています（そうでない場合、タスクは解決できません）が、一般的には、名前を繰り返すことができます。 各個人の名前は16個の8ビット文字で構成されています。

非表示のテキスト

各名前を128要素のビット文字列と見なします。各エントリには、b [i]とc [i]という2つの行があります。

まず、各iについて、すべてのエントリの差b [i] -c [i]の合計s [i]を見つけた場合にどうなるかを見てみましょう。

名と姓を除くすべての名前が行bとcに同じ回数出現するため、合計すると名前が破棄され、名と姓のビットの差が合計に残ります。したがって、s [i]の値は、-1、0、または1の値を取ることができます。

s [i] =-1の場合、名のb [i]の値は0、2番目の名前の値は1です。s[i] = 1の場合、値はそれぞれ1と0になります。ただし、s [i] = 0の場合、姓と名のこのビットの値は同じであるとしか言えません。どうやって見つけますか？

あるkについて、s [k]がゼロでないことがわかっていると仮定します。 XOR値（b [i]＆b [k]）^（c [i]＆c [k]）を見つけたらどうなりますか？

最初と最後を除くすべての名前nについて、式n [i]＆n [k]は合計に2回（1回はb、2回目はc）含まれ、ゼロの寄与を与えます。 fが名で、pが最後の場合、合計は（f [i]＆f [k]）^（p [i]＆p [k]）になります。 f [i] = p [i]であるビットのみに関心があります（残りの値は既に見つかっています）。したがって、（f [i]＆f [k]）^（p [i]＆p [k]）= f [i]＆（f [k] ^ p [k]）、およびs [k]！= 0以降、次にf [k] ^ p [k] = 1で、合計量はf [i]です。

残念ながら、どのビットが名前が異なるかを事前に言うことはできません。したがって、念のため、合計を検討します

（b [i]＆b [k]）^（c [i]＆c [k]）すべてのペアi、k。合計で、128 * 127/2 = 8128の1ビットカウンターと128の2ビットカウンターが必要です（s [i]をカウントするため）。

たとえば、次のような処理を記述できます（レコード内の両方の名前が同じバイト配列で送信され、行に書き込まれると仮定します）。

  static byte[] FindDiffNames(IEnumerable<byte[]> seq) { const int LName=16; byte[,] pairs=new byte[LName*8,LName]; byte[] res=new byte[2*LName]; foreach(byte[] name in seq) { for(int i=0;i<LName;i++) { res[i+LName]^=(byte)(name[i]&res[i]); res[i]^=(byte)(name[i]^name[i+LName]); res[i+LName]^=(byte)(name[i+LName]&res[i]); for(int k=0;k<LName*8;k++) { byte mask=(byte)(1<<(k&7)); if((name[k>>3]&mask)!=0) pairs[k,i]^=name[i]; if((name[LName+(k>>3)]&mask)!=0) pairs[k,i]^=name[i+LName]; } } } for(int i=0;i<LName;i++) { int b0=res[i],b1=res[i+LName],s=0; for(int j=0;j<LName*8;j++) s|=pairs[j,i]; s&=~b0; res[i]=(byte)((b0&~b1)|s); res[i+LName]=(byte)((b0&b1)|s); } return res; }

この手法を使用すると、2つまたは3つの要素を追加する（または2つを追加してから1つを削除する）ことによって取得されるセットの差を見つけることもできます。差がより強い場合、ペアだけでなくビットのトリプルの接続詞の合計を保存する必要があります。 XORはすでに十分ではありません-少なくとも3ビットの交互合計を数える必要があります。

UPD：コメントでのこのタスクの議論で、セプティムはよりシンプルなソリューションを提案しました。名前を128ビット整数（xi、yi）と見なし、合計S1 =合計（xi-yi）、S2 =合計（xi ^ 2-yi ^ 2）（最初の合計は符号付き129ビット、2番目は-符号付き257ビット。オーバーフローを無視し、それぞれ2 ^ 129と2 ^ 257を法として動作します）。それらの値がS1 = x1-xn、S2 = x1 ^ 2-xn ^ 2であることは明らかです。x1は名、xnは最後です。これから、x1 =（S1 + S2 / S1）/ 2、xn = x1-S1を簡単に見つけることができます。

問題6.整数がシーケンスに書き込まれ、その半分以上が同じ数Xに等しい。シーケンスの1回のスキャンでこの数を見つけます。

非表示のテキスト

シーケンスから2つの異なる数字を消す場合、問題の条件は真のままであることに注意してください。したがって、すべての要素が同じ数になるまで、異なる数のペアを消すことができます。この番号はXです。

このメソッドを実装するために、シーケンスの一部の要素が格納されるセルと、カウンター-この要素のコピーをいくつ表示し、まだ削除していないかを開始しましょう。

次の要素を読むとき、次の3つのオプションがあります。

-カウンターはゼロです。読み取り要素をセルに入れ、カウンターを1増やします。

-要素はセルの値と等しい。カウンターを1増やします。

-アイテムがセルの値と等しくありません。カウンターを1減らします。

シーケンス全体を調べた後、セルに目的の番号が表示されます。

残念ながら、数Xが1 / kの場合よりも多く発生する場合（kは既知）、この解決策を一般化することはできません。また、カウンターでk-1セルを開始し、一度にk個の異なる要素を削除します。k-1の終わりにXの役割の候補を取得しますが、それを認識できません-カウンターの値が最大にならない場合でも。ただし、2回目のパスを許可されている場合は、各候補者が順番に出会った回数を計算し、最も頻繁に保証されるものを提供できます。

元の問題には別の解決策があります。各ビットごとに、それが0であった回数と1をカウントし、より頻繁に値を与えます。おそらく、Xがケースの1/3を超える場合にそれをケースに一般化することが可能になるでしょう-ビットの各ペアの統計を計算しましょう...それが助けたらどうでしょうか？

次の2つの非常によく似たタスクを1つのパスで解決することはほとんどできません。ただし、ログ（M）パスには興味深い解決策があります。

問題7.シーケンスにはM未満の非負の整数が含まれており、各数値は1回しか発生しないことがわかっています。 このシーケンスで発生しない最小の番号を見つけます。

問題8.シーケンスにM + 1個の非負整数が含まれ、すべての数値がM未満です。少なくとも2回出現する数値を見つけます。

非表示のテキスト

解決策はほとんど同じです。範囲0..M-1を2つ以上の部分に分割します。各部分について、その中に含まれる数字の数を計算します。最初の問題では、その長さよりも数が少ない最初のサブバンドを残します。2番目の問題では、長さよりも多くの数が落ちるサブバンドを残します。このプロセスは、1つの数値の範囲が残るまで繰り返されます。それが答えになります。

私には長い間興味を持っているが、その解決策がわからない問題がまだある。

問題9.シーケンスには、1からNまでの数字が何らかの順序で含まれています。 各番号は1回出現します。 Nは事前に知られています。 シーケンスの1回のスキャンで記録された順列のパリティを決定する必要があります。 これに必要な最小メモリ量はいくらですか？

パラドックスとは、事前に選択した任意の時点で、1ビットの情報を記憶するだけで十分なことです。ただし、その後、N + 1ビットが必要になります。この瞬間以降、どの要素がシーケンスに含まれるかを記憶するためです。

一回で

More articles: