Edisi # 24: Pelatihan TI - masalah saat ini dan tantangan dari perusahaan terkemuka

Pertanyaan

1. Ayam
   

   Seorang petani menjual beberapa ekor ayam kepada empat pelanggan yang berbeda pada hari tertentu. Sedemikian rupa sehingga setiap pelanggan membeli setengah dari ayam yang tersisa dan setengah ayam lagi.
   
   Bisakah Anda mencari tahu berapa banyak ayam yang dijual oleh petani pada hari itu jika kami memberi tahu Anda bahwa pelanggan keempat membeli satu ayam?

   
   
   Terjemahan

   Dalam satu hari, petani menjual beberapa ekor ayam kepada empat pembeli. Ternyata masing-masing dari mereka membeli setengah ayam yang tersisa dan setengah film lagi.
   
   Dapatkah Anda memberi tahu saya berapa banyak ayam yang dijual hari itu, jika diketahui bahwa pembeli keempat membeli ayam utuh?
   
   
   
2. Peluru dan revolver
   

   Seorang gangster Rusia menculikmu. Dia menempatkan dua peluru secara berurutan dalam revolver enam putaran kosong, memutarnya, mengarahkannya ke kepala dan menembak. * klik * Anda masih hidup. Dia kemudian bertanya kepada Anda, "apakah Anda ingin saya memutarnya lagi dan menembakkan atau menarik pelatuknya lagi segera?" Untuk setiap opsi, berapa probabilitas Anda akan ditembak?

   
   
   Terjemahan

   Anda diculik oleh bandit Rusia ( oh, stereotip ini! ). Dia secara berurutan memasukkan 2 peluru ke revolver enam tembakan, menggulir drum, mengarah ke kepala Anda dan menarik pelatuknya. * klik *. Kamu masih hidup. Bandit itu bertanya kepada Anda - "Apakah Anda ingin saya menggulir lagi dan menembak, atau segera menembak?" Berapa probabilitas ditembak di setiap kasus?
   
   
   

Tugasnya

1. Sortir tumpukan menggunakan rekursi
   

   Diberikan tumpukan, tugasnya adalah mengurutkannya menggunakan rekursi. Penggunaan konstruksi loop apa pun seperti while, for..etc tidak diizinkan. Kami hanya dapat menggunakan fungsi ADT berikut di Stack S:
   
   is_empty (S): Menguji apakah tumpukan kosong atau tidak.
   push (S): Menambahkan elemen baru ke stack.
   pop (S): Menghapus elemen atas dari tumpukan.
   top (S): Mengembalikan nilai elemen atas. Perhatikan bahwa fungsi ini tidak menghapus elemen dari tumpukan.
   
   Contoh:
   
   Input: -3 <- Atas
   14
   18
   -5
   30
   
   Output: 30 <- Atas
   18
   14
   -3
   -5

   
   
   Terjemahan

   Diberikan tumpukan, tugasnya adalah mengurutkannya menggunakan rekursi. Penggunaan konstruksi siklik, seperti sementara, untuk ..., dll. Dilarang. Hanya perintah abstraksi berikut yang diizinkan pada S stack:
   
   is_empty (S): Memeriksa apakah stack kosong.
   push (S): Menambahkan item baru ke stack.
   pop (S): Menghapus elemen atas tumpukan.
   top (S): Mengembalikan nilai elemen atas. Harap perhatikan bahwa item tersebut tidak dihapus secara bersamaan.
   
   Contoh:
   
   Input: -3 <- Atas tumpukan
   14
   18
   -5
   30
   
   Output: 30 <- Atas tumpukan
   18
   14
   -3
   -5
   
   

Diberikan string input dan kamus kata, cari tahu apakah string input dapat tersegmentasi ke dalam urutan kata kamus yang dipisahkan oleh spasi. Lihat contoh berikut untuk detail lebih lanjut.

Pertimbangkan kamus berikut
{i, seperti, sam, dinyanyikan, samsung, ponsel, es,
krim, es krim, bung, pergi, mangga}

Input: ilike
Keluaran: Ya
String dapat disegmentasi sebagai "saya suka".

Input: ilikesamsung
Keluaran: Ya
Tali dapat tersegmentasi sebagai "saya suka samsung"
atau "aku suka sam dinyanyikan".

Menara dengan tinggi stabil n adalah menara yang terdiri dari tepat n ubin dengan tinggi satuan yang ditumpuk sedemikian rupa, sehingga tidak ada ubin yang lebih besar ditempatkan di ubin yang lebih kecil. Contohnya ditunjukkan di bawah ini:

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

Kami memiliki jumlah ubin yang tak terbatas dengan ukuran 1, 2, ..., m. Tugasnya adalah menghitung jumlah menara tinggi dan n stabil yang berbeda yang dapat dibangun dari ubin ini, dengan batasan yang dapat Anda gunakan paling banyak k ubin dari setiap ukuran di menara.

Catatan: Dua menara dengan tinggi n berbeda jika dan hanya jika ada tinggi h (1 <= h <= n), sehingga menara memiliki ubin dengan ukuran berbeda pada ketinggian h.

Contoh:

Input: n = 3, m = 3, k = 1.
Output: 1
Kemungkinan urutan: {1, 2, 3}.
Maka jawabannya adalah 1.

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

Solusi

1. Pertanyaan 1

   Jawab: 15. Di sini mereka menjelaskan alasannya.
   
   
2. Pertanyaan 2

   Dalam komentar menjawab pertanyaan ini dengan benar
   Probabilitas bahwa dalam slot drum berikutnya adalah kartrid - 1/4
   Jika Anda menggulir drum, maka kemungkinannya akan berhenti pada kartrid adalah 2/6 = 1/3
   
   
   
3. Tugas 1

   Opsi Solusi, Pemrograman Dinamis:
   

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

   Solusi di 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. Tugas 3

   Opsi Solusi:
   

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