שימוש ברקוריסה בג'ווה למציאת כל האפשרויות במערך

[Dimka]

שאלה למי שמכיר כמובן,

איך אפשר (בעזרת רקורסיה) להגיע לכל הקומבינציות במערך?

הנה שאלה לדוגמה שהייתה לי:

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

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

נניח המערך הוא 3,4,6,8

6 * 4 = 3 * 8 ולכן אמת.

ואילו הכנסת המערך 1,2,3,4 לשיטה יוציא שקר. כיוון שאין קומבינציה כזו.

האלגוריתם שחשבתי עליו:

1. מעבר על המערך והכפלת כל הערכים ומציאת הסכום.

2. הכפלת כל מני קומבינציות בצורה רקורסיבית וכל פעם העלאה שלהם בריבוע והשוואה לערך שיצרנו ב-1.

3. אם נמצאה קבוצה כלשהי ששווה לערך של 1, מוציאים אמת, שקר אם לא נמצאה...

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

[Ghosthunter]

עבור כל איבר יש 2 אפשרויות - שיופיע בקבוצה הראשונה או שיופיע בקבוצה השנייה.

זאת אומרת שכל פעם אתה צריך לקרוא פעמיים בצורה רקורסיבית - כל פעם כאשר האיבר בקבוצה אחרת.

תמשיך מכאן.

[Dimka]

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

[ירח אפל]

תמצא את שורש מכפלת כל האברים.

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

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

אם מצאת אז תחזיר ערך אמת.

ומעבר על האפשרויות.

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

בכל קבוצה אתה עובר על האיברים אחד אחד בלולאה ומכפיל בתשובה של הרקרוסיה עבור שאר האיברים.

[Dimka]

תודה, אבל זה בעצם השלב שבו אני תקוע מלכתחילה

אתאר את הבעיה:

נגיד המערך 1 2 3 4 5

אין לי בעיה לבדוק תת מערכים של המערך הזה:

1

12

123

1234

12345

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

(כמובן שהמערך עלול להיות באורך n)

[ירון ר]

התרגיל עניין אותי.

אז מצורפים 2 פתרונות

נ.ב:

כתבתי ב-C#. אבל היא מאוד קרובה ל-JAVA כך שמאוד קל לתרגם.

כמובן שאם משהוא לא ברור שאל....

[attachment deleted by admin]

[שניצל]

יכלת להעלות רק את קבצי ה-cs במקום להעלות את כל הפרוייקט...

[Dimka]

התרגיל עניין אותי.

אז מצורפים 2 פתרונות

נ.ב:

כתבתי ב-C#. אבל היא מאוד קרובה ל-JAVA כך שמאוד קל לתרגם.

כמובן שאם משהוא לא ברור שאל....

תודה, לצערי אני לא מכיר C# ואפילו ב- C רגיל כלל לא בקיא.

אתה יכול בבקשה להסביר במילים איך הגעת לכל הקומבינציות?

חילקת את המערך או משהו?

(אגב בתוכנה שלך השתמשת בדוגמה שנתתי, אבל אצלי זה יכול להיות מערך בגודל n).

[שניצל]

א. אין קשר בין C ל-#C.

ב. אם אתה יודע Java אז התחביר של #C אמור להיות די מובן.

[ירון ר]

זה אמור לפתור כל מערך בגודל n. (זה רק עניין של זמן וגודל מחסנית, אם למשל n=1000)

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

הרעיון של הפתרון השני (נתחיל בשני כי הוא פשוט יותר):

הרעיון מתבסס על הרעיון הבינארי. (כמו במחשבון של ווינדוס) הגדרתי 0 - קבוצה ראשונה. 1 - קבוצה שניה.

כל שנותר לעבור על כל המספרים שיתנו את כל התוצאות הביאריות...

תוכל לקרוא על זה בוויקי:

http://he.wikipedia.org/wiki/%D7%91%D7%A1%D7%99%D7%A1_%D7%91%D7%99%D7%A0%D7%90%D7%A8%D7%99

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

111110

ולא עד

111111

אבל זה לא נורא וקל לתקן את זה. (פשוט לכתוב בתנאי עצירה מינוס 1)

הרעיון של הפתרון הראשון:

הוא דומה קצת לרעיון השני, אבל הוא מבוסס על הסתברות (ישנם מצבים שהאלגוריתם הזה אמור להיות מהיר יותר וישנם מצבים שלא)

גם כאן, נגדיר 0 - קבוצה ראשונה. 1 - קבוצה שניה.

ניתן לחלק את האלגוריתם ל-2:

1. לעבור על כל האפשרויות הבנומיות של n 'סביות' מסויים.

2. לעבור על כל n.

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

00011

00101

01001

10001

00110

..

10100

11000

וכל n זה מספר הסיביות שהן '1'

[Dimka]

מבחינה בינארית אתה מדבר על מעבר של כתובות? כי נראה לי הפתרון אמור להיות יותר פשוט, ללא שימוש או מעבר לבסיס 2.

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

[שניצל]

אכן יש פתרון יותר פשוט - רקורסיה (התשובה בגוף השאלה).

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

קל לראות כמובן שאם אתה פותר אותה, קל להגיע לפתרון של הבעיה המקורית (פשוט תציב x=y=1).

ברקורסיה אתה צריך לנסות את כל האופציות האפשריות לחלוקה לשתי הקבוצות.

[ירון ר]

ברקורסיה אתה צריך לנסות את כל האופציות האפשריות לחלוקה לשתי הקבוצות.

ואיך אתה מנסה את כל האפשרויות בצורה רקורסיבית?

[ירח אפל]

האמת שזה מאוד פשוט

מבנה כללי צריך להיות כזה

מציאת שורש מכפלת כל האיברים ובדיקה אם הוא שלם.

בדוק (מערך, אורך המערך, שורש מכפלת האיברים)

פונקציה------

בדוק (מערך,אורך מערך, מכפלה)

אם מכפלה חלקי מערך [ N ] שווה 1 החזר אמת

אם מכפלה מוד מערך [ N ] שונה מאפס החזר שקר

לולאה 1-I =N עד 1

{אם [ בדוק (מערך, I, מכפלה חלקי מערך N ] ) ] אמת החזר אמת}

החזר שקר

סוף פונקציה------

[שניצל]

ואיך אתה מנסה את כל האפשרויות בצורה רקורסיבית?

כמו שעושים בד"כ ברקורסיה.

קודם כל, תפתור אותה עבור מקרה בסיס (נניח, כשהמערך בגודל 0 או בגודל 1).

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