المسألة رقم 24: التدريب على تكنولوجيا المعلومات - القضايا والتحديات الحالية من الشركات الرائدة

الأسئلة

1. الدجاج
   

   قام مزارع ببيع بعض الدجاج لأربعة عملاء مختلفين في يوم معين. كان ذلك أن كل عميل اشترى نصف الدجاج المتبقي ونصف دجاجة أخرى.
   
   هل يمكنك معرفة عدد الدواجن التي تم بيعها من قبل المزارع في ذلك اليوم إذا أخبرناك أن العميل الرابع اشترى دجاجة واحدة؟

   
   
   الترجمة

   في يوم واحد ، باع المزارع عدة دجاجات لأربعة مشترين. اتضح أن كل واحد منهم اشترى نصف الدجاج المتبقي ونصف فيلم آخر.
   
   هل يمكنك إخباري بعدد الدجاج الذي تم بيعه في ذلك اليوم ، إذا كان من المعروف أن المشتري الرابع اشترى دجاجة كاملة؟
   
   
   
2. الرصاص و المسدس
   

   رجل عصابات روسي يختطفك. يضع رميتين متتاليتين في مسدس فارغ من ست جولات ، يدورها ، يوجهها إلى رأسك ويطلق النار. * انقر * أنت ما زلت على قيد الحياة. ثم يسألك ، "هل تريد مني أن أدورها مرة أخرى وأطلق النار أو اسحب الزناد مرة أخرى على الفور؟" لكل خيار ، ما هو احتمال أن يتم إطلاق النار عليك؟

   
   
   الترجمة

   لقد تم اختطافك من قبل قطاع طرق روسي ( أوه ، هذه الصور النمطية! ). قام بإدخال 2 رصاصة بالتسلسل في مسدس من ست طلقات ، ودحرج الأسطوانة ، صوب رأسك وسحب الزناد. * اضغط *. أنت ما زلت على قيد الحياة. سألتك قاطعة الطريق - "هل تريد مني التمرير مرة أخرى والتصوير أو التصوير على الفور؟" ما هو احتمال إطلاق النار في كل حالة؟
   
   
   

المهام

1. فرز مكدس باستخدام العودية
   

   بالنظر إلى المكدس ، فإن المهمة هي فرزها باستخدام العودية. استخدام أي بنيات حلقة مثل حين ، ل .. الخ غير مسموح. يمكننا فقط استخدام وظائف ADT التالية على Stack S:
   
   is_empty (S): اختبار ما إذا كان المكدس فارغًا أم لا.
   push (S): إضافة عنصر جديد إلى المكدس.
   pop (S): إزالة العنصر العلوي من المكدس.
   top (S): إرجاع قيمة العنصر العلوي. لاحظ أن هذه الوظيفة لا تزيل العنصر من المكدس.
   
   مثال:
   
   الإدخال: -3 <- Top
   14
   18
   -5
   30
   
   الإخراج: 30 <- أعلى
   18
   14
   -3
   -5

   
   
   الترجمة

   بالنظر إلى المكدس ، فإن المهمة هي فرزها باستخدام العودية. يحظر استخدام التركيبات الدورية ، مثل حين ، لـ ... ، وما إلى ذلك. يُسمح فقط بأوامر التجريد التالية على مكدس S:
   
   is_empty (S): للتحقق مما إذا كان المكدس فارغًا.
   push (S): إضافة عنصر جديد إلى المكدس.
   pop (S): إزالة العنصر العلوي من المكدس.
   top (S): إرجاع قيمة العنصر العلوي. يرجى ملاحظة أن العنصر لم يتم حذفه في نفس الوقت.
   
   أمثلة:
   
   الإدخال: -3 <- أعلى المكدس
   14
   18
   -5
   30
   
   الإخراج: 30 <- أعلى المكدس
   18
   14
   -3
   -5
   
   

بالنظر إلى سلسلة الإدخال وقاموس الكلمات ، اكتشف ما إذا كان يمكن تقسيم سلسلة الإدخال إلى تسلسل مفصول بمسافة من كلمات القاموس. راجع الأمثلة التالية لمزيد من التفاصيل.

تأمل القاموس التالي
{i ، مثل ، sam ، sung ، samsung ، mobile ، ice ،
كريم ، آيس كريم ، رجل ، اذهب ، مانجو}

الإدخال: ilike
الإخراج: نعم
يمكن تقسيم السلسلة على أنها "أحب".

الإدخال: ilikesamsung
الإخراج: نعم
يمكن تقسيم السلسلة كـ "i like samsung"
أو "أحب سام سونغ".

البرج المستقر للارتفاع n عبارة عن برج يتكون من n بلاطات بالضبط من ارتفاع الوحدة مكدسة رأسيًا بهذه الطريقة ، بحيث لا يتم وضع بلاطة أكبر على بلاطة أصغر. يتم عرض مثال أدناه:

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

لدينا عدد لا نهائي من البلاط بأحجام 1 ، 2 ، ... ، م. المهمة هي حساب عدد الأبراج المستقرة المختلفة للارتفاع n التي يمكن بناؤها من هذه البلاطات ، مع تقييد يمكنك استخدامه كحد أقصى من البلاط في كل حجم في البرج.

ملاحظة: يختلف برجان من الارتفاع n إذا وفقط إذا كان هناك ارتفاع h (1 <= h <= n) ، بحيث يكون للأبراج بلاط بأحجام مختلفة عند الارتفاع h.

أمثلة:

الإدخال: ن = 3 ، م = 3 ، ك = 1.
الإخراج: 1
التسلسلات المحتملة: {1 ، 2 ، 3}.
وبالتالي فإن الإجابة هي 1.

المدخلات: ن = 3 ، م = 3 ، ك = 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

   الحل في جافا:
   

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