מבחן מה"ט אלגוריתמיקה ותכנות (Java ו-C#) 97104 - קיץ 2020 מועד א'
הנדסת תוכנה · סמל 97104 · 13 שאלות · פתרון מלא לכל סעיף
מבחן הגמר הממלכתי של מה"ט באלגוריתמיקה ותכנות (Java ו-C#), קיץ 2020 מועד א', כל 13 השאלות כמו בשאלון. לכל סעיף יש תשובה סופית ופתרון מלא ומוסבר, צעד אחרי צעד. נסו לפתור לבד, ואז פתחו את הפתרון.
הנחיות הבחינה
משך הבחינה: ארבע שעות וחצי.
מבנה השאלון: בבחינה זו, מותר לך לענות על מספר שאלות כרצונך, אך סך כל הנקודות שתוכל לצבור בכלל הבחינה לא יעלה על 120. ניתן לצבור נקודות גם מחלקי שאלות.
מבחן ב- Java (עמוד 2)
מבחן ב- C# (עמוד 17)
בכל מבחן 13 שאלות.
חלק א': שאלות 1-6 (ערך כל שאלה – 10 נקודות)
חלק ב': שאלות 7-9 (ערך כל שאלה – 12 נקודות)
חלק ג': שאלות 10-13 (ערך כל שאלה – 18 נקודות)
חומר עזר: 1. מחשבון. (אין להשתמש במחשב כף יד או במחשבון עם תקשורת חיצונית).
2. קלסר אחד בלבד עם חומר ההרצאות. אין להוציא דפים מהקלסר.
שאלה 1 · קליטה עד זקיף: מונים וממוצע
כתוב קטע בפעולה ראשית (main) שיקלוט מספרים שלמים. הקלט יסתיים כאשר ייקלט מספר 0.
על התוכנית לחשב ולהדפיס:
•כמה מספרים נקלטו.
•כמה מספרים זוגיים נקלטו.
•ממוצע מספרים חיוביים שנקלטו.
הערה: אפשר להניח שיש לפחות מספר אחד חיובי.
◂ פתרון מלא לשאלה 1
פתרון
לולאת while עד קליטת 0; מונה לכל המספרים, מונה לזוגיים, ומונה וצובר לחיוביים; בסוף ממוצע = סכום החיוביים חלקי מספרם (חילוק ממשי).
הרעיון: מספר הקלטים אינו ידוע מראש, ולכן משתמשים בלולאת while עם "זקיף": קולטים מספר לפני הלולאה, וכל עוד הוא שונה מ-0 מטפלים בו וקולטים את הבא. ה-0 עצמו רק מסמן סוף ואינו נספר.
1. מונה `count` לכל המספרים שנקלטו (חוץ מה-0 המסיים).
2. מונה `countEven` למספרים זוגיים: מספר זוגי אם `num % 2 == 0` (גם מספר שלילי זוגי, למשל , מקיים זאת).
3. לממוצע החיוביים צריך שני משתנים: מונה `countPos` וצובר `sumPos`. מגדילים אותם רק כאשר `num > 0`.
4. אחרי הלולאה מחשבים ממוצע = `sumPos / countPos`. מכיוון ששני המשתנים שלמים, ממירים ל-double לפני החילוק, אחרת התוצאה תיחתך למספר שלם. לפי ההערה , ולכן אין חילוק ב-0.
הבדיקות של "זוגי" ושל "חיובי" בלתי תלויות (8 הוא גם זוגי וגם חיובי), ולכן הן שני `if` נפרדים.
import java.util.Scanner;
public class Q1
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int count = 0; // כמה מספרים נקלטו
int countEven = 0; // כמה מספרים זוגיים נקלטו
int countPos = 0; // כמה מספרים חיוביים נקלטו
int sumPos = 0; // סכום המספרים החיוביים
int num = in.nextInt();
while (num != 0)
{
count++;
if (num % 2 == 0)
countEven++;
if (num > 0)
{
countPos++;
sumPos += num;
}
num = in.nextInt();
}
double avg = (double) sumPos / countPos;
System.out.println("Numbers: " + count);
System.out.println("Even numbers: " + countEven);
System.out.println("Average of positives: " + avg);
}
}using System;
class Program
{
static void Main(string[] args)
{
int count = 0; // כמה מספרים נקלטו
int countEven = 0; // כמה מספרים זוגיים נקלטו
int countPos = 0; // כמה מספרים חיוביים נקלטו
int sumPos = 0; // סכום המספרים החיוביים
int num = int.Parse(Console.ReadLine());
while (num != 0)
{
count++;
if (num % 2 == 0)
countEven++;
if (num > 0)
{
countPos++;
sumPos += num;
}
num = int.Parse(Console.ReadLine());
}
double avg = (double)sumPos / countPos;
Console.WriteLine("Numbers: " + count);
Console.WriteLine("Even numbers: " + countEven);
Console.WriteLine("Average of positives: " + avg);
}
}דוגמה: עבור הקלט 5, , 7, 0 יודפס: נקלטו 3 מספרים, מספר זוגי אחד (), וממוצע החיוביים (ב-Java יודפס `6.0`, ב-C# יודפס `6`).
תשובה: קטע התוכנית שלמעלה.
שאלה 2 · מחלקת שעון: דקות עד חצות והשוואה
נתונה המחלקה Clock המגדירה טיפוס נתונים שעון.
public class Clock
{
private int hour; //0-23 שעה
private int min; //0-59 דקות
public Clock(int hour, int min)
{
this.hour = hour;
this.min = min;
}
}public class Clock
{
private int hour; //0-23 שעה
private int min; //0-59 דקות
public Clock(int hour, int min)
{
this.hour = hour;
this.min = min;
}
}כתוב פעולה getInterval() המחזירה את משך הזמן (בדקות) שנשאר עד לחצות (24:00).
לדוגמה: אם השעה היא 20:45, הפעולה תחזיר 195 (דקות).
כתוב קטע בפעולה ראשית (main) במחלקה אחרת.
הקטע צריך לקלוט מהמשתמש זמני נחיתה של שתי טיסות. עבור כל טיסה ייקלט זוג מספרים שלמים.
לדוגמה: עבור טיסה הנוחתת ב- 19:50 יש לקלוט שני מספרים (19 ו- 50).
בקטע הקוד יש לבדוק איזו מבין שתי הטיסות אמורה לנחות מאוחר יותר ולהציג הודעה מתאימה.
עליך להיעזר בפעולה שכתבת בסעיף א'.
◂ פתרון מלא לשאלה 2
סעיף א
מחזירים , כלומר `1440 - (hour*60 + min)`; עבור 20:45 מתקבל 195.
הרעיון: נמיר את השעה של העצם לדקות שעברו מאז חצות, ונחסר מכמות הדקות ביממה.
1. דקות שעברו מאז 00:00: .
2. ביממה יש דקות, ולכן הזמן שנשאר עד חצות הוא .
3. בדיקה עם הדוגמה: , ו- דקות, כמו בשאלה.
הפעולה נכתבת בתוך המחלקה Clock (היא פעולה של העצם, ולכן ניגשת ישירות לתכונות הפרטיות):
public class Clock
{
private int hour; //0-23 שעה
private int min; //0-59 דקות
public Clock(int hour, int min)
{
this.hour = hour;
this.min = min;
}
public int getInterval()
{
int minutesFromMidnight = this.hour * 60 + this.min;
return 24 * 60 - minutesFromMidnight;
}
}C# (הפעולה בתוך המחלקה Clock):
public int GetInterval()
{
int minutesFromMidnight = this.hour * 60 + this.min;
return 24 * 60 - minutesFromMidnight;
}תשובה: `getInterval()` מחזירה `1440 - (hour * 60 + min)`.
סעיף ב
יוצרים שני עצמי Clock, מחשבים לכל אחד getInterval(); הטיסה שנשאר לה פחות זמן עד חצות נוחתת מאוחר יותר (שוויון = אותה שעה).
הרעיון: ככל שהטיסה נוחתת מאוחר יותר, נשאר פחות זמן עד חצות. לכן מספיק להשוות את הערכים ש-getInterval() מחזירה: הטיסה עם הערך הקטן יותר היא המאוחרת.
1. קולטים שעה ודקות לכל טיסה (ארבעה מספרים).
2. יוצרים לכל טיסה עצם Clock בעזרת הבנאי.
3. מזמנים getInterval() לכל עצם (אי אפשר לגשת ישירות לתכונות hour ו-min, כי הן private, ולכן הפעולה מסעיף א' היא הדרך הנכונה להשוות).
4. משווים: אם הזמן שנשאר לטיסה 1 קטן יותר – טיסה 1 נוחתת מאוחר יותר; אם של טיסה 2 קטן יותר – טיסה 2; אחרת הן נוחתות באותה שעה.
import java.util.Scanner;
public class Flights
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int h1 = in.nextInt();
int m1 = in.nextInt();
int h2 = in.nextInt();
int m2 = in.nextInt();
Clock flight1 = new Clock(h1, m1);
Clock flight2 = new Clock(h2, m2);
int left1 = flight1.getInterval();
int left2 = flight2.getInterval();
if (left1 < left2)
System.out.println("Flight 1 lands later");
else if (left2 < left1)
System.out.println("Flight 2 lands later");
else
System.out.println("Both flights land at the same time");
}
}using System;
class Flights
{
static void Main(string[] args)
{
int h1 = int.Parse(Console.ReadLine());
int m1 = int.Parse(Console.ReadLine());
int h2 = int.Parse(Console.ReadLine());
int m2 = int.Parse(Console.ReadLine());
Clock flight1 = new Clock(h1, m1);
Clock flight2 = new Clock(h2, m2);
int left1 = flight1.GetInterval();
int left2 = flight2.GetInterval();
if (left1 < left2)
Console.WriteLine("Flight 1 lands later");
else if (left2 < left1)
Console.WriteLine("Flight 2 lands later");
else
Console.WriteLine("Both flights land at the same time");
}
}דוגמה: טיסה 1 ב-20:45 (נשארו 195 דקות) וטיסה 2 ב-19:50 (נשארו דקות). , ולכן יודפס שטיסה 1 נוחתת מאוחר יותר.
תשובה: קטע התוכנית שלמעלה.
שאלה 3 · מעקב: ספירת ספרות אי-זוגיות ומינימום
נתונה הפעולה what המקבלת כפרמטר מספר שלם וחיובי num.
public static int what(int num)
{
int c = 0;
while (num > 0)
{
c += (num % 2);
num /= 10;
}
return c;
}public static int What(int num)
{
int c = 0;
while (num > 0)
{
c += (num % 2);
num /= 10;
}
return c;
}מה תחזיר הפעולה עבור num=12345? חובה לכתוב מעקב בטבלה.
תן דוגמה למספר שלם וחיובי num, שעבורו הפעולה תחזיר 0.
מה מבצעת הפעולה עבור מספר num שלם וחיובי כלשהו? הסבר באופן כללי.
נתונה הפעולה why() הבאה:
public static void why()
{
int[] arr = {1245, 34781, 23, 468, 139 };
int res = arr[0];
for (int i = 1; i < arr.length; i++)
{
if (what(arr[i]) < what(res))
{
res = arr[i];
}
}
System.out.println(res);
}public static void Why()
{
int[] arr = { 1245, 34781, 23, 468, 139 };
int res = arr[0];
for (int i = 1; i < arr.Length; i++)
{
if (What(arr[i]) < What(res))
{
res = arr[i];
}
}
Console.WriteLine(res);
}עקוב באמצעות טבלת מעקב אחר ביצוע הפעולה why() ורשום מה יהיה הפלט.
הסבר מה תבצע why() עבור מערך כלשהו של מספרים שלמים וחיוביים.
◂ פתרון מלא לשאלה 3
סעיף א
3
בכל סיבוב `num % 10` היא הספרה האחרונה, אבל הקוד מוסיף ל-c את `num % 2`. מכיוון ש-10 זוגי, השארית של num בחלוקה ב-2 שווה לשארית של הספרה האחרונה שלו – כלומר 1 אם הספרה האחרונה אי-זוגית ו-0 אם זוגית. אחר כך `num /= 10` מוחק את הספרה האחרונה.
אחרי הסיבוב החמישי num=0, התנאי `num > 0` נכשל והפעולה מחזירה את c.
תשובה: הפעולה תחזיר 3.
למשל num=2468 (כל הספרות זוגיות).
הפעולה מוסיפה 1 על כל ספרה אי-זוגית, ולכן היא תחזיר 0 בדיוק כאשר כל הספרות של num זוגיות.
דוגמה: num=2468. הספרות 8, 6, 4, 2 – בכל סיבוב `num % 2` שווה 0, ולכן c נשאר 0.
תשובה: למשל 2468.
הפעולה מחזירה את מספר הספרות האי-זוגיות במספר num.
בכל סיבוב הלולאה מטפלת בספרת האחדות של num: `num % 2` הוא 1 אם הספרה הזאת אי-זוגית ו-0 אם היא זוגית (כי לפי 10 זוגי, הזוגיות של מספר נקבעת לפי ספרת האחדות שלו). את הערך הזה מוסיפים ל-c, ואז `num /= 10` מוחק את הספרה. הלולאה עוברת כך על כל הספרות עד ש-num מתאפס.
תשובה: הפעולה סופרת ומחזירה כמה ספרות אי-זוגיות יש ב-num.
סעיף ב
468
לפי סעיף א', what מחזירה את מספר הספרות האי-זוגיות. נחשב אותו לכל איבר:
- 1245: הספרות האי-זוגיות 1, 5 – הערך 2.
- 34781: הספרות 3, 7, 1 – הערך 3.
- 23: הספרה 3 – הערך 1.
- 468: אין – הערך 0.
- 139: הספרות 1, 3, 9 – הערך 3.
בהתחלה `res = arr[0] = 1245`, ו-what(res)=2.
בסוף הלולאה מודפס res.
תשובה: הפלט הוא 468.
מדפיסה את האיבר שיש בו הכי מעט ספרות אי-זוגיות (בשוויון – הראשון מביניהם במערך).
זה אלגוריתם חיפוש מינימום, כאשר "הגודל" של כל מספר הוא what שלו – מספר הספרות האי-זוגיות בו. res מתחיל באיבר הראשון ומתחלף רק כאשר נמצא איבר שמספר הספרות האי-זוגיות בו קטן ממש מזה של res. לכן בסוף res הוא איבר עם מספר מינימלי של ספרות אי-זוגיות, ואם יש כמה כאלה – הראשון ביניהם במערך (כי בשוויון אין החלפה).
תשובה: why() מדפיסה את המספר במערך שיש בו הכי מעט ספרות אי-זוגיות; אם יש כמה כאלה – את הראשון שבהם.
שאלה 4 · בדיקת מערך מאוזן סביב התא האמצעי
מערך של מספרים שלמים יקרא "מערך מאוזן" אם הוא מקיים את התנאים הבאים:
•גודל המערך שלושה תאים לפחות.
•גודל המערך הוא מספר אי-זוגי
•ערכו של התא המרכזי (האמצעי) קטן מכל הערכים שנמצאים בתאים שלפניו וגדול מכל הערכים שנמצאים בתאים שאחריו במערך.
המערך arr={22,56,123,12,10,-4,2} הוא "מערך מאוזן" מאחר שהוא עונה על כל שלוש הדרישות:
•אורכו של המערך הוא 7 - גדול מ- 3 ואי-זוגי.
•ערך בתא המרכזי arr[3]=12.
כל הערכים אשר נמצאים במקומות 0-2 גדולים מ- 12, וכל הערכים הנמצאים במקומות 3-6 קטנים מ- 12.
כתוב פעולה שמקבלת מערך מספרים שלמים ומחזירה ערך true אם הוא "מערך מאוזן", ולא הפעולה תחזיר ערך false.
מהי סיבוכיות הפעולה מסעיף א'? הסבר את תשובתך.
◂ פתרון מלא לשאלה 4
סעיף א
בודקים אורך ואי-זוגי; mid = n/2; כל איבר לפני mid חייב להיות גדול מ-arr[mid] וכל איבר אחריו קטן מ-arr[mid]; אחרת false.
הרעיון: בודקים את שלושת התנאים לפי הסדר, ומחזירים false ברגע שאחד מהם נכשל.
1. תנאי סף: אם או ש-n זוגי – המערך אינו מאוזן, מחזירים false מיד. (בדיקה זו גם מבטיחה שיש תא אמצעי אחד.)
2. התא המרכזי: במערך באורך אי-זוגי n, התא האמצעי הוא במקום `mid = n / 2` (חילוק שלם). למשל עבור : , ולפניו 3 תאים (0-2) ואחריו 3 תאים (4-6).
3. התאים שלפני האמצע (מקומות 0 עד mid-1): כל אחד חייב להיות גדול ממש מ-arr[mid]. אם נמצא תא עם ערך קטן או שווה – false.
4. התאים שאחרי האמצע (מקומות mid+1 עד n-1): כל אחד חייב להיות קטן ממש מ-arr[mid]. אם נמצא תא עם ערך גדול או שווה – false.
5. אם עברנו את כל הבדיקות – המערך מאוזן, מחזירים true.
(בדוגמה שבשאלה נכתב "במקומות 3-6"; התא במקום 3 הוא התא המרכזי עצמו, והבדיקה היא על המקומות 4-6.)
public static boolean isBalanced(int[] arr)
{
int n = arr.length;
if (n < 3 || n % 2 == 0)
return false;
int mid = n / 2;
for (int i = 0; i < mid; i++)
if (arr[i] <= arr[mid])
return false;
for (int i = mid + 1; i < n; i++)
if (arr[i] >= arr[mid])
return false;
return true;
}public static bool IsBalanced(int[] arr)
{
int n = arr.Length;
if (n < 3 || n % 2 == 0)
return false;
int mid = n / 2;
for (int i = 0; i < mid; i++)
if (arr[i] <= arr[mid])
return false;
for (int i = mid + 1; i < n; i++)
if (arr[i] >= arr[mid])
return false;
return true;
}בדיקה עם הדוגמה: n=7, mid=3, arr[3]=12. לפניו 22, 56, 123 – כולם גדולים מ-12; אחריו 10, , 2 – כולם קטנים מ-12, ולכן מוחזר true. עבור {5,3} מוחזר false (אורך 2), ועבור {3,3,1} מוחזר false (3 אינו גדול ממש מ-3).
תשובה: הפעולה שלמעלה.
סעיף ב
, כאשר n הוא אורך המערך.
נסמן ב-n את מספר התאים במערך.
1. בדיקות הסף וחישוב mid הם מספר קבוע של פעולות – .
2. שתי הלולאות עוברות יחד על כל התאים חוץ מהאמצעי, כל תא לכל היותר פעם אחת: תאים בכל לולאה, ובסך הכול השוואות במקרה הגרוע (מערך מאוזן).
סך הכול מספר הפעולות גדל באופן לינארי באורך המערך.
תשובה: הסיבוכיות היא , כאשר n הוא אורך המערך.
שאלה 5 · חיפוש איברים כפולים במערך ושיפור יעילות
נתונה הפעולה one() המקבלת מערך של מספרים שלמים:
public static boolean one(int[] arr)
{
for (int i = 0; i < arr.length - 1; i++)
{
for (int k = i + 1; k < arr.length; k++)
{
if (arr[i] == arr[k])
{
return true;
}
}
}
return false;
}public static bool One(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
for (int k = i + 1; k < arr.Length; k++)
{
if (arr[i] == arr[k])
return true;
}
}
return false;
}נתון המערך הבא: int[] arr={3,5,7,5,2}. עקוב אחרי ביצוע הפעולה ורשום מה תחזיר הפעולה.
מה מבצעת הפעולה one באופן כללי?
מהי הסיבוכיות של הפעולה? הסבר את תשובתך
נתון שמערך arr ממוין בסדר עולה. האם אפשר לכתוב את הפעולה one בצורה יעילה יותר?
אם כן – הצע רעיון או כתוב את הפעולה היעילה יותר. אם לא – הסבר למה.
האם תשובתך תשתנה אם המערך יהיה ממוין בסדר יורד?
◂ פתרון מלא לשאלה 5
סעיף א
true (כאשר i=1, k=3: arr[1]=arr[3]=5).
הלולאה החיצונית בוחרת איבר arr[i], והפנימית משווה אותו לכל האיברים שאחריו. ברגע שנמצאת התאמה הפעולה מחזירה true ועוצרת.
המעקב נעצר כאן, כי `return` יוצא מהפעולה.
תשובה: הפעולה תחזיר true.
סעיף ב
בודקת אם יש במערך ערך שמופיע יותר מפעם אחת: true אם יש שני איברים שווים, אחרת false.
הפעולה משווה כל זוג מקומות במערך. אם יש זוג כלשהו עם ערכים שווים היא מחזירה true; אם עברה על כל הזוגות ולא מצאה – מחזירה false.
תשובה: one בודקת אם במערך יש ערך שמופיע לפחות פעמיים (כפילות): מחזירה true אם יש, ו-false אם כל הערכים שונים.
סעיף ג
, כאשר n הוא אורך המערך.
נסמן ב-n את אורך המערך. במקרה הגרוע (אין כפילויות) נבדקים כל הזוגות: עבור i=0 יש השוואות, עבור i=1 יש , וכן הלאה. בסך הכול
השוואות.
תשובה: , כאשר n הוא מספר התאים במערך.
סעיף ד
כן: במערך ממוין ערכים שווים צמודים, ולכן מספיק מעבר אחד שמשווה כל איבר לשכנו arr[i]==arr[i+1]; סיבוכיות .
כן. במערך ממוין, כל העותקים של אותו ערך נמצאים ברצף, זה ליד זה. לכן אם יש ערך כפול, בהכרח יש שני תאים סמוכים שווים. מספיק לעבור פעם אחת על המערך ולהשוות כל איבר לאיבר שאחריו.
public static boolean oneSorted(int[] arr)
{
for (int i = 0; i < arr.length - 1; i++)
{
if (arr[i] == arr[i + 1])
return true;
}
return false;
}public static bool OneSorted(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
if (arr[i] == arr[i + 1])
return true;
}
return false;
}לולאה אחת של השוואות – סיבוכיות במקום .
תשובה: כן – משווים רק איברים סמוכים, בסיבוכיות .
סעיף ה
לא. גם בסדר יורד ערכים שווים צמודים, ואותה פעולה בדיוק עובדת ב-.
לא. מה שחשוב לרעיון הוא שהערכים השווים יושבים ברצף, וזה נכון בכל מיון – עולה או יורד. הפעולה מסעיף ד' בודקת רק שוויון בין שכנים ואינה תלויה בכיוון המיון, ולכן היא נכונה גם למערך ממוין בסדר יורד, באותה סיבוכיות .
תשובה: לא, התשובה לא משתנה.
שאלה 6 · מחרוזות של אותיות גדולות וזוגות סימטריים
נתונה הפעולה why() הבאה המקבלת מחרוזת:
public static boolean why(String str)
{
for (int i = 0; i < str.length(); i++)
{
if (str.charAt(i) < 'A' || str.charAt(i) > 'Z')
{
return false;
}
}
return true;
}public static bool Why(string str)
{
for (int i = 0; i < str.Length; i++)
if (str[i] < 'A' || str[i] > 'Z')
{
return false;
}
return true;
}תן דוגמה למחרוזת באורך של חמישה תווים לכל הפחות שעבורה הפעולה why תחזיר ערך true.
תן דוגמה למחרוזת באורך של חמישה תווים לכל הפחות שעבורה הפעולה why תחזיר ערך false.
מה מבצעת הפעולה? הסבר את תשובתך.
מהי סיבוכיות של הפעולה? הסבר את תשובתך
נתונה הפעולה mystery המקבלת מערך מחרוזות. הפעולה משתמשת בפעולה why:
public static boolean mystery(String[] arr)
{
for (int i = 0; i < arr.length / 2; i++)
{
if (why(arr[i]) == why(arr[arr.length - 1 - i]))
return false;
}
return true;
}public static bool Mystery(string[] arr)
{
for (int i = 0; i < arr.Length / 2; i++)
{
if (Why(arr[i]) == Why(arr[arr.Length - 1 - i]))
return false;
}
return true;
}תן דוגמה למערך arr בגודל שישה תאים שעבורו הפעולה mystery תחזיר ערך true.
תן דוגמה למערך arr בגודל שישה תאים שעבורו הפעולה mystery תחזיר ערך false.
מהי סיבוכיות של הפעולה mystery? הסבר את תשובתך.
◂ פתרון מלא לשאלה 6
סעיף א
למשל "HELLO".
הפעולה מחזירה false ברגע שהיא פוגשת תו שאינו בטווח 'A' עד 'Z', כלומר תו שאינו אות גדולה באנגלית. כדי לקבל true, כל התווים חייבים להיות אותיות גדולות.
"HELLO" – חמישה תווים, כולם בין 'A' ל-'Z', הלולאה מסתיימת בלי return false, ומוחזר true.
תשובה: למשל "HELLO".
למשל "Hello".
מספיק תו אחד שאינו אות גדולה. ב-"Hello" התו במקום 1 הוא 'e', שערכו (101) גדול מ-'Z' (90), ולכן הפעולה מחזירה false.
תשובה: למשל "Hello".
בודקת אם כל תווי המחרוזת הם אותיות גדולות באנגלית (A-Z): true אם כן, false אם יש תו אחר.
הלולאה עוברת על התווים לפי הסדר. התנאי `str.charAt(i) < 'A' || str.charAt(i) > 'Z'` מתקיים בדיוק כאשר התו אינו אות גדולה באנגלית (ספרה, אות קטנה, רווח, סימן). ברגע שנמצא תו כזה מוחזר false. אם הלולאה הסתיימה – כל התווים היו אותיות גדולות, ומוחזר true. (עבור מחרוזת ריקה הלולאה לא מתבצעת ומוחזר true.)
תשובה: הפעולה מחזירה true אם המחרוזת מורכבת רק מאותיות גדולות באנגלית, ו-false אחרת.
, כאשר n הוא אורך המחרוזת.
נסמן ב-n את אורך המחרוזת. במקרה הגרוע (כל התווים אותיות גדולות, או שהתו הלא-תקין הוא האחרון) הלולאה עוברת על כל n התווים, ובכל סיבוב מתבצעות השוואות בזמן קבוע.
תשובה: , כאשר n הוא אורך המחרוזת.
סעיף ב
למשל {"CAT", "DOG", "RED", "blue", "Sun", "a1"}.
הפעולה משווה כל תא arr[i] לתא הסימטרי לו מהסוף, arr[n-1-i]. אם עבור זוג כלשהו why מחזירה אותו ערך לשני התאים – מוחזר false. לכן כדי לקבל true צריך שבכל זוג סימטרי מחרוזת אחת תהיה כולה אותיות גדולות והשנייה לא.
במערך בגודל 6 הזוגות הם (0,5), (1,4), (2,3):
`{"CAT", "DOG", "RED", "blue", "Sun", "a1"}`
אף זוג לא החזיר ערכים שווים, ולכן הלולאה מסתיימת ומוחזר true.
תשובה: למשל {"CAT", "DOG", "RED", "blue", "Sun", "a1"}.
למשל {"CAT", "DOG", "RED", "BLUE", "SUN", "SKY"}.
מספיק זוג סימטרי אחד שבו why מחזירה אותו ערך לשני התאים. במערך `{"CAT", "DOG", "RED", "BLUE", "SUN", "SKY"}` כל המחרוזות באותיות גדולות. כבר בזוג הראשון why("CAT") = why("SKY") = true, ולכן מוחזר false.
תשובה: למשל {"CAT", "DOG", "RED", "BLUE", "SUN", "SKY"}.
: n אורך המערך, m אורך המחרוזת הארוכה ביותר.
נסמן ב-n את מספר התאים במערך וב-m את אורך המחרוזת הארוכה ביותר בו.
1. הלולאה של mystery מתבצעת פעמים.
2. בכל סיבוב יש שתי קריאות ל-why, וכל קריאה עולה לכל היותר (לפי סעיף א4).
3. סך הכול: .
אם מתייחסים לאורך המחרוזות כקבוע (מחרוזות קצרות), הסיבוכיות היא .
תשובה: , כאשר n הוא אורך המערך ו-m אורך המחרוזת הארוכה ביותר.
שאלה 7 · מחלקת משאית: בנאי, סינון ומקסימום
חברת משאיות החליטה למחשב את ניהול המשאיות שלה. לצורך כך הגדירו את המחלקה הבאה:
שם המחלקה (Truck), למחלקה התכונות הבאות:
•מספר רישוי - String truckId.
•שם נהג - String driverName.
•מספר מקומות אחסון עבור המטען - int numStorage.
•האם המשאית פנויה להובלה? - boolean isFree.
כתוב את המחלקה Truck כפי שתוארה לעיל וכמו כן ממש פעולת בנאי בהתאם לתיאור הבא:
פעולת הבנאי מקבלת מספר רישוי, שם נהג ומספר מקומות אחסון. הפעולה מאתחלת את אובייקט המשאית כפנויה להובלה.
כתוב פעולה במחלקה הראשית המקבלת מערך של אובייקטים מסוג Truck ומדפיסה את שמות כל הנהגים שהמשאית שלהם פנויה ויש בה לפחות שבעה מקומות אחסון.
כתוב פעולה במחלקה הראשית המקבלת מערך של אובייקטים מסוג Truck ומחזירה את מספר הרישוי של משאית פנויה אשר לה מספר המקומות לאחסון הגדול ביותר מבין המשאיות במערך האובייקטים מסוג Truck.
אם אין אף משאית פנויה הפעולה תחזיר מחרוזת "Unable to service".
אפשר להניח כי במחלקה קיימות כל הפעולות get, set.
◂ פתרון מלא לשאלה 7
סעיף א
ארבע תכונות פרטיות; בנאי עם שלושה פרמטרים (truckId, driverName, numStorage) שמציב אותם ו-isFree = true.
הרעיון: התכונות מוגדרות private (הסתרת מידע). הבנאי מקבל רק שלושה פרמטרים – מספר רישוי, שם נהג ומספר מקומות – ומציב אותם בתכונות. את isFree לא מקבלים כפרמטר: לפי התיאור, כל משאית חדשה פנויה להובלה, ולכן הבנאי מציב בה true.
נוסיף גם פעולות get ו-set (השאלה מרשה להניח שהן קיימות; נשתמש בהן בסעיפים ב ו-ג).
public class Truck
{
private String truckId; // מספר רישוי
private String driverName; // שם נהג
private int numStorage; // מספר מקומות אחסון
private boolean isFree; // האם פנויה להובלה
public Truck(String truckId, String driverName, int numStorage)
{
this.truckId = truckId;
this.driverName = driverName;
this.numStorage = numStorage;
this.isFree = true;
}
public String getTruckId() { return truckId; }
public String getDriverName() { return driverName; }
public int getNumStorage() { return numStorage; }
public boolean getIsFree() { return isFree; }
public void setIsFree(boolean isFree) { this.isFree = isFree; }
}public class Truck
{
private string truckId; // מספר רישוי
private string driverName; // שם נהג
private int numStorage; // מספר מקומות אחסון
private bool isFree; // האם פנויה להובלה
public Truck(string truckId, string driverName, int numStorage)
{
this.truckId = truckId;
this.driverName = driverName;
this.numStorage = numStorage;
this.isFree = true;
}
public string GetTruckId() { return truckId; }
public string GetDriverName() { return driverName; }
public int GetNumStorage() { return numStorage; }
public bool GetIsFree() { return isFree; }
public void SetIsFree(bool isFree) { this.isFree = isFree; }
}תשובה: המחלקה שלמעלה.
סעיף ב
עוברים על המערך ומדפיסים getDriverName() של כל משאית שבה getIsFree() אמת ו-getNumStorage() >= 7.
הרעיון: סריקה אחת של המערך. לכל משאית בודקים שני תנאים שחייבים להתקיים יחד (ולכן `&&`): המשאית פנויה, ומספר מקומות האחסון בה הוא לפחות 7 (`>= 7`, כי "לפחות שבעה" כולל 7). אם שניהם מתקיימים מדפיסים את שם הנהג. מכיוון שהתכונות פרטיות והפעולה נמצאת במחלקה הראשית, הגישה אליהן היא דרך פעולות ה-get.
public static void printDrivers(Truck[] trucks)
{
for (int i = 0; i < trucks.length; i++)
{
if (trucks[i].getIsFree() && trucks[i].getNumStorage() >= 7)
System.out.println(trucks[i].getDriverName());
}
}public static void PrintDrivers(Truck[] trucks)
{
for (int i = 0; i < trucks.Length; i++)
{
if (trucks[i].GetIsFree() && trucks[i].GetNumStorage() >= 7)
Console.WriteLine(trucks[i].GetDriverName());
}
}דוגמה: עבור המשאיות (Dani, 8 מקומות, פנויה), (Rina, 12, לא פנויה), (Yossi, 5, פנויה), (Avi, 7, פנויה) יודפסו Dani ו-Avi.
תשובה: הפעולה שלמעלה.
סעיף ג
חיפוש מקסימום רק בין המשאיות הפנויות; maxStorage מתחיל ב- והתוצאה מתחילה ב-"Unable to service", כך שאם אין משאית פנויה היא מוחזרת.
הרעיון: זה חיפוש מקסימום, אבל רק בין המשאיות הפנויות.
1. מאתחלים `maxStorage = -1` (קטן מכל מספר מקומות אפשרי, שהוא לפחות 0), ואת התוצאה `bestId` ל-"Unable to service".
2. עוברים על כל המשאיות. משאית שאינה פנויה מדלגים עליה. אם המשאית פנויה ומספר המקומות בה גדול מ-maxStorage – מעדכנים את maxStorage ושומרים את מספר הרישוי שלה.
3. בסוף מחזירים את bestId. אם לא הייתה אף משאית פנויה, התנאי לא התקיים אף פעם, ו-bestId נשאר "Unable to service" – בדיוק מה שנדרש.
שימו לב: אסור לאתחל את המקסימום לפי המשאית הראשונה במערך, כי ייתכן שהיא אינה פנויה.
public static String bestFreeTruck(Truck[] trucks)
{
String bestId = "Unable to service";
int maxStorage = -1;
for (int i = 0; i < trucks.length; i++)
{
if (trucks[i].getIsFree() && trucks[i].getNumStorage() > maxStorage)
{
maxStorage = trucks[i].getNumStorage();
bestId = trucks[i].getTruckId();
}
}
return bestId;
}public static string BestFreeTruck(Truck[] trucks)
{
string bestId = "Unable to service";
int maxStorage = -1;
for (int i = 0; i < trucks.Length; i++)
{
if (trucks[i].GetIsFree() && trucks[i].GetNumStorage() > maxStorage)
{
maxStorage = trucks[i].GetNumStorage();
bestId = trucks[i].GetTruckId();
}
}
return bestId;
}דוגמה: עבור המשאיות מהדוגמה בסעיף ב', המשאית של Rina (12 מקומות) אינה פנויה, ולכן מוחזר מספר הרישוי של המשאית של Dani (8 מקומות – המקסימום בין הפנויות). אם כל המשאיות תפוסות מוחזר "Unable to service".
תשובה: הפעולה שלמעלה.
שאלה 8 · השוואת שני מערכים: כל איברי a קטנים
נתונה הפעולה secret המקבלת שני מערכים של מספרים שלמים:
public static boolean secret(int[] a, int[] b)
{
for (int i = 0; i < a.length; i++)
{
for (int k = 0; k < b.length; k++)
{
if (a[i] >= b[k])
return false;
}
}
return true;
}public static bool Secret(int[] a, int[] b)
{
for (int i = 0; i < a.Length; i++)
{
for (int k = 0; k < b.Length; k++)
{
if (a[i] >= b[k])
return false;
}
}
return true;
}עקוב אחר ביצוע הפעולה secret עבור הפרמטרים הבאים:
int[] a = {4,6,2,7}
int[] b = {8,7,9}תן דוגמה למערכים a ו- b בגודל של ארבעה תאים שעבורם זימון הפעולה secret (a, b) יחזיר תוצאה שונה מהתוצאה של סעיף א'.
מה מבצעת הפעולה secret באופן כללי?
מהי הסיבוכיות של הפעולה secret? הסבר את תשובתך.
כתוב פעולה חדשה, יעילה יותר, אשר מבצעת אותה מטלה כמו הפעולה secret.
מהי הסיבוכיות של הפעולה החדשה? הסבר את תשובתך.
◂ פתרון מלא לשאלה 8
סעיף א
false (כאשר i=3, k=1: a[3]=7 >= b[1]=7).
הלולאות משוות כל איבר של a לכל איבר של b. ברגע שנמצא מוחזר false.
המעקב נעצר בשורה האחרונה, כי `return` יוצא מהפעולה.
תשובה: הפעולה מחזירה false.
סעיף ב
למשל a={1,2,3,4}, b={5,6,7,8} – מוחזר true.
בסעיף א' התקבל false, ולכן צריך מערכים שעבורם יוחזר true: אף איבר של a לא גדול או שווה לאיבר כלשהו של b, כלומר כל איברי a קטנים מכל איברי b.
a={1,2,3,4}, b={5,6,7,8}: הגדול ב-a הוא 4 והקטן ב-b הוא 5, ו-, ולכן אף השוואה לא מתקיימת ומוחזר true.
תשובה: a={1,2,3,4}, b={5,6,7,8}.
סעיף ג
מחזירה true אם כל איבר במערך a קטן ממש מכל איבר במערך b (כלומר המקסימום של a קטן מהמינימום של b), אחרת false.
הפעולה בודקת את כל הזוגות (a[i], b[k]). היא מחזירה false אם יש זוג אחד שבו האיבר מ-a גדול מהאיבר מ-b או שווה לו. לכן היא מחזירה true בדיוק כאשר כל איבר של a קטן ממש מכל איבר של b.
ניסוח שקול: האיבר הגדול ביותר במערך a קטן מהאיבר הקטן ביותר במערך b. (אם אחד המערכים ריק אין זוגות לבדוק, ומוחזר true.)
תשובה: secret בודקת אם כל ערכי המערך a קטנים ממש מכל ערכי המערך b.
סעיף ד
, כאשר n אורך a ו-m אורך b.
נסמן ב-n את אורך a וב-m את אורך b. במקרה הגרוע (מוחזר true) הלולאה החיצונית מתבצעת n פעמים, ובכל אחת הפנימית מתבצעת m פעמים: השוואות. (אם שני המערכים באורך n – זה .)
תשובה: .
סעיף ה
מוצאים את המקסימום של a ואת המינימום של b (מעבר אחד על כל מערך) ומחזירים maxA < minB; מערך ריק – true.
הרעיון: לפי סעיף ג', "כל איבר של a קטן מכל איבר של b" שקול ל-"המקסימום של a קטן מהמינימום של b". אם הגדול ב-a קטן מהקטן ב-b, אז כל איבר של a (שקטן או שווה למקסימום) קטן מכל איבר של b (שגדול או שווה למינימום). ולהפך – אם התנאי נכשל, הזוג (maxA, minB) עצמו מפר אותו.
1. אם אחד המערכים ריק – מחזירים true, כמו הפעולה המקורית.
2. מוצאים את maxA במעבר אחד על a.
3. מוצאים את minB במעבר אחד על b.
4. מחזירים את תוצאת ההשוואה maxA < minB.
public static boolean secret2(int[] a, int[] b)
{
if (a.length == 0 || b.length == 0)
return true;
int maxA = a[0];
for (int i = 1; i < a.length; i++)
if (a[i] > maxA)
maxA = a[i];
int minB = b[0];
for (int k = 1; k < b.length; k++)
if (b[k] < minB)
minB = b[k];
return maxA < minB;
}public static bool Secret2(int[] a, int[] b)
{
if (a.Length == 0 || b.Length == 0)
return true;
int maxA = a[0];
for (int i = 1; i < a.Length; i++)
if (a[i] > maxA)
maxA = a[i];
int minB = b[0];
for (int k = 1; k < b.Length; k++)
if (b[k] < minB)
minB = b[k];
return maxA < minB;
}בדיקה עם סעיף א': maxA = 7, minB = 7, ו- אינו נכון – מוחזר false, כמו בפעולה המקורית.
תשובה: הפעולה secret2 שלמעלה.
סעיף ו
.
הפעולה החדשה עוברת פעם אחת על a (n צעדים) ופעם אחת על b (m צעדים), והלולאות אינן מקוננות. ההשוואה הסופית היא .
תשובה: – לינארית בסכום אורכי המערכים (לעומת בפעולה המקורית).
שאלה 9 · מעקב: ספירת מופעי אותיות במערך תווים
לפניך התוכנית הבאה:
public class Ex {
public static int[] secret(char[] data)
{
int[] temp = new int[26];
for (int i = 0; i < temp.length; i++)
temp[i] = 0;
for (int k = 0; k < data.length; k++)
{
int ind= (int) data[k] - 65;
temp[ind]++;
}
return temp;
}
public static void main(String[] args)
{
char[] let={'A','F','B','B','F','K','A', 'A','D','F'};
int[] res = secret(let);
for (int i = 0; i < res.length; i++)
{
int t = res[i];
if (t > 0)
{
int code=i+65;
char ch=(char)code;
for (int k = 1; k <= t; k++)
System.out.print( ch);
System.out.println();
}
}
}
}using System;
public class Ex
{
public static int[] Secret(char[] data)
{
int[] temp = new int[26];
for (int i = 0; i < temp.Length; i++)
temp[i] = 0;
for (int k = 0; k < data.Length; k++)
{
int ind = (int)data[k] - 65;
temp[ind]++;
}
return temp;
}
public static void Main(string[] args)
{
char[] let={'A','F','B','B','F','K','A','A','D','F'};
int[] res = Secret(let);
for (int i = 0; i < res.Length; i++)
{
int t = res[i];
if (t > 0)
{
int code = i + 65;
char ch = (char)code;
for (int k = 1; k <= t; k++)
Console.Write(ch);
Console.WriteLine();
}
}
}
}הפלט עבור ההוראות הבאות:
1. System.out.println((int)'A');
2. System.out.println((int)'B');
3. System.out.println((int)'Z');
4. System.out.println((char)65);
5. System.out.println((char)66);
6. System.out.println((char)90);1. Console.WriteLine((int)'A');
2. Console.WriteLine((int)'B');
3. Console.WriteLine((int)'Z');
4. Console.WriteLine((char)65);
5. Console.WriteLine((char)66);
6. Console.WriteLine((char)90);יהיה
1. 65
2. 66
3. 90
4. A
5. B
6. Zקוד ASCII עבור התווים 'A'...'Z'
עקוב אחרי ביצוע התוכנית ורשום מה יהיה הפלט.
הערה: יש להציג מערך res אחרי ביצוע הזימון int[] res = secret(let);
מה מבצעת הפעולה באופן כללי (מה יהיה פלט הפעולה עבור כל מערך תווים שכולל רק תווים A-Z)?
◂ פתרון מלא לשאלה 9
סעיף א
res: במקומות 0,1,3,5,10 הערכים 3,2,1,3,1 ושאר 26 התאים 0. הפלט: AAA, BB, D, FFF, K (כל אחד בשורה).
שלב 1 – הפעולה secret. המערך temp בגודל 26 מאופס (תא לכל אות). לכל תו data[k] מחשבים `ind = (int)data[k] - 65` – המקום של האות באלף-בית ('A' נותן 0, 'B' נותן 1, וכן הלאה), ומגדילים את temp[ind] ב-1.
המערך res אחרי הזימון (26 תאים):
שלב 2 – הלולאה ב-main. עבור כל i שבו , מחשבים `code = i + 65` ומדפיסים את התו (char)code בדיוק t פעמים, ואז ירידת שורה. תאים עם 0 מדולגים.
AAA
BB
D
FFF
Kתשובה: הפלט הוא חמש שורות: AAA, BB, D, FFF, K.
סעיף ב
secret סופרת כמה פעמים מופיעה כל אות A-Z; התוכנית מדפיסה לפי סדר האלף-בית שורה לכל אות שמופיעה, ובה האות חוזרת כמספר הופעותיה (המערך מוצג ממוין).
1. secret בונה מערך מונים: temp[j] הוא מספר הפעמים שהאות שקוד ה-ASCII שלה מופיעה במערך התווים. כל תו נספר פעם אחת, באמצעות המרתו לאינדקס 0-25.
2. הלולאה ב-main עוברת על המונים לפי הסדר מ-'A' עד 'Z', ולכל אות שהופיעה לפחות פעם אחת מדפיסה שורה שבה האות חוזרת מספר פעמים כמספר הופעותיה. אותיות שלא הופיעו לא מודפסות.
בפועל התוכנית מדפיסה את כל תווי המערך ממוינים לפי סדר האלף-בית, כאשר כל קבוצת אותיות זהות נמצאת בשורה נפרדת (זהו רעיון "מיון מנייה").
תשובה: הפעולה סופרת את מספר המופעים של כל אות גדולה, והתוכנית מדפיסה לפי סדר אלף-ביתי, לכל אות שמופיעה, שורה שבה האות חוזרת כמספר מופעיה.
שאלה 10 · מחלקת מערך: מעקב פלט והחזרת מקסימום ומינימום
לפניך שתי מחלקות: המחלקה MyArray והמחלקה Program
import java.util.*;
public class MyArray
{
private int[] arr;
private Scanner in ;
public MyArray(int n)
{
in = new Scanner(System.in);
arr = new int[n];
for (int i = 0; i < n; i++)
if (i % 2 == 0) arr[i] = 1;
else arr[i] = -1;
}
public void one(int n)
{
for (int i = 0; i < n; i++)
arr[i] = in.nextInt();
}
public void two()
{
for (int i = 0; i < arr.length; i++)
System.out.println(i + " " + arr[i]);
}
public void three()
{
int lastPlace = arr.length - 1;
int halfLen = lastPlace / 2;
int temp;
for (int i = 0; i <= halfLen; i++)
{
temp = arr[i];
arr[i] = arr[lastPlace - i];
arr[lastPlace - i] = temp;
}
}
}
class Program
{
public static void main(String[] args)
{
MyArray star = new MyArray(8);
System.out.println("------------------------------");
star.two();
star.one(6);
System.out.println("------------------------------");
star.two();
System.out.println("------------------------------");
star.three();
star.two();
}
}using System;
class MyArray
{
private int[] arr;
public MyArray(int n)
{
arr = new int[n];
for (int i = 0; i < n; i++)
if (i % 2 == 0) arr[i] = 1;
else arr[i] = -1;
}
public void One(int n)
{
for (int i = 0; i < n; i++)
arr[i] = int.Parse(Console.ReadLine());
}
public void Two()
{
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(i + " " + arr[i]);
}
}
public void Three()
{
int lastPlace = arr.Length - 1;
int halfLen = lastPlace / 2;
int temp;
for (int i = 0; i <= halfLen; i++)
{
temp = arr[i];
arr[i] = arr[lastPlace - i];
arr[lastPlace - i] = temp;
}
}
}
class Program
{
public static void Main(string[] args)
{
MyArray star = new MyArray(8);
Console.WriteLine("--------------------------");
star.Two();
star.One(6);
Console.WriteLine("--------------------------");
star.Two();
Console.WriteLine("--------------------------");
star.Three();
star.Two();
}
}מה יהיה הפלט של המחלקה Program עבור הקלט (משמאל לימין) 5, -3, 8, 3, 6, 7?
כתוב פעולה פנימית במחלקה MyArray המחזירה שני ערכים, את הערך הגדול ביותר ואת הערך הקטן ביותר של המחלקה.
◂ פתרון מלא לשאלה 10
סעיף א
קו מקפים; 0..7 עם 1,-1,1,-1,1,-1,1,-1; קו; 0..7 עם 5,-3,8,3,6,7,1,-1; קו; 0..7 עם -1,1,7,6,3,8,-3,5.
נעקוב אחרי המצב של המערך arr בעצם star לאורך main.
1. `new MyArray(8)` – הבנאי יוצר מערך של 8 תאים, ובכל מקום זוגי שם 1 ובכל מקום אי-זוגי :
2. מודפס קו מקפים, ואז two() מדפיסה כל תא בשורה: המקום, רווח, הערך.
3. `one(6)` – קולטת 6 מספרים לתאים 0 עד 5. התאים 6 ו-7 לא משתנים:
4. קו מקפים, ו-two() מדפיסה את המערך החדש. אחר כך עוד קו מקפים.
5. three() – `lastPlace = 7`, `halfLen = 7 / 2 = 3` (חילוק שלם). הלולאה רצה עבור i=0..3 ומחליפה את arr[i] עם arr[7-i]:
כלומר three() הופכת את סדר המערך.
6. two() מדפיסה את המערך ההפוך (בלי קו מקפים לפניה, כי three() לא מדפיסה).
הפלט (ב-Java קווי המקפים באורך 30 תווים; ב-C# באורך 26):
------------------------------
0 1
1 -1
2 1
3 -1
4 1
5 -1
6 1
7 -1
------------------------------
0 5
1 -3
2 8
3 3
4 6
5 7
6 1
7 -1
------------------------------
0 -1
1 1
2 7
3 6
4 3
5 8
6 -3
7 5תשובה: הפלט שלמעלה.
סעיף ב
פעולה maxMin() שמחפשת במעבר אחד את המקסימום והמינימום של arr ומחזירה מערך בגודל 2: res[0]=max, res[1]=min.
הרעיון: פעולה מחזירה ערך אחד בלבד, ולכן כדי להחזיר שני ערכים נחזיר מערך בגודל 2: במקום 0 הערך הגדול ביותר, ובמקום 1 הערך הקטן ביותר.
1. מאתחלים את max ואת min לערך של התא הראשון (ולא ל-0: הערכים במערך יכולים להיות שליליים, כמו ו-, ואז אתחול ל-0 היה נותן מקסימום שגוי).
2. עוברים על שאר התאים: אם הערך גדול מ-max – מעדכנים את max; אם הוא קטן מ-min – מעדכנים את min.
3. יוצרים מערך בגודל 2, שמים בו את max ואת min ומחזירים אותו.
הפעולה פנימית במחלקה, ולכן ניגשת ישירות לתכונה arr. (המערך תמיד לא ריק אם n גדול מ-0 בבנאי.)
public int[] maxMin()
{
int max = arr[0];
int 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];
}
int[] res = new int[2];
res[0] = max;
res[1] = min;
return res;
}public int[] MaxMin()
{
int max = arr[0];
int 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];
}
int[] res = new int[2];
res[0] = max;
res[1] = min;
return res;
}דוגמה: אחרי ההרצה בסעיף א' המערך הוא {-1, 1, 7, 6, 3, 8, -3, 5}, והפעולה מחזירה {8, -3}.
תשובה: הפעולה maxMin() שלמעלה.
שאלה 11 · סידור זוגיים לפני אי-זוגיים בשתי שיטות
נתונה הפעולה Arrange המקבלת מערך מספרים שלמים:
public static void arrange(int[] arr)
{
int left = 0;
int right = arr.length - 1;
while (left < right)
{
if (arr[left] % 2 == 0)
left++;
else if (arr[right] % 2 != 0)
right--;
else
{
int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
}
}
}public static void Arrange(int[] arr)
{
int left = 0;
int right = arr.Length - 1;
while (left < right)
{
if (arr[left] % 2 == 0)
left++;
else
if (arr[right] % 2 != 0)
right--;
else
{
int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
}
}
}נתון מערך int [] arr={123, 45, 678, 12, 345}.
מה יהיה תוכן המערך אחרי זימון הפעולה arrange(arr)?
תן דוגמה למערך brr בגודל של חמישה תאים, כך התוכן של המערך לא ישתנה אחרי ביצוע הפעולה.
מה מבצעת הפעולה arrange באופן כללי?
נתונה הפעולה order המקבלת מערך של מספרים שלמים:
public static void order(int[] arr)
{
int[] temp = new int[arr.length];
int k = 0;
for (int i = 0; i < arr.length; i++)
if (arr[i] % 2 == 0)
temp[k++] = arr[i];
for (int i = 0; i < arr.length; i++)
if (arr[i] % 2 != 0)
temp[k++] = arr[i];
for (int i = 0; i < arr.length; i++)
arr[i] = temp[i];
}public static void Order(int[] arr)
{
int[] temp = new int[arr.Length];
int k = 0;
for (int i = 0; i < arr.Length; i++)
if (arr[i] % 2 == 0)
temp[k++] = arr[i];
for (int i = 0; i < arr.Length; i++)
if (arr[i] % 2 != 0)
temp[k++] = arr[i];
for (int i = 0; i < arr.Length; i++)
arr[i] = temp[i];
}נתון מערך int [] arr={12, 55, 34, 46, 67}. מה יהיה תוכן המערך אחרי זימון הפעולה order(arr)?
מה מבצעת הפעולה order באופן כללי?
האם קיים מערך crr בגודל של חמישה תאים, שעבורו שני זימונים arrange(crr) ו- order(crr) יביאן לאותן תוצאות? אם כן - תן דוגמה של המערך crr, אם לא - הסבר למה.
מה הן סיבוכיות זמן הריצה של הפעולות order ו- arrange?
◂ פתרון מלא לשאלה 11
סעיף א
{12, 678, 45, 123, 345}
איך הפעולה עובדת: left מתקדם מההתחלה כל עוד הוא מצביע על מספר זוגי (הזוגי כבר "במקום"). right נסוג מהסוף כל עוד הוא מצביע על מספר אי-זוגי. כאשר arr[left] אי-זוגי וגם arr[right] זוגי – מחליפים ביניהם. בכל סיבוב מתבצעת פעולה אחת בלבד (if / else if / else).
עכשיו left=2 ו-right=2, התנאי `left < right` נכשל והלולאה מסתיימת.
תשובה: arr={12, 678, 45, 123, 345}.
למשל brr={2, 4, 6, 1, 3} (כל הזוגיים כבר לפני כל האי-זוגיים).
החלפה מתבצעת רק כאשר נמצא מספר אי-זוגי משמאל למספר זוגי. אם כל המספרים הזוגיים כבר נמצאים לפני כל האי-זוגיים, left יתקדם על הזוגיים ו-right ייסוג על האי-זוגיים עד שייפגשו – בלי אף החלפה.
עבור brr={2, 4, 6, 1, 3}: left עובר 0→1→2→3 (2, 4, 6 זוגיים), ואז left=3, right=4: arr[3]=1 אי-זוגי ו-arr[4]=3 אי-זוגי, ולכן right-- ו-right=3; הלולאה נעצרת. המערך לא השתנה.
תשובה: למשל {2, 4, 6, 1, 3}.
מסדרת את המערך כך שכל המספרים הזוגיים בתחילתו וכל האי-זוגיים בסופו (בהחלפות, ללא שמירה על הסדר המקורי).
הפעולה שומרת על השמורה: כל התאים שלפני left זוגיים, וכל התאים שאחרי right אי-זוגיים. בכל סיבוב היא מקדמת את אחד המצביעים או מחליפה זוג "לא במקום" (אי-זוגי בצד שמאל וזוגי בצד ימין). כשהמצביעים נפגשים, כל המערך מחולק: זוגיים ואחריהם אי-זוגיים. ההחלפות יכולות לשנות את הסדר היחסי בין המספרים (בסעיף 1, 123 עבר מהמקום 0 למקום 3).
תשובה: arrange מעבירה את כל המספרים הזוגיים לתחילת המערך ואת כל האי-זוגיים לסופו, בתוך המערך עצמו (בלי לשמור על הסדר המקורי ביניהם).
סעיף ב
{12, 34, 46, 55, 67}
1. הלולאה הראשונה מעתיקה ל-temp את הזוגיים לפי הסדר: 12, 34, 46 (k=3).
2. הלולאה השנייה מוסיפה אחריהם את האי-זוגיים לפי הסדר: 55, 67 (k=5).
3. הלולאה השלישית מעתיקה את temp חזרה ל-arr.
תשובה: arr={12, 34, 46, 55, 67}.
מסדרת את המערך כך שכל הזוגיים בתחילתו ואחריהם כל האי-זוגיים, תוך שמירה על הסדר המקורי בתוך כל קבוצה (בעזרת מערך עזר).
order משתמשת במערך עזר temp: קודם מעתיקה אליו את כל המספרים הזוגיים בסדר שבו הופיעו, אחר כך את כל האי-זוגיים בסדר שבו הופיעו, ולבסוף מעתיקה אותו חזרה ל-arr. בניגוד ל-arrange, הסדר היחסי בתוך הזוגיים ובתוך האי-זוגיים נשמר.
תשובה: order מסדרת את המערך כך שהזוגיים בתחילתו והאי-זוגיים בסופו, וכל קבוצה שומרת על הסדר המקורי שלה.
כן, למשל crr={2, 4, 6, 1, 3}: שתי הפעולות משאירות אותו {2, 4, 6, 1, 3}.
כן. נבחר מערך שבו הזוגיים כבר לפני האי-זוגיים, למשל crr={2, 4, 6, 1, 3}.
•arrange(crr): כפי שראינו בסעיף א2, אין אף החלפה, והתוצאה {2, 4, 6, 1, 3}.
•order(crr): הזוגיים לפי הסדר 2, 4, 6 ואחריהם האי-זוגיים 1, 3 – שוב {2, 4, 6, 1, 3}.
שתי הפעולות מביאות לאותה תוצאה.
תשובה: כן, למשל crr={2, 4, 6, 1, 3}.
סעיף ג
שתיהן (ל-order גם זיכרון נוסף ).
נסמן ב-n את אורך המערך.
•arrange: בכל סיבוב left גדל, right קטן, או שמתבצעת החלפה. אחרי החלפה arr[left] זוגי, ולכן בסיבוב הבא left בהכרח יגדל. המרחק מתחיל ב- וקטן ב-1 בכל סיבוב של קידום, ולכן יש לכל היותר כ- סיבובים: .
•order: שלוש לולאות נפרדות (לא מקוננות), כל אחת של n סיבובים: צעדים, כלומר . בנוסף היא משתמשת במערך עזר בגודל n.
תשובה: לשתי הפעולות סיבוכיות זמן .
שאלה 12 · מחלקת משפחה: חישוב עלות טיול לפי גילים
חברת הטיולים "טייל בהנאה" מארגנת טיול משפחות לאתר מבוקש.
משפחות הנרשמות לטיול נדרשות לשלם את העלות הכוללת של הטיול המורכבת מתשלום עבור הסיור באתר הטיול ותשלום עבור הארוחות הניתנות למשתתפים במהלך הטיול.
עלות הסיור באתר הטיול היא קבועה, וערכה הוא 100 שקלים לכל משפחה, אך עלות הארוחות למשפחה אינה בהכרח קבועה, והיא נקבעת על פי הגיל של כל אחד מבני המשפחה בהתאם למחירון הבא:
•עלות ארוחה למשתתף עד גיל 3 (כולל): 20.5 שקלים.
•עלות ארוחה למשתתף שגילו מעל 3 ועד 12 (כולל): 30 שקלים.
•עלות ארוחה למשתתף שגילו מעל 12: 40.5 שקלים.
נתונה המחלקה Family המגדירה טיפוס הנתונים "משפחה".
למחלקה יש שלוש תכונות:
•name – שם משפחה, מסוג מחרוזת.
•num – מספר נפשות במשפחה, מספר שלם.
•totalSum – עלות טיול הכוללת, מספר ממשי.
עליך לרשום כותרת המחלקה, תכונות של המחלקה ולממש חלק מפעולות המחלקה:
כתוב פעולה הבונה (בנאי) המקבל מספר נפשות במשפחה ומאתחל עלות הטיול הכוללת להיות 0
כתוב פעולה getTotalSum המחזירה עלות הטיול הכוללת.
כתוב פעולה input הקולטת עבור כל אחד מבני המשפחה את גילו. הפעולה תחשב את העלות הכוללת למשפחה (סיור + ארוחות) ותעדכן את תכונה המתאימה.
כתוב מחלקה עם פעולה ראשית - main שקולטת עבור כל משפחה המעוניינת להשתתף בטיול את השם שלה ואת מספר הנפשות בה. התוכנית תיצור עצם מטיפוס Family, ותקלוט את הגיל של כל אחד מבני המשפחה.
התוכנית תחשב ותדפיס את העלות הכוללת עבור כל משפחה.
קלט התוכנית יסתיים כאשר תיקלט מחרוזת "STOP" עבור שם המשפחה.
יש להשתמש בפעולות שכתבת בסעיף א'.
◂ פתרון מלא לשאלה 12
סעיף א
בנאי Family(int num) שמציב את num ומאתחל totalSum = 0.
כותרת המחלקה ושלוש התכונות (פרטיות), ואחריהן הבנאי. לפי הדרישה, הבנאי מקבל רק את מספר הנפשות (בלי פרמטרים נוספים): הוא שומר אותו בתכונה num ומאתחל את totalSum ל-0. את שם המשפחה נציב בעזרת פעולת set נפרדת (setName), כי הבנאי אינו מקבל אותו.
הקוד המלא של המחלקה (כולל הבנאי, getTotalSum ו-input מסעיפים 2 ו-3) מופיע בסעיף 3.
public Family(int num)
{
this.num = num;
this.totalSum = 0;
}תשובה: הבנאי שלמעלה.
public double getTotalSum() { return this.totalSum; }
פעולת get פשוטה: מחזירה את ערך התכונה totalSum. טיפוס ההחזרה double, כי זו עלות ממשית (למשל 20.5).
public double getTotalSum()
{
return this.totalSum;
}תשובה: הפעולה שלמעלה.
לולאה של num סיבובים: קולטים גיל ומוסיפים 20.5 (עד 3), 30 (4-12) או 40.5 (מעל 12); בסוף totalSum = 100 + סכום הארוחות.
1. לולאה שרצה num פעמים – פעם לכל בן משפחה.
2. בכל סיבוב קולטים גיל, ולפי המחירון מוסיפים לצובר meals את מחיר הארוחה: אם – 20.5; אחרת, אם – 30 (כאן כבר ידוע ש-); אחרת – 40.5. שרשרת if / else if מבטיחה שכל משתתף ייספר במחיר אחד בלבד.
3. אחרי הלולאה מוסיפים את עלות הסיור, 100 שקלים פעם אחת למשפחה, ומעדכנים: `totalSum = 100 + meals`.
הפעולה לא מקבלת פרמטרים – מספר הנפשות כבר שמור בתכונה num.
ב-Java נגדיר עצם Scanner אחד כתכונה סטטית של המחלקה, כדי שגם input וגם התוכנית הראשית (סעיף ב) יקראו מאותו עצם קלט.
import java.util.Scanner;
public class Family
{
private String name; // שם משפחה
private int num; // מספר נפשות
private double totalSum; // עלות הטיול הכוללת
public static Scanner in = new Scanner(System.in); // עצם קלט אחד לכל התוכנית
public Family(int num)
{
this.num = num;
this.totalSum = 0;
}
public void setName(String name)
{
this.name = name;
}
public String getName()
{
return this.name;
}
public double getTotalSum()
{
return this.totalSum;
}
public void input()
{
double meals = 0;
for (int i = 0; i < this.num; i++)
{
int age = in.nextInt();
if (age <= 3)
meals += 20.5;
else if (age <= 12)
meals += 30;
else
meals += 40.5;
}
this.totalSum = 100 + meals;
}
}using System;
public class Family
{
private string name; // שם משפחה
private int num; // מספר נפשות
private double totalSum; // עלות הטיול הכוללת
public Family(int num)
{
this.num = num;
this.totalSum = 0;
}
public void SetName(string name)
{
this.name = name;
}
public string GetName()
{
return this.name;
}
public double GetTotalSum()
{
return this.totalSum;
}
public void Input()
{
double meals = 0;
for (int i = 0; i < this.num; i++)
{
int age = int.Parse(Console.ReadLine());
if (age <= 3)
meals += 20.5;
else if (age <= 12)
meals += 30;
else
meals += 40.5;
}
this.totalSum = 100 + meals;
}
}דוגמה: משפחה של 3 נפשות בגילים 2, 10, 40: שקלים.
תשובה: המחלקה שלמעלה.
סעיף ב
לולאת while על שם המשפחה עד "STOP"; לכל משפחה: קליטת num, new Family(num), setName, input(), הדפסת getTotalSum().
הרעיון: מספר המשפחות לא ידוע מראש, ולכן לולאת while עם זקיף – שם המשפחה "STOP".
1. קולטים שם משפחה לפני הלולאה.
2. כל עוד השם אינו "STOP" (ב-Java משווים מחרוזות עם `equals`, לא עם `==`):
•קולטים את מספר הנפשות;
•יוצרים עצם `new Family(num)` ומציבים את השם בעזרת setName;
•מזמנים input() – היא קולטת את הגילים ומחשבת את העלות (שימוש בפעולה מסעיף א');
•מדפיסים את שם המשפחה ואת getTotalSum();
•קולטים את שם המשפחה הבאה.
3. כשנקלט "STOP" הלולאה מסתיימת (ולא נוצר עצם עבורו).
import java.util.Scanner;
public class Trip
{
public static void main(String[] args)
{
Scanner in = Family.in; // אותו עצם קלט שמשמש את input
String name = in.next();
while (!name.equals("STOP"))
{
int num = in.nextInt();
Family f = new Family(num);
f.setName(name);
f.input();
System.out.println(f.getName() + ": " + f.getTotalSum());
name = in.next();
}
}
}using System;
class Trip
{
static void Main(string[] args)
{
string name = Console.ReadLine();
while (name != "STOP")
{
int num = int.Parse(Console.ReadLine());
Family f = new Family(num);
f.SetName(name);
f.Input();
Console.WriteLine(f.GetName() + ": " + f.GetTotalSum());
name = Console.ReadLine();
}
}
}דוגמה: עבור הקלט Cohen, 3, 2, 10, 40, Levi, 2, 3, 13, STOP יודפס (ב-C# המספרים מודפסים בלי .0: `Cohen: 191`, `Levi: 161`):
Cohen: 191.0 (כי )
Levi: 161.0 (כי )
תשובה: התוכנית שלמעלה.
שאלה 13 · רקורסיה על מחרוזת: אותיות גדולות וקטנות
נתונה פעולה רקורסיבית what(String s, int k) הבאה:
public static String what(String s, int k)
{
if (s.length() == k)
return "";
if (s.charAt(k) >= 'A' && s.charAt(k) <= 'Z')
return s.charAt(k) + what(s, k + 1);
if (s.charAt(k) >= 'a' && s.charAt(k) <= 'z')
return what(s, k + 1) + s.charAt(k);
return what(s, k + 1);
}public static string What(string s, int k)
{
if (s.Length == k)
return "";
if (s[k] >= 'A' && s[k] <= 'Z')
return s[k] + What(s, k + 1);
if (s[k] >= 'a' && s[k] <= 'z')
return What(s, k + 1) + s[k];
return What(s, k + 1);
}מה תהיה תוצאת הזימון what(s1, 0) עבור מחרוזת s1= A3BC12eDba?
תן דוגמה למחרוזת s2 כך שתוצאת הזימון what(s2, 0) תהיה "ABC".
תן דוגמה למחרוזת s3 כך שתוצאת הזימון what(s3, 0) תהיה "ABCabc".
האם קיימת מחרוזת s4 באורך של שמונה תווים לפחות כך שתוצאת הזימון what(s4, 0) תהיה "ABCabc"? אם כן - תן דוגמה למחרוזת כזאת, אם לא - הסבר למה.
האם קיימת מחרוזת s5 באורך 8 תווים לפחות כך שתוצאת הזימון what(s5, 0) תהיה "abcABC"?
אם כן - תן דוגמה למחרוזת כזאת, אם לא - הסבר למה.
מה מבצעת הפעולה what?
הפרמטר k מוגדר כמשתנה מסוג שלם. האם כל ערך שלם מתאים לזימון הפעולה? אם יש ערכים שיכולים לגרום לשגיאת זמן ריצה, הסבר איזה שינוי יש לעשות, כדי למנוע שגיאה.
◂ פתרון מלא לשאלה 13
סעיף א
"ABCDabe"
איך הפעולה עובדת: בכל קריאה מטפלים בתו s[k] וקוראים ברקורסיה לשאר המחרוזת (k+1):
•אות גדולה – מוסיפים אותה לפני תוצאת הקריאה הרקורסיבית;
•אות קטנה – מוסיפים אותה אחרי תוצאת הקריאה הרקורסיבית;
•כל תו אחר (למשל ספרה) – מדלגים עליו.
תנאי העצירה: k שווה לאורך המחרוזת – מוחזרת מחרוזת ריקה.
s1 = "A3BC12eDba" באורך 10. הקריאות יורדות מ-k=0 עד k=10, והערכים חוזרים מלמטה למעלה:
תשובה: what(s1, 0) מחזירה "ABCDabe".
סעיף ב
למשל s2 = "A1B2C3" (או פשוט "ABC").
התוצאה מכילה רק אותיות גדולות, ולכן ב-s2 אסור שיהיו אותיות קטנות. האותיות הגדולות נשמרות בסדר שבו הן מופיעות, ותווים אחרים נמחקים.
s2 = "A1B2C3": האותיות A, B, C נשמרות לפי הסדר והספרות נמחקות, והתוצאה "ABC".
תשובה: למשל "A1B2C3".
סעיף ג
s3 = "ABCcba".
האותיות הגדולות יוצאות בסדר המקורי, והאותיות הקטנות יוצאות אחריהן בסדר הפוך. כדי לקבל בסוף "abc" צריך שהאותיות הקטנות יופיעו ב-s3 בסדר c, b, a.
s3 = "ABCcba": החלק הגדול "ABC", ואחריו הקטנות c, b, a בסדר הפוך – "abc". התוצאה "ABCabc".
תשובה: "ABCcba".
סעיף ד
כן, למשל s4 = "A1B2Cc3b4a" (10 תווים).
כן. תווים שאינם אותיות (ספרות, סימנים) לא משפיעים על התוצאה, ואפשר להוסיף אותם בכל מקום כדי להאריך את המחרוזת. גם המיקום של האותיות הקטנות ביחס לגדולות לא משנה – משנה רק הסדר בתוך כל קבוצה.
s4 = "A1B2Cc3b4a" (10 תווים): הגדולות A, B, C לפי הסדר, והקטנות c, b, a בסדר הפוך – "abc". התוצאה "ABCabc".
תשובה: כן, למשל "A1B2Cc3b4a".
סעיף ה
לא: בתוצאה כל האותיות הגדולות תמיד באות לפני כל האותיות הקטנות.
לא. נראה שבתוצאה של what כל האותיות הגדולות נמצאות לפני כל האותיות הקטנות.
באינדוקציה מהסוף להתחלה: התוצאה של what(s, k+1) היא "גדולות ואחריהן קטנות". בקריאה what(s, k):
•אות גדולה מתווספת בהתחלה – לפני הגדולות האחרות, ולכן עדיין לפני כל הקטנות;
•אות קטנה מתווספת בסוף – אחרי כל האותיות;
•תו אחר לא מוסיף דבר.
בכל המקרים המבנה "גדולות ואחריהן קטנות" נשמר.
ב-"abcABC" יש אותיות קטנות לפני אותיות גדולות, ולכן אי אפשר לקבל אותה, בלי קשר לאורך המחרוזת.
תשובה: לא קיימת מחרוזת כזאת.
סעיף ו
מחזירה מחרוזת של כל האותיות הגדולות (מהמקום k ואילך) בסדרן המקורי, ואחריהן כל האותיות הקטנות בסדר הפוך; שאר התווים מושמטים.
לפי הניתוח בסעיפים א-ה, what(s, k) עוברת על התווים מהמקום k עד סוף המחרוזת ובונה מחרוזת חדשה:
1. כל האותיות הגדולות באנגלית, בסדר שבו הן מופיעות ב-s;
2. אחריהן כל האותיות הקטנות באנגלית, בסדר הפוך להופעתן ב-s;
3. תווים שאינם אותיות באנגלית (ספרות, רווחים, סימנים) מושמטים.
תשובה: what מחזירה את האותיות הגדולות של s (מהמקום k ואילך) לפי הסדר, ואחריהן את האותיות הקטנות בסדר הפוך, בלי שאר התווים.
סעיף ז
לא. k שלילי או k גדול מאורך המחרוזת גורמים לגישה מחוץ לגבולות (charAt/s[k]); יש לשנות את תנאי העצירה ל-k < 0 || k >= s.length().
לא. ערכים תקינים הם רק אורך המחרוזת.
•k שלילי: התנאי `s.length() == k` לא מתקיים, והגישה `s.charAt(k)` (ב-C#: `s[k]`) עם אינדקס שלילי זורקת חריגת זמן ריצה (ב-Java: StringIndexOutOfBoundsException, ב-C#: IndexOutOfRangeException).
•k גדול מאורך המחרוזת: גם כאן תנאי העצירה (שוויון) לא מתקיים, והגישה ל-s[k] חורגת מהגבולות.
התיקון: נחליף את תנאי העצירה כך שיעצור לכל k מחוץ לטווח האינדקסים החוקיים:
public static String what(String s, int k)
{
if (k < 0 || k >= s.length())
return "";
if (s.charAt(k) >= 'A' && s.charAt(k) <= 'Z')
return s.charAt(k) + what(s, k + 1);
if (s.charAt(k) >= 'a' && s.charAt(k) <= 'z')
return what(s, k + 1) + s.charAt(k);
return what(s, k + 1);
}public static string What(string s, int k)
{
if (k < 0 || k >= s.Length)
return "";
if (s[k] >= 'A' && s[k] <= 'Z')
return s[k] + What(s, k + 1);
if (s[k] >= 'a' && s[k] <= 'z')
return What(s, k + 1) + s[k];
return What(s, k + 1);
}עבור אורך המחרוזת התוצאה זהה לפעולה המקורית, ולכל ערך אחר מוחזרת מחרוזת ריקה בלי שגיאה.
תשובה: לא – k שלילי או גדול מאורך המחרוזת גורם לשגיאת זמן ריצה; משנים את תנאי העצירה ל-`k < 0 || k >= s.length()`.