שאלה קטנה ברקורסיה

[elixvx]

תרגילל קטן שנתקעתי בוא ואני לא מצליח לעשות. (בC#)

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

בקיצור 2 האיברים הכי קטנים.

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

תודה לעוזרים

[opbenesh]

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

תוכל לבחור מתוכם בקלות את השניים הכי קטנים בכל המערך.

תחשוב על איך זה מתורגם לרקורסיה, ומשם המימוש יהיה קל מאוד (:

בהצלחה!

[שניצל]

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

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

[steelmanx]

אפשר גם להחזיר Tuple.

[APPC]

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

תוכל לבחור מתוכם בקלות את השניים הכי קטנים בכל המערך.

תחשוב על איך זה מתורגם לרקורסיה, ומשם המימוש יהיה קל מאוד (:

בהצלחה!

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

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

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

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

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

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

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

לדוגמה: אם הערך הנמוך ביותר הוא 20, וזה שאחריו הוא 37, אפשר להחזיר משתנה מספרי אחד שמכיל: 20.37.

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

מקווה שעזרתי.

[שניצל]

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

לדוגמה: אם הערך הנמוך ביותר הוא 20, וזה שאחריו הוא 37, אפשר להחזיר משתנה מספרי אחד שמכיל: 20.37.

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

איכסאיכסאיכסאיכס

כבר עדיף להגדיר struct ולהחזיר אותו. או כמו שנאמר כאן להחזיר Tuple (שזה בדיוק struct שכזה), טיפוס שקיים החל מדוטנט 4.

[APPC]

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

[elixvx]

תודה על העזרה, לצערי ני לא מכיר משתנה מסוג Tuple. סה"כ אני לומד לבגרות של מדעי המחשב ב'.

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

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

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

היא בכלל לא רקרוסיבית.

כמו שאמרתי ערך אחד זה לא בעיה. (ככה עשיתי)

public static int Check (int[] arr, int len) { if (len = = 0) return arr[0] ; return math.min( arr[len], Check(arr, len-1)) 

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

הבעיה היא שוב מציאת 2 הערכים בריצה אחת.

מצטער אם לא הבנתי אתכם נכון.

[steelmanx]

אתה צריך להחזיר int[]

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

[שניצל]

כאמור מעליי, תתחיל מלהחזיר []int ולא סתם int.

הרעיון בפתרון בעיות ברקורסיה הוא "wishful thinking". תחשוב שהאלגוריתם יעבוד נכון על מערך קטן יותר, דהיינו תחשוב ב-(Check(arr,len-1 תחזיר את שני האיברים הקטנים ביותר מבין len-1 האיברים הראשונים. עכשיו אתה צריך להחזיר מערך שמכיל את שני האיברים הקטנים ביותר מבין האיברים האלה והאיבר האחרון.

[elixvx]

חח אני יודע שני צריך להחזיר int[] (כתבתי את זה גם בהודעה הקודמת)

הדוגמא שננתי היא לרקורסיה שמחזירה רק את האיבר הכי קטן, בלי הבא אחריו.

כנראה לא הבנתם אותי.

עעדיין לא הבנתי איך אני מחזיר את 2 הכי קטנים.

מה יהיה תנאי העצירה?

(כיאלו לקבל את הכי קטן ואז לשלוח שוב את המערך ללא איבר זה? זה לא חוכמה..)

[noodle]

אני אנסה לכוון אותך.

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

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

[elixvx]

טוב זה בערך הפתרון שחשבתי עליו:

הפעולה פשוט כל פעם תשווה את האיבר האחרון במערך לאיבר הראשון

אם הוא קטן ממנו היא תחליף ביניהם אם לא היא תשווה אותו לאיבר השני ותחליף בניהים אם הוא קטן יותר.

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

ושוב נשלח את הפעולה.

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

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

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

הנה מה שכתבתי ( קצן מבולגן לא היה לי כוח להשקיע יותר מידי):

http://img535.imageshack.us/img535/1892/20120513220607611.jpg

מקווה שמובן.

האם זה נכון?

[שניצל]

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

[elixvx]

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

כן חשבתי על זה אח"כ.

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

נראה לי. אני אחשוב על זה יותר לעומק מחר אחרי הבגרות באנגלית.