מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - אביב 2024 מועד ב'
הנדסת תוכנה · סמל 97104 · 14 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), אביב 2024 מועד ב', כל 14 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 16)
בכל מבחן 14 שאלות.
שאלות 1-7: יש לענות על ארבע שאלות בלבד. ערך כל שאלה - 12 נקודות.
שאלות 8-11: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 15 נקודות.
שאלות 12-14: יש לענות על שתי שאלות בלבד. ערך כל שאלה - 11 נקודות.
חומר עזר: 1. מחשבון (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · מספרים אקראיים תלת-ספרתיים: מינימום וסכום ספרות
כתבו קטע תוכנית המייצר 50 מספרים שלמים אקראיים חיוביים תלת ספרתיים.
על התוכנית להדפיס את המספר הקטן ביותר שנוצר ואת סכום ספרותיו.
◂ פתרון מלא לשאלה 1
פתרון
לולאה של 50 סיבובים מגרילה מספר בין 100 ל-999 ומעדכנת מינימום; אחרי הלולאה מפרקים את המינימום לספרות (%10, /10) ומדפיסים אותו ואת סכום ספרותיו.
הרעיון: מספר תלת-ספרתי חיובי הוא מספר בין 100 ל-999 (כולל), ולכן מגרילים לפי הנוסחה מההנחיות עם ו-. בזמן ההגרלה שומרים את הקטן ביותר עד כה, ובסוף מחשבים את סכום ספרותיו.
1. מינימום: מאתחלים `min = 1000` – ערך גדול מכל מספר תלת-ספרתי, כך שהמספר הראשון שיוגרל בוודאות יחליף אותו. בכל סיבוב, אם המספר החדש קטן מ-min, מעדכנים את min. (אפשר גם לאתחל את min במספר הראשון שהוגרל.)
2. סכום ספרות: אחרי הלולאה עובדים על עותק `n` של המינימום. בכל סיבוב `n % 10` היא הספרה הימנית – מוסיפים אותה לסכום, ו-`n / 10` מוחק אותה. כשמגיעים ל-0 עברנו על כל הספרות. למשל עבור 107: .
3. מדפיסים את המינימום ואת סכום ספרותיו. (הדפסת 50 המספרים עצמם אינה חובה, היא רק מאפשרת לראות שהתוצאה נכונה.)
סיבוכיות: 50 סיבובים ועוד 3 סיבובים לפירוק הספרות – מספר קבוע של פעולות.
import java.util.Random;
public class Q1
{
public static void main(String[] args)
{
Random rand = new Random();
int min = 1000; // גדול מכל מספר תלת-ספרתי
for (int i = 0; i < 50; i++)
{
int num = 100 + rand.nextInt(999 - 100 + 1); // מספר בין 100 ל-999
System.out.print(num + " ");
if (num < min)
min = num;
}
System.out.println();
int sum = 0;
int n = min; // עותק, כדי לא לקלקל את min
while (n > 0)
{
sum += n % 10; // הספרה הימנית
n /= 10; // מוחקים אותה
}
System.out.println("Min: " + min);
System.out.println("Sum of digits: " + sum);
}
}using System;
class Q1
{
static void Main(string[] args)
{
Random rand = new Random();
int min = 1000; // גדול מכל מספר תלת-ספרתי
for (int i = 0; i < 50; i++)
{
int num = rand.Next(100, 999 + 1); // מספר בין 100 ל-999
Console.Write(num + " ");
if (num < min)
min = num;
}
Console.WriteLine();
int sum = 0;
int n = min; // עותק, כדי לא לקלקל את min
while (n > 0)
{
sum += n % 10; // הספרה הימנית
n /= 10; // מוחקים אותה
}
Console.WriteLine("Min: " + min);
Console.WriteLine("Sum of digits: " + sum);
}
}תשובה: קטע התוכנית שלמעלה: מגרילים 50 מספרים בין 100 ל-999, שומרים את הקטן ביותר, ובסוף מדפיסים אותו ואת סכום ספרותיו.
שאלה 2 · קליטת מחרוזות: ספירת האות A ואורך זוגי
כתבו קטע תוכנית הקולטת מחרוזות עד שתיקלט מחרוזת שהתו האחרון שלה זהה לתו הראשון שלה.
עבור כל מחרוזת יש להדפיס כמה פעמים מופיעה בה האות 'A'.
נוסף על כך יש לחשב ולהדפיס מספר מחרוזות באורך זוגי.
◂ פתרון מלא לשאלה 2
פתרון
לולאת do-while שעוצרת אחרי מחרוזת שהתו הראשון שלה שווה לאחרון; לכל מחרוזת סופרים את התווים 'A' ומדפיסים, ומונה נפרד סופר מחרוזות באורך זוגי ומודפס בסוף.
הרעיון: תנאי העצירה תלוי במחרוזת שנקלטה, וגם המחרוזת האחרונה (זו שהתו הראשון שלה שווה לאחרון) היא מחרוזת שנקלטה – לכן מטפלים גם בה. זה בדיוק המבנה של לולאת do-while: קולטים, מטפלים, ורק אחר כך בודקים אם לעצור.
1. ספירת 'A': לכל מחרוזת עוברים בלולאה על כל התווים `str.charAt(i)` (ב-C#: `str[i]`) ומגדילים מונה `countA` בכל פעם שהתו הוא `'A'`. המונה מאופס מחדש לכל מחרוזת, ומודפס מיד אחרי המעבר עליה. למשל עבור BANANA יודפס 3.
2. אורך זוגי: מחרוזת היא באורך זוגי אם `str.length() % 2 == 0`; במקרה כזה מגדילים את `evenCount`. המונה הזה אינו מאופס – הוא צובר לאורך כל הקלט ומודפס אחרי הלולאה.
3. עצירה: הלולאה ממשיכה כל עוד `str.charAt(0) != str.charAt(str.length() - 1)`. מניחים שכל מחרוזת שנקלטת אינה ריקה (אחרת אין לה תו ראשון).
דוגמה: עבור הקלט AAB, xyzw, BANANA, AbA יודפסו 2, 0, 3, 2 (הקלט נעצר ב-AbA, שמתחילה ומסתיימת ב-A), ובסוף מספר המחרוזות באורך זוגי: 2 (xyzw ו-BANANA).
import java.util.Scanner;
public class Q2
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int evenCount = 0; // מספר המחרוזות באורך זוגי
String str;
do
{
str = in.next();
int countA = 0; // כמה פעמים מופיעה 'A' במחרוזת הנוכחית
for (int i = 0; i < str.length(); i++)
{
if (str.charAt(i) == 'A')
countA++;
}
System.out.println(str + ": " + countA);
if (str.length() % 2 == 0)
evenCount++;
}
while (str.charAt(0) != str.charAt(str.length() - 1)); // עוצרים כשהתו הראשון = התו האחרון
System.out.println("Even length: " + evenCount);
}
}using System;
class Q2
{
static void Main(string[] args)
{
int evenCount = 0; // מספר המחרוזות באורך זוגי
string str;
do
{
str = Console.ReadLine();
int countA = 0; // כמה פעמים מופיעה 'A' במחרוזת הנוכחית
for (int i = 0; i < str.Length; i++)
{
if (str[i] == 'A')
countA++;
}
Console.WriteLine(str + ": " + countA);
if (str.Length % 2 == 0)
evenCount++;
}
while (str[0] != str[str.Length - 1]); // עוצרים כשהתו הראשון = התו האחרון
Console.WriteLine("Even length: " + evenCount);
}
}תשובה: קטע התוכנית שלמעלה (לולאת do-while; מונה 'A' לכל מחרוזת ומונה כולל של מחרוזות באורך זוגי).
שאלה 3 · מערך מאוזן: בדיקה ומילוי אקראי
מערך של מספרים שלמים נקרא "מערך מאוזן" אם סכום של כל הערכים הנמצאים במקומות הזוגיים שווה לסכום של כל הערכים הנמצאים במקומות האי-זוגיים.
המערך הבא הוא מערך "מאוזן":
כתבו פעולה המקבלת מערך של מספרים שלמים arr. הפעולה תחזיר ערך true, אם המערך "מאוזן", ולא, הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean isBalanced(int[] arr)public static bool IsBalanced(int[] arr)כתבו פעולה המקבלת מספר שלם וחיובי size>2 ושני פרמטרים נוספים x ו- y, מטיפוס מספר שלם.
הפעולה תיצור מערך בגודל size ותמלא אותו במספרים אקראיים בין x ל- y (כולל) כך שהמערך יהיה מאוזן. הפעולה תחזיר את המערך.
כותרת הפעולה:
public static int[] fill(int size, int x, int y)public static int[] Fill(int size, int x, int y)◂ פתרון מלא לשאלה 3
סעיף א
סוכמים בנפרד את התאים במקומות הזוגיים ובמקומות האי-זוגיים ומחזירים האם שני הסכומים שווים.
הרעיון: עוברים פעם אחת על המערך. האינדקס i קובע לאיזה סכום שייך התא: אם `i % 2 == 0` המקום זוגי, אחרת אי-זוגי. בסוף משווים את שני הסכומים.
1. מאתחלים שני צוברים: `evenSum = 0` ו-`oddSum = 0`.
2. לכל i מוסיפים את `arr[i]` לצובר המתאים לזוגיות של i.
3. מחזירים `evenSum == oddSum` – ביטוי בוליאני שערכו true בדיוק כשהמערך מאוזן.
בדיקה עם הדוגמה: במקומות הזוגיים 0, 2, 4, 6: ; במקומות האי-זוגיים 1, 3, 5: . הסכומים שווים, והפעולה מחזירה true.
סיבוכיות: מעבר אחד על המערך – .
public static boolean isBalanced(int[] arr)
{
int evenSum = 0, oddSum = 0;
for (int i = 0; i < arr.length; i++)
{
if (i % 2 == 0)
evenSum += arr[i]; // מקום זוגי
else
oddSum += arr[i]; // מקום אי-זוגי
}
return evenSum == oddSum;
}public static bool IsBalanced(int[] arr)
{
int evenSum = 0, oddSum = 0;
for (int i = 0; i < arr.Length; i++)
{
if (i % 2 == 0)
evenSum += arr[i]; // מקום זוגי
else
oddSum += arr[i]; // מקום אי-זוגי
}
return evenSum == oddSum;
}תשובה: הפעולה isBalanced שלמעלה.
סעיף ב
יוצרים מערך בגודל size וממלאים אותו במספרים אקראיים בין x ל-y שוב ושוב (do-while) עד ש-isBalanced מחזירה true; מחזירים את המערך.
הרעיון: לא בונים את האיזון "ביד" – ממלאים את כל המערך במספרים אקראיים, בודקים בעזרת הפעולה מסעיף א' אם הוא מאוזן, ואם לא – ממלאים מחדש. כך מובטח שהמערך המוחזר מאוזן וכל ערכיו בין x ל-y.
1. יוצרים מערך `arr` בגודל size.
2. בלולאת do-while: ממלאים כל תא במספר אקראי בין x ל-y כולל, לפי הנוסחה מההנחיות: `x + rand.nextInt(y - x + 1)` (ב-C#: `rand.Next(x, y + 1)`).
3. תנאי ההמשך הוא `!isBalanced(arr)` – כל עוד המערך אינו מאוזן ממלאים אותו מחדש.
4. כשהלולאה מסתיימת המערך מאוזן, ומחזירים אותו.
הערה: כש-size זוגי תמיד קיים מילוי מאוזן (למשל כל הערכים שווים), ולכן הלולאה תסתיים. כש-size אי-זוגי יש מקום זוגי אחד יותר ממקומות אי-זוגיים, ואם x ו-y גדולים וקרובים זה לזה ייתכן שאין שום מילוי מאוזן (למשל , , : אבל ). מניחים שהנתונים מאפשרים מערך מאוזן, כפי שהשאלה מניחה.
public static int[] fill(int size, int x, int y)
{
Random rand = new Random(); // import java.util.Random;
int[] arr = new int[size];
do
{
for (int i = 0; i < size; i++)
arr[i] = x + rand.nextInt(y - x + 1); // מספר בין x ל-y כולל
}
while (!isBalanced(arr)); // ממלאים מחדש עד שהמערך מאוזן
return arr;
}public static int[] Fill(int size, int x, int y)
{
Random rand = new Random();
int[] arr = new int[size];
do
{
for (int i = 0; i < size; i++)
arr[i] = rand.Next(x, y + 1); // מספר בין x ל-y כולל
}
while (!IsBalanced(arr)); // ממלאים מחדש עד שהמערך מאוזן
return arr;
}תשובה: הפעולה fill שלמעלה (מילוי אקראי חוזר עד שהמערך מאוזן).
שאלה 4 · מפעל נעליים: מכירות לפי מחלקה ממספר קטלוג
במפעל נעלים יש ארבע מחלקות ייצור:
•מחלקה 1 – נעלי נשים
•מחלקה 2 – נעלי גברים
•מחלקה 3 – נעלי ילדים
•מחלקה 4 – נעלי ספורט
לכל סוג נעליים קיים מספר בקטלוג המורכב משלוש ספרות. ספרת המאות מציינת את קוד המחלקה (1-4), שתי הספרות האחרונות מציינות את קוד המוצר.
לדוגמה: המספר 321 בקטלוג מציין נעל ילדים אשר קוד המוצר שלה הוא 21.
כתבו תוכנית הקולטת רשימה של מספרי קטלוג של נעלים אשר נמכרו בחודש האחרון. עבור כל מספר קטלוג ייקלט גם מספר זוגות נעליים של אותו הקוד. הקלט מסתיים כאשר ייקלט 0 בתור מספר הקטלוג.
על התוכנית להדפיס את מספר זוגות הנעלים שמכרה כל מחלקה במשך החודש ואת מספר זוגות הנעלים שמכר המפעל.
◂ פתרון מלא לשאלה 4
פתרון
לולאת while עד מספר קטלוג 0; קוד המחלקה הוא catalog/100, ומספר הזוגות מתווסף למונה pairs[dept] ולסכום הכולל; בסוף מדפיסים את ארבעת המונים ואת הסכום.
הרעיון: צריך ארבעה צוברים, אחד לכל מחלקה, ולכן נוח להשתמש במערך מונים שהאינדקס שלו הוא קוד המחלקה. קוד המחלקה הוא ספרת המאות של מספר הקטלוג, כלומר `catalog / 100` (חילוק שלמים). למשל – מחלקה 3, נעלי ילדים.
1. מבני נתונים: מערך `pairs` בגודל 5, ומשתמשים בתאים 1–4 בלבד (כך האינדקס שווה ישירות לקוד המחלקה). צובר `total` לכל המפעל.
2. קליטה עם זקיף: קולטים מספר קטלוג לפני הלולאה; כל עוד הוא שונה מ-0 קולטים את מספר הזוגות שלו, מטפלים בו, וקולטים את מספר הקטלוג הבא. ה-0 רק מסמן סוף, ולכן אחריו לא נקלט מספר זוגות.
3. טיפול בשורה: `dept = catalog / 100`, ואז `pairs[dept] += count` ו-`total += count`. מספר הקטלוג יכול להופיע כמה פעמים – הזוגות פשוט מצטברים.
4. פלט: אחרי הלולאה מדפיסים את `pairs[1]` עד `pairs[4]` ואת `total`. (הסכום הכולל שווה גם לסכום ארבעת המונים.)
דוגמה: עבור הקלט 321 5, 105 2, 412 3, 230 4, 399 1, 0 יודפס: מחלקה 1 – 2, מחלקה 2 – 4, מחלקה 3 – , מחלקה 4 – 3, ובסך הכול זוגות.
import java.util.Scanner;
public class Q4
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int[] pairs = new int[5]; // pairs[1]..pairs[4] – מונה זוגות לכל מחלקה
int total = 0; // סך כל הזוגות שמכר המפעל
int catalog = in.nextInt();
while (catalog != 0)
{
int count = in.nextInt(); // מספר הזוגות שנמכרו מקוד זה
int dept = catalog / 100; // ספרת המאות = קוד המחלקה
pairs[dept] += count;
total += count;
catalog = in.nextInt();
}
for (int d = 1; d <= 4; d++)
System.out.println("Department " + d + ": " + pairs[d]);
System.out.println("Total: " + total);
}
}using System;
class Q4
{
static void Main(string[] args)
{
int[] pairs = new int[5]; // pairs[1]..pairs[4] – מונה זוגות לכל מחלקה
int total = 0; // סך כל הזוגות שמכר המפעל
int catalog = int.Parse(Console.ReadLine());
while (catalog != 0)
{
int count = int.Parse(Console.ReadLine()); // מספר הזוגות שנמכרו מקוד זה
int dept = catalog / 100; // ספרת המאות = קוד המחלקה
pairs[dept] += count;
total += count;
catalog = int.Parse(Console.ReadLine());
}
for (int d = 1; d <= 4; d++)
Console.WriteLine("Department " + d + ": " + pairs[d]);
Console.WriteLine("Total: " + total);
}
}תשובה: התוכנית שלמעלה (מערך מונים לפי ספרת המאות, זקיף 0).
שאלה 5 · מעקב: ממוצע ספרות ומספר עם ממוצע מקסימלי
נתונה הפעולה one המקבלת כפרמטר מספר שלם וחיובי num.
public static double one(int num)
{
double x = 0;
int y = 0;
while (num > 0)
{
x += (num % 10);
y ++;
num /= 10;
}
return x/y;
}public static double One(int num)
{
double x = 0;
int y = 0;
while (num > 0)
{
x += (num % 10);
y ++;
num /= 10;
}
return x/y;
}מה תחזיר הפעולה עבור num=12345? עקבו באמצעות טבלת מעקב אחר זימון הפעולה one(12345).
מה מבצעת הפעולה עבור מספר num שלם וחיובי כלשהו?
נתונה הפעולה two הבאה:
public static void two(int[] arr)
{
int res = 0;
for (int i = 1; i < arr.length; i++)
{
if (one(arr[i]) > one(arr[res]))
{
res = i;
}
}
System.out.println(arr[res]);
}public static void Two(int[] arr)
{
int res = 0;
for (int i = 1; i < arr.Length; i++)
{
if (One(arr[i]) > One(arr[res]))
{
res = i;
}
}
Console.WriteLine(arr[res]);
}נתון מערך של מספרים שלמים וחיוביים arr הבא:
int[] arr = {24, 34783, 1245, 68, 468, 95};עקבו באמצעות טבלת מעקב אחר ביצוע זימון הפעולה two(arr) ורשמו מה יהיה הפלט.
הסבירו מה תבצע הפעולה two(arr) עבור מערך כלשהו של מספרים שלמים וחיוביים.
◂ פתרון מלא לשאלה 5
סעיף א
one(12345) מחזירה 3.0.
עוקבים אחרי המשתנים בכל סיבוב של הלולאה. בכל סיבוב `num % 10` היא הספרה הימנית, היא מתווספת ל-x, y גדל ב-1 ו-num מאבד את ספרתו הימנית.
כש-num מגיע ל-0 הלולאה מסתיימת, והפעולה מחזירה . מכיוון ש-x מטיפוס double, החילוק הוא ממשי.
תשובה: הפעולה מחזירה 3.0.
הפעולה מחזירה את ממוצע הספרות של num (סכום הספרות חלקי מספר הספרות).
בלולאה x צובר את כל הספרות של num (סכום הספרות), ו-y סופר כמה ספרות יש. בסוף מוחזר – סכום הספרות חלקי מספר הספרות, כלומר הממוצע של ספרות המספר. למשל עבור 12345: .
תשובה: הפעולה מחזירה את ממוצע הספרות של num.
סעיף ב
יודפס 68.
res שומר את האינדקס של המספר שממוצע ספרותיו הגדול ביותר עד כה. קודם מחשבים את ממוצע הספרות (הערך של one) לכל איבר:
עכשיו עוקבים אחרי הלולאה (בהתחלה ):
בסוף מודפס `arr[3]`. שימו לב שגם ל-95 ממוצע 7.0, אבל ההשוואה היא `>` חזק, ולכן הוא אינו מחליף את 68.
תשובה: הפלט הוא 68.
הפעולה מדפיסה את האיבר שממוצע ספרותיו הגדול ביותר; אם יש כמה כאלה – את הראשון מביניהם.
הפעולה עוברת על המערך ומחפשת מקסימום, אבל לא של הערכים עצמם אלא של ממוצע הספרות שלהם (הערך שמחזירה one). res מתעדכן רק כשנמצא ממוצע גדול ממש מהמקסימום הנוכחי, ולכן במקרה של שוויון נשאר האיבר הראשון. בסוף מודפס האיבר עצמו (לא הממוצע).
תשובה: two מדפיסה את המספר במערך שממוצע ספרותיו הגדול ביותר (הראשון מביניהם אם יש כמה).
שאלה 6 · מעקב: פיצול תווי מחרוזת לפי מחרוזת שנייה
נתונה הפעולה mystery המקבלת שתי מחרוזות:
public static String mystery(String s1, String s2)
{
String out1 = "";
String out2 = "";
for(int i=0; i<s1.length(); i++)
{
char ch = s1.charAt(i);
int pos = s2.indexOf(ch);
if(pos == -1)
{
if(out1.indexOf(ch) == -1)
out1 = out1 + ch;
}
else
{
if(out2.indexOf(ch) == -1)
out2 =out2 + ch;
}
}
return out1 + out2;
}public static string Mystery (string s1, string s2)
{
string out1 = "";
string out2 = "";
for(int i=0; i<s1.Length; i++)
{
char ch = s1[i];
int pos = s2.IndexOf(ch);
if(pos == -1)
{
if(out1.IndexOf(ch) == -1)
out1 = out1 + ch;
}
else
{
if(out2.IndexOf(ch) == -1)
out2 =out2 + ch;
}
}
return out1 + out2;
}נתונות שתי מחרוזות s1="COMPUTERS" ו- s2="CANNOTTHINK"
עקבו בעזרת טבלת מעקב אחרי זימון הפעולה mystery(s1, s2) ורשמו מה תחזיר הפעולה
מה מבצעת הפעולה mystery באופן כללי?
האם קיימות שתי מחרוזות שונות s1 ו-s2 שעבורם זימונים mystery(s1, s2) ו- mystery(s2, s1) יחזירו אותה תוצאה? אם כן, הביאו דוגמה של זוג מחרוזות כאלה, ולא, הסבירו למה הדבר אינו אפשרי.
◂ פתרון מלא לשאלה 6
סעיף א
mystery(s1, s2) מחזירה "MPUERSCOT".
עוברים על התווים של s1 לפי הסדר. לכל תו בודקים את מקומו ב-s2 (pos). אם הוא לא מופיע ב-s2 () הוא מתווסף ל-out1, אחרת ל-out2 – ובשני המקרים רק אם הוא עוד לא נמצא שם.
במחרוזת s2="CANNOTTHINK" המקומות הם: C–0, A–1, N–2, N–3, O–4, T–5, T–6, H–7, I–8, N–9, K–10.
בסוף מוחזר out1 + out2 = "MPUERS" + "COT".
תשובה: הפעולה מחזירה "MPUERSCOT".
סעיף ב
מחזירה את התווים של s1 (כל תו פעם אחת, לפי סדר הופעתם) כשקודם באים אלה שאינם מופיעים ב-s2 ואחריהם אלה שמופיעים גם ב-s2.
•out1 אוסף את התווים של s1 שאינם מופיעים ב-s2.
•out2 אוסף את התווים של s1 שכן מופיעים ב-s2.
•הבדיקה `indexOf(ch) == -1` על out1 / out2 מונעת כפילויות: כל תו נכנס פעם אחת בלבד, בסדר ההופעה הראשונה שלו ב-s1.
תשובה: הפעולה מחזירה מחרוזת של התווים השונים של s1, לפי סדר הופעתם: קודם התווים שאינם מופיעים ב-s2, ואחריהם התווים שמופיעים גם ב-s2.
סעיף ג
כן. למשל s1="ABA" ו-s2="AB": שני הזימונים מחזירים "AB".
מהסעיף הקודם, התוצאה של mystery(s1, s2) תלויה רק בתווים השונים של s1 ובסדר הופעתם הראשונה, ובשאלה אילו מהם מופיעים ב-s2. לכן אם לשתי המחרוזות אותם תווים שונים באותו סדר הופעה ראשונה, אבל אחת מהן מכילה חזרה, הן שונות ובכל זאת התוצאות שוות.
ניקח s1="ABA" ו-s2="AB":
1. mystery("ABA", "AB"): A מופיע ב-s2 ← out2="A"; B מופיע ← out2="AB"; A שוב – כבר קיים ב-out2 ולא מתווסף. out1="" ולכן מוחזר "AB".
2. mystery("AB", "ABA"): A מופיע ב-"ABA" ← out2="A"; B מופיע ← out2="AB". מוחזר "AB".
שתי התוצאות שוות, למרות ש-"ABA" ≠ "AB".
תשובה: כן, למשל s1="ABA" ו-s2="AB" – שני הזימונים מחזירים "AB".
שאלה 7 · מחלקת צעצוע: בנאי, מעקב והשלמת קוד
נתונה המחלקה צעצוע Toy שיש לה ארבע תכונות:
•קוד צעצוע – code, מטיפוס שלם, int
•גיל מינימלי – age, מטיפוס שלם, int
•מחיר – price, מטיפוס ממשי, double
•האם אפשר להזמין באינטרנט isPossible, מטיפוס בוליאני, boolean (true – אפשר להזמין, false – אי אפשר להזמין)?
במחלקה הוגדרה פעולה הבונה (בנאי, constructor)
public Toy (int code, int age, double price, boolean isPossible)public Toy (int code, int age, double price, bool isPossible)לכל תכונות של המחלקה הוגדרו פעולות get/set
כתבו פעולה בונה המקבלת קוד צעצוע ומחירו. הפעולה תיצור עצם חדש עם גיל מינימלי עשר שאי אפשר להזמין אותו באינטרנט.
כותרת הפעולה:
public Toy(int code, double price)לפניכם קטע קוד בפעולה הראשית main(). עקבו בעזרת טבלת המעקב אחרי ביצוע קטע הקוד הבא ורשמו מה יהיה הפלט:
Toy t1 = new Toy(1122, 10, 120.0, true);
Toy t2 = new Toy (2233, 55.0);
// (*) כאן יש להוסיף פקודה/פקודות בסעיף ג'
if( t1.getAge()> 6 && !t1.getIsPossible())
System.out.println("1");
else
System.out.println("2");
if(t2.getPrice()< 100)
System.out.println("3");
else
if(!t2.getIsPossible())
System.out.println("4");Toy t1 = new Toy(1122, 10, 120.0, true);
Toy t2 = new Toy (2233, 55.0);
// (*) כאן יש להוסיף פקודה/פקודות בסעיף ג'
if( t1.GetAge()> 6 && !t1.GetIsPossible())
Console.WriteLine("1");
else
Console.WriteLine("2");
if(t2.GetPrice()< 100)
Console.WriteLine("3");
else
if(!t2.GetIsPossible())
Console.WriteLine("4");השלימו בקוד בסעיף ב' במקום (*) פקודה או פקודות כך שפלט קטע הקוד יהיה "1" בלבד.
◂ פתרון מלא לשאלה 7
סעיף א
בנאי שמציב את code ו-price מהפרמטרים, age = 10 ו-isPossible = false.
הרעיון: בנאי צריך לתת ערך לכל ארבע התכונות. שתיים מגיעות מהפרמטרים (קוד ומחיר), ושתיים קבועות לפי הנוסח: גיל מינימלי עשר – `age = 10`, ואי אפשר להזמין באינטרנט – `isPossible = false`. משתמשים ב-`this` כדי להבדיל בין התכונה לפרמטר בעל אותו שם.
public Toy(int code, double price)
{
this.code = code;
this.price = price;
this.age = 10; // גיל מינימלי עשר
this.isPossible = false; // אי אפשר להזמין באינטרנט
}public Toy(int code, double price)
{
this.code = code;
this.price = price;
this.age = 10; // גיל מינימלי עשר
this.isPossible = false; // אי אפשר להזמין באינטרנט
}(אפשר גם לזמן את הבנאי המלא: ב-Java `this(code, 10, price, false);` וב-C# `: this(code, 10, price, false)`.)
תשובה: הבנאי שלמעלה.
סעיף ב
הפלט: 2 ואחריו 3 (בשתי שורות).
קודם רושמים את מצב העצמים אחרי היצירה. t1 נוצר בבנאי המלא; t2 נוצר בבנאי מסעיף א', ולכן הגיל שלו 10 ואי אפשר להזמין אותו באינטרנט.
עכשיו עוקבים אחרי התנאים:
כיוון שהתנאי השני אמת, ה-else שלו (הבדיקה של "4") אינו מתבצע.
תשובה: יודפס 2 ובשורה הבאה 3.
סעיף ג
t1.setIsPossible(false); t2.setPrice(150.0); t2.setIsPossible(true);
נתון: הקוד מסעיף ב'. מבוקש: שיודפס רק "1".
1. כדי שיודפס "1" (ולא "2"): צריך ש-`t1.getAge() > 6` (כבר מתקיים, הגיל 10) וגם `!t1.getIsPossible()` – כלומר t1 לא ניתן להזמנה באינטרנט. לכן: `t1.setIsPossible(false);`
2. כדי שלא יודפס "3": צריך ש-`t2.getPrice() < 100` יהיה שקר, כלומר מחיר t2 לפחות 100. למשל `t2.setPrice(150.0);`
3. כדי שלא יודפס "4": כשהתנאי של "3" שקר נבדק `!t2.getIsPossible()`. כדי שהוא יהיה שקר צריך ש-t2 יהיה ניתן להזמנה: `t2.setIsPossible(true);`
t1.setIsPossible(false);
t2.setPrice(150.0);
t2.setIsPossible(true);t1.SetIsPossible(false);
t2.SetPrice(150.0);
t2.SetIsPossible(true);עם הפקודות האלה: התנאי הראשון וגם `!false` – אמת, יודפס 1; שקר; `!true` שקר – לא יודפס דבר נוסף.
תשובה: במקום (*) מוסיפים `t1.setIsPossible(false); t2.setPrice(150.0); t2.setIsPossible(true);` (כל מחיר של 100 ומעלה מתאים).
שאלה 8 · מספרים זרים ומערך זרים
כתבו פעולה המקבלת מספר שלם וחיובי num וספרה digit. הפעולה תבדוק אם הספרה נמצאת בתוך מספר. אם כן – הפעולה תחזיר ערך true, ולא, הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean exist(int num, int digit)public static bool Exist(int num, int digit)שני מספרים שלמים וחיוביים נקראים "זרים" אם אין להם אף ספרה משותפת אחת.
כתבו פעולה המקבלת שני מספרים שלמים וחיוביים. הפעולה תבדוק אם הם "זרים". אם כן – הפעולה תחזיר ערך true, ולא, הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean isStrangers(int num1, int num2)public static bool IsStrangers(int num1, int num2)מערך של מספרים שלמים וחיוביים נקרא "מערך זרים" אם כל איברי המערך "זרים" זה לזה.
כתבו פעולה המקבלת מערך מספרים שלמים וחיוביים ובודקת אם הוא "מערך זרים". אם כן - הפעולה תחזיר ערך true, ולא, הפעולה תחזיר ערך false.
כותרת הפעולה:
public static boolean isItStrangers(int[] arr)public static bool IsItStrangers(int[] arr)מהי סיבוכיות הפעולות שכתבתם בסעיפים א', ב' ו- ג'. הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 8
סעיף א
מפרקים את num לספרות (%10, /10) ומחזירים true ברגע שספרה שווה ל-digit; אם לא נמצאה – false.
הרעיון: עוברים על ספרות num מימין לשמאל: `num % 10` היא הספרה הימנית ו-`num /= 10` מוחק אותה. אם אחת הספרות שווה ל-digit – מחזירים מיד true. אם הלולאה הסתיימה (num הגיע ל-0) בלי למצוא – מחזירים false.
למשל exist(1234, 3): הספרות 4, 3 – בספרה השנייה נמצאה התאמה, true. exist(1234, 5): עוברים על 4, 3, 2, 1 – false.
public static boolean exist(int num, int digit)
{
while (num > 0)
{
if (num % 10 == digit) // הספרה הימנית שווה ל-digit
return true;
num /= 10; // מוחקים את הספרה הימנית
}
return false;
}public static bool Exist(int num, int digit)
{
while (num > 0)
{
if (num % 10 == digit) // הספרה הימנית שווה ל-digit
return true;
num /= 10; // מוחקים את הספרה הימנית
}
return false;
}תשובה: הפעולה exist שלמעלה.
סעיף ב
לכל ספרה של num1 בודקים בעזרת exist אם היא נמצאת ב-num2; אם כן – false, ואם אף ספרה לא נמצאה – true.
הרעיון: שני מספרים אינם זרים אם יש ספרה של num1 שמופיעה גם ב-num2. לכן מפרקים את num1 לספרות, ולכל ספרה משתמשים בפעולה מסעיף א' כדי לבדוק אם היא קיימת ב-num2. ברגע שנמצאה ספרה משותפת מחזירים false; אם עברנו על כל הספרות – המספרים זרים, ומחזירים true.
למשל isStrangers(123, 456): אף אחת מ-3, 2, 1 אינה ב-456 – true. isStrangers(123, 345): הספרה 3 נמצאת ב-345 – false.
public static boolean isStrangers(int num1, int num2)
{
while (num1 > 0)
{
if (exist(num2, num1 % 10)) // ספרה של num1 נמצאת גם ב-num2
return false;
num1 /= 10;
}
return true;
}public static bool IsStrangers(int num1, int num2)
{
while (num1 > 0)
{
if (Exist(num2, num1 % 10)) // ספרה של num1 נמצאת גם ב-num2
return false;
num1 /= 10;
}
return true;
}תשובה: הפעולה isStrangers שלמעלה.
סעיף ג
בודקים כל זוג איברים i<j בעזרת isStrangers; אם זוג אחד אינו זר – false, אחרת true.
הרעיון: "כל האיברים זרים זה לזה" פירושו שכל זוג איברים במקומות שונים הם זרים. עוברים על כל הזוגות בשתי לולאות מקוננות: i מ-0 עד הלפני-אחרון, ו-j מ- עד הסוף (כך כל זוג נבדק פעם אחת, ואיבר אינו מושווה לעצמו). אם נמצא זוג שאינו זר – מחזירים false מיד; אם כל הזוגות זרים – true.
למשל {12, 345, 67, 890} הוא מערך זרים (אין ספרה שחוזרת בשני מספרים), אבל {12, 345, 61} אינו – ל-12 ול-61 יש את הספרה 1.
public static boolean isItStrangers(int[] arr)
{
for (int i = 0; i < arr.length - 1; i++)
for (int j = i + 1; j < arr.length; j++)
if (!isStrangers(arr[i], arr[j]))
return false;
return true;
}public static bool IsItStrangers(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
for (int j = i + 1; j < arr.Length; j++)
if (!IsStrangers(arr[i], arr[j]))
return false;
return true;
}תשובה: הפעולה isItStrangers שלמעלה.
סעיף ד
א: (מספר הספרות של num); ב: ; ג: , ומכיוון שמספר הספרות של int חסום (עד 10) – .
נסמן ב-d את מספר הספרות של מספר (עבור num זה ), וב-n את אורך המערך.
1. סעיף א' (exist): הלולאה מסתובבת לכל היותר פעם אחת לכל ספרה של num, ובכל סיבוב מספר קבוע של פעולות – .
2. סעיף ב' (isStrangers): הלולאה עוברת על הספרות של num1, ובכל סיבוב מזמנת את exist על num2 בעלות . בסך הכול .
3. סעיף ג' (isItStrangers): הלולאות המקוננות בודקות במקרה הגרוע את כל הזוגות: זוגות, וכל בדיקה עולה . בסך הכול .
מספר מטיפוס int הוא בן 10 ספרות לכל היותר, ולכן d חסום בקבוע. אם מתייחסים לכך: סעיפים א' ו-ב' הם , וסעיף ג' הוא .
תשובה: א – ; ב – ; ג – , כלומר במונחי גודל המערך.
שאלה 9 · מחלקת מדד איכות אוויר: דירוג והדפסות
מדד איכות האוויר (Air Quality Index - AIQ) משמש להערכת רמת הזיהום של אוויר באזורים שונים של הארץ. מדד AIQ הוא מספר שלם נע בין 0 ל- 500. המשרד לאיכות הסביבה מפרסם כל יום "מפת זיהום ארצית" הכוללת נתונים של רמת הזיהום ביישובים שונים. לשם כך פיתחו מתכנתי המשרד מחלקה AIQData. למחלקה ארבע תכונות:
•תאריך – date, מטיפוס מחרוזת, String
•שם היישוב – city, מטיפוס מחרוזת, String
•מספר תושבים – popul, מטיפוס מספר שלם, int
•מדד איכות האוויר – aiq, מטיפוס שלם, int
כדי להעלות את מודעות האוכלוסייה הרחבה להשלכות הבריאותיות של זיהום האוויר, הוחלט במקום לפרסם מדד מספרי מדויק, לפרסם "דירוג" לפי הכלל הבא:
כתבו פעולה פנימית במחלקה AIQData המחזירה דירוג לפי מדד איכות האוויר. כותרת הפעולה:
public int raiting()public int Raiting()כתבו פעולה המקבלת מערך נתונים של איכות האוויר (מערך הפניות לעצמים מטיפוס AIQData) ותאריך מסוים checkDate. על הפעולה להדפיס שמות של כל היישובים שאיכות האוויר בתאריך זה הייתה "לא בריאה" או "מסוכנת". חובה להשתמש בפעולה שכתבתם בסעיף א'.
כותרת הפעולה:
public static void printDangerous(AIQData[] arr, String checkDate)public static void PrintDangerous(AIQData[] arr, string checkDate)כתבו פעולה המקבלת מערך נתונים של איכות האוויר (מערך הפניות לעצמים מטיפוס AIQData) ומערך שמות יישובים cities. הפעולה תחשב ותדפיס עבור כל יישוב כמה פעמים איכות האוויר הייתה "טובה" וכמה פעמים היא הייתה "מסוכנת".
כותרת הפעולה:
public static void printCities(AIQData[] arr, String[] cities)public static void PrintCities(AIQData[] arr, string[] cities)◂ פתרון מלא לשאלה 9
סעיף א
שרשרת תנאים על aiq: עד 49 – 1, עד 99 – 2, עד 149 – 3, עד 199 – 4, אחרת (200-500) – 5.
הרעיון: הפעולה פנימית, ולכן ניגשים ישירות לתכונה aiq של העצם. הטווחים בטבלה רצופים ולא חופפים, ולכן בודקים את הגבול העליון של כל טווח לפי הסדר: אם aiq לא עבר את 49 – הדירוג 1; אחרת, אם לא עבר את 99 – 2; וכן הלאה. כל `return` מסיים את הפעולה, כך שאין צורך לבדוק גם את הגבול התחתון. מה שנשאר אחרי 199 הוא הטווח 200–500 – דירוג 5.
בדיקת גבולות: 49 ← 1, 50 ← 2, 99 ← 2, 100 ← 3, 149 ← 3, 150 ← 4, 199 ← 4, 200 ← 5.
public int raiting()
{
if (aiq <= 49)
return 1; // טוב
if (aiq <= 99)
return 2; // מתון
if (aiq <= 149)
return 3; // לא בריא לקבוצות רגישות
if (aiq <= 199)
return 4; // לא בריא
return 5; // מסוכן (200-500)
}public int Raiting()
{
if (aiq <= 49)
return 1; // טוב
if (aiq <= 99)
return 2; // מתון
if (aiq <= 149)
return 3; // לא בריא לקבוצות רגישות
if (aiq <= 199)
return 4; // לא בריא
return 5; // מסוכן (200-500)
}תשובה: הפעולה raiting שלמעלה.
סעיף ב
עוברים על המערך ומדפיסים את שם היישוב של כל רשומה שהתאריך שלה שווה ל-checkDate והדירוג שלה 4 או 5.
הרעיון: "לא בריא" הוא דירוג 4 ו"מסוכן" הוא דירוג 5, כלומר מחפשים רשומות עם `raiting() >= 4`. כל רשומה במערך היא מדידה של יישוב אחד בתאריך אחד, ולכן עוברים על כל הרשומות ומדפיסים את שם היישוב כשמתקיימים שני תנאים:
1. התאריך של הרשומה שווה ל-checkDate. ב-Java משווים מחרוזות עם `equals` (ולא `==`, שמשווה הפניות); ב-C# האופרטור `==` משווה את תוכן המחרוזות.
2. הדירוג שמחזירה הפעולה מסעיף א' הוא 4 או יותר.
הפעולה סטטית (מחוץ למחלקה), ולכן ניגשים לתכונות דרך פעולות ה-get.
public static void printDangerous(AIQData[] arr, String checkDate)
{
for (int i = 0; i < arr.length; i++)
{
if (arr[i].getDate().equals(checkDate) && arr[i].raiting() >= 4)
System.out.println(arr[i].getCity());
}
}public static void PrintDangerous(AIQData[] arr, string checkDate)
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].GetDate() == checkDate && arr[i].Raiting() >= 4)
Console.WriteLine(arr[i].GetCity());
}
}תשובה: הפעולה printDangerous שלמעלה.
סעיף ג
לכל יישוב ב-cities עוברים על כל המערך arr, סופרים רשומות של אותו יישוב עם דירוג 1 (טוב) ועם דירוג 5 (מסוכן), ומדפיסים את שני המונים.
הרעיון: לולאה חיצונית על היישובים, ולכל יישוב לולאה פנימית על כל רשומות המדידה. לכל יישוב מאפסים שני מונים: good (דירוג 1 – "טוב") ו-danger (דירוג 5 – "מסוכן"). רשומה נספרת רק אם שם היישוב שלה שווה לשם הנוכחי, ואז לפי הדירוג שלה מגדילים את המונה המתאים. אחרי הלולאה הפנימית מדפיסים את שם היישוב ואת שני המונים. יישוב שאין לו מדידות יקבל 0 ו-0.
סיבוכיות: אם ב-cities יש m יישובים וב-arr יש n רשומות – .
public static void printCities(AIQData[] arr, String[] cities)
{
for (int c = 0; c < cities.length; c++)
{
int good = 0, danger = 0;
for (int i = 0; i < arr.length; i++)
{
if (arr[i].getCity().equals(cities[c]))
{
if (arr[i].raiting() == 1) // טוב
good++;
else if (arr[i].raiting() == 5) // מסוכן
danger++;
}
}
System.out.println(cities[c] + ": good " + good + ", dangerous " + danger);
}
}public static void PrintCities(AIQData[] arr, string[] cities)
{
for (int c = 0; c < cities.Length; c++)
{
int good = 0, danger = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].GetCity() == cities[c])
{
if (arr[i].Raiting() == 1) // טוב
good++;
else if (arr[i].Raiting() == 5) // מסוכן
danger++;
}
}
Console.WriteLine(cities[c] + ": good " + good + ", dangerous " + danger);
}
}תשובה: הפעולה printCities שלמעלה.
שאלה 10 · מעקב: הפרדת שליליים מאי-שליליים במערך
נתונה הפעולה why המקבלת מערך של מספרים שלמים:
public static void why (int[] arr){
int[] temp = new int[arr.length];
int k = 0;
for (int i = 0; i < arr.length; i++)
if (arr[i] < 0)
temp[k++] = arr[i];
for (int i = 0; i < arr.length; i++)
if (arr[i] >= 0)
temp[k++] = arr[i];
for (int i = 0; i < arr.length; i++)
arr[i] = temp[i];
}public static void Why (int[] arr){
int[] temp = new int[arr.Length];
int k = 0;
for (int i = 0; i < arr.Length; i++)
if (arr[i] < 0)
temp[k++] = arr[i];
for (int i = 0; i < arr.Length; i++)
if (arr[i] >= 0)
temp[k++] = arr[i];
for (int i = 0; i < arr.Length; i++)
arr[i] = temp[i];
}נתון מערך `int [] arr = {12, 0, -344, -46, 670, 0}`.
מה יהיה תוכן המערך אחרי זימון הפעולה why(arr)?
מה מבצעת הפעולה why באופן כללי?
נתונה הפעולה what המקבלת מערך מספרים שלמים:
public static void what (int[] arr){
int start = 0;
int end = arr.length - 1;
while (start < end)
{
if (arr[start] < 0)
start ++;
else if (arr[end] >= 0)
end --;
else
{
int temp = arr[end];
arr[end] = arr[start];
arr[start] = temp;
}
}
}public static void What (int[] arr){
int start = 0;
int end = arr.Length - 1;
while (start < end)
{
if (arr[start] < 0)
start ++;
else if (arr[end] >= 0)
end --;
else
{
int temp = arr[end];
arr[end] = arr[start];
arr[start] = temp;
}
}
}נתון מערך `int [] arr = {123, -45, -678, 12, -345, 67}`.
מה יהיה תוכן המערך אחרי זימון הפעולה what(arr) ?
תנו דוגמה למערך brr בגודל של חמישה תאים, כך התוכן של המערך לא ישתנה אחרי ביצוע הפעולה.
מה מבצעת הפעולה what באופן כללי?
האם קיים מערך crr בגודל של שישה תאים, שעבורו שני זימונים why(crr) ו- what(crr) יביאו לאותן תוצאות? אם כן - תנו דוגמה של המערך crr, אם לא – הסבירו למה.
מה הן סיבוכיות זמן הריצה של הפעולות what ו- why?
◂ פתרון מלא לשאלה 10
סעיף א
{-344, -46, 12, 0, 670, 0}
הפעולה ממלאה מערך עזר temp בשני מעברים, ו-k מצביע על התא הפנוי הבא ב-temp.
1. מעבר ראשון – רק השליליים, לפי הסדר:
2. מעבר שני – רק האי-שליליים (), לפי הסדר: 12 (k=3), 0 (k=4), 670 (k=5), 0 (k=6). עכשיו temp = {-344, -46, 12, 0, 670, 0}.
3. מעבר שלישי: מעתיקים את temp חזרה ל-arr.
תשובה: arr = {-344, -46, 12, 0, 670, 0}.
מסדרת את המערך כך שכל המספרים השליליים בתחילתו ואחריהם כל האי-שליליים, וכל קבוצה שומרת על הסדר המקורי שלה.
המעבר הראשון מעתיק ל-temp את כל השליליים לפי סדר הופעתם, המעבר השני מוסיף אחריהם את כל המספרים הגדולים או שווים ל-0 לפי סדר הופעתם, והמעבר השלישי מעתיק חזרה. התוצאה: חלוקת המערך לשליליים ואחריהם אי-שליליים, בלי לשנות את הסדר היחסי בתוך כל קבוצה (חלוקה יציבה), בעזרת מערך עזר.
תשובה: why מעבירה את כל השליליים לתחילת המערך ואת כל האי-שליליים לסופו, תוך שמירה על הסדר המקורי בתוך כל קבוצה.
סעיף ב
{-345, -45, -678, 12, 123, 67}
start מתקדם מההתחלה כל עוד הוא על מספר שלילי, end נסוג מהסוף כל עוד הוא על מספר אי-שלילי, וכששניהם "תקועים" (start על אי-שלילי ו-end על שלילי) מחליפים ביניהם.
תשובה: arr = {-345, -45, -678, 12, 123, 67}.
למשל brr = {-5, -3, 1, 2, 4} (כל השליליים לפני כל האי-שליליים).
החלפה מתבצעת רק כאשר start עומד על מספר אי-שלילי ו-end עומד על מספר שלילי, כלומר כשיש מספר אי-שלילי לפני מספר שלילי. אם כל השליליים כבר נמצאים לפני כל האי-שליליים, לא תתבצע אף החלפה.
ניקח brr = {-5, -3, 1, 2, 4}: start מתקדם על ו- עד (הערך 1); אז end נסוג על 4 ו-2 עד , התנאי כבר לא מתקיים והלולאה נגמרת – בלי אף החלפה.
תשובה: למשל brr = {-5, -3, 1, 2, 4} (גם מערך שכולו שליליים או שכולו אי-שליליים מתאים).
מעבירה את כל השליליים לתחילת המערך ואת כל האי-שליליים לסופו בעזרת החלפות בין שני מצביעים, בלי מערך עזר; הסדר היחסי בתוך כל קבוצה לא בהכרח נשמר.
שני מצביעים מתקרבים זה לזה מהקצוות: start מדלג על שליליים שכבר במקומם (בצד שמאל), end מדלג על אי-שליליים שכבר במקומם (בצד ימין), וכשמוצאים זוג שנמצא "בצד הלא נכון" מחליפים אותו. בסיום כל השליליים בתחילת המערך וכל האי-שליליים בסופו.
בניגוד ל-why, החלוקה נעשית "במקום" (בלי מערך עזר), אבל הסדר בתוך כל קבוצה עלול להשתנות – בסעיף 1 ה-123 עבר ממקום 0 למקום 4, אחרי ה-12, וה- עבר לפני ה-.
תשובה: what מחלקת את המערך – שליליים בתחילתו ואי-שליליים בסופו – בעזרת החלפות, בלי מערך עזר ובלי לשמור על הסדר המקורי.
סעיף ג
כן. למשל crr = {-1, -2, 3, 4, 5, 6}: שתי הפעולות משאירות אותו ללא שינוי.
שתי הפעולות מביאות את השליליים לתחילת המערך; ההבדל ביניהן הוא רק בסדר הפנימי. אם המערך כבר מחולק (כל השליליים לפני כל האי-שליליים):
1. why מעתיקה את השליליים לפי הסדר ואחריהם את האי-שליליים לפי הסדר – בדיוק המערך המקורי.
2. what אינה מבצעת אף החלפה (כמו בסעיף ב2) – המערך נשאר כמו שהוא.
לכן, למשל, עבור crr = {-1, -2, 3, 4, 5, 6} שתי הפעולות משאירות את המערך {-1, -2, 3, 4, 5, 6}.
תשובה: כן, למשל crr = {-1, -2, 3, 4, 5, 6} (כל מערך שבו השליליים כבר לפני האי-שליליים).
סעיף ד
שתיהן .
1. why: שלוש לולאות נפרדות (לא מקוננות), כל אחת עוברת פעם אחת על n התאים – צעדים, כלומר .
2. what: בכל סיבוב של הלולאה start גדל ב-1, או end קטן ב-1, או מתבצעת החלפה. אחרי החלפה, בסיבוב הבא start יתקדם (כי עכשיו `arr[start]` שלילי), ולכן כל החלפה "מנצלת" צעד אחד של start. המרחק בין start ל-end הוא לכל היותר , ולכן מספר הסיבובים לכל היותר בערך – .
תשובה: סיבוכיות זמן הריצה של שתי הפעולות היא , כאשר n אורך המערך.
שאלה 11 · מעקב: בדיקת פלינדרום של האותיות הגדולות
נתונה מחרוזת s="aMrAdDYrM". עקבו בעזרת טבלת המעקב אחרי זימון הפעולה why(s) ורשמו מהי תוצאת הזימון.
public static boolean why(String s)
{
while(s.length() > 1)
{
if(s.charAt(0)<'A' || s.charAt(0)>'Z')
{
s = s.substring(1);
}
else
if(s.charAt(s.length()-1)<'A' || s.charAt(s.length()-1)>'Z')
{
s = s.substring(0,s.length()-1);
}
else
{
if(s.charAt(0)!=s.charAt(s.length()-1)) return false;
s = s.substring(1, s.length()-1);
}
}
return true;
}public static bool Why(string s)
{
while(s.Length > 1)
{
if(s[0]<'A' || s[0]>'Z')
{
s = s.Substring(1);
}
else
if(s[s.Length-1]<'A' || s[s.Length-1]>'Z')
{
s = s.Substring(0,s.Length-1);
}
else
{
if(s[0]!=s[s.Length-1]) return false;
s = s.Substring(1, s.Length-2);
}
}
return true;
}נתונה הפעולה what הבאה:
public static boolean what(String s)
{
while(s.length() > 1)
{
if(s.charAt(0) != s.charAt(s.length()-1)) return false;
s = s.substring(1, s.length()-1);
}
return true;
}public static bool What(string s)
{
while(s.Length > 1)
{
if(s[0] != s[s.Length-1]) return false;
s = s.Substring(1, s.Length-1);
}
return true;
}תנו דוגמה למחרוזת s באורך שישה תווים כך שזימון what(s) יחזיר ערך true.
נתונה הפעולה where הבאה. הפעולה משתמשת בפעולה what:
public static boolean where(String s)
{
String str = "";
for(int i = 0; i < s.length(); i++)
if(s.charAt(i)>='A' && s.charAt(i)<='Z') str += s.charAt(i);
return what(str);
}public static bool Where(string s)
{
string str = "";
for(int i = 0; i < s.Length; i++)
if(s[i]>='A' && s[i]<='Z') str += s[i];
return What(str);
}האם הפעולה where שקולה (מבצעת בדיוק אותו הדבר) לפעולה why? אם כן, הסבירו מה מבצעות שתי הפעולות באופן כללי, ולא – תנו דוגמה של מחרוזת s שעבורה תוצאות הזימונים why(s) ו- where(s) יהיו שונות.
◂ פתרון מלא לשאלה 11
סעיף א
why("aMrAdDYrM") מחזירה false.
בכל סיבוב הפעולה בודקת את התו הראשון והאחרון: אם התו הראשון אינו אות גדולה (מחוץ לטווח 'A'–'Z') – מוחקים אותו; אחרת, אם האחרון אינו אות גדולה – מוחקים אותו; ואם שניהם אותיות גדולות – משווים ביניהם: אם הם שונים מחזירים false, ואם שווים מוחקים את שניהם. (ב-C# `s.Substring(1, s.Length-2)` – תת-מחרוזת באורך ממקום 1 – היא בדיוק המחרוזת בלי התו הראשון והאחרון, כמו `s.substring(1, s.length()-1)` ב-Java.)
תשובה: תוצאת הזימון why(s) היא false.
סעיף ב
Java: כל פלינדרום באורך 6, למשל "ABCCBA". בגרסת C# הפעולה מחזירה true רק כשכל התווים שווים, למשל "AAAAAA" (מחרוזת זו מתאימה לשתי הגרסאות).
גרסת Java: בכל סיבוב משווים את התו הראשון לאחרון; אם הם שונים מחזירים false, ואם שווים מוחקים את שניהם (`substring(1, s.length()-1)`) וממשיכים פנימה. הפעולה מחזירה true בדיוק כשהמחרוזת היא פלינדרום (נקראת אותו דבר משני הכיוונים).
דוגמה: s="ABCCBA":
1. A = A ← s="BCCB"
2. B = B ← s="CC"
3. C = C ← s="" (אורך 0), הלולאה נגמרת ומוחזר true.
גרסת C#: בשאלון ה-C# כתוב `s.Substring(1, s.Length-1)`, וב-C# הפרמטר השני הוא אורך תת-המחרוזת. לכן זו המחרוזת בלי התו הראשון בלבד – התו האחרון נשאר. בכל סיבוב משווים את התו הראשון של הסיפא הנוכחית לאותו תו אחרון, ולכן What מחזירה true רק אם כל התווים במחרוזת שווים. עבור "ABCCBA" גרסת C# מחזירה false (בסיבוב השני B ≠ A). דוגמה שמתאימה לה: "AAAAAA" – בכל סיבוב A = A, עד שנשאר תו אחד ומוחזר true. מחרוזת זו היא גם פלינדרום, ולכן מתאימה גם לגרסת Java.
תשובה: למשל s="AAAAAA" (מחזירה true בשתי הגרסאות); בגרסת Java מתאים כל פלינדרום באורך 6, למשל "ABCCBA".
סעיף ג
Java: כן – שתיהן בודקות אם רצף האותיות הגדולות במחרוזת (לפי הסדר) הוא פלינדרום. בגרסת C# הן אינן שקולות: עבור s="ABA" Why מחזירה true ו-Where מחזירה false.
1. where: מעתיקה ל-str רק את האותיות הגדולות של s, לפי הסדר, ומזמנת את what – כלומר בודקת אם רצף האותיות הגדולות הוא פלינדרום.
2. why: תו שאינו אות גדולה נמחק ברגע שהוא מגיע לקצה, ולכן הוא לעולם אינו משתתף בהשוואה. ההשוואות נעשות רק בין אותיות גדולות: האות הגדולה הראשונה מול האחרונה, אחר כך השנייה מול הלפני-אחרונה, וכן הלאה – בדיוק ההשוואות ש-what מבצעת על str. כשנשאר תו אחד או אף תו, שתיהן מחזירות true.
למשל עבור "aMrAdDYrM" רצף האותיות הגדולות הוא "MADYM", שאינו פלינדרום (A ≠ Y), ושתי הפעולות מחזירות false (כמו בסעיף א'). עבור "xAbBA" הרצף "ABA" הוא פלינדרום ושתיהן מחזירות true.
תשובה (Java): כן. שתי הפעולות בודקות אם האותיות הגדולות שבמחרוזת, לפי סדר הופעתן, יוצרות פלינדרום.
גרסת C# – לא שקולות. Why זהה לגרסת Java (בודקת פלינדרום של האותיות הגדולות), אבל Where מזמנת את What של C#, שכפי שראינו בסעיף ב' בודקת אם כל התווים שווים. לכן עבור s="ABA":
•Why("ABA"): A = A ← s="B" – מוחזר true.
•Where("ABA"): str="ABA", ו-What("ABA"): A = A ← s="BA"; B ≠ A ← מוחזר false.
תשובה (C#): לא; למשל עבור s="ABA" Why מחזירה true ו-Where מחזירה false.
שאלה 12 · מספר מאוזן ומערך דו-ממדי סופר מאוזן
נתונות הגדרות הבאות:
•מספר שלם וחיובי נקרא "מספר מאוזן" אם סכום ספרות הזוגיות שלו שווה לסכום ספרות האי-זוגיות.
לדוגמה:
המספרים 121, 134, 41111, 2334 הם "מספרים מאוזנים".
המספרים 43, 186, -121, 35 הם לא "מספרים מאוזנים".
•מערך חד-ממדי של מספרים שלמים (חיוביים, שליליים ואפסים) נקרא "מאוזן בקצוות" אם הערך הגדול ביותר במערך הוא "מספר מאוזן" וגם הערך הקטן ביותר במערך הוא "מספר מאוזן"
•מערך דו - ממדי של מספרים שלמים נקרא "סופר מאוזן" אם כל השורות שלו מהוות מערכים "מאוזנים בקצוות".
כתבו פעולה המקבלת מערך דו-ממדי של מספרים שלמים ובודקת אם הוא מערך " סופר מאוזן".
אם כן – הפעולה תחזיר ערך true, ולא – הפעולה תחזיר ערך false.
מהי הסיבוכיות של הפעולה שכתבתם בסעיף א'? הסבירו את תשובתכם.
◂ פתרון מלא לשאלה 12
סעיף א
שלוש פעולות: isBalancedNum (חיובי וסכום הספרות הזוגיות = סכום האי-זוגיות), isBalancedEdges (המקסימום והמינימום של שורה מאוזנים), isSuperBalanced (כל השורות מאוזנות בקצוות).
הרעיון: מפרקים את הבעיה לפי שלוש ההגדרות, פעולה לכל הגדרה, וכל פעולה משתמשת בקודמת.
1. isBalancedNum(num) – מספר מאוזן. "ספרות זוגיות" הן ספרות שערכן זוגי (0, 2, 4, 6, 8), כפי שעולה מהדוגמאות: ב-134 הספרה הזוגית 4 והאי-זוגיות . מפרקים את המספר לספרות ומוסיפים כל ספרה לצובר המתאים לזוגיותה; המספר מאוזן אם הצוברים שווים. מספר שאינו חיובי (0 או שלילי, כמו בדוגמה) אינו מאוזן לפי ההגדרה, ולכן מחזירים עבורו false. בדיקה: 2334 – זוגיות , אי-זוגיות ✓; 43 – ✗.
2. isBalancedEdges(arr) – מערך מאוזן בקצוות. מוצאים במעבר אחד את הערך הגדול ביותר ואת הקטן ביותר, ומחזירים true רק אם שניהם מספרים מאוזנים. שימו לב שאם בשורה יש מספר שלילי או 0, הוא עלול להיות המינימום – ואז השורה אינה מאוזנת בקצוות.
3. isSuperBalanced(mat) – מערך דו-ממדי סופר מאוזן. עוברים על השורות; אם שורה כלשהי אינה מאוזנת בקצוות מחזירים false מיד, ואם כולן מאוזנות – true. ב-Java כל שורה `mat[i]` היא מערך חד-ממדי ואפשר להעביר אותה ישירות; ב-C# במערך מלבני `int[,]` מעתיקים את השורה למערך עזר.
דוגמה: עבור המערך שבו השורות {121, 500, 2334} ו-{134, 2334, 41111}: בשורה הראשונה המקסימום 2334 והמינימום 121 – שניהם מאוזנים; בשורה השנייה המקסימום 41111 והמינימום 134 – מאוזנים. התוצאה true. אם בשורה השנייה 41111 מוחלף ב-43, המינימום הוא 43, שאינו מאוזן, והתוצאה false.
// מספר מאוזן: סכום הספרות הזוגיות שווה לסכום הספרות האי-זוגיות
public static boolean isBalancedNum(int num)
{
if (num <= 0)
return false; // רק מספר שלם וחיובי יכול להיות מאוזן
int evenSum = 0, oddSum = 0;
while (num > 0)
{
int d = num % 10;
if (d % 2 == 0)
evenSum += d;
else
oddSum += d;
num /= 10;
}
return evenSum == oddSum;
}
// מערך מאוזן בקצוות: המקסימום והמינימום הם מספרים מאוזנים
public static boolean isBalancedEdges(int[] arr)
{
int max = arr[0], min = arr[0];
for (int i = 1; i < arr.length; i++)
{
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
}
return isBalancedNum(max) && isBalancedNum(min);
}
// סופר מאוזן: כל השורות מאוזנות בקצוות
public static boolean isSuperBalanced(int[][] mat)
{
for (int i = 0; i < mat.length; i++)
{
if (!isBalancedEdges(mat[i]))
return false;
}
return true;
}// מספר מאוזן: סכום הספרות הזוגיות שווה לסכום הספרות האי-זוגיות
public static bool IsBalancedNum(int num)
{
if (num <= 0)
return false; // רק מספר שלם וחיובי יכול להיות מאוזן
int evenSum = 0, oddSum = 0;
while (num > 0)
{
int d = num % 10;
if (d % 2 == 0)
evenSum += d;
else
oddSum += d;
num /= 10;
}
return evenSum == oddSum;
}
// מערך מאוזן בקצוות: המקסימום והמינימום הם מספרים מאוזנים
public static bool IsBalancedEdges(int[] arr)
{
int max = arr[0], min = arr[0];
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
}
return IsBalancedNum(max) && IsBalancedNum(min);
}
// סופר מאוזן: כל השורות מאוזנות בקצוות
public static bool IsSuperBalanced(int[,] mat)
{
for (int i = 0; i < mat.GetLength(0); i++)
{
int[] row = new int[mat.GetLength(1)]; // מעתיקים את שורה i
for (int j = 0; j < row.Length; j++)
row[j] = mat[i, j];
if (!IsBalancedEdges(row))
return false;
}
return true;
}תשובה: הפעולה isSuperBalanced (עם פעולות העזר isBalancedEdges ו-isBalancedNum) שלמעלה.
סעיף ב
עבור מערך של n שורות ו-m עמודות (כלומר לינארית במספר התאים).
נסמן את מספר השורות ב-n ואת מספר העמודות ב-m.
1. isBalancedNum: מספר הסיבובים הוא מספר הספרות, ולמספר int יש לכל היותר 10 ספרות – .
2. isBalancedEdges: מעבר אחד על השורה למציאת מקסימום ומינימום – , ועוד שתי בדיקות של .
3. isSuperBalanced: במקרה הגרוע (כל השורות מאוזנות) קוראים ל-isBalancedEdges עבור כל אחת מ-n השורות: .
תשובה: הסיבוכיות היא – כל תא במערך נבדק מספר קבוע של פעמים.
שאלה 13 · מחלקות תאריך, נוסע וטיול
חברת "טיולי עם" מארגנת טיולים ליעדים שונים בעולם. למערכת הממוחשבת של החברה יש שלוש מחלקות: Date, Traveler, Travel.
המחלקה Date מציינת תאריך. למחלקה יש שלוש תכונות:
day – יום, month – חודש, year – שנה.
למחלקה הוגדרו פעולה בונה, פעולות set/get לכל התכונות. כמו כן, הוגדרה הפעולה המקבלת כפרמטר תאריך מסוים ובודקת אם התאריך הנוכחי (התאריך שמיוצג באמצעות האובייקט שמפעיל את הפעולה, this), לפני מהתאריך other שהתקבל כפרמטר.
כותרת הפעולה:
public boolean before(Date other)public bool Before(Date other)המחלקה Traveler מייצגת נוסע. למחלקה יש את התכונות הבאות:
•שם נוסע – name – מטיפוס מחרוזת, String
•תאריך התפוגה של הדרכון – expireDate – מטיפוס תאריך, Date
•יעד הנסיעה הרצוי – destination – מטיפוס מחרוזת, String
•סכום המקדמה ששילם – payment – מטיפוס מספר שלם, int
למחלקה הוגדרו פעולה בונה, פעולות set/get לכל התכונות.
כתבו פעולה הבודקת אם הנוסע יכול להצטרף לטיול שמחירו price, תאריך היציאה start ויעד הטיול dest. הנוסע יכול להצטרף לטיול אם הדרכון שלו בתוקף, יעד הטיול הוא היעד הרצוי ונוסע שילם לפחות חצי ממחיר הטיול.
כותרת הפעולה:
public boolean canGo(Date start, int price, String dest)public bool CanGo(Date start, int price, string dest)המחלקה Travel מייצגת טיול. למחלקה ארבע תכונות:
•יעד הטיול – destination, מטיפוס מחרוזת, String
•מערך נרשמים לטיול – travelers, מערך הפניות לעצמים מטיפוס Traveler
•מחיר הטיול – price, מטיפוס מספר שלם, int
•תאריך היציאה לטיול – startDate, מטיפוס תאריך, Date
למחלקה הוגדרו פעולה בונה, פעולות set/get לכל התכונות.
כתבו פעולה המדפיסה את שמות הנרשמים שהדרכון שלהם אינו בתוקף בתאריך היציאה.
כותרת הפעולה:
public void notValidNames()public void NotValidNames()הטיול מובטח רק אם בין הנרשמים יש לפחות minNum נוסעים שיכולים לצאת לטיול.
כתבו פעולה הבודקת אם הטיול מובטח. אם כן – הפעולה תחזיר ערך true, ולא, הפעולה תחזיר ערך false.
כותרת הפעולה:
public boolean isGuaranted(int minNum)public bool IsGuaranted(int minNum)◂ פתרון מלא לשאלה 13
סעיף א
פעולה פנימית ב-Traveler: מחזירה true אם התפוגה אינה לפני start (!expireDate.before(start)), destination שווה ל-dest, ו-payment*2 >= price.
הרעיון: הפעולה פנימית במחלקה Traveler (היא בודקת את הנוסע שמפעיל אותה), ולכן ניגשים ישירות לתכונותיו. שלושה תנאים צריכים להתקיים יחד:
1. הדרכון בתוקף בתאריך היציאה: הדרכון פג אם תאריך התפוגה הוא לפני תאריך היציאה, כלומר `expireDate.before(start)`. לכן התנאי הוא השלילה שלו: `!expireDate.before(start)`. משתמשים בפעולה before שהוגדרה במחלקה Date. (אם תאריך התפוגה הוא בדיוק יום היציאה – הדרכון עדיין בתוקף באותו יום.)
2. היעד: היעד הרצוי של הנוסע שווה ליעד הטיול – השוואת מחרוזות: ב-Java `destination.equals(dest)`, ב-C# `destination == dest`.
3. מקדמה של לפחות חצי: . כדי להימנע מחילוק שלמים (למשל בחילוק שלמים), כותבים את התנאי השקול .
// במחלקה Traveler
public boolean canGo(Date start, int price, String dest)
{
boolean validPassport = !this.expireDate.before(start); // הדרכון לא פג לפני היציאה
boolean sameDest = this.destination.equals(dest); // היעד הרצוי = יעד הטיול
boolean paidHalf = this.payment * 2 >= price; // שילם לפחות חצי
return validPassport && sameDest && paidHalf;
}// במחלקה Traveler
public bool CanGo(Date start, int price, string dest)
{
bool validPassport = !this.expireDate.Before(start); // הדרכון לא פג לפני היציאה
bool sameDest = this.destination == dest; // היעד הרצוי = יעד הטיול
bool paidHalf = this.payment * 2 >= price; // שילם לפחות חצי
return validPassport && sameDest && paidHalf;
}תשובה: הפעולה canGo שלמעלה, במחלקה Traveler.
סעיף ב
פעולה פנימית ב-Travel: עוברת על travelers ומדפיסה את שם כל נוסע שתאריך התפוגה שלו לפני startDate.
הרעיון: הפעולה פנימית במחלקה Travel, ולכן יש לה גישה ישירה למערך travelers ולתאריך startDate של הטיול. עבור כל נרשם מקבלים את תאריך התפוגה שלו בעזרת `getExpireDate()` (התכונה פרטית למחלקה Traveler), ובודקים בעזרת before אם הוא לפני תאריך היציאה – זה בדיוק המקרה שבו הדרכון אינו בתוקף (ההפך מהתנאי בסעיף א'). במקרה כזה מדפיסים את השם בעזרת `getName()`.
אם המערך אינו מלא עד הסוף (יש בו תאים ריקים), הבדיקה `travelers[i] != null` מונעת שגיאה.
// במחלקה Travel
public void notValidNames()
{
for (int i = 0; i < travelers.length; i++)
{
if (travelers[i] != null && travelers[i].getExpireDate().before(this.startDate))
System.out.println(travelers[i].getName());
}
}// במחלקה Travel
public void NotValidNames()
{
for (int i = 0; i < travelers.Length; i++)
{
if (travelers[i] != null && travelers[i].GetExpireDate().Before(this.startDate))
Console.WriteLine(travelers[i].GetName());
}
}תשובה: הפעולה notValidNames שלמעלה, במחלקה Travel.
סעיף ג
פעולה פנימית ב-Travel: סופרת את הנרשמים ש-canGo(startDate, price, destination) מחזירה עבורם true, ומחזירה count >= minNum.
הרעיון: נוסע "יכול לצאת לטיול" בדיוק כשהפעולה canGo מסעיף א' מחזירה true עבור הנתונים של הטיול הזה: תאריך היציאה `startDate`, המחיר `price` והיעד `destination` – כולם תכונות של העצם Travel שמפעיל את הפעולה.
1. מאפסים מונה count.
2. עוברים על כל הנרשמים, ולכל נרשם מזמנים `travelers[i].canGo(startDate, price, destination)`; אם התשובה true מגדילים את count.
3. הטיול מובטח אם יש לפחות minNum כאלה: מחזירים `count >= minNum`.
// במחלקה Travel
public boolean isGuaranted(int minNum)
{
int count = 0;
for (int i = 0; i < travelers.length; i++)
{
if (travelers[i] != null && travelers[i].canGo(this.startDate, this.price, this.destination))
count++;
}
return count >= minNum;
}// במחלקה Travel
public bool IsGuaranted(int minNum)
{
int count = 0;
for (int i = 0; i < travelers.Length; i++)
{
if (travelers[i] != null && travelers[i].CanGo(this.startDate, this.price, this.destination))
count++;
}
return count >= minNum;
}תשובה: הפעולה isGuaranted שלמעלה, במחלקה Travel.
שאלה 14 · רקורסיה: זוגות עם סכום והפרש נתונים
נתונה הפעולה הרקורסיבית what המקבלת מערך מספרים שלמים הממוין בסדר עולה ומספר שלם וחיובי num:
public static boolean what(int[] arr, int num)
{
return what(arr, num, 0,arr.length-1, false);
}
public static boolean what(int[] arr, int num, int i, int k,
boolean f)
{
if(i >= k) return f;
if(arr[i] + arr[k] < num)
return what(arr, num, i+1,k,f);
if(arr[i] + arr[k] > num)
return what(arr, num, i,k-1,f);
System.out.println(arr[i]+ " " + arr[k]);
return what(arr, num, i+1, k-1, true);
}public static bool What(int[] arr, int num)
{
return What(arr, num, 0,arr.Length-1, false);
}
public static bool What(int[] arr, int num, int i, int k,
bool f)
{
if(i >= k) return f;
if(arr[i] + arr[k] < num)
return What(arr, num, i+1,k,f);
if(arr[i] + arr[k] > num)
return What(arr, num, i,k-1,f);
Console.WriteLine(arr[i]+ " " + arr[k]);
return What(arr, num, i+1, k-1, true);
}נתון המערך הבא של מספרים שלמים:
int[] a={2,4,7,13,18,21,30};עקבו אחרי זימון what(a, 20) רשמו את תוצאת הזימון. יש להראות מעקב!
מה מבצעת הפעולה what באופן כללי?
נתונה הפעולה הרקורסיבית why המקבלת מערך מספרים שלמים הממוין בסדר עולה ומספר שלם וחיובי num:
public static int why(int[] arr, int num)
{
return why(arr, num, 0,1, 0);
}
public static int why(int[] arr, int num, int i, int k, int f)
{
if(i == arr.length-1)return f;
if(k == arr.length)return f;
if(arr[k] - arr[i] < num)
return why(arr, num, i, k+1, f);
if(arr[k] - arr[i] > num)
return why(arr, num, i+1, k, f);
System.out.println(arr[i]+" " + arr[k]);
return why(arr, num, i+1,k+1, f+1);
}public static int Why(int[] arr, int num)
{
return Why(arr, num, 0,1, 0);
}
public static int Why(int[] arr, int num, int i, int k, int f)
{
if(i == arr.Length-1)return f;
if(k == arr.Length)return f;
if(arr[k] - arr[i] < num)
return Why(arr, num, i, k+1, f);
if(arr[k] - arr[i] > num)
return Why(arr, num, i+1, k, f);
Console.WriteLine(arr[i]+" " + arr[k]);
return Why(arr, num, i+1,k+1, f+1);
}נתון המערך הבא של מספרים שלמים:
int[] a={2,4,7,13,18,21,30};האם קיים מספר num שעבורו זימון why(a, num) יחזיר 2? אם כן, תנו דוגמה למספר כזה וציינו מה יהיה הפלט, ולא – הסבירו למה הדבר לא אפשרי.
מה מבצעת הפעולה why באופן כללי?
◂ פתרון מלא לשאלה 14
סעיף א
יודפס "2 18" ואחריו "7 13", והזימון מחזיר true.
i מתחיל בתחילת המערך ו-k בסופו. בכל זימון: אם מחזירים את f; אם הסכום קטן מ-20 מקדמים את i (צריך מספר גדול יותר); אם הסכום גדול מ-20 מורידים את k; ואם הוא שווה ל-20 מדפיסים את הזוג וממשיכים עם , ו-.
המערך: = 2, 4, 7, 13, 18, 21, 30.
הערך true חוזר דרך כל הזימונים עד הזימון הראשון.
2 18
7 13תשובה: יודפסו הזוגות "2 18" ו-"7 13", ותוצאת הזימון היא true.
סעיף ב
מדפיסה את כל הזוגות של איברים במערך שסכומם num, ומחזירה true אם נמצא לפחות זוג אחד כזה (אחרת false).
זו שיטת "שני המצביעים" על מערך ממוין: i מתקדם מההתחלה ו-k נסוג מהסוף. כשהסכום קטן מדי, הגדלת i מגדילה אותו; כשהסכום גדול מדי, הקטנת k מקטינה אותו. כך עוברים על כל הזוגות האפשריים שסכומם num, ומדפיסים כל זוג שנמצא. הפרמטר f מתחיל ב-false והופך ל-true ברגע שנמצא זוג ראשון, וזה הערך שמוחזר בסוף.
תשובה: what מדפיסה את כל זוגות האיברים (במקומות שונים) שסכומם num, ומחזירה true אם יש לפחות זוג אחד כזה, אחרת false.
סעיף ג
כן. למשל num=3: יודפסו "4 7" ו-"18 21" והזימון יחזיר 2.
הרעיון: why מחפשת זוגות שההפרש ביניהם הוא num (ראו סעיף ד'), ו-f סופר כמה זוגות נמצאו. לכן צריך num שיש בדיוק שני זוגות איברים שההפרש ביניהם num.
ההפרשים בין איברים סמוכים: , , , , , . ההפרש 3 מופיע פעמיים: ו-, ואין זוג נוסף שהפרשו 3 (שאר ההפרשים גדולים מ-3 או שווים ל-2). ניקח ונעקוב:
4 7
18 21(גם , 9, 11, 14 או 17 מתאימים – לכל אחד מהם בדיוק שני זוגות.)
תשובה: כן, למשל num=3: יודפסו "4 7" ו-"18 21" והזימון יחזיר 2.
סעיף ד
מדפיסה את כל זוגות האיברים במערך שההפרש ביניהם הוא num, ומחזירה את מספר הזוגות האלה.
גם כאן יש שני מצביעים, אבל שניהם נעים קדימה: i על האיבר הקטן ו-k על הגדול. אם ההפרש קטן מ-num מקדמים את k (מגדילים את ההפרש); אם הוא גדול מ-num מקדמים את i (מקטינים את ההפרש); ואם הוא שווה – מדפיסים את הזוג, מקדמים את שניהם ומגדילים את המונה f. הרקורסיה נעצרת כש-i מגיע לאיבר האחרון או ש-k יוצא מהמערך, ומוחזר f.
תשובה: why מדפיסה את כל זוגות האיברים שההפרש ביניהם שווה ל-num ומחזירה כמה זוגות כאלה נמצאו.