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

الأسئلة

1. المغناطيس والمغناطيسية وغير المغناطيسية
   

   كيف يمكنك التفريق بين المغناطيس والمغناطيسية والمواد غير المغناطيسية؟

   
   
   الترجمة

   كيف تميز المغناطيس والمواد المغناطيسية وغير المغناطيسية؟ ( سؤال تقريبًا عن الحديد من منظور غير متوقع. يتطلب بعض المعرفة بالفيزياء )
   
2. عدوى فيروسية
   

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

   
   
   الترجمة

   يواجه العالم عدوى فيروسية رهيبة. الحكومات في جميع البلدان تعطي كل مواطن زجاجتين من الأدوية. لقد أعطيت لك نفس المجموعة. تحتاج إلى تناول قرص واحد من كل زجاجة يوميًا لمدة شهر للحصول على مناعة ضد الفيروس. إذا تناولت حبة واحدة فقط أو اثنتين من نفس الزجاجة ، فإن موتًا مؤلمًا سيحدث.
   
   عند تناول حصة أخرى من الأجهزة اللوحية ، تفتح الزجاجتين وتسكب الأقراص بسرعة في راحة يدك. في وقت متأخر ، لكنك تفهم أن ثلاث أقراص قد انسكبت ، بالإضافة إلى حقيقة أنها تبدو متشابهة تمامًا. لا يمكن التخلص من الجهاز اللوحي ، لأن الكمية محدودة ، ولا يمكنك إعادتها ، وإلا ، في حالة حدوث خطأ ، ستموت يومًا ما. كيف ستحل هذه المشكلة؟
   
   ( ملاحظة كانت هناك مهمة مماثلة بالفعل في الإصدارات السابقة. )
   

المهام

1. فرز العناصر حسب التردد
   

   اطبع عناصر المصفوفة بتردد تنازلي. إذا كان لرقمين نفس التردد ، فقم بطباعة الرقم الذي جاء أولاً.
   
   أمثلة:
   
   الإدخال: arr [] = {2، 5، 2، 8، 5، 6، 8، 8}
   الإخراج: arr [] = {8، 8، 8، 2، 2، 5، 5، 6}
   
   الإدخال: arr [] = {2، 5، 2، 6، -1، 9999999، 5، 8، 8، 8}
   الإخراج: arr [] = {8، 8، 8، 2، 2، 5، 5، 6، -1، 9999999}
   

   
   
   الترجمة

   اطبع عناصر المصفوفة بترتيب تنازلي لتكرار الحدوث. إذا كان لرقمين نفس التردد - الإخراج أولاً ما يحدث أولاً.
   
   أمثلة:
   
   الإدخال: arr [] = {2، 5، 2، 8، 5، 6، 8، 8}
   الإخراج: arr [] = {8، 8، 8، 2، 2، 5، 5، 6}
   
   الإدخال: arr [] = {2، 5، 2، 6، -1، 9999999، 5، 8، 8، 8}
   الإخراج: arr [] = {8، 8، 8، 2، 2، 5، 5، 6، -1، 9999999}
2. تحقق bst
   

   شجرة البحث الثنائية (BST) هي بنية بيانات شجرة ثنائية قائمة على العقدة لها الخصائص التالية.
   
   • تحتوي الشجرة الفرعية اليسرى للعُقدة على عُقد ذات مفاتيح أقل من مفتاح العقدة فقط.
   • تحتوي الشجرة الفرعية الصحيحة للعقدة على عقد ذات مفاتيح أكبر من مفتاح العقدة فقط.
   • يجب أن تكون كلتا الشريحتين اليسرى واليمنى أشجار بحث ثنائية.
   
   من الخصائص المذكورة أعلاه ، يتبع بشكل طبيعي ما يلي:
   • لكل عقدة (عنصر في الشجرة) مفتاح مميز.
   
   

                         4
                      / \
                    2 5
                  / \
                1 3
   

   
   مهمتك هي إنشاء برنامج للتحقق مما إذا كانت شجرة ثنائية BST أم لا.
   

   
   
   الترجمة

   إعطاء شجرة بحث ثنائية لها الخصائص التالية:
   * تحتوي الشجرة الفرعية اليسرى لكل عقدة على أرقام أقل من قيمة هذه العقدة.
   * تحتوي الشجرة الفرعية الصحيحة لكل عقدة على أرقام أكبر من قيمة هذه العقدة.
   * كلا الشريحتين اليسرى واليمنى عبارة عن أشجار بحث ثنائية.
   
   من الموصوف ، يتبع ذلك أن كل عقدة في الشجرة تحتوي على مفتاح فريد.
   
   

                         4
                      / \
                    2 5
                  / \
                1 3
   

   
   مهمتك هي كتابة برنامج للتحقق مما إذا كانت الشجرة شجرة بحث ثنائية أم لا.
3. لتر وماء وسفينتان "مترابطتان"
   

   هناك سفينتان بسعة "أ" و "ب" على التوالي. لدينا إمدادات المياه اللانهائية. قدم خوارزمية فعالة لتصنيع 1 لتر من الماء في أحد الأوعية. يمكنك رمي كل الماء من أي وعاء في أي وقت. افترض أن "أ" و "ب" عبارة عن نسختين مشتركتين.

   
   
   الترجمة

   إعطاء سفينتين بسعة "أ" و "ب" ومصدر لا نهاية له من المياه. اقترح خوارزمية فعالة لقياس 1 لتر بالضبط من الماء باستخدام هذه الأوعية. يمكنك صب كل الماء من أي وعاء في أي وقت. نفترض أيضًا أن "a" و "b" هما نظام مشترك .
   

