問題＃8：ITトレーニング-主要企業の現在の問題と課題

ご質問

1. 蜂が移動した総距離
   

   2つの列車が同じ軌道上にあり、お互いに向かって近づいています。 最初の列車の速度は50 KM / hで、2番目の列車の速度は70 KM / hです。 2つの列車間の距離が100 KMのとき、列車間で蜂が飛び始めます。 ミツバチは最初に最初の列車から2番目の列車に飛びます。 2番目の列車に到達すると、列車はすぐに2番目の列車に戻ります...など、列車が衝突するまで続きます。 蜂が移動した合計距離を計算します。 蜂の速度は40 KM / hです。

   
   
   翻訳

   1つの線路上の2つの列車が互いに向かって行きます。 最初の列車の速度は50 km / h、2番目の列車の速度は70 km / hです。 列車間の距離が100 kmになると、蜂は列車間を飛行し始めます。 ミツバチは最初の列車から2番目の列車に飛びます。 2番目に到達すると、すぐに1番目に戻り、列車が衝突するまでそのように飛行し続けます。
   速度が40 km / hの場合、蜂が移動した距離をカウントします。
   
   
   
2. 毒入りワイン
   

   小国の王は240人の上院議員を彼の年次パーティーに招待します。 伝統として、各上院議員は王にワインのボトルをもたらします。 すぐに、女王は、上院議員の一人が毒入りのワインのボトルを彼に与えて王を暗殺しようとしていることを発見します。 残念ながら、彼らはどの上院議員も、どのボトルのワインが毒されているのかも知らず、毒は完全に見分けがつかない。 しかし、王には処刑予定の囚人が5人います。 彼はそれらを味覚テスターとして使用して、どのワインのボトルに毒が含まれているかを判断することにしました。 毒入りのワインを飲んだ後、24時間以内に死にます。 王様は、2日間でどのボトルのワインが毒されているかを判断し、お祭りが計画どおりに続行できるようにする必要があります。 王はどのようにして囚人にワインを管理し、今から48時間後に彼が毒入りのワインのボトルを見つけたことを保証することができますか？
   

   
   
   翻訳

   小さな国の王は、240人の上院議員を毎年のお祝いに招待しました。 伝統に従って、各上院議員は王にワインのボトルをプレゼントします。 しかし、すぐに女王は、上院議員の一人が王に毒入りのワインを与えることで王を毒殺しようとしていることを知りました。 残念ながら、彼らは上院議員が誰であるか、またどの種類のボトルが毒されているかを知りません。さらに、毒は検出できません。 すぐに死刑判決を受けた王室の刑務所には5人の囚人がいます。 王は彼らの助けを借りて、毒入りのワインのボトルを見つけることにしました。 毒は24時間後にのみ機能します-飲酒者は死にます。 王は、計画された活動を継続するために、2日間でどのボトルが中毒になったかを特定する必要があります。 48時間以内に毒瓶の発見を保証するために、彼はどのようにして囚人にワインを分配できますか？
   

タスク

1. 等しい数の0と1を持つ最大のサブアレイ
   

   0と1のみを含む配列がある場合、等しい数の0と1を含む最大のサブ配列を見つけます。
   
   例：
   入力：arr [] = {1、0、1、1、1、0、0}
   出力：1〜6（出力サブアレイの開始インデックスと終了インデックス）
   
   入力：arr [] = {1、1、1、1}
   出力：そのようなサブアレイはありません
   
   入力：arr [] = {0、0、1、1、0}
   出力：0〜3または1〜4
   

   
   
   翻訳

   ゼロと1を含む配列が与えられます。 同じ数の0と1を含む最大のサブアレイを見つける必要があります。
   
   例：
   入力：arr [] = {1、0、1、1、1、0、0}
   出力：1〜6（入力配列インデックス）
   
   入力：arr [] = {1、1、1、1}
   出力：そのようなサブアレイはありません
   
   入力：arr [] = {0、0、1、1、0}
   出力：0〜3または1〜4
   
   
   
