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

ご質問

1. 2つのサイコロを使用する月の日
   

   2つの6面のサイコロを使用して、どのように月の日を表すことができますか？ サイコロの各面に0から9の数字を1つ書くことができ、1から31の日を表す必要があります。たとえば、1のサイコロは0を示し、別のサイコロは29を示します。そして別のものは9を表示する必要があります。
   

   
   
   翻訳

   2つの16進数キューブを使用して月の日をどのように想像しますか？ キューブの各面に0〜9の数字を書き込むことができます。1〜31の数字を指定する必要があります。たとえば、1番目の数字では、1つのキューブを「0」の面で、もう1つのキューブを「1」で回転できます。 同様に、番号29については、1つのサイコロが「2」で、2番目が「9」です。
   
   
   
2. 目隠しとコイン
   

   あなたは目隠しされており、10枚のコインがテーブルの前に置かれています。 コインに触れることは許可されていますが、感じ方によってコインがどれだけ上にあるのかわかりません。 5枚のコインが頭上にあり、5枚のコインが尾を引くが、どのコインがどれであるかではないことを伝えられます。
   
   それぞれ同じ数のヘッドアップで2枚のコインを作ることができますか？ コインは何回でも反転できます。
   
   

   
   
   翻訳

   あなたは目隠しされており、目の前のテーブルには10枚のコインがあります。 あなたはそれらに触れることは許されていますが、その接触に対して、どちら側を向いているかはわかりません。 また、5枚のコインが5枚、尾が横たわっていると主張されています。
   
   イーグルがめくり上げたコインの数が等しい2つのスタックを作成する方法は？ コインを何度でも反転できます。
   
   
   

タスク

1. 綱引き
   

   n個の整数のセットが与えられた場合、2つのサブセットの合計の差が可能な限り最小になるように、n / 2サイズの2つのサブセットにセットを分割します。 nが偶数の場合、2つのサブセットのサイズは厳密にn / 2でなければならず、nが奇数の場合、1つのサブセットのサイズは（n-1）/ 2でなければならず、他のサブセットのサイズは（n + 1）/ 2でなければなりません。
   
   たとえば、セットを{3、4、5、-3、100、1、89、54、23、20}とすると、セットのサイズは10です。このセットの出力は{4、100、1、 23、20}および{3、5、-3、89、54}。 両方の出力サブセットのサイズは5であり、両方のサブセットの要素の合計は同じです（148および148）。
   nが奇数である別の例を考えてみましょう。 与えられたセットを{23、45、-34、12、0、98、-99、4、189、-1、4}とします。 出力サブセットは{45、-34、12、98、-1}および{23、0、-99、4、189、4}でなければなりません。 2つのサブセットの要素の合計は、それぞれ120と121です。
   

   
   
   翻訳

   n個の整数のセットが与えられた場合、それらをそれぞれ次元n / 2の2つのサブセットに分割し、これらのサブセットの合計間の差が最小になるようにする必要があります。 nが偶数の場合、サブセットのサイズは正確にn / 2でなければなりません。nが奇数の場合、1つのサブセットのサイズは（n-1）/ 2、2番目-（n + 1）/ 2でなければなりません
   
   例：
   入力：{3、4、5、-3、100、1、89、54、23、20}
   収量：{4、100、1、23、20}および{3、5、-3、89、54}。 両方のサブセットのサイズは5で、合計は148です。
   
   入力：{23、45、-34、12、0、98、-99、4、189、-1、4}
   収量：{45、-34、12、98、-1}および{23、0、-99、4、189、4}。 それぞれサブセット120と121の合計。
   
   
   
2. 2つの要素が隣接しない最大合計
   

   正の数の配列が与えられた場合、配列内で隣接する2つの数字はないという制約を持つサブシーケンスの最大合計を求めます。 したがって、3 2 7 10は13（3と10の合計）または3 2 5 10 7は15（3、5と7の合計）を返す必要があります。最も効率的な方法で質問に答えてください。
   
   例：
   
   入力：arr [] = {5、5、10、100、10、5}
   出力：110
   
   入力：arr [] = {1、2、3}
   出力：4
   
   入力：arr [] = {1、20、3}
   出力：20
   

   
   
   翻訳

   正数の配列が与えられた場合、サブシーケンスの2つの要素が配列の隣接セルにないという条件で、サブシーケンスの最大合計を見つけます。 したがって、3 2 7 10は13（3と10の合計）を返し、3 2 5 10 7は15（3 5 7の合計）を返します。 コードは可能な限り効率的でなければなりません。
   
   例：
   
   入力：arr [] = {5、5、10、100、10、5}
   出力：110
   
   入力：arr [] = {1、2、3}
   出力：4
   
   入力：arr [] = {1、20、3}
   出力：20
   
   
   
   
3. 特定のグラスに含まれる水の量を見つけるプログラム
   

   1リットルと同じ容量のグラスがいくつかあります。 メガネは次のように保管されます。
   

                       1
                     2 3
                  4 5 6
                7 8 9 10
   

   
   あなたはトップグラスのみに水を入れることができます。 1杯以上の水を1杯目のグラスに入れると、2杯目と3杯目のグラスの両方に水があふれて均等に満たされます。 Glass 5は、2番目のガラスと3番目のガラスの両方から水を受け取ります。
   Xリットルの水があり、その水をトップグラスに入れた場合、j番目のグラスにはどのくらいの水が含まれますか？ それを見つけるためのプログラムを書いてください。
   
   例。 あなたが上に2リットルを置く場合。
   1-1リットル
   2-1/2リットル
   3-1/2リットル
   

   
   
   翻訳

   1リットルの容量を持ついくつかの缶は、次のようなピラミッドによって構築されます。
   

                       1
                     2 3
                  4 5 6
                7 8 9 10
   

   
   一番上の缶にのみ水を注ぐことができます。 缶が溢れると、水は下の缶（2と3）に均等に流れ始めます。 バンク5は2缶や3缶などから水を受け取ります。
   Xリットルの水をトップジャーに注ぐ場合、どのくらいの水がjに入りますか？ この問題を解決するプログラムを作成してください。
   
   例。 2リットルを注ぐ場合：
   1-1リットル
   2-1/2リットル
   3-1/2リットル
   

解決策

1. 質問1

   答えはすぐに見つかりました 。
   
   
   
2. 質問2

   Rsa97は適切なソリューションを提案しました。
   
   
   
3. タスク1

   元のソリューション：
   

   #include <iostream> #include <stdlib.h> #include <limits.h> using namespace std; // function that tries every possible solution by calling itself recursively void TOWUtil(int* arr, int n, bool* curr_elements, int no_of_selected_elements, bool* soln, int* min_diff, int sum, int curr_sum, int curr_position) { // checks whether the it is going out of bound if (curr_position == n) return; // checks that the numbers of elements left are not less than the // number of elements required to form the solution if ((n/2 - no_of_selected_elements) > (n - curr_position)) return; // consider the cases when current element is not included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, sum, curr_sum, curr_position+1); // add the current element to the solution no_of_selected_elements++; curr_sum = curr_sum + arr[curr_position]; curr_elements[curr_position] = true; // checks if a solution is formed if (no_of_selected_elements == n/2) { // checks if the solution formed is better than the best solution so far if (abs(sum/2 - curr_sum) < *min_diff) { *min_diff = abs(sum/2 - curr_sum); for (int i = 0; i<n; i++) soln[i] = curr_elements[i]; } } else { // consider the cases where current element is included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, sum, curr_sum, curr_position+1); } // removes current element before returning to the caller of this function curr_elements[curr_position] = false; } // main function that generate an arr void tugOfWar(int *arr, int n) { // the boolen array that contains the inclusion and exclusion of an element // in current set. The number excluded automatically form the other set bool* curr_elements = new bool[n]; // The inclusion/exclusion array for final solution bool* soln = new bool[n]; int min_diff = INT_MAX; int sum = 0; for (int i=0; i<n; i++) { sum += arr[i]; curr_elements[i] = soln[i] = false; } // Find the solution using recursive function TOWUtil() TOWUtil(arr, n, curr_elements, 0, soln, &min_diff, sum, 0, 0); // Print the solution cout << "The first subset is: "; for (int i=0; i<n; i++) { if (soln[i] == true) cout << arr[i] << " "; } cout << "\nThe second subset is: "; for (int i=0; i<n; i++) { if (soln[i] == false) cout << arr[i] << " "; } } // Driver program to test above functions int main() { int arr[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}; int n = sizeof(arr)/sizeof(arr[0]); tugOfWar(arr, n); return 0; } 

   
   
   
   
4. タスク2

   ソリューションオプション：
   

    #include<stdio.h> /*Function to return max sum such that no two elements are adjacent */ int FindMaxSum(int arr[], int n) { int incl = arr[0]; int excl = 0; int excl_new; int i; for (i = 1; i < n; i++) { /* current max excluding i */ excl_new = (incl > excl)? incl: excl; /* current max including i */ incl = excl + arr[i]; excl = excl_new; } /* return max of incl and excl */ return ((incl > excl)? incl : excl); } /* Driver program to test above function */ int main() { int arr[] = {5, 5, 10, 100, 10, 5}; int n = sizeof(arr) / sizeof(arr[0]); printf("%dn", FindMaxSum(arr, n)); return 0; } 

   
   
   
   
5. タスク3

   ソリューションオプション：
   

    // Program to find the amount of water in j-th glass // of i-th row #include <stdio.h> #include <stdlib.h> #include <string.h> // Returns the amount of water in jth glass of ith row float findWater(int i, int j, float X) { // A row number i has maximum i columns. So input // column number must be less than i if (j > i) { printf("Incorrect Inputn"); exit(0); } // There will be i*(i+1)/2 glasses till ith row // (including ith row) float glass[i * (i + 1) / 2]; // Initialize all glasses as empty memset(glass, 0, sizeof(glass)); // Put all water in first glass int index = 0; glass[index] = X; // Now let the water flow to the downward glasses // till the row number is less than or/ equal to i (given row) // correction : X can be zero for side glasses as they have lower rate to fill for (int row = 1; row <= i ; ++row) { // Fill glasses in a given row. Number of // columns in a row is equal to row number for (int col = 1; col <= row; ++col, ++index) { // Get the water from current glass X = glass[index]; // Keep the amount less than or equal to // capacity in current glass glass[index] = (X >= 1.0f) ? 1.0f : X; // Get the remaining amount X = (X >= 1.0f) ? (X - 1) : 0.0f; // Distribute the remaining amount to // the down two glasses glass[index + row] += X / 2; glass[index + row + 1] += X / 2; } } // The index of jth glass in ith row will // be i*(i-1)/2 + j - 1 return glass[i*(i-1)/2 + j - 1]; } // Driver program to test above function int main() { int i = 2, j = 2; float X = 2.0; // Total amount of water printf("Amount of water in jth glass of ith row is: %f", findWater(i, j, X)); return 0; }