Problema n. ° 24: capacitación en TI: problemas y desafíos actuales de compañías líderes

Preguntas

1. Pollos
   

   Un agricultor vendió algunas gallinas a cuatro clientes diferentes en un día en particular. Fue tal que cada cliente compró la mitad de los pollos restantes y medio pollo más.
   
   ¿Puede averiguar cuántos pollos vendió el granjero ese día si le decimos que el cuarto cliente compró un solo pollo?

   
   
   Traducción

   En un día, el granjero vendió varias gallinas a cuatro compradores. Resultó que cada uno de ellos compró la mitad de los pollos restantes y otra mitad de película.
   
   ¿Puede decirme cuántas gallinas se vendieron ese día, si se sabe que el cuarto comprador compró un pollo entero?
   
   
   
2. Balas y revólver
   

   Un gángster ruso te secuestra. Pone dos balas en orden consecutivo en un revólver vacío de seis rondas, lo gira, lo apunta a la cabeza y dispara. * clic * Todavía estás vivo. Luego te pregunta: "¿quieres que gire de nuevo y dispare o apriete el gatillo de nuevo de inmediato?" Para cada opción, ¿cuál es la probabilidad de que te disparen?

   
   
   Traducción

   Fuiste secuestrado por un bandido ruso (¡ oh, estos estereotipos! ). Él insertó secuencialmente 2 balas en un revólver de seis disparos, desplazó el tambor, apuntó a su cabeza y apretó el gatillo. * clic *. Aun estas vivo El bandido te preguntó: "¿Quieres que me desplace de nuevo y dispare, o dispare inmediatamente?" ¿Cuál es la probabilidad de recibir un disparo en cada caso?
   
   
   

Las tareas

1. Ordenar una pila usando recursividad
   

   Dada una pila, la tarea es ordenarla usando recursividad. El uso de cualquier construcción de bucle como while, for..etc no está permitido. Solo podemos usar las siguientes funciones ADT en la Pila S:
   
   is_empty (S): prueba si la pila está vacía o no.
   push (S): agrega un nuevo elemento a la pila.
   pop (S): elimina el elemento superior de la pila.
   top (S): devuelve el valor del elemento superior. Tenga en cuenta que esta función no elimina el elemento de la pila.
   
   Ejemplo:
   
   Entrada: -3 <- Arriba
   14
   18 años
   -5
   30
   
   Salida: 30 <- Arriba
   18 años
   14
   -3
   -5

   
   
   Traducción

   Dada una pila, la tarea es ordenarla usando recursividad. Se prohíbe el uso de construcciones cíclicas, como while, for ... etc. Solo los siguientes comandos de abstracción están permitidos en la pila S:
   
   is_empty (S): Comprueba si la pila está vacía.
   push (S): agrega un nuevo elemento a la pila.
   pop (S): elimina el elemento superior de la pila.
   top (S): devuelve el valor del elemento superior. Tenga en cuenta que el elemento no se elimina al mismo tiempo.
   
   Ejemplos:
   
   Entrada: -3 <- Parte superior de la pila
   14
   18 años
   -5
   30
   
   Salida: 30 <- Parte superior de la pila
   18 años
   14
   -3
   -5
   
   

Dada una cadena de entrada y un diccionario de palabras, averigüe si la cadena de entrada puede segmentarse en una secuencia de palabras del diccionario separadas por espacios. Vea los siguientes ejemplos para más detalles.

Considere el siguiente diccionario
{i, like, sam, sung, samsung, mobile, ice,
crema, helado, hombre, ve, mango}

Entrada: como
Salida: sí
La cadena se puede segmentar como "me gusta".

Entrada: ilikesamsung
Salida: sí
La cadena se puede segmentar como "me gusta Samsung"
o "me gusta Sam Sung".

Una torre estable de altura n es una torre que consta de exactamente n fichas de altura de unidad apiladas verticalmente de tal manera que no se coloca ninguna ficha más grande en una ficha más pequeña. A continuación se muestra un ejemplo:

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

Tenemos un número infinito de fichas de tamaños 1, 2, ..., m. La tarea es calcular el número de diferentes torres estables de altura n que se pueden construir a partir de estos mosaicos, con una restricción que puede usar como máximo k mosaicos de cada tamaño en la torre.

Nota: Dos torres de altura n son diferentes si y solo si existe una altura h (1 <= h <= n), de modo que las torres tengan azulejos de diferentes tamaños a la altura h.

Ejemplos:

Entrada: n = 3, m = 3, k = 1.
Salida: 1
Posibles secuencias: {1, 2, 3}.
Por lo tanto, la respuesta es 1.

Entrada: n = 3, m = 3, k = 2.
Salida: 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]

Soluciones

1. Pregunta 1

   Respuesta: 15. Aquí explicaron por qué.
   
   
2. Pregunta 2

   En los comentarios respondí correctamente esta pregunta
   La probabilidad de que en la siguiente ranura del tambor haya un cartucho - 1/4
   Si desplaza el tambor, entonces la probabilidad de que se detenga en el cartucho es 2/6 = 1/3
   
   
   
3. Tarea 1

   Opción de solución, programación dinámica:
   

   #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. Tarea 2

   Solución 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. Tarea 3

   Opción de solución:
   

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