2. 合計セットビットをカウントする
   

   正の整数nが与えられた場合、1からnまでのすべての数値のバイナリ表現で設定ビットの総数を数えます。
   
   例：
   
   入力：n = 3
   出力：4
   
   入力：n = 6
   出力：9
   
   入力：n = 7
   出力：12
   
   入力：n = 8
   出力：13
   

   
   
   翻訳

   正の整数nが与えられた場合、1からnまでのすべての数値のビットの合計をバイナリ表現で計算する必要があります。
   
   例：
   入力：n = 3
   出力：4
   
   入力：n = 6
   出力：9
   
   入力：n = 7
   出力：12
   
   入力：n = 8
   出力：13
   
   
   
3. 繰り返しと欠落を見つける
   

   整数のソートされていないnサイズの配列を指定します。 配列要素の範囲は1〜nです。 セット{1、2、... n}から1つの番号が欠落しており、1つの番号が配列内に2回出現しています。 これらの2つの数字を見つけます。
   
   例：
   
   arr [] = {3、1、3}
   出力：2、3 // 2が欠落し、3が2回発生
   
   arr [] = {4、3、6、2、1、1}
   出力：1、5 // 5が欠落し、1が2回発生
   
   

   
   
   翻訳

   次元nの整数の並べ替えられていない配列が与えられます。 配列の要素-1からnまでの数字のシーケンス。 シーケンス内の1つの番号がスキップされ、1つが繰り返されます。 これらの番号を見つける必要があります。
   
   例：
   
   arr [] = {3、1、3}
   出力：2、3 // 2スキップ、3反復
   
   arr [] = {4、3、6、2、1、1}
   出力：1、5 // 5スキップ、1反復
   
   
   
   

解決策

1. 質問1

   正しい答えが見つかりました -33.3 km。
   
   
   
2. 質問2

   解決策は、3進法でボトルに番号を付けることです。各数字は、ボトルに関する各囚人の行動に対応します。
   0-飲まなかった、
   1-初日に飲んだ
   2-2日目に飲んだ。
   たとえば、コード11201のボトルは、囚人が1日目に1,2と5を飲み、3日目の囚人が2日目に飲み、4人目が飲まなかったことを意味します。 -二日目、それからこのボトルは毒されています。
   合計で、一意の組み合わせは3 ^ 5 = 243、つまり 48時間で結論付けられたように、どのボトルが汚染されているかを明確に判断することができます。
   
   解決策もコメントで提案されました。
   
   
   
3. タスク1

   解決策には、値の連続的な合計が含まれます。また、0は「-1」と見なされます。 ここでオプションの1つが提案されました。
   
   
   
4. タスク2

   正しい解決策の変形は、 コメントの提案でした。
   
   
   
5. タスク3

   解決策の1つは、要素の絶対値をインデックスとして使用し、このインデックスの下の要素の符号を変更して配列をウォークスルーすることです。 その場合、すでにネガティブとマークされている要素のインデックスは重複値です。
   
   2番目のパスでは、正の値を見つける必要があります。
   
   

   #include<stdio.h> #include<stdlib.h> void printTwoElements(int arr[], int size) { int i; printf("\n The repeating element is"); for(i = 0; i < size; i++) { if(arr[abs(arr[i])-1] > 0) arr[abs(arr[i])-1] = -arr[abs(arr[i])-1]; else printf(" %d ", abs(arr[i])); } printf("\nand the missing element is "); for(i=0; i<size; i++) { if(arr[i]>0) printf("%d",i+1); } } /* Driver program to test above function */ int main() { int arr[] = {7, 3, 4, 5, 5, 6, 2}; int n = sizeof(arr)/sizeof(arr[0]); printTwoElements(arr, n); return 0; } 

   
   
   アルゴリズムの複雑さはO（n）です。