problem2

בעיה ב'

הוראות המופיעות בגוף של מבנה while ומתבצעות כל עוד תנאי הלולאה מתקיים צריכות להיות מוזזות ימינה ביחס לשורה הראשונה במבנה. הקוד התקין:

age = input(‘Insert age; -1 to stop: ‘)

while age != ‘-1’:

print(age)

age = input(‘Insert age; -1 to stop: ‘)

(א) נתונות שתי מחרוזות s1 ו-s2, שונות זו מזו. יש למצוא את תת המחרוזת הקצרה ביותר של s1 המתחילה בתחילת s1, כלומר בתו הראשון בה, והיא אינה תת מחרוזת של s2, ולהדפיס תת מחרוזת זו. לדוגמה אם אלו s1 ו-s2 –

s1 = “Christmas without presents.”

s2 = “Christmas won’t be Christmas without any presents.”

הפונקציה תחזיר את המחרוזת הזאת –

“Christmas without p”

(ב) נתונות שתי מחרוזות s1 ו-s2, שונות זו מזו. יש למצוא את תת המחרוזת הקצרה ביותר של s1 שאינה תת מחרוזת של s2 ולהדפיס תת מחרוזת זו. אם יש יותר מתת מחרוזת אחת כזו תודפס מחרוזת אחת כלשהי. לדוגמה אם אלו s1 ו-s2 –

s1 = “Christmas without presents.”

s2 = “Christmas won’t be Christmas without any presents.”

תת המחרוזת הקצרה ביותר של s1 שאינה מוכלת במחרוזת s2 היא בגודל 3, ובמקרה זה היא אחת בלבד, ‘t p’.

(ג) כתבו את הפונקציה findShortest –

def findShortest(s1, s2):

לפונקציה שני פרמטרים: s1 ו-s2, שתי מחרוזות שונות זו מזו. הפונקציה מוצאת את תת המחרוזת הקצרה ביותר של s1 שאינה תת מחרוזת של s2, ומחזירה תת מחרוזת זו.

פתרון

(א) נתחיל ונשתית את הפתרון על רעיון זה: נסרוק בזו אחר זו תתי-מחרוזות של s1. כל תת מחרוזת הנסרקת בלולאה תהיה ארוכה בתו אחד מתת המחרוזת הקודמת שנסרקה. כך בהינתן מחרוזת s1 זו –

s1 = “Christmas without presents.”

נסרוק את תת המחרוזות האלו –

“Ch”

“Chr”

“Chri”

“Chris”

וכן הלאה. עבור כל תת מחרוזת תתבצע בדיקה: האם היא תת מחרוזת של s2.

לאור האמור בבואנו לכתוב תכנית המבוססת על גישה זו נתחיל בפתירת תת-בעיה שלה, והיא זו –

נתונה מחרוזת. יש ליצור את כל מקטעי המחרוזת המתחילים בתו הראשון בה.

דרך אחת לפתור בעיה זו היא לסרוק את האינדקסים של s1, החל מאינדקס 0, ועבור כל אינדקס להשתמש באופרטור [ ] כדי ליצור עותק של תת המחרוזת המתחילה בתו הראשון ב-s1 ומסתיימת באינדקס הנסרק (לא כולל). הנה הצעה לקוד המבצע זאת –

s1 = “Christmas without presents.”

for i in range(len(s1)):

substring = s1[:i]

print(substring)

השורה הראשונה בלולאה –

for i in range(len(s1)):

ערוכה לפי התבנית הכללית של סריקת אינדקסים (ראו גם בעיה א’). נתחיל לקרוא אותה מחלקה הבא לאחר המילה in –

range(len(s1))

יש כאן זימון של הפונקציה range לצורך יצירת סדרה של מספרים: החל מ-0 ועד המספר שהוא אורך המחרוזת s1, לא כולל מספר זה. במקרה שלפנינו הסדרה הנוצרת מתחילה עקרונית כך –

0, 1, 2, 3, 4, …

כל מספר בסדרה זו מוצב במשתנה הלולאה i ובגוף הלולאה ישמש בתור אינדקס למחרוזת. כך ההוראה הזאת בגוף הלולאה –

substring = s1[:i]

יוצרת מקטע של המחרוזת s1 המתחיל בראשיתה ומסתיים בתו הנמצא באינדקס הנסרק הנוכחי, לא כולל תו זה. כך הקוד כולו יוצר את כל תת המחרוזות של s1 המתחילות בתחילתה ומדפיס כל אחת ואחת מתת מחרוזות אלו. בסיבוב הראשון נוצרת תת מחרוזת עבור טווח האינדקסים 0:0, כלומר מקטע ריק, בסיבוב השני נוצרת תת מחרוזת עבור טווח האינדקסים 0:1, כלומר התו הראשון במחרוזת; וכן הלאה.

עתה יש להוסיף לסריקה את הבדיקה הנדרשת: האם תת המחרוזת אינה מוכלת בתוך המחרוזת s2 –

s1 = “Christmas without presents.”

s2 = “Christmas won’t be Christmas without any presents.”

for i in range(len(s1)):

substring = s1[:i]

if substring not in s2:

print(substring)

>>>

Christmas without p

Christmas without pr

Christmas without pre

Christmas without pres

Christmas without prese

Christmas without presen

Christmas without present

Christmas without presents

קטע קוד זה מדפיס את כל תת המחרוזות של s1 המתחילות בתו הראשון בה ואינן מוכלות במחרוזת s2. נשים לב כי המחרוזת ‘Christmas wi’ מוכלת בתוך המחרוזת s2.

כדי להשלים את הפתרון עלינו להדפיס את תת המחרוזת הקצרה ביותר המקיימת את התנאי. במימוש המוצע המחרוזת הזאת היא המחרוזת המוצבת במשתנה substring ברגע הכניסה הראשונה לגוף ה-if. יוצא מכאן שכדי להשלים את הפתרון עלינו להדפיס את תת המחרוזת הראשונה המקיימת את התנאי, ולעצור את הלולאה מיד. אפשר לעשות זאת באמצעות הוראת break, כך –

s1 = “Christmas without presents.”

s2 = “Christmas won’t be Christmas without any presents.”

for i in range(len(s1)):

substring = s1[:i]

if substring not in s2:

break

print(substring)

>>>

Christmas without p

כאן, כשמצאנו בפעם הראשונה תת מחרוזת של s1 המקיימת את התנאי, נכנסנו לגוף ה-if, הדפסנו את תת המחרוזת, וקטענו מיד את סריקת תת המחרוזות באמצעות ביצוע הוראת break.

יש מתכנתות ומתכנתים רבים שבעיניהם שימוש ב-break אינו נחשב אלגנטי. נוסף על כך במקרה כמו זה שלפנינו, כשלולאה צריכה להמשיך להסתובב כל עוד מתקיים תנאי מסוים, טבעי להשתמש בלולאת while. הנה הצעה לפתרון השאלה באמצעות לולאת while –

s1 = “Christmas without presents.”

s2 = “Christmas won’t be Christmas without any presents.”

i = 0

found = False

while i < len(s1) and not found:

substring = s1[:i]

if substring not in s2:

print(substring)

found = True

continue

i = i + 1

>>>

Christmas without p

לפני הלולאה הגדרנו שני משתנים. משתנה אחד הוא i – כמו בגרסה הקודמת של הקוד גם כאן משתנה זה יסרוק את האינדקסים של המחרוזת s1, החל מ-0 ועד אורך המחרוזת (לא כולל): בסוף כל סיבוב של הלולאה, לאחר יצירת תת המחרוזת הנוכחית ובדיקתה, ערכו מוגדל ב-1. המשתנה האחר הוא found. זה משתנה דגל (flag). הוא מתחיל את חייו כשהוא מכיל False. כשהקוד מוצא את תת המחרוזת המבוקשת ערכו של המשתנה found מוחלף ל-True כדי לאותת על מציאתה. הלולאה ממשיכה כל עוד לא נסרקו כל האינדקסים שיש לסרוק וגם המשתנה found מכיל False (כלומר הערך של הביטוי not found הוא True). ברגע שנמצאת תת המחרוזת המבוקשת, לאחר הדפסתה והצבת True במשתנה found, מתבצעת הוראת continue. הוראה זו מדלגת על כל ההוראות הבאות אחריה – ספציפית: קידום i ב-1 – ועוברת לבדוק את תנאי הלולאה. כיוון שהתנאי כבר לא מתקיים – הרי found מכיל עתה True ולכן תוצאת הביטוי not found היא False – הלולאה מסתיימת.

(ב) ההבדל העקרוני בין השאלה בסעיף זה לבין השאלה בסעיף הקודם היא שהפעם עלינו למצוא את כל תת המחרוזות של s1, לא רק אלו המתחילות בתחילת המחרוזת. כדי להמחיש את המבוקש נעיין במחרוזת s1 זו –

s1 = ‘best’

תת המחרוזות שעלינו לאתר ולבדוק כאן הן כדלקמן –

bes

est

best

כאן ציינו את תת המחרוזות לפי אורכן: כל תת המחרוזות באורך 1, כל תת המחרוזות באורך 2, וכן הלאה. זה הסדר שבו עלינו לאתר את תת המחרוזות ולבחון אותן, הואיל והמבוקש הוא תת המחרוזת הקצרה ביותר של s1 שאינה מוכלת במחרוזת s2. אם כן עלינו לסרוק את כל הגדלים האפשריים של תת המחרוזות, החל מ-1 ועד לגודל המקסימלי. הנה הצעה למימוש –

s1 = “best”

for i in range(1, len(s1) + 1):

for j in range(len(s1)):

if len(s1[j:j+i]) == i:

print(s1[j:j+i])

>>>

bes

est

best

הלולאה החיצונית סורקת את כל הגדלים האפשריים של תת מחרוזות של s1, החל מ-1 ועד גודל המחרוזת כולה, כולל; עבור מחרוזת הדוגמה, ‘best’, סדרת הגדלים היא 1, 2, 3 ו-4 כולל. הלולאה הפנימית סורקת אחד-אחד את האינדקסים של התווים במחרוזת s1, ועבור כל אינדקס מייצרת את תת המחרוזת המתחילה באינדקס זה ושאורכה הוא בדיוק הגודל הנסרק כרגע בלולאת ה-for החיצוינת (התנאי מבטיח שהאורך יהיה בדיוק הגודל הזה, ושלא יובאו בחשבון מחרוזות קצרות יותר המתקבלות כשהגבול העליון בטווח שצוין בתוך האופרטור [ ] חורג מגודל המחרוזת – למשל s1[2:6] אוטומטית מקוצר ל-s[2:4]).

נשלב את המימוש האחרון בפתרון השאלה כולו –

found = False

for i in range(1, len(s1) + 1):

for j in range(len(s1)):

substring = s1[j:j+i]

if (len(substring) == i

and

substring not in s2 and not found):

print(substring)

found = True

>>>

t p

נוסף על בדיקה שתת המחרוזת הנוכחית היא בגודל הנוכחי שסורקת לולאת ה-for החיצונית, הוראת ה-if כאן מוודאת שתת מחרוזת זו אינה מוכלת ב-s2 וגם שעדיין לא מצאנו מחרוזת כזו; הבדיקה האחרונה מתבצעת באמצעות משתנה דגל בדומה לפתרון לשאלה בסעיף הקודם בו השתמשנו בלולאת while.

(ג) לאחר שפתרנו את השאלה בסעיף ב’, פתרון השאלה בסעיף הנוכחי הוא ישיר למדי. הנה הצעה לפתרון –

def findShortest(s1, s2):

for i in range(1, len(s1) + 1):

for j in range(len(s1)):

substring = s1[j:j+i]

if (len(substring) == i

and substring not in s2):

return substring

print(findShortest(“Christmas without presents”,

“Christmas won’t be Christmas without any presents.”))

>>>

t p

להכנסת הקוד לתוך הפונקציה הייתה השפעה חשובה על היבט אחד שלו, והטעמתה היא הסיבה העיקרית להכללת הסעיף הנוכחי בשאלה. הטיפול במצב שבו מצאנו את תת המחרוזת המבוקשת. שלא כמו בקוד מחוץ לפונקציה, לא היינו צריכים לקטוע את הלולאה (למשל באמצעות ההוראה break) או להשתמש במשתנה דגל כדי להימנע מהדפסות של מחרוזות נוספות המקיימות את התנאי לאחר שכבר נמצאה מחרות אחת כזו. בגרסת הפונקציה, ברגע שאנו מוצאים את תת המחרוזת המבוקשת, בבדיקה של הוראת ה-if בגוף הלולאה הפנימית, אנו מחזירים את תת המחרוזת הזאת באמצעות הוראת return, וביצוע הוראה זו הוא עצמו קוטע את הלולאה, ולמעשה קוטע את ביצוע הפונקציה כולו.