تمرينات

تمرين 12.6
اكتب عملية باسم areFactors تأخذ عدداً صحيحاً n ومصفوفة أعداد صحيحة، وتعيد القيمة true إذا كانت جميع الأرقام في المصفوفة عواملاً للعدد n (أي أن n يقبل القسمة عليهم جميعاً). مساعدة: انظر التمرين 6.1.
تمرين 12.7 اكتب عملية تأخذ مصفوفة أعداد صحيحة وعدد صحيح اسمه target كمتحولات، وتعيد الدليل الأول الذي يظهر target عنده في المصفوفة، وذلك في حال ظهوره، و1- فيما عدا ذلك.

تمرين 12.8

بعض المبرمجين يخالفون القاعدة العامة التي تقول بأن أسماء المتغيرات والعمليات يجب أن تكون ذات معنى يعبر عن وظيفتها. بدلاً من ذلك، يعتقد هؤلاء أن المتغيرات والعمليات يجب أن تسمى تيمناً بالفاكهة.
لكل واحدة من العمليات التالية، اكتب جملة واحدة تصف ما تفعله تلك العملية بشكل مبسَّط. ولكل متغير، اكتب جملة تعرف الدور الذي يؤديه.
كود:
public static int banana(int[] a) {
   int grape = 0;
   int i = 0;
   while (i < a.length) {
      grape = grape + a[i];
      i++;
   }
   return grape;
}
public static int apple(int[] a, int p) {
   int i = 0;
   int pear = 0;
   while (i < a.length) {
      if (a[i] == p) pear++;
      i++;
   }
   return pear;
}
public static int grapefruit(int[] a, int p) {
   for (int i = 0; i<a.length; i++) {
      if (a[i] == p) return i;
   }
   return -1;
}
الغرض من هذا التمرين هو التدرب على قراءة الشفرة والتعرف على أماط الحسابات التي شاهدناها من قبل.

تمرين 12.9

a. ما هو خرج البرنامج التالي؟
b. ارسم مخططاً هرمياً يبين حالة البرنامج قبيل عودة mus.
c. صف ما تفعله mus في بضعة كلمات.
كود:
public static int[] make(int n) {
  int[] a = new int[n];
  for (int i=0; i<n; i++) {
    a[i] = i+1;
  }
  return a;
}
public static void dub(int[] jub) {
  for (int i=0; i<jub.length; i++) {
    jub[i] *= 2;
  }
}
public static int mus(int[] zoo) {
  int fus = 0;
  for (int i=0; i<zoo.length; i++) {
    fus = fus + zoo[i];
  }
  return fus;
}
public static void main(String[] args) {
  int[] bob = make(5);
  dub(bob);
  System.out.println(mus(bob));
}

تمرين 12.10

معظم أساليب اجتياز المصفوفات التي رأيناها حتى الآن يمكن كتابتها بشكل تعاودي أيضاً. إن عمل ذلك ليس شائعاً، لكنه تمرين مفيد.
a. اكتب عملية باسم maxInRange تأخذ مصفوفة أعداد صحيحة ومجال من الأدلة (lowIndex وhighIndex)، وتوجد القيمة العظمى في المصفوفة، وذلك بمعالجة العناصر بين lowIndex وhighIndex فقط، بما في ذلك نهايتي المجال.
يجب أن تكون هذه العملية تعاودية. إذا كان طول المجال 1، أي إذا كان lowIndex == highIndex، سنعرف مباشرة أن العنصر الوحيد الوجود في المجال لا بد أن يكون أكبر قيمة موجودة. إذن تلك هي الحالة الأساسية (base case).
في حال وجود أكثر من عنصر واحد في المجال، يمكننا أن نجزئ المصفوفة إلى أجزاء، نوجد القيمة العظمى في كل قطعة، وبعدها نوجد القيمة العظمى للقيم العظمى.
b. العمليات مثل maxInRange قد تكون صعبة الاستخدام. لإيجاد العنصر الأكبر في مصفوفة، علينا تزويدها بمجال يحتوي المصفوفة بالكامل.
double max = maxInRange(array, 0, a.length-1);
اكتب عملية باسم max تأخذ مصفوفة كمعامل وتستعمل maxInRange لإيجاد وإعادة القيمة العظمى. أحياناً تدعى العمليات التي تشبه max بالعمليات المغلفة (wrapper methods)، لأنها تشكل طبقة عازلة حول العملية الغريبة وتجعل استخدامها أسهل. تدعى العملية التي تجري الحساب الفعلي بالعملية المساعدة (helper mthod).
اكتب نسخة تعاودية من العملية find باستخدام أسلوب العمليات المغلفة والمساعدة (wrapper-helper pattern). يجب أن تأخذ find مصفوفة أعداد صحيحة وعدد صحيح كهدف. عليها أن تعيد دليل الموقع الأول الذي يظهر فيه الهدف في المصفوفة، أما في حال عدم ظهوره تعيد القيمة 1-.

تمرين 12.11

من الطرق الغير فعالة كثيراً في ترتيب عناصر مصفوفة هي البحث عن العنصر الأكبر وتبديله مع العنصر الأول، بعدها إيجاد العنصر الأصغر منه مباشرة وتبديله مع العنصر الثاني، وهكذا. هذه الطريقة تدعى الترتيب الانتقائي (selection sort) – انظر http://en.wikipedia.com/wiki/Selection_sort.
a. اكتب عملية باسم indexOfMaxInRange تأخذ مصفوفة أعداد صحيحةـ وتوجد العنصر الأكبر في المجال المعطى، وتعيد دليله. يمكنك تعديل نسختك التعاودية من العملية maxInRange أو يمكنك كتابة نسخة تكرارية من الصفر.
b. اكتب عملية باسم swapElement تأخذ مصفوفة أعداد صحيحة ودليلين، وتبدل بين العنصرين الموجودين عند الدليلين المعطيين.
c. اكتب عملية باسم selectionSort تأخذ مصفوفة أعداد صحيحة وتستخدم indexOfMaxInRange وswapElement لترتيب المصفوفة من الأكبر إلى الأصغر.

تمرين 12.12

اكتب عملية باسم letterHist تأخذ سلسلة محرفية كمعامل وتعيد مخطط الأعمدة لأحرف السلسلة المحرفية. العنصر الصفري من المخطط يجب أن يحتوي على عدد أحرف a في السلسلة (كبير أو صغير)؛ العنصر الخامس والعشرون يجب أن يحتوي على عدد أحرف z. يجب على برنامجك أن يجتاز السلسلة المحرفية مرة واحدة.
تمرين 12.13 يقال عن الكلمة أنها doubloon إذا ظهر كل حرف من حروف الكلمة مرتين فيها. مثلاً، الكلمات التالية هي جميع الdoubloons التي وجدتها في قاموسي.
Abba, Anna, appall, appearer, appeases, arraigning, beriberi, bilabial, boob, Caucasus, coco, Dada, deed, Emmett, Hannah, horseshoer, intestines, Isis, mama, Mimi, murmur, noon, Otto, papa, peep, reappear, redder, sees, Shanghaiings, Toto
اكتب عملية باسم isDoubloon تعيد قيمة true إذا كانت الكلمة المعطاة doubloon وfalse فيما عدا ذلك.

تمرين 12.14

يقال عن كلمتين أنهما anagram (جناس تصحيفي) إذا كان لهما نفس الحروف (ونفس عدد التكرار لكل حرف). مثلاً، إذا أعدنا ترتيب "stop" ستصبح "pots"، و"allen downey" ستصبح "well annoyed".
اكتب عملية تأخذ سلسلتين محرفيتين وتعيد true إذا كان للسلسلتين نفس الحروف (لكن الترتيب مختلف).
تحد اختياري: اجعل البرنامج يقرأ محارف السلسلتين مرة واحدة فقط.

تمرين 12.15

في لعبة سكرابل، لكل لاعب مجموعة من القطع المكتوب عليها حروف، ويكون الهدف من اللعبة هو استعمال هذه الأحرف لتكوين كلمات. نظام حساب النقاط معقد، لكن الكلمات الأطول تساوي أكثر من الكلمات الأقصر في العادة.
تخيل أنك أعطيت مجموعة من القطع بشكل سلسلة محرفية، مثل "quijibo" وأنك أعطيت سلسلة أخرى لتختبرها، مثل "jib". اكتب عملية باسم canSpell تأخذ سلسلتين محرفيتين وتعيد true إذا كان تكوين الكلمة باستخدام مجموعة القطع ممكناً. يمكن أن تملك أكثر من قطعة بنفس الحرف، لكن لا يمكنك استعمال القطعة الواحدة أكثر من مرة.
تحد اختياري: اقرأ حروف السلسلتين مرة واحدة فقط.

تمرين 12.16

في لعبة سكرابل الحقيقية، يوجد قطع فارغة يمكن استعمالها لتمثل أي حرف مطلوب )أو ما يدعى wild card).
فكر بخوارزمية للعملية canSpell يمكن لها أن تعالج المحارف العامة. لا تشغل نفسك بتفاصيل المجريات مثل كيفية تمثيل الأحرف العامة. قم بوصف الخوارزمية وحسب، سواء باستعمال اللغة الطبيعية، أو باستعمال طريقة "الشفرة الزائفة" — pseudocode، أو Java.