الحلول

1. السؤال 1

   اقترح أنديول حل .
   
   
   
2. السؤال 2

   في التعليقات ، اقترحوا الحل الصحيح - هنا وهنا - أيضًا بعض الخيارات.
   
   
   
3. المهمة 1

   الحل الأولي:
   

   #include<bits/stdc++.h> using namespace std; // Used for sorting struct ele { int count, index, val; }; // Used for sorting by value bool mycomp(struct ele a, struct ele b) { return (a.val < b.val); } // Used for sorting by frequency. And if frequency is same, // then by appearance bool mycomp2(struct ele a, struct ele b) { if (a.count != b.count) return (a.count < b.count); else return a.index > b.index; } void sortByFrequency(int arr[], int n) { struct ele element[n]; for (int i = 0; i < n; i++) { element[i].index = i; /* Fill Indexes */ element[i].count = 0; /* Initialize counts as 0 */ element[i].val = arr[i]; /* Fill values in structure elements */ } /* Sort the structure elements according to value, we used stable sort so relative order is maintained. */ stable_sort(element, element+n, mycomp); /* initialize count of first element as 1 */ element[0].count = 1; /* Count occurrences of remaining elements */ for (int i = 1; i < n; i++) { if (element[i].val == element[i-1].val) { element[i].count += element[i-1].count+1; /* Set count of previous element as -1 , we are doing this because we'll again sort on the basis of counts (if counts are equal than on the basis of index)*/ element[i-1].count = -1; /* Retain the first index (Remember first index is always present in the first duplicate we used stable sort. */ element[i].index = element[i-1].index; } /* Else If previous element is not equal to current so set the count to 1 */ else element[i].count = 1; } /* Now we have counts and first index for each element so now sort on the basis of count and in case of tie use index to sort.*/ stable_sort(element, element+n, mycomp2); for (int i = n-1, index=0; i >= 0; i--) if (element[i].count != -1) for (int j=0; j<element[i].count; j++) arr[index++] = element[i].val; } // Driver program int main() { int arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}; int n = sizeof(arr)/sizeof(arr[0]); sortByFrequency(arr, n); for (int i=0; i<n; i++) cout << arr[i] << " "; return 0; } 

   
   
   
   
4. المهمة 2

   حل جافا:
   

    /Java implementation to check if given Binary tree //is a BST or not /* Class containing left and right child of current node and key value*/ class Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; } } public class BinaryTree { //Root of the Binary Tree Node root; /* can give min and max value according to your code or can write a function to find min and max value of tree. */ /* returns true if given search tree is binary search tree (efficient version) */ boolean isBST() { return isBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } /* Returns true if the given tree is a BST and its values are >= min and <= max. */ boolean isBSTUtil(Node node, int min, int max) { /* an empty tree is BST */ if (node == null) return true; /* false if this node violates the min/max constraints */ if (node.data < min || node.data > max) return false; /* otherwise check the subtrees recursively tightening the min/max constraints */ // Allow only distinct values return (isBSTUtil(node.left, min, node.data-1) && isBSTUtil(node.right, node.data+1, max)); } /* Driver program to test above functions */ public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node(4); tree.root.left = new Node(2); tree.root.right = new Node(5); tree.root.left.left = new Node(1); tree.root.left.right = new Node(3); if (tree.isBST()) System.out.println("IS BST"); else System.out.println("Not a BST"); } } 

   
   
   
   
5. المهمة 3

   خيار الحل:
   

    #include <iostream> using namespace std; // A utility function to get GCD of two numbers int gcd(int a, int b) { return b? gcd(b, a % b) : a; } // Class to represent a Vessel class Vessel { // A vessel has capacity, and current amount of water in it int capacity, current; public: // Constructor: initializes capacity as given, and current as 0 Vessel(int capacity) { this->capacity = capacity; current = 0; } // The main function to fill one litre in this vessel. Capacity of V2 // must be greater than this vessel and two capacities must be co-prime void makeOneLitre(Vessel &V2); // Fills vessel with given amount and returns the amount of water // transferred to it. If the vessel becomes full, then the vessel // is made empty. int transfer(int amount); }; // The main function to fill one litre in this vessel. Capacity // of V2 must be greater than this vessel and two capacities // must be coprime void Vessel:: makeOneLitre(Vessel &V2) { // solution exists iff a and b are co-prime if (gcd(capacity, V2.capacity) != 1) return; while (current != 1) { // fill A (smaller vessel) if (current == 0) current = capacity; cout << "Vessel 1: " << current << " Vessel 2: " << V2.current << endl; // Transfer water from V1 to V2 and reduce current of V1 by // the amount equal to transferred water current = current - V2.transfer(current); } // Finally, there will be 1 litre in vessel 1 cout << "Vessel 1: " << current << " Vessel 2: " << V2.current << endl; } // Fills vessel with given amount and returns the amount of water // transferred to it. If the vessel becomes full, then the vessel // is made empty int Vessel::transfer(int amount) { // If the vessel can accommodate the given amount if (current + amount < capacity) { current += amount; return amount; } // If the vessel cannot accommodate the given amount, then // store the amount of water transferred int transferred = capacity - current; // Since the vessel becomes full, make the vessel // empty so that it can be filled again current = 0; return transferred; } // Driver program to test above function int main() { int a = 3, b = 7; // a must be smaller than b // Create two vessels of capacities a and b Vessel V1(a), V2(b); // Get 1 litre in first vessel V1.makeOneLitre(V2); return 0; }