problem4

בעיה ד'

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

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

while age != ‘-1’:

    print(age)

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

 

כתבו את הפונקציה multipleAndConsecutive –

def multipleAndConsecutive(s):

לפונקציה פרמטר אחד: s, מחרוזת לא ריקה. הפונקציה מחזירה קבוצה (set) של תווים (תת מחרוזות באורך 1) במחרוזתs . כל תו בקבוצה המוחזרת מופיע במחרוזת s יותר מפעם אחת, וכל ההופעות שלו במחרוזת s הן רצופות. דוגמות –

print(multipleAndConsecutive(“sbbbxyxyy”))

>>>

{‘b’}

 

print(multipleAndConsecutive(“sbbbxxyy”))

>>>

{‘b’, ‘y’, ‘x’}

 

פתרון

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

for char in set(s):         

    if s.count(char) > 1:

שימו לב כי לולאה זו אינה סורקת את כל התווים במחרוזת הנתונה s כי אם את קבוצת כל התווים השונים זה מזה הנמצאים בה, כנדרש. 

כעת אנו צריכים לטפל במצב שבו נמצא שהתו הנסרק הנוכחי בלולאה, כלומר התו המוצב במשתנה הלולאה char, אמנם מופיע יותר מפעם אחת במחרוזת s. כאמור במצב זה עלינו לבדוק אם כל ההופעות של התו הזה – שתיים או יותר – הן רצופות. למעשה אנחנו צריכים לפתור תת בעיה זו –

 

נתונים מחרוזת s ותו במחרוזת זו, char. ידוע כי התו char מופיע במחרוזת s פעמיים או יותר. יש למצוא אם כל ההופעות שלו במחרוזת הן רצופות או שאינן רצופות. 

 

יש כמה דרכים לפתור בעיה זו, ובדיון כאן נציע שני פתרונות שונים זה מזה. הפתרון האחד מבוסס על השוואת אינדקסים: אם כל אינדקס שהתו מופיע בו במחרוזת, החל מההופעה השניה, גדול מקודמו ב-1, אזי כל ההופעות של התו במחרוזת הן רצופות; אם אין זה המצב לא כל ההופעות של התו במחרוזות הן רצופות. כדי להבין את הפתרון המבוסס על רעיון זה, נעיין בדוגמות לאופן פעולתו. נניח שאנו יודעים שהתו ‘b’ מופיע יותר מפעם אחת במחרוזת “sbbbxyxyy” ואנו רוצים למצוא אם כל ההופעות שלו במחרוזת הן רצופות. נתקדם באופן זה – 

• נתחיל במציאת האינדקס של ההופעה הראשונה של ‘b’ ב-“sbbbxyxyy” – זה האינדקס 1. 

• אחר כך נמצא את האינדקס של ההופעה השניה של ‘b’ ב-“sbbbxyxyy” – זה האינדקס 2. אנו יודעים שיש הופעה שניה כיוון שכאמור ידוע ש-‘b’ מופיע במחרוזת “sbbbxyxyy” יותר מפעם אחת. 

• בנקודה זו נבדוק אם האינדקס של ההופעה השניה גדול ב-1 מהאינדקס של ההופעה הראשונה. נגלה כי אמנם זה המצב, ונסיק כי שתי ההופעות הראשונות של התו ‘b’ במחרוזת “sbbbxyxyy” הן סמוכות זו לזו. לכן נמשיך הלאה. 

• אחר כך נבדוק אם יש הופעה נוספת של ‘b’ במחרוזת “sbbbxyxyy”. נמצא שיש, ונאתר את האינדקס שלה: 3. 

• נבדוק אם האינדקס של ההופעה השלישית גדול ב-1 מהאינדקס של ההופעה השניה. נגלה כי זה המצב, ולכן שוב נמשיך הלאה.

• נבדוק אם יש הופעה נוספת של ‘b’ במחרוזת “sbbbxyxyy”. נמצא שאין, ולכן נפסיק כאן, ונסיק שאמנם כל ההופעות ‘b’ במחרוזת “sbbbxyxyy” הן רצופות. 

דוגמה נוספת: נניח שאנו יודעים שהתו ‘y’ מופיע יותר מפעם אחת במחרוזת “sbbbxyxyy” ואנו רוצים למצוא אם כל ההופעות שלו במחרוזת הן רצופות. נתקדם באופן זה – 

• נתחיל במציאת האינדקס של ההופעה הראשונה של ‘y’ ב-“sbbbxyxyy” – זה האינדקס 5. 

• אחר כך נמצא את האינדקס של ההופעה השניה של ‘y’ ב-“sbbbxyxyy” – זה האינדקס 7. 

• נבדוק אם האינדקס של ההופעה השניה גדול ב-1 מהאינדקס של ההופעה הראשונה. נגלה כי זה אינו המצב’ ולכן נסיק שלא כל ההופעות של התו ‘y’ במחרוזת “sbbbxyxyy” הן רצופות. ממילא נעצור כאן ולא נמשיך לאינדקס של ההופעה השלישית של ‘y’ במחרוזת (אינדקס 8). 

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

(1) נגדיר משתנה לוגי, נקרא לו consecutive. נאתחל אותו ל-True. בסוף ביצוע האלגוריתם יכיל משתנה זה True אם כל ההופעות של התו char במחרוזת s הן רצופות, או False אם אין זה המצב. 

(2) נסרוק אחד-אחד את האינדקסים של ההופעות של char במחרוזת s. אם במהלך הסריקה נגלה שהאינדקס הנוכחי אינו גדול ב-1 מקודמו, נציב False במשתנה consecutive, ונעצור את הלולאה מיד. אם לא נגלה אינדקס כזה, הלולאה תסתיים לאחר שנסיים לסרוק את כל ההופעות של char במחרוזת s, והמשתנה consecutive יכיל True (ערך האתחול שלו). 

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

consecutive = True

הוראה זו מבטאת את ההנחה שכל ההופעות של התו char במחרוזת s הן רצופות. המשך הקוד יבדוק אם הנחה זו נכונה: אם בתום בדיקת ההופעות של התו הנסרק הנוכחי יתברר שיש שתי הופעות של התו char שאינן מופיעות באינדקסים סמוכים יוצב הערך False במשתנה consecutive. לפי האלגוריתם הבדיקה עצמה מבוססת על השוואת אינדקסים. לכן  במחשבה ראשונה אפשר לשער שהקוד צריך להימשך בסריקת אינדקסים, למשל כך  – 

for char in set(s):         

    if s.count(char) >= 2:

        consecutive = True 

        for i in range(len(s)): 

          if s[i] == char: 

עבור התו הנסרק הנוכחי char, לולאת ה-for הפנימית סורקת את כל האינדקסים של המחרוזת s. הוראת ה-if השוכנת בתוך לולאה זו בודקת אם באינדקס הנסרק הנוכחי מופיע התו char. מכאן יוצא שכאשר אנו נכנסים לגוף הוראת ה-if הזאת יש בידינו – במשתנה i – את האינדקס הנוכחי של התו char ב-s. בנקודה זו עלינו לחשוב כיצד נוכל להגיע אל התו המופיע באינדקס הקודם של המחרוזת או, לצורך העניין, אל התו המופיע באינדקס הבא של המחרוזת, ולהשוות את התו הזה לתו באינדקס i, כפי שתארנו למעלה. אך נעצור כאן ולא נתקדם בכיוון הזה, כיוון שמשפט אחד באלגוריתם שהצענו מורה שרצוי יותר לבצע את סריקת האינדקסים באמצעות לולאת while. המשפט הוא זה: “אם במהלך הסריקה נגלה שהאינדקס הנוכחי אינו גדול ב-1 מקודמו, נציב False במשתנה consecutive, ונעצור את הלולאה מיד”. אם למשל נסרוק את התו ‘y’ במחרוזת הזאת – 

“sbbbxyxyy”

נבין מיד בסריקת ההופעה השניה של התו (באינדקס 7) שלא כל ההופעות של ‘y’ במחרוזת s הן רצופות (כיוון שאינדקס 7 אינו גדול ב-1 מהאינדקס של ההופעה הקודמת, 5), ויהיה עלינו להפסיק את הסריקה מיד ולא לבדוק את ההופעה השלישית של התו (זו באינדקס 8). אם כן יש לנו כאן לולאה מסוג “כל עוד”, ולכן נעדיף להשתמש בלולאת while (בכל זאת להלן נראה גם פתרון המבוסס על לולאת for). הנה הצעה ראשונה למימוש גוף האלגוריתם שהוצג למעלה באמצעות לולאת while –

for char in set(s):         

    if s.count(char) >= 2:                         

        consecutive = True 

        currentInd = s.find(char)

        while currentInd != -1 and consecutive: 

            nextInd = s.find(char, currentInd + 1)

            if (nextInd != -1 and s[currentInd] != s[currentInd+1]):                     

                consecutive = False 

                continue 

            currentInd = nextInd

מיד נעיין שלב-שלב בתוספת שהוספנו לקוד הקיים. אך קודם לזה כדאי מאוד שתנסו להבין כיצד הוא פועל בכוחות עצמכם, הן כדי לתרגל קריאת קוד, הן כיוון שעיון זה יסייע לכם בהבנת המשך הדיון כאן. תוכלו להסתייע בשתי טבלאות מעקב אלו (על אודות טבלאות מעקב ראו למעלה, שאלה 3). מטעמי מקום הטבלאות מוצגות בתבנית אנכית ולא אופקית. הנה טבלה העוקבת אחר ביצוע לולאת ה-while הבודקת את הופעותיו של התו ‘b’ במחרוזת “sbbbxyxyy”.

והנה טבלה העוקבת אחר ביצוע הלולאה הבודקת את הופעותיו של התו ‘y’ במחרוזת “sbbbxyxyy“.

התוספת שהוספנו לקוד מתחילה בהוראה הזאת –

currentInd = s.find(char)

ההוראה מוצאת את האינדקס הראשון שבו מופיע char במחרוזת s. אם למשל נסרוק את התו ‘y’ במחרוזת “sbbbxyxyy”, ההוראה תציב את האינדקס 5 במשתנה currentInd. נשים לב כי בשלב זה לא ייתכן שהפונקציה find תחזיר 1- (מינוס 1), כיוון שידוע כי התו char מופיע במחרוזת s לפחות פעמיים. עניין זה חשוב להבנת השלב הבא של הקוד, כלומר המעבר לביצוע מבנה לולאת ה-while. התנאי הנבדק בתחילת הלולאה הוא זה – 

currentInd != -1 and consecutive

תזכורת: מימין לאופרטור and ננקטת כתיבה מקוצרת. הכתיבה המלאה היא זאת – 

currentInd != -1 and consecutive == True

מה פירוש הביטוי הלוגי המורכב הזה? אלו שני תנאים חייבים להתקיים כדי שגוף הלולאה יתבצע? מאליו מובן שנרצה להמשיך לסרוק אינדקסים רק אם טרם סרקנו את כולם. לכן התנאי הראשון הנבדק כאן הוא שהפונקציה find מצאה הופעה נוספת של התו char במחרוזת s, ולכן לא החזירה 1- . התנאי השני יוודא שהלולאה תעצר במקרה שהגענו למסקנה, אגב סריקת האינדקסים, שאיתרנו הופעה של התו char במחרוזת s שאינה צמודה להופעה שקדמה לה. כאמור אם נאתר מצב כזה, נשנה את הערך המוצב במשתנה consecutive מ-True, ערך האתחול שלו, ל-False. השינוי הזה מתבצע בגוף לולאת ה-while. בגוף הלולאה יש ארבע שורות, ואלו הן –

nextInd = s.find(char, currentInd + 1)

if (nextInd != -1 and currentInd + 1 != nextInd):

    consecutive = False 

    continue

גוף הלולאה מתחיל באיתור האינדקס של ההופעה הבאה של התו char  במחרוזת s. הארגומנט השני המועבר לפונקציה מציין כי יש לחפש את ההופעה הזאת במחרוזת s החל מהתו המופיע לאחר ההופעה הראשונה של התו. כאמור בסיבוב הראשון של הלולאה אנו יכולים לדעת בוודאות שהפונקציה find  לא תחזיר 1- (מינוס 1), כיוון שידוע שיש לפחות שתי הופעות של התו char במחרוזת s. עם זה אפשר שאלו הן שתי ההופעות היחידות, ואם זה המצב הזימון הבא של הפונקציה find יחזיר 1-. לכן, במבנה ה-if בגוף הלולאה, עוד לפני הבדיקה אם האינדקס של ההופעה הבאה גדול ב-1 מהאינדקס של ההופעה הנוכחית – כלומר אם שתי ההופעות צמודות זה לזה – אנו בודקים אם קיימת הופעה נוספת של char ב-s לאחר זו הנמצאת ב-currentInd. הבדיקה הזאת מנוסחת בביטוי הלוגי הראשון המופיע בתנאי של מבנה ה-if –

if (nextInd != -1 and  currentInd + 1 != nextInd):

הביטוי הלוגי הפשוט השני (מימין ל-and) בודק אם שתי ההופעות של char במחרוזת s – זו שהאינדקס שלה מצוי ב-currentInd וזו שהאינדקס שלה מצוי ב-nextInd – אינן צמודות זו לזו. אם זה המצב ערכו של המשתנה consecutive מוחלף ב-False וההוראה continue מעבירה אותנו ישירות לבדיקה של תנאי הלולאה, בלי לבצע את ההוראה הבאה בגוף הלולאה (מיד נדון בה). או אז, בבדיקת תנאי הלולאה, מתברר כי תנאי זה כבר אינו מתקיים, כיוון ש-consecutive אינו מכיל True, והלולאה נעצרת. לעומת זאת אם ההופעה הבאה של char במחרוזת s צמודה לזו הנוכחית, אין מתבצע גוף ה-if, והזרימה עוברת להוראה הבאה לאחר לולאת ה-while –

currentInd = nextInd

הוראה זו מעדכנת את האינדקס המוצב במשתנה currentInd לאינדקס של ההופעה הבאה של char ב-s, זה המוצב עכשיו במשתנה nextInd. כשנתחיל בביצוע הבא של גוף לולאת ה-while נאתר את ההופעה הבאה לאחר זו הנמצאת באינדקס שיש ב-nextInd, נציב אותה במשתנה nextInd, ונמשיך הלאה בבדיקה לפי המתואר למעלה. 

כשלולאת ה-while מסתיימת, כלומר כשהסתיימה הבדיקה אם כל ההופעות של התו char במחרוזת s הן רצופות, כל שנותר הוא לבדוק את תכנו של המשתנה consecutive. אם יש בו True, פירוש הדבר הוא שכל ההופעות של התו char במחרוזת s הן רצופות. לפי השאלה עלינו לשמור את התו הזה יחד עם כל התווים המקיימים את התנאי המתואר בשאלה בקבוצה (set). לכן נוסיף את התו המוצב במשתנה char לקבוצה שהוגדרה מראש והתחילה את חייה בתור קבוצה ריקה. עד לסיום לולאת ה-for, כלומר עד לסוף סריקת כל התווים השונים זה מזה שיש במחרוזת s תהיה בידינו קבוצת התווים המבוקשת. הנה הקוד המלא של הפונקציה multipleAndConsecutive ובו הפעולות שתוארו זה עתה –

def multipleAndConsecutive(s): 

    chars = set() 

    for char in set(s):         

        if s.count(char) >= 2:                         

            consecutive = True 

            currentInd = s.find(char)

            while currentInd != -1 and consecutive: 

                nextInd = s.find(char, currentInd + 1)

                if (nextInd != -1 and 

                    currentInd + 1 != nextInd):

                    consecutive = False 

                    continue 

                currentInd = nextInd              

            if consecutive: 

                chars.add(char)

    return chars

 

נעיר כי אפשר לכתוב מימוש של הפונקציה multipleAndConsecutive המבוסס על הרעיון הבסיסי שהפתרון הנ”ל מבוסס עליו אך משתמש בלולאת for ולא בלולאת while. הנה דוגמה למימוש כזה –

def multipleAndConsecutive(s): 

    chars = set() 

    for char in set(s): 

        times = s.count(char)        

        if times >= 2:                         

            consecutive = True 

            currentInd = s.find(char)

            for time in range(times – 1):                         

                nextInd = s.find(char, currentInd + 1)

                if currentInd + 1 != nextInd:                     

                    consecutive = False 

                    break 

                currentInd = nextInd

            if consecutive: 

                chars.add(char)

    return chars 

 

print(multipleAndConsecutive(“sbbbxxyy”))

 

בראש גופה של הלולאה החיצונית הגדרנו משתנה (times) המחזיק את מספר ההופעות של התו char במחרוזת s. עשינו זאת כי בגרסה הנוכחית של הפונקציה אנו נזקקים למספר זה פעמיים: פעם בבדיקה אם התו מופיע פעמיים או יותר במחרוזת s, ופעם נוספת לצורך לולאת ה-for הפנימית, זו הבאה לבדוק אם כל ההופעות של התו char הן רצופות. תנו דעתכם: שלא כמו בשימושים בה עד כה באוסף שאלות זה, לולאת ה-for כאן אינה סורקת תווים באוסף הנתון בשאלה – כאן: המחרוזת s – ואף אינה סורקת אינדקסים של אוסף. זו לולאת for שמטרתה לבצע קטע קוד נתון מספר מסוים של פעמים. שימו לב שבגוף הלולאה כאן לא נעשה שימוש כלל במשתנה הלולאה times  – כל ייעודו הוא לשרת את הגדרת הלולאה בתור לולאה שרצה מספר מסוים של פעמים – כאן: times – 1, כלומר מספר ההופעות של התו הנסרק הנוכחי במחרוזת פחות 1. מדוע פחות 1? כיוון שאם למשל יש 3 הופעות, יש לבצע 2 בדיקות של ההופעה הנוכחית לעומת ההופעה הבאה; ואם יש 4 הופעות, יש לבצע שלוש בדיקות; וכן הלאה. כיוון שמספר הבדיקות נקבע מראש, אין צורך בבחינה של ערך ההחזרה של הפונקציה find כדי לבדוק אם סיימנו את כל הבדיקות, כפי שעשינו בלולאת ה-while. בה בעת, כיוון שלא השתמשנו בלולאת while נאלצנו להשתמש בהוראה break כדי לטפל במקרה שבו מתברר, קודם לסיום הלולאה, שלא כל ההופעות של התו char במחרוזת s הן רצופות. לא מעט מתכנתים יעדיפו לא להשתמש בהוראה זו ולממש באמצעות לולאת while. 

עד כאן הפתרון הראשון לשאלה. נפנה לפתרון השני. הרעיון שהוא מבוסס עליו נובע מתובנה זו: נניח שהתו char מופיע times פעמים במחרוזת s. מובן שכל times ההופעות של התו char במחרוזת s הן רצופות אך ורק אם המחרוזת הזאת –

char * times

היא תת מחרוזת של s. נניח למשל שידוע לנו שהתו ‘y’ מופיע במחרוזת s 3 פעמים. ברור שכל הופעותיו במחרוזת הן רצופות אך ורק אם המחרוזת הזאת היא תת מחרוזת של המחרוזת s –

‘y’ * 3 → ‘yyy’

ובמידה שווה ברור שאם המחרוזת ‘yyy’ אינה תת מחרוזת של s, לא כל ההופעות של ‘y’ במחרוזת s הן רצופות.  יוצא מכאן כי עבור כל תו המופיע יותר מפעם אחת במחרוזת s, בבואנו לבדוק אם כל ההופעות שלו במחרוזת הן רצופות, כל שעלינו לעשות הוא לבדוק אם המחרוזת s מכילה מחרוזת שהיא הכפלת התו הזה כמספר הופעותיו במחרוזת s. הנה מימוש בקוד של פתרון המבוסס על רעיון זה –

def multipleAndConsecutive(s): 

    chars = set() 

    for char in set(s): 

        times = s.count(char)        

        if times >= 2 and char * times in s:         

            chars.add(char)

    return chars

ניתן דעתנו כי בקוד זה יש דוגמה נוספת לתבנית יצירת אוסף בלולאה, תבנית שכבר פגשנו דוגמות לה בפתרונות קודמים, כלומר: אתחול אוסף חדש וריק, סריקת ערך-ערך באוסף נתון, והכנסת הערך הנסרק לאוסף החדש אם הוא מקיים תנאי מסוים  (להסבר נוסף ראו שאלה 1). מאבחנה זו נובע כי אפשר לקצר את הקוד באמצעות ביטוי Comprehension, וספציפית ביטוי Set Comprehension, הואיל ונוצרת כאן קבוצה. הנה הקוד המקוצר (בפונקציה יש שורת קוד אחת בלבד) –

def multipleAndConsecutive(s): 

    return {char for char in set(s) if s.count(char) >= 2 and char * s.count(char) in s}

 

שימו לב כי בביטוי ה- Set Comprehensionיש הכפלת קוד: כיוון שאנו זקוקים לחישוב מספר ההופעות של התו char במחרוזת s פעמיים – הן בבדיקה אם מספר ההופעות גדול מ-2 הן בבדיקה אם כל ההופעות רצופות – וכיוון שהביטוי כולו נכתב בשורה אחת בלבד, היה עלינו לכתוב את חישוב מספר ההופעות פעמיים בביטוי זה.