第24期：IT培训-领先公司的当前问题和挑战

问题

1. 鸡
   

   一位农民在特定的一天将几只鸡卖给了四个不同的顾客。 如此一来，每个客户购买了剩余鸡只的一半，又购买了一半。
   
   如果我们告诉您第四位顾客购买了一只鸡，您能找出当日农民出售了多少只鸡吗？

   
   
   笔译

   有一天，农夫把几只鸡卖给了四个买主。 原来，他们每个人都买了剩下的一半的鸡肉和另一半的胶片。
   
   如果知道第四位购买者买了整只鸡，您能告诉我那天卖了几只鸡吗？
   
   
   
2. 子弹和左轮手枪
   

   一名俄罗斯黑帮绑架了您。 他将两枚子弹以连续的顺序放在空的六发左轮手枪中，旋转它，将其指向您的头部射击。 *单击*您还活着。 然后，他问您：“您是否要我再次旋转它，立即开火或再次扳动扳机？” 对于每个选项，您被枪杀的概率是多少？

   
   
   笔译

   您被俄罗斯强盗绑架了（ 哦，这些成见！ ）。 他依次将2发子弹插入6发左轮手枪，滚动了鼓，对准了您的头部，然后扣动了扳机。 *单击*。 你还活着。 匪徒问您-“您要我再次滚动并拍摄还是立即拍摄？” 在每种情况下被枪击的概率是多少？
   
   
   

任务

1. 使用递归对堆栈进行排序
   

   给定一个堆栈，任务是使用递归对其进行排序。 不允许使用while，for..etc等任何循环结构。 我们只能在Stack S上使用以下ADT函数：
   
   is_empty（S）：测试堆栈是否为空。
   推（S）：将新元素添加到堆栈中。
   pop（S）：从堆栈中删除顶部元素。
   top（S）：返回top元素的值。 请注意，此功能不会从堆栈中删除元素。
   
   范例：
   
   输入：-3 <-顶部
   14
   18岁
   -5
   30
   
   输出：30 <-顶部
   18岁
   14
   -3
   -5

   
   
   笔译

   给定一个堆栈，任务是使用递归对其进行排序。 禁止使用循环构造，例如while，for等。 S堆栈上仅允许使用以下抽象命令：
   
   is_empty（S）：检查堆栈是否为空。
   推（S）：将新项目添加到堆栈中。
   弹出（S）：删除堆栈的顶部元素。
   top（S）：返回top元素的值。 请注意，该项目不能同时删除。
   
   范例：
   
   输入：-3 <-堆栈顶部
   14
   18岁
   -5
   30
   
   输出：30 <-堆栈顶部
   18岁
   14
   -3
   -5
   
   

给定一个输入字符串和一个单词词典，找出是否可以将输入字符串分段成一个空格分隔的词典单词序列。 有关更多详细信息，请参见以下示例。

考虑以下字典
{i，例如sam，sung，samsung，mobile，冰，
奶油，冰淇淋，男人，去，芒果}

输入：ilike
输出：是
该字符串可以分段为“我喜欢”。

输入：ilikesamsung
输出：是
该字符串可以分段为“我喜欢三星”
或“我喜欢三星”。

高度为n的稳定塔是这样一种塔，它由正好垂直堆叠的n个单位高度的瓷砖组成，这样就不会在较小的瓷砖上放置较大的瓷砖。 下面是一个示例：

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

我们有无数个大小为1、2，...，m的图块。 任务是计算可以从这些图块构建的高度为n的不同稳定塔的数量，但要限制在塔中最多只能使用每种大小的k个图块。

注意：当且仅当存在高度h（1 <= h <= n）时，两个高度n的塔不同，这样，两个塔在高度h处具有不同大小的图块。

范例：

输入：n = 3，m = 3，k = 1。
输出1
可能的顺序：{1,2,3}。
因此答案是1。

输入：n = 3，m = 3，k = 2
输出：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]

解决方案

1. 问题1

   答：15. 他们在这里解释了原因。
   
   
2. 问题2

   在评论中正确回答了这个问题
   感光鼓下一个插槽中有墨盒的可能性-1/4
   如果滚动感光鼓，则它将停止在墨盒上的概率为2/6 = 1/3
   
   
   
3. 任务1

   解决方案选项，动态编程：
   

   #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. 任务2

   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. 任务3

   解决方案选项：
   

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