שאלה ברקורסיה בC

[1ca1]

שאלה ברקורסיה בC

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

 

[Zack DA]

קרא על BFS ועל מימושים שלו....

 

[אופסשםמשתמש]

מממ אני חושב BACKTRACKING

אני לא יודע מה ההגבלות שלך, וקרוב לוודאי שאנשים הרבה יותר מבינים ממני ימצאו דרכים יותר טובות... אבל בכל זאת אני אנסה.. לי זה נראה כמו BACKTRACKING.. אתה לוקח את מה שכבר עשית ומוסיף לפונ' הרקורסיבית עוד פרמטר=אורך הדרך. ועוד פרמטר שהוא מצביע למשתנה (כדי שתוכל לשנות אותו) או שהוא משתנה גלובלי...המשתנה הזה זה אורך הדרך הכי קצרה שמצאת בנתיים, תאתחל אותו לintmax עכשיו אתה הולך וכל פעם מעביר לעצמך לפונ' ברקורסיה את הערך של כמה כבר אורך הדרך שעברת, וכמובן לא שוכח לעדכן את האורך אחרי כל צעד.. כל כניסה אתה בודק אם האורך גדול מהדרך הכי קצרה שמצאת עד עכשיו, אם כן, אז מיותר לבדוק את ההמשך הדרך לא תתקצר... פה הקטע של הBackTracking אז הרקורסיה תחזור פעם אחת אחורה בעץ ותנסה כיוון אחר, אם סיימת בהצלחה.. ז"א שהרקורסיה מצאה דרך יותר קצרה (אחרת היא לא היתה מסיימת אלא חוזרת אחורה על פי הסעיף הקודם), אז אתה מעדכן את הפרמטר השני שמציין את אורך הדרך הכי קצרה שמצאת עד עכשיו.. אם קראת עד לפה אז : 1. כל הכבוד 2. מקווה שהבנת תקנו אותי אם אני טועה/לא ברור

 

[1ca1]

תודה אך לא ממש הבנתי

אני צריך את הדבר הכי נאיבי ופשוט, אני לא נבחן על יעילות או סיבוכיות ושטויות כאלה, רק לכתוב משהו שעובד, חיפשתי BFS,DFS לא ממש הבנתי... בקיצור נחזור על הבעיה, מטריצה 5X5, הולכים מ(0,0) עד (4,4), כל תא במטריצה מכיל את ה"משקל" שלו, מחפשים דרך קצרה ביותר מבחינת סכום ה"משקלים", עדיפות לפתרון רקורסיבי... אם תוכלו אולי לצרף דוגמא לדברים שאתם מדברים עליהם, כי אני ממש לא מבין בחיפושים וכאלה... (לא למדתי עדיין את הקורס באלגוריתמים וכאלה...)

 

[אופסשםמשתמש]

הריי

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

 

[1ca1]

תשמע מה עשיתי

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

 

[אופסשםמשתמש]

OK זה פשוט

אני מניח שהפונ' שלך לא עוברת על אותה נק' פעמיים כי אחרת היא נתקעת על לולאה אינסופית. עכשיו, אתה מגדיר עוד משתנה גלובלי, ואתה קורא לו MinWay ונותן לו לפני הפונקציה ערך 24321 זה ערך נורא חשוב, זה כביכול הדרך הכי קצרה שמצאת עד עכשיו. עכשיו, לפונ' שכבר כתבת יש חתימה, אז לחתימה שלה אתה מוסיף משתנה נורא נורא חשוב: Way ופעם ראשונה שאתה קורא לפונ' אתה שם במשתנה הזה ערך 0. בכניסה לפונ' אתה מוסיף את הערך של המשבצת למשתנה החשוב WAY... אם הגעת עד הלום זה טוב, עכשיו לחלק הקשה. בסוף הדרך, במקום שאתה רוצה להוסיף אחד לכמות הדרכים שמצאת, אתה בודק אם WAY קטן מMINWAY אם כן אתה משנה אותו.. אם לא אז לא... אם לא הבנת, אני מתאבד

 

[1ca1]

סבבה תודה...

ד"א מה זאת חתימה של פונקציה? אף פעם לא נתקלתי במושג הזה, האם אתה מתכוון לאבטיפוס? prototype?

 

[אופסשםמשתמש]

כן, אצלינו קוראים לזה חתימה ../images/Emo4.gif

למרות שגם אני התרגיל לביטוי protoType

 

[טיקטי1]

את השאלה הראשונה אתה יכול

לפתור עם נוסחה כי יש לך 8 צעדים 4 מהם חייבים להיות למטה 4 מהם חייבים להיות שמאלה