מציאת הספרה המקסימלית במספר - פתרון רקורסיבי

[Judas Iscariot]

שלומות,

אני זקוק לעזרה

ה"משימה":

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

הנה הפתרון שלי(בשפת בני אדם):

הפרד ממספר את ספרת האחדות שלו/פרק המספר עד הגיעך ל0.

אם הגעת ל0 אזי

0 <- מקסימום

אחרת

אם ספרת האחדות הנוכחית גדולה מן המקסימום אזי

הצב במקסימום את ספרת האחדות הנוכחית

מקסימום = מקסימום(ללא ספרת האחדות)

בפסקל:

Function FindMaxDigit(N:integer):integer;
Begin	
	If N = 0 Then
		FindMaxDigit := 0
	Else
		Begin
			If FindMaxDigit(N mod 10) > FindMaxDigit Then
				FindMaxDigit := FindMaxDigit(N mod 10);
			FindMaxDigit := FindMaxDigit(N div 10);
	    End;
End;{IfFivePresnet}

אז הנה איפה שאני צריך את עזרתכם תוכניתנים מוכשרים:

א. אני לא בטוח שהפיתרון("אלגוריתם") נכון

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

עזרה תתקבל בברכה

[k-o-b-y]

כי בהשוואה אתה משתמש ב FindMaxDigit בפעם השנייה כמו משתנה כשזו בעצם פונקציה. אתה לא יכול לעשות את זה. חוץ מזה יש לך יותר מדי קריאות לפונקציה. למה אתה שולח ל FindMaxDigit את N mod 10 שזו ספרת האחדות ולא את N div 10 שזה המספר בלי ספרת האחדות? ובמידה והתנאי מתקיים אתה צריך להחזיר את הספרה שקיבלת ולא לקרוא שוב לפונקציה.

תנסה את זה:

Function FindMaxDigit(N:integer):integer;
Var
	lastMax : Integer;
Begin	
	If N = 0 Then
		FindMaxDigit := 0
	Else
		Begin
			lastMax := FindMaxDigit(N div 10);
			If lastMax > (N mod 10) Then
				FindMaxDigit := lastMax
			Else
				FindMaxDigit := N mod 10;
	    End;
End;

[MalGano]

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

[שניצל]

huh?

אז מה אם המשתנה "משוכפל"? גם ככה זה זניח לעומת ה-overhead של הפונקציה עצמה.

[MalGano]

ואם יש לי הרבה משתנים? זה לא יעיל (לא שרקורסיה זה דבר יעיל בפני עצמו...).

[Niseg]

הפתרון של k-o-b-y נכון זה נראה כמו פסקל ולא השתמשתי בשפה הזאת איזה 15 שנה אבל קוד אני יכול לקרוא בכל שפה .

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

אין כלכך בעיה להגדיר משתנים בפונקציה רקורסיבית הכל תלוי בעיקר בדרך שמשתמשים בהם ובגודל שלהם. רקורסיה היא לרוב לא פתרון אידאלי למערכות שמוגבלות בזכרון. בכל מקרה אפשר לפתור את הבעיה הזאת בקלות בלי רקורסיה כי היא בעיה של חיפוש ליניארי על כל הערכים. בכל מקרה הבנתי שהמטלה הזאת נועדה ללמד אנשים איך משתמשים ברקורסיה והכלל הכי חשוב ברקורסיה הוא : התכנסות. לפונקציה תמיד יש בדיקה בהתחלה אם צריך להפסיק את הרקורסיה . במקרה של הבעיה הזאת הפסקת הרקורסיה קוראת מתי שהמספר שמעבירים לפונקציה הוא 0 שאומר שספרת ה 10 בחזקת m כשm הוא אורך הרקורסיה היא 0 שאומרת שעברנו את הספרה הmost sagnficant של המספר.

[TheReaper]

אני לא יודע לגבי רקורסיה ודברים כאלה אבל האלגוריתם די פשוט

בתוכנית הראשית-

לבדוק האם המספר הוא0

אם כן MAX=0

אם לא קרא לפונקציה findmax שמקבלת את המספר(נקרא לו N)

לפונקציה יש משתנה מקומי בשם NUM

שמים את N MOD 10 בNUM

שמים את N DIV 10 ב N

כל עוד N שונה מ0 בצע

אם N MOD 10 גדול מNUM

אזי השם בNUM את הספרה

השם ב N את N DIV 10

ולסיום

Findmax:=num

[k-o-b-y]

ואם יש לי הרבה משתנים? זה לא יעיל (לא שרקורסיה זה דבר יעיל בפני עצמו...).

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