רוטר - לא מצליח לפתור תרגיל בעזרת שיטת ההפרד ומשול ברקורסיה

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"לא מצליח לפתור תרגיל בעזרת שיטת ההפרד ומשול ברקורסיה"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #15771	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 15771

Ice_Man
חבר מתאריך 14.11.05
1161 הודעות

22:37 18.03.10

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

שאלה 1,ג
בעיקרון זה הפיתרון אבל אין לי מושג איך לכתוב אותו:
כדי למצוא את המקסימלי מצד ימין, אתה קורא קריאה רקורסיבית, כשהאינדקסים שאתה שולח בתור ראשון ואחרון, הם האינדקס של mid+1 והאינדקס שקיבלת כאחרון
כדי למצוא את המקסימלי מצד שמאל, אתה קורא קריאה רקורסיבית, כשהאינדקסים שאתה שולח בתור ראשון ואחרון, הם האינדקס של שקיבלת כראשון ו mid
ואז יש לך שני ערכים - מה שיזר משמאל, ומה שחזר מימין.
אתה צריך להחזיר את הגדול מביניהם.
אם מישהו יכול לרשום לי בפסודו קוד או ב java את הפיתרון אשמח
וכאן רק צריך שמישהו יסביר, מה זה אומר a
אפשר דוגמא של מערך שיכול להיות, אני לא מבין מה אני צריך לחשוב אם אפשר או אי אפשר.. תודה..

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
מכתב	ronen333	19.03.10 01:00	1
תודה אבל אני לא מבין משהו	Ice_Man	19.03.10 19:51	2
חחח כן סליחה	ronen333	19.03.10 21:17	3
ואתה בטוח שאין לך עוד טעות	Ice_Man	19.03.10 21:40	4
ועוד שאלה	Ice_Man	19.03.10 22:27	5
הראתי לך את הנוסחא הרקורסיבית והסיבוכיות שלה	ronen333	20.03.10 11:37	6
די בטוח	ronen333	20.03.10 11:40	7
תודה וזה טוב גם למערך של מספר זוגי של מספרים ?	Ice_Man	20.03.10 13:59	8
כן זה עדיין יעבוד. תבדוק בעצמך	ronen333	20.03.10 15:13	10
אחלה אחי, עשיתי הרצה על דף מספר זוגי של איברים וזה נראה	Ice_Man	20.03.10 14:24	9
זה בדיוק אותו הדבר, זה זמן ריצה קבוע	ronen333	20.03.10 15:16	11
יאלה ננצל אותך עוד טיפה, באמת טיפה אבל	Ice_Man	20.03.10 16:52	12
מיון מיזוג הוא היחיד שלא ריבועי מביניהם	ronen333	20.03.10 17:46	13

ronen333
חבר מתאריך 20.2.03
6069 הודעות

01:00 19.03.10

1. מכתב
בתגובה להודעה מספר 0

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

MAX(A,p,r)
if(r=p)
return a
mid:=(p+r)/2
temp1:= max(A,mid+1,r)
temp2:= max(A,p,mid)
if(temp1>temp2)
return temp1;
else
return temp2;

מה ז"א "מה זה אומר a" , a זה המערך שלך...
נוסחת הנסיגה היא:

T(N)=2T(N/2)+1

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice_Man
חבר מתאריך 14.11.05
1161 הודעות

19:51 19.03.10

2. תודה אבל אני לא מבין משהו
בתגובה להודעה מספר 1

בקוד הראשון מה זה הa הזה פתאום ? מה זה אומר ?
ושרשמת
temp1:= max(A,mid+1,r)
temp2:= max(A,p,mid)
התכוונת אני מניח ל
temp1:= MAX(A,mid+1,r)
temp2:= MAX(A,p,mid)
?

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

21:17 19.03.10

3. חחח כן סליחה
בתגובה להודעה מספר 2

לא שמתי לב שלא הייתי CASE SENSTIVITY... . ועוד תיקון
בהחזרה זה אמור להיות

if(p==r)
return a[p]

בדיוק אותו תנאי כמו בפסודו קוד שרשמו לך בשאלה.
הa זה המערך שלך...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice_Man
חבר מתאריך 14.11.05
1161 הודעות

21:40 19.03.10

4. ואתה בטוח שאין לך עוד טעות
בתגובה להודעה מספר 3

בתוך ה temp1 וה temp2 ? אוליmid-1 או משהו כזה איפהשהו ?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice_Man
חבר מתאריך 14.11.05
1161 הודעות

22:27 19.03.10

5. ועוד שאלה
בתגובה להודעה מספר 4

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

11:37 20.03.10

6. הראתי לך את הנוסחא הרקורסיבית והסיבוכיות שלה
בתגובה להודעה מספר 5

ערכתי לאחרונה בתאריך 20.03.10 בשעה 11:42 בברכה, ronen333

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

11:40 20.03.10

7. די בטוח
בתגובה להודעה מספר 4

אומנם רשמתי את זה בשעה מאוחרת, אבל אני די בטוח שזה עובד.. לא הרצתי את זה אבל אינטואיטיבית זה נראה לי הפתרון.
וזה לא MID-1 בגלל שבאז אתה מפספס איבר בכל בדיקה שלך.
הרי אם זה המערך שלך
0,1,2,3,4,5,6
אז אתה רוצה זה יפתור את התת בעיה בין 0 ל3, 4 ל6. וכך הלאה..

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice_Man
חבר מתאריך 14.11.05
1161 הודעות

13:59 20.03.10

8. תודה וזה טוב גם למערך של מספר זוגי של מספרים ?
בתגובה להודעה מספר 7

כמו 0,1,2,3,4,5 ?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

15:13 20.03.10

10. כן זה עדיין יעבוד. תבדוק בעצמך
בתגובה להודעה מספר 8

5/2=2
אז זה ירוץ מ0 עד 2 ומ3 עד 5.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice_Man
חבר מתאריך 14.11.05
1161 הודעות

14:24 20.03.10

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

ערכתי לאחרונה בתאריך 20.03.10 בשעה 14:32 בברכה, Ice_Man

בסדר. רק עוד דבר אחד
רשמת סיבוכיות זמן:
T(N)=2T(N/2)+1
אני חושב שזה
T(N)=2T(N/2)+4
או
T(N)=2T(N/2)+5
תלא מסכים ?
עוברים על שתי השורות הראשונות תמיד
וגם על השתי שורות לפני אחרונות או שתי שורות אחרונות

חוץ מזה המון תודה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

15:16 20.03.10

11. זה בדיוק אותו הדבר, זה זמן ריצה קבוע
בתגובה להודעה מספר 9

שלא תלוי בN.
אם אתה רוצה להיות מדויק אז צריך להיות רשום:

T(N)=2T(N/2)+Θ(1)

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice_Man
חבר מתאריך 14.11.05
1161 הודעות

16:52 20.03.10

12. יאלה ננצל אותך עוד טיפה, באמת טיפה אבל
בתגובה להודעה מספר 11

יש לך מערך כזה:
7,6,30,20,90,80
איזה מיון יהיה הכי יעיל עבורו. merge, bubble או insertion ?

merge באני דיי בטוח שלא,
לדעתי insertion
מה אתה חושב ?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

17:46 20.03.10

13. מיון מיזוג הוא היחיד שלא ריבועי מביניהם
בתגובה להודעה מספר 12

סיבוכיות זמן הריצה של MERGE SORT הוא NLOGN ,ואילו השאר יבצעו N^2 איטרציות.
כמובן שמדובר על המקרה הגרוע ביותר- ככה שיכול להיות בתכל'ס שבמערך הספציפי שהבאת הוא יהיה יותר מהיר עבור מיון אחר (נגיד BUBBLE SORT משופר).
אבל לא כזה סביר..
תעשה כל אחד מהמיונים ותראה כמה איטרציות לוקחות לו לסדר את המערך.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד