Numéro 24: Formation informatique - problèmes et défis actuels des grandes entreprises

Des questions

1. Poulets
   

   Un agriculteur a vendu quelques poulets à quatre clients différents un jour donné. Il était tel que chaque client a acheté la moitié des poulets restants et un demi-poulet de plus.
   
   Pouvez-vous savoir combien de poulets ont été vendus par l'agriculteur ce jour-là si nous vous disons que le quatrième client a acheté un seul poulet?

   
   
   La traduction

   En une journée, l'agriculteur a vendu plusieurs poulets à quatre acheteurs. Il s'est avéré que chacun d'eux a acheté la moitié des poulets restants et un autre demi-film.
   
   Pouvez-vous me dire combien de poulets ont été vendus ce jour-là, si l'on sait que le 4e acheteur a acheté un poulet entier?
   
   
   
2. Balles et revolver
   

   Un gangster russe vous kidnappe. Il met deux balles dans un ordre consécutif dans un revolver à six coups vide, le fait tourner, le pointe vers votre tête et tire. * cliquez * Vous êtes toujours en vie. Il vous demande ensuite: "voulez-vous que je le fasse tourner à nouveau et que je tire ou que j'appuie à nouveau sur la détente tout de suite?" Pour chaque option, quelle est la probabilité que vous soyez abattu?

   
   
   La traduction

   Vous avez été kidnappé par un bandit russe ( oh, ces stéréotypes! ). Il a séquentiellement inséré 2 balles dans un revolver à six coups, a fait défiler le tambour, a visé votre tête et a appuyé sur la détente. * cliquez sur *. Tu es toujours en vie. Le bandit vous a demandé - "Voulez-vous que je fasse défiler à nouveau et que je tire, ou que je tire immédiatement?" Quelle est la probabilité d'être abattu dans chaque cas?
   
   
   

Les tâches

1. Trier une pile à l'aide de la récursivité
   

   Étant donné une pile, la tâche consiste à la trier à l'aide de la récursivité. L'utilisation de n'importe quelle construction de boucle comme while, for..etc n'est pas autorisée. Nous ne pouvons utiliser que les fonctions ADT suivantes sur la pile S:
   
   is_empty (S): teste si la pile est vide ou non.
   push (S): ajoute un nouvel élément à la pile.
   pop (S): supprime l'élément supérieur de la pile.
   top (S): Renvoie la valeur de l'élément supérieur. Notez que cette fonction ne supprime pas d'élément de la pile.
   
   Exemple:
   
   Entrée: -3 <- Haut
   14
   18
   -5
   30
   
   Sortie: 30 <- Haut
   18
   14
   -3
   -5

   
   
   La traduction

   Étant donné une pile, la tâche consiste à la trier à l'aide de la récursivité. L'utilisation de constructions cycliques, telles que while, for ... etc. est interdite. Seules les commandes d'abstraction suivantes sont autorisées sur la pile S:
   
   is_empty (S): vérifie si la pile est vide.
   push (S): ajoute un nouvel élément à la pile.
   pop (S): supprime l'élément supérieur de la pile.
   top (S): renvoie la valeur de l'élément supérieur. Veuillez noter que l'élément n'est pas supprimé en même temps.
   
   Exemples:
   
   Entrée: -3 <- Haut de la pile
   14
   18
   -5
   30
   
   Sortie: 30 <- Haut de la pile
   18
   14
   -3
   -5
   
   

Étant donné une chaîne d'entrée et un dictionnaire de mots, découvrez si la chaîne d'entrée peut être segmentée en une séquence de mots de dictionnaire séparée par des espaces. Voir les exemples suivants pour plus de détails.

Considérez le dictionnaire suivant
{i, comme, sam, chanté, samsung, mobile, glace,
crème, glace, homme, allez, mangue}

Entrée: ilike
Sortie: Oui
La chaîne peut être segmentée en "j'aime".

Entrée: ilikesamsung
Sortie: Oui
La chaîne peut être segmentée en "j'aime samsung"
ou "j'aime sam chanté".

Une tour stable de hauteur n est une tour composée exactement de n tuiles de hauteur unitaire empilées verticalement de manière à ce qu'aucune tuile plus grosse ne soit placée sur une tuile plus petite. Un exemple est illustré ci-dessous:

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

Nous avons un nombre infini de carreaux de tailles 1, 2, ..., m. La tâche consiste à calculer le nombre de différentes tours stables de hauteur n qui peuvent être construites à partir de ces tuiles, avec une restriction que vous pouvez utiliser au plus k tuiles de chaque taille dans la tour.

Remarque: Deux tours de hauteur n sont différentes si et seulement s'il existe une hauteur h (1 <= h <= n), de sorte que les tours ont des tuiles de tailles différentes à la hauteur h.

Exemples:

Entrée: n = 3, m = 3, k = 1.
Sortie: 1
Séquences possibles: {1, 2, 3}.
La réponse est donc 1.

Entrée: n = 3, m = 3, k = 2.
Sortie: 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]

Des solutions

1. Question 1

   Réponse: 15. Ici, ils ont expliqué pourquoi.
   
   
2. Question 2

   Dans les commentaires répondu correctement à cette question
   La probabilité que dans la prochaine fente du tambour se trouve une cartouche - 1/4
   Si vous faites défiler le tambour, la probabilité qu'il s'arrête sur la cartouche est de 2/6 = 1/3
   
   
   
3. Tâche 1

   Option de solution, programmation dynamique:
   

   #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. Tâche 2

   Solution en 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. Tâche 3

   Option de solution:
   

    #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; }