שאלת מבחן במבוא למדעי המחשב - הטכניון 2020 - רקורסיה

שאלה 4 (25 נקודות): נתונה מחרוזת str שמכילה אותיות אנגלית גדולות בלבד. ממשו פונקציה שמדפיסה פעם אחת כל מחרוזת שניתן להרכיב מהתווים של המחרוזת הנתונה בסדר למילוני (לקסיקוגרפי). ```c void PrintAllPossibleSubstrings(char *str) ``` דוגמה: בהינתן מחרוזת `"SAAB"`, הפונקציה תוציא את הפלט הבא (רק 16 מילים ראשונות מופעיות): A AA AAB AABS AAS AASB AB ABA ABAS ABS ABSA AS ASA ASAB ASB ASBA הערות: • יש להשתמש בשיטת backtracking כפי שנלמדה בכיתה. • בשאלה זו אין דרישות סיבוכיות, אולם כמקובל ב-backtracking יש לוודא שלא מתבצעות קריאות רקורסיביות מיותרות עם פתרונות שאינם חוקיים. • ניתן ומומלץ להשתמש בפונקציות עזר (ויש לממש את כולן). ```c void PrintAllPossibleSubstrings(char *str) { ```

רמז: מיינו את תווי המחרוזת לפני תחילת ה-backtracking — כך סדר הבחירות יהיה לקסיקוגרפי באופן טבעי. כדי להימנע מכפילויות כשיש תווים חוזרים, דלגו על תו $i$ אם $\texttt{sorted}[i]=\texttt{sorted}[i-1]$ ו-$\texttt{used}[i-1]=\text{false}$.

פתרון: **רעיון הפתרון:** נמיין את תווי המחרוזת לסדר לקסיקוגרפי, ואז נשתמש ב-**backtracking** כך שבכל שלב נבחר תו זמין ונוסיף אותו למחרוזת הנוכחית. כדי להימנע מהדפסת מחרוזות כפולות (כשיש תווים חוזרים), נדלג על תו אם קיים לפניו תו זהה שטרם נבחר באותה רמת רקורסיה. **תנאי דילוג (למניעת כפילויות):** אם `sorted[i] == sorted[i-1]` וגם `!used[i-1]`, אז בחירת `sorted[i]` תניב בדיוק את אותה תוצאה כמו בחירת `sorted[i-1]` — לכן נדלג. **מימוש:** ```c #include <stdio.h> #include <stdlib.h> #include <string.h> int compare(const void *a, const void *b) { return (*(char*)a - *(char*)b); } /* * sorted - המחרוזת הממוינת * n - אורכה * used - מערך בוליאני: האם used[i] נבחר כבר * current - המחרוזת שבונים כרגע * depth - כמה תווים כבר נבחרו (=אורך current) */ void backtrack(char *sorted, int n, int *used, char *current, int depth) { for (int i = 0; i < n; i++) { if (used[i]) continue; /* דילוג על כפילויות באותה רמת רקורסיה */ if (i > 0 && sorted[i] == sorted[i-1] && !used[i-1]) continue; /* בחירה */ used[i] = 1; current[depth] = sorted[i]; current[depth + 1] = '\0'; printf("%s\n", current); /* כל תת-מחרוזת חוקית */ backtrack(sorted, n, used, current, depth + 1); /* ביטול בחירה */ used[i] = 0; } } void PrintAllPossibleSubstrings(char *str) { int n = strlen(str); char *sorted = malloc(n + 1); int *used = calloc(n, sizeof(int)); char *current = malloc(n + 1); strcpy(sorted, str); qsort(sorted, n, sizeof(char), compare); /* מיון לקסיקוגרפי */ current[0] = '\0'; backtrack(sorted, n, used, current, 0); free(sorted); free(used); free(current); } ``` **מעקב על `"SAAB"` (לאחר מיון: `"AABS"`):** | `depth` | `i` | תו נבחר | `current` מודפס | |---------|-----|---------|----------------| | 0 | 0 | A | `A` | | 1 | 1 | A | `AA` | | 2 | 2 | B | `AAB` → `AABS` | | 2 | 3 | S | `AAS` → `AASB` | | 1 | 2 | B | `AB` → `ABA`, `ABAS`, `ABS`, `ABSA` | | 1 | 3 | S | `AS` → `ASA`, `ASAB`, `ASB`, `ASBA` | | 0 | 1 | — | **דילוג** (A=A, used[0]=0) | | 0 | 2 | B | `B`, `BA`, `BAA`, `BAAS`, `BAS`, `BASA`, `BS`, … | | 0 | 3 | S | `S`, `SA`, `SAA`, `SAAB`, … | הפלט מתחיל בדיוק כנדרש: `A, AA, AAB, AABS, AAS, AASB, AB, ABA, …` **נכונות backtracking:** לא מתבצעת רקורסיה מיותרת — הקריאה הרקורסיבית מתרחשת רק לאחר הוספת תו חוקי, וכל שלב מדפיס את המחרוזת לפני הרקורסיה כדי לכסות גם מחרוזות קצרות. $\blacksquare$