Problem Nr. 24: IT-Schulung - aktuelle Probleme und Herausforderungen führender Unternehmen

Fragen

1. Hühner
   

   Ein Bauer verkaufte an einem bestimmten Tag ein paar Hühner an vier verschiedene Kunden. Es war so, dass jeder Kunde die Hälfte der verbleibenden Hühner und ein halbes Huhn mehr kaufte.
   
   Können Sie herausfinden, wie viele Hühner an diesem Tag vom Landwirt verkauft wurden, wenn wir Ihnen sagen, dass der vierte Kunde ein einzelnes Huhn gekauft hat?

   
   
   Übersetzung

   An einem Tag verkaufte der Bauer mehrere Hühner an vier Käufer. Es stellte sich heraus, dass jeder von ihnen die Hälfte der verbleibenden Hühner und einen weiteren halben Film kaufte.
   
   Können Sie mir sagen, wie viele Hühner an diesem Tag verkauft wurden, wenn bekannt ist, dass der 4. Käufer ein ganzes Huhn gekauft hat?
   
   
   
2. Kugeln und Revolver
   

   Ein russischer Gangster entführt dich. Er legt zwei Kugeln nacheinander in einen leeren Sechs-Runden-Revolver, dreht ihn, richtet ihn auf Ihren Kopf und schießt. * klick * Du lebst noch. Dann fragt er Sie: "Soll ich es noch einmal drehen und sofort abfeuern oder den Abzug betätigen?" Wie hoch ist die Wahrscheinlichkeit, dass Sie für jede Option erschossen werden?

   
   
   Übersetzung

   Sie wurden von einem russischen Banditen entführt ( oh, diese Stereotypen! ). Er steckte nacheinander zwei Kugeln in einen Sechs-Schuss-Revolver, rollte die Trommel, zielte auf Ihren Kopf und drückte den Abzug. * klick *. Du bist noch am Leben. Der Bandit fragte dich: "Soll ich noch einmal scrollen und schießen oder sofort schießen?" Wie hoch ist die Wahrscheinlichkeit, jeweils erschossen zu werden?
   
   
   

Die Aufgaben

1. Sortieren Sie einen Stapel mithilfe der Rekursion
   

   Bei einem Stapel besteht die Aufgabe darin, ihn mithilfe der Rekursion zu sortieren. Die Verwendung von Schleifenkonstrukten wie while, for..etc ist nicht zulässig. Wir können die folgenden ADT-Funktionen nur auf Stack S verwenden:
   
   is_empty (S): Testet, ob der Stapel leer ist oder nicht.
   push (S): Fügt dem Stapel ein neues Element hinzu.
   pop (S): Entfernt das oberste Element vom Stapel.
   top (S): Gibt den Wert des obersten Elements zurück. Beachten Sie, dass diese Funktion kein Element vom Stapel entfernt.
   
   Beispiel:
   
   Eingabe: -3 <- Oben
   14
   18
   -5
   30
   
   Ausgabe: 30 <- Oben
   18
   14
   -3
   -5

   
   
   Übersetzung

   Bei einem Stapel besteht die Aufgabe darin, ihn mithilfe der Rekursion zu sortieren. Die Verwendung von zyklischen Konstrukten wie while, for ... usw. ist verboten. Auf dem S-Stapel sind nur die folgenden Abstraktionsbefehle zulässig:
   
   is_empty (S): Überprüft, ob der Stapel leer ist.
   push (S): Fügt dem Stapel ein neues Element hinzu.
   pop (S): Entfernt das oberste Element des Stapels.
   top (S): Gibt den Wert des obersten Elements zurück. Bitte beachten Sie, dass der Artikel nicht gleichzeitig gelöscht wird.
   
   Beispiele:
   
   Eingabe: -3 <- Stapeloberseite
   14
   18
   -5
   30
   
   Ausgabe: 30 <- Oberseite des Stapels
   18
   14
   -3
   -5
   
   

Finden Sie anhand einer Eingabezeichenfolge und eines Wörterbuchs mit Wörtern heraus, ob die Eingabezeichenfolge in eine durch Leerzeichen getrennte Folge von Wörterbuchwörtern unterteilt werden kann. Weitere Informationen finden Sie in den folgenden Beispielen.

Betrachten Sie das folgende Wörterbuch
{Ich mag, Sam, gesungen, Samsung, Handy, Eis,
Sahne, Eis, Mann, geh, Mango}

Eingabe: ilike
Ausgabe: Ja
Die Zeichenfolge kann als "i like" segmentiert werden.

Eingabe: ilikesamsung
Ausgabe: Ja
Die Zeichenfolge kann als "Ich mag Samsung" segmentiert werden.
oder "Ich mag Sam Sung".

Ein stabiler Turm der Höhe n ist ein Turm, der aus genau n Kacheln der Einheitshöhe besteht, die vertikal so gestapelt sind, dass keine größere Kachel auf eine kleinere Kachel gelegt wird. Ein Beispiel ist unten gezeigt:

           [1]
        [2]
     [3]
 [4]

Wir haben unendlich viele Fliesen der Größen 1, 2, ..., m. Die Aufgabe besteht darin, die Anzahl der verschiedenen stabilen Türme der Höhe n zu berechnen, die aus diesen Kacheln gebaut werden können, mit einer Einschränkung, dass Sie höchstens k Kacheln jeder Größe im Turm verwenden können.

Hinweis: Zwei Türme der Höhe n unterscheiden sich genau dann, wenn eine Höhe h (1 <= h <= n) vorhanden ist, so dass die Türme in der Höhe h unterschiedlich große Kacheln aufweisen.

Beispiele:

Eingabe: n = 3, m = 3, k = 1.
Ausgabe: 1
Mögliche Folgen: {1, 2, 3}.
Daher lautet die Antwort 1.

Eingabe: n = 3, m = 3, k = 2.
Ausgabe: 7
{1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 2, 3}, {1, 3, 3}, {2, 2, 3}, {2 , 3, 3}.

           [1]
        [2]
     [3]
 [4]

Lösungen

1. Frage 1

   Antwort: 15. Hier erklärten sie warum.
   
   
2. Frage 2

   In den Kommentaren wurde diese Frage richtig beantwortet
   Die Wahrscheinlichkeit, dass sich im nächsten Schlitz der Trommel eine Patrone befindet - 1/4
   Wenn Sie die Trommel scrollen, beträgt die Wahrscheinlichkeit, dass sie auf der Patrone stoppt, 2/6 = 1/3
   
   
   
3. Aufgabe 1

   Lösungsoption, Dynamische Programmierung:
   

   #include <iostream> #include <string.h> using namespace std; /* A utility function to check whether a word is present in dictionary or not. An array of strings is used for dictionary. Using array of strings for dictionary is definitely not a good idea. We have used for simplicity of the program*/ int dictionaryContains(string word) { string dictionary[] = {"mobile","samsung","sam","sung","man","mango", "icecream","and","go","i","like","ice","cream"}; int size = sizeof(dictionary)/sizeof(dictionary[0]); for (int i = 0; i < size; i++) if (dictionary[i].compare(word) == 0) return true; return false; } // Returns true if string can be segmented into space separated // words, otherwise returns false bool wordBreak(string str) { int size = str.size(); if (size == 0) return true; // Create the DP table to store results of subroblems. The value wb[i] // will be true if str[0..i-1] can be segmented into dictionary words, // otherwise false. bool wb[size+1]; memset(wb, 0, sizeof(wb)); // Initialize all values as false. for (int i=1; i<=size; i++) { // if wb[i] is false, then check if current prefix can make it true. // Current prefix is "str.substr(0, i)" if (wb[i] == false && dictionaryContains( str.substr(0, i) )) wb[i] = true; // wb[i] is true, then check for all substrings starting from // (i+1)th character and store their results. if (wb[i] == true) { // If we reached the last prefix if (i == size) return true; for (int j = i+1; j <= size; j++) { // Update wb[j] if it is false and can be updated // Note the parameter passed to dictionaryContains() is // substring starting from index 'i' and length 'ji' if (wb[j] == false && dictionaryContains( str.substr(i, ji) )) wb[j] = true; // If we reached the last character if (j == size && wb[j] == true) return true; } } } /* Uncomment these lines to print DP table "wb[]" for (int i = 1; i <= size; i++) cout << " " << wb[i]; */ // If we have tried all prefixes and none of them worked return false; } // Driver program to test above functions int main() { wordBreak("ilikesamsung")? cout <<"Yesn": cout << "Non"; wordBreak("iiiiiiii")? cout <<"Yesn": cout << "Non"; wordBreak("")? cout <<"Yesn": cout << "Non"; wordBreak("ilikelikeimangoiii")? cout <<"Yesn": cout << "Non"; wordBreak("samsungandmango")? cout <<"Yesn": cout << "Non"; wordBreak("samsungandmangok")? cout <<"Yesn": cout << "Non"; return 0; } 

   
   
   
   
4. Aufgabe 2

   Lösung in Java:
   

    import java.util.ListIterator; import java.util.Stack; class Test { // Recursive Method to insert an item x in sorted way static void sortedInsert(Stack<Integer> s, int x) { // Base case: Either stack is empty or newly inserted // item is greater than top (more than all existing) if (s.isEmpty() || x > s.peek()) { s.push(x); return; } // If top is greater, remove the top item and recur int temp = s.pop(); sortedInsert(s, x); // Put back the top item removed earlier s.push(temp); } // Method to sort stack static void sortStack(Stack<Integer> s) { // If stack is not empty if (!s.isEmpty()) { // Remove the top item int x = s.pop(); // Sort remaining stack sortStack(s); // Push the top item back in sorted stack sortedInsert(s, x); } } // Utility Method to print contents of stack static void printStack(Stack<Integer> s) { ListIterator<Integer> lt = s.listIterator(); // forwarding while(lt.hasNext()) lt.next(); // printing from top to bottom while(lt.hasPrevious()) System.out.print(lt.previous()+" "); } // Driver method public static void main(String[] args) { Stack<Integer> s = new Stack<>(); s.push(30); s.push(-5); s.push(18); s.push(14); s.push(-3); System.out.println("Stack elements before sorting: "); printStack(s); sortStack(s); System.out.println(" \n\nStack elements after sorting:"); printStack(s); } } 

   
   
   
   
5. Aufgabe 3

   Lösungsoption:
   

    #include <bits/stdc++.h> using namespace std; #define N 100 int possibleWays(int n, int m, int k) { int dp[N][N]; int presum[N][N]; memset(dp, 0, sizeof dp); memset(presum, 0, sizeof presum); // Initialing 0th row to 0. for (int i = 1; i < n + 1; i++) { dp[0][i] = 0; presum[0][i] = 1; } // Initialing 0th column to 0. for (int i = 0; i < m + 1; i++) presum[i][0] = dp[i][0] = 1; // For each row from 1 to m for (int i = 1; i < m + 1; i++) { // For each column from 1 to n. for (int j = 1; j < n + 1; j++) { // Initialing dp[i][j] to presum of (i - 1, j). dp[i][j] = presum[i - 1][j]; if (j > k) { dp[i][j] -= presum[i - 1][j - k - 1]; } } // Calculating presum for each i, 1 <= i <= n. for (int j = 1; j < n + 1; j++) presum[i][j] = dp[i][j] + presum[i][j - 1]; } return dp[m][n]; } // Driver Program int main() { int n = 3, m = 3, k = 2; cout << possibleWays(n, m, k) << endl; return 0; }