אני סטודנט שנה א' להנדסת חשמל באוניברסיטת תל אביב, כך שהידע שלי ב-C מוגבל למה שעברנו עד כה בשיעורים.

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

להלן הלינק לשאלה במלואה: http://img847.imageshack.us/img847/1818/tichnut2.p...

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

אם יש במערך שתי תתי סדרות או יותר אז מספיק להחזיר רק אחת מהן.

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

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

תודה מראש לכל מי שמקדיש מזמנו.

רקורסיה היא כן התשובה, אתה פשוט צריך להסתכל מכיוון אחר.

תחשוב על השאלה הבאה: "האם אפשר להגיע לסכום הרצוי בלי האיבר הראשון במערך? ואיתו?"

לא חייבים ברקורסיה... למעשה, אני חושב שהיא פחות מתאימה.

פתרון לא רקורסיבי נאיבי -

רמז: לחשוב על מערך ה sub_seq כ counter בינארי.

ספויילר -

אם תמנה עליו את כל האפשרויות, למעשה תמנה את כל האפשרויות לתת קבוצות. בכל מעבר בלולאה עליך לבדוק האם הסכום הנוצר מתת הקבוצה = לסכום הרצוי.

תוצר לוואי של הדרך הזו - אתה מקבל "חינם" את הסימון במערך המטרה.

נו, זאת בעיית ה subset-sum המפורסמת. (אתה יכול לגלל אם אתה מחפש ספויילרים).

אין לה פיתרון פולינומי( היא NPC נדמה לי...), יש כמה פתרונות יפים. ברקורסיה זה ממש קל.

רקורסיה זאת צורה חשיבה -> קח בעיה, תן בה ביס, קיבלת בעיה קטנה יותר (מאותו סוג).

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

לקבל אם תתן ביס (תשלוף איבר) אחד ?

והנה רקורסיה בזווית קצת שונה :

תחשוב על זה ככה, מה אם הייתי נותן לך את את אותה הבעיה עם טוויסט אחד, הגודל של כל קבוצה הוא 3.

עכשיו אז זה קל, נכון? כמו שאמרת לולאה בתוך לולאה בתוך לולאה... אחלה. עכשיו בוא נעשה את זה 4.

מה אתה צריך לשנות? כלום! רק להוסיף עוד לולאה פנימית. אוקי, מה אם נשנה את 4 ל n?

שים לב אגב, {3,4} ו {4,3} זה אותו סט. פה אנחנו מנסים את שניהם (אינדקסים של לולאות).

ברגע שזה 2 בחזקת N, זה אכן לא פולינומיאלי. עבור כל מספר במערך, ייתכן והוא שייך לקבוצה כזו (אם היא קיימת) וייתכן שלא. המערך בגודל N, עבור כל משתנה 2 אפשרויות, זה 2 בחזקת N. כאשר אתה עושה את זה רקורסיבית, אתה אכן בונה עץ בינארי בעצם שנותן לך את כל תתי הקבוצות של המספרים ועליהן אתה בעצם בודק אם הן מתחברות לכדי מספר המטרה. זו אכן בעיה שקל יותר לבנות רקורסיבית מאשר איטרטיבית. אם בכל זאת אתה רוצה ללכת באיטרציות, תצטרך ממש לבנות את כל תתי הקבוצות, שזה מסובך יותר קומבינטורית, כי אתה צריך קבוצות בכל הגדלים, כלומר מ1 עד N תצטרך לבנות את כל תתי הקבוצות בכל הגדלים, ואז לבדוק על כל קבוצה, וזה כבר הרבה יותר מסובך לתכנות.

הקטע הבעייתי שאני רואה ברקורסיה הוא להלן: בהנחה שהמערך שהוזן על ידי המשתמש הוא : (-17,5,8,1,-5,-12-,0,8)

לדוגמא סכום המטרה הוא מינוס 10, אז האיברים המתאימים במערך נמצאים במקומות seq{1}+seq{4}+seq{7} למשל.

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

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

הרעיון הוא להשתמש בגישת ה-wishful thinking. הרעיון הוא כמו איך שעובדת הוכחה מתמטית באינדוקציה.

יש לך מערך נתון בגודל n. כעת, נניח שאתה יודע ב-100% שהפונקציה עובדת אם מעבירים לה מערך בגודל n-1 (לא משנה איך היא עובדת - נניח מישהו כבר פתר את המקרה הזה עבורך). איך תפתור את הבעיה עבור המערך שלך?