| כותב |
|
רקורסיה
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 07 January 2009 בשעה 08:19 | | IP רשוּם
|
|
|
|
אני צריך לכתוב תוכנית רקורסיבית אשר
מקבלת מערך של המספרים שלמים ומחזירה את האורך של התת סדרה העולה הכי ארוכה במערך.
יש לי רעיון והוא כך
f(i)- מוגדר להיות תת הסדרה הארוכה ביותר עד האיבר i
f(1)=1
f(i+1)=max{f(j)|1=<j=<i and A[j]<=A[i+1]}
העניין הוא שאני מוגבל בצורה הבאה:
אסור לי להשתמש בלולאות וכן אסור לי להשתמש בפונקציות עזר.
וכאן בדיוק הבעיה
בשביל לפתור את זה אני אצטרך פונקציה רקורסיבית אחת שעוברת על איברי המערך וכן פונקציית עזר שמוצאת לי את המקסימום בין אברי f(j)
יש למישהו פתרון אחר? או כיצד לעשות זאת ללא פונקציית עזר?
שאלה 2:
צריך לכתוב פונקציה רקורסיבית אשר מקבלת מערך של מספרים שלמים וחיוביים ומחזירה
1 אם ניתן לחלק את כל המספרים לשתי קבוצות שהסכום הכולל שלהן שווה. אחרת הפונקציה
תחזיר 0.
יש לי רעיון והוא כך:
יש לסכום את כל האיברים שבמערך ולקבל את הסכום. לחלק אותו ב 2. ומה שצריך כעת זה למצוא האם י ש תת קבוצה במערך שמכסה את חצי מהסכום, אם כן אז יש חלוקה אחרת אין.
הבעיה היא כאן שוב שמותר לי להשתמש בפונקציית עזר אחת ללא שימוש בלולאות
וכאן אצטרך 2 פונקציות עזר. האחת שמחשבת תא הסכום של המערך (מה שנתון לי זה המערך והגודל שלו) והשניה שבודקת את היא מכסה את חצי הסכום.
האם למישהו יש כאן גם הצעה לפיתרון
תודה
|
| חזרה לתחילת העמוד |
|
| |
דוד
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 08 January 2009 בשעה 00:11 | | IP רשוּם
|
|
|
|
הנה פתרון רקורסיבי לשאלה הראשונה, אם לא הבנת משהו אני אסביר:
קוד:
public static int Solution(int[] Arr)
{
return Solution(Arr, 0, 0, 0);
}
public static int Solution(int[] Arr, int i, int Count, int Sum)
{
if (Arr.Length == 1) return 1;
if (i == Arr.Length -1) return Sum+1;
if (Arr[i + 1] > Arr[i]) Count++;
else Count = 0;
if (Count > Sum) Sum = Count;
i++;
return Solution(Arr, i, Count, Sum);
} |
|
|
|
| חזרה לתחילת העמוד |
|
| |
רקורסיה
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 08 January 2009 בשעה 08:24 | | IP רשוּם
|
|
|
|
קודם כל תודה על הפיתרון
רק שהוא לא נכון (כנראה לשא הבנת את הבעיה)
בכל זאת פתרתי את הבעיות
ברקרוסיה שלך אתה מוצא סידרה עולה רצופה הכי ארוכה בעוד שזה לא בהכרח
מה שחיפשו זה תת סדרה עולה לאו דווקא רצופה.
בכל מקרה,
תודה
|
| חזרה לתחילת העמוד |
|
| |
hadas
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 08 January 2009 בשעה 12:56 | | IP רשוּם
|
|
|
|
שלום,
יש לי שאלה:
התבקשתי לכתוב פונקצייה רקרוסיבית שמקבלת מחרוזת ומורידה מהמחרוזת תווים שחוזרים ומשאירה רק את ההופעה הראשונה שלהם.
כתבתי משהו אומנם רקרוסיבי אבל אני עדיים תקועה עם for
כך שכנראה אני צריכה לשנות קו מחשבה.
יש למישהו פיתרון???
|
| חזרה לתחילת העמוד |
|
| |
רקורסיה
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 08 January 2009 בשעה 14:42 | | IP רשוּם
|
|
|
|
אז ככה...
את צריכה לחשוב על כך
רורסיה שקולה ללולאה
ולכן אם ניתקעת עם לולאת for
תיצרי רקורסיה שפשוט מקדמת index כךשהו שמציין את ה index של הלולאה
|
| חזרה לתחילת העמוד |
|
| |
hadas
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 08 January 2009 בשעה 15:31 | | IP רשוּם
|
|
|
|
תודה על העצה:)
אמת שבדקתי שוב ומה שכתבתי לא מסתדר לי
יש לך משהו יותר ספציפי? כל דבר.. אני כבר על סף ייאוש
|
| חזרה לתחילת העמוד |
|
| |
דוד
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 08 January 2009 בשעה 15:44 | | IP רשוּם
|
|
|
|
מה הכוונה לאו דווקא רצופה? אתה יכול לתת דוגמה?
|
| חזרה לתחילת העמוד |
|
| |
רקוריסיה
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 08 January 2009 בשעה 19:08 | | IP רשוּם
|
|
|
|
hadas:
אני יול לתת לך רעיון
תחשבי על זה כך:
כאשר אני רואה תו בפעם הראשונה אני רוצה לשמור אותו
וכאשר אני רואה אותו שוב אני לא רוצהשהוא יוצג
לכן מה שניתן לעשות זה להעביר חתימה של הפונקציה מערך שיקרא result
וכמובן שיש את מערך המקור שמכיל את התווים המקוריים נגיד source.
אז אם source={a,a,a,b,b,a,s,s,a,s}
אזי כאשר אני הראה את התו הראשון ב source אני אבדוק אם הוא נימצא ב result כמובן שהוא לא נמצא אזי אני אעתיק אותו ואמשיך רקורסיבית על שאר המערך.
כמובן שאני אגיע לתו השני ב source וכאשר אני אראה שוב a אני אבדוק אם הוא נימצא ב result וכעת הוא ימצא אזי אני אמשיך רקורסיבית על שאר המערך ולא אכני ס אותו ל result ככה באופן הזה כל מה שיחזור יותר מפעם אחת לא יכנס למערך התוצאה result
מקווה שזה יעזור.
לדוד:
ניקח את המערך הבא
{1,34,3,7,45,5,9}
תת הסדרה הרצופה הארוכה ביותר הוא 1,3,7,9
|
| חזרה לתחילת העמוד |
|
| |
עופר
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 11 January 2009 בשעה 19:27 | | IP רשוּם
|
|
|
|
רקורסיה כתב:
אני צריך לכתוב תוכנית רקורסיבית אשר מקבלת מערך של המספרים שלמים ומחזירה את האורך של התת סדרה העולה הכי ארוכה במערך.
יש לי רעיון והוא כך
f(i)- מוגדר להיות תת הסדרה הארוכה ביותר עד האיבר i
f(1)=1
f(i+1)=max{f(j)|1=<j=<i and A[j]<=A[i+1]}
העניין הוא שאני מוגבל בצורה הבאה:
אסור לי להשתמש בלולאות וכן אסור לי להשתמש בפונקציות עזר.
וכאן בדיוק הבעיה
בשביל לפתור את זה אני אצטרך פונקציה רקורסיבית אחת שעוברת על איברי המערך וכן פונקציית עזר שמוצאת לי את המקסימום בין אברי f(j)
יש למישהו פתרון אחר? או כיצד לעשות זאת ללא פונקציית עזר?
|
|
|
כיצד עשית זאת בסופו של דבר?
|
| חזרה לתחילת העמוד |
|
| |
דוד
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 11 January 2009 בשעה 20:27 | | IP רשוּם
|
|
|
|
אני יודע שכבר פתרת את השאלה הראשונה, אבל יש לי רעיון נחמד-
להשתמש באלגוריתם הרקורסיבי שרשמתי למעלה, ולהוסיף לו מיון ללא לולאות (בדיקת הרצף תתחיל רק לאחר קבלת true על מערך ממויין)... אחרי שממיינים אפשר פשוט לבדוק איבר איבר משמאל לימין אם המיקום הקודם שלו במערך גדול מזה של האיבר שלפניו אך קטן מזה של האיבר שאחריו. למנות את הרצף הארוך ביותר שמקיים את התנאי הזה וקיבלנו תשובה! הבנת למה התכוונתי? נשמע הגיוני?
|
| חזרה לתחילת העמוד |
|
| |
אורח
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 12 January 2009 בשעה 07:12 | | IP רשוּם
|
|
|
|
יש פתרון לבעיה הראשונה?
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
מדעי המחשב
