פסקל, תרגילים קלים ברקורסיה

[idodo cohen]

פסקל, תרגילים קלים ברקורסיה

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

 

[freak2100]

בוא נתחיל

בלהמיר את הבעייה לבעייה טיפה יותר פשוטה. שים לב שבכל שורה מודפס מספר שונה של תווים. עכשיו, בהנתן מספר n ותו אתה יודע לעשות for ולהדפיס n תווים? אז זה החלק הפשוט. בשביל לפשט את הבעייה, נתעלם כרגע מההדפסה הזאת (שוב, כי היא טריוויטלית), ונדפיס בכל שורה רק את מספר התווים שצריכים להיות מודפסים בה. בדוגמה שלך: 3 2 1 2 3 ואם נסתכל על המקרה הכללי: n n-1 n-2 n-3 ... 1 ... n-3 n-2 n-1 n עד כאן מובן? יופי. עכשיו, שים לב שיש לך n, n-1, n-2 וכו'. זה כבר אמור לרמוז לך משהו לגבי הקריאה הרקורסיבית. שים לב שכל אחת מהשורות מודפסת פעמים, חוץ מהשורה האמצעית, 1, שמודפסת פעם אחת. במה נבדל 1 מכל שאר השורות? עכשיו תנסה לחשוב על זה שכל שלב של הקריאה הרקורסיבית מכיר רק מספר אחד. השלב הראשון מכיר רק את המספר n, למשל. זה אומר שהשורה שבה כתוב המספר n חייבת להיות מודפסת בתוך השגרה הזאת. איך תעשה את זה? תנסה לחשוב על מה שכתבתי. אם אתה עדיין מסתבך, ננסה לתת לך עוד רמזים. בסך הכל לתת לך פתרון זה פשוט, אבל המטרה היא שתנסה לפתח אותו בעצמך ותבין מאיפה זה הגיע

 

[asm32]

הפיתרון שלי

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

void f1(char c,int n) { static int original_num=0; int i; if(original_num==0) original_num=n; for(i=0;i<n;i++) printf("%c",c); printf("\n"); if(n!=1) f1(c,n-1); if(n!=original_num) { for(i=0;i<(n+1);i++) printf("%c",c); printf("\n"); } }​

 

[asm32]

במחשבה שניה

אין צורך במשתנים סטטים

void f1(char c,int n) { int i; for(i=0;i<n;i++) printf("%c",c); printf("\n"); if(n!=1) { f1(c,n-1); for(i=0;i<n;i++) printf("%c",c); printf("\n"); } }​

 

[freak2100]

לא יודע למה הסתבכת ככה, אבל

למה, לכל הרוחות, אם אתה מגדיר משתנה סטטי, אתה מגדיר אותו ל0 ואז בודק אם הוא שווה לאפס - ומאתחל אותו להיות n? לא יותר פשוט ליצור אותו כשהוא מאותחל לn? לא יותר הגיוני וסביר?

 

[asm32]

../images/Emo6.gif

 

[idodo cohen]

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

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

תודה על העזרה

 

[freak2100]

הוא טוב לשני דברים

יש דברים שפשוט יותר קל לעשות בצורה רקורסיבית, למשל סדרת פיבונאצי', שזאת הדוגמה הקלאסית סידרת פיבונאצי' היא הסדרה:

1, 1, 2, 3, 5, 8, 13, ...​

ז"א ששני האיברים הראשונים הם 1, וכל איבר הוא סכום של שני האיברים הקודמים בסדרה. שים לב שנורא קל לנסח את זה כמשוואה רקורסיבית:

fib = fib(n-1) + fib(n-2)​

עבור כל n>1. עבור n=0 וn=1, הפונרציה צריכה להחזיר 1 (אם מתייחסית ל0 כאל המספר הראשון בסדרה, כמובן). לכן, ברקורסיה הפונקציה תהיה מהמבנה הבא:

fib { if (n < 1) return 1; else return fib(n-1) + fib(n-2); }​

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

fib{ current_num = 1; last_num = 1; current_i = 1; if (n<1) return 1; else { while (current_i<n){ current_i++; current_num = current_num + last_num; last_num = current_num - last_num; } return current_num; } }​

משהו כזה... טיפה יותר מסובך, לא ככה?

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

 

[freak2100]

הפונקציה* מתייחסים*

 

[vinney]

הוספתי את התשובה שלך לשאלות נפוצות

תודה!

 

[freak2100]

../images/Emo6.gif

תודה

לא יודע עד כמה התשובה שלי כללית, מדוייקת וממצה, אבל...

 

[freak2100]

רק משהו אחד...

שים לב שבFAQ ההזחה של הקוד נדפקה... זה די גרוע בהתחשב בעובדה שזה פורום מדעי המחשב פה

אם יש לך זמן... תנסה לסדר את זה, לדעתי להחליף את הרווחים ב&nbsp; יעבוד, ואם לא אפשר להוסיף "תו שקוף" בין רווח לרווח. אבל רק אם יש לך זמן

 

[vinney]

אי אפשר לערוך את זה

זה לוקח את ההודעה כמו שזה...

 

[freak2100]

לונורא....

חבל שתפוז, שזאת כזאת מערכת גדולה ומתקדמת, דווקא לא משוכללת במיוחד ולא מכילה פיצ'רים קטנים אך חשובים כמו זה... או לפחות אם הם היו קובעים פורמט אחיד, ככה שגם ב"תצוגה מקדימה", גם בFAQ וגם על גבי הפורום ההודעה הייתה נראית בדיוק אותו דבר... אבל מילא.

 

[vinney]

המם.... הם משתפרים לאט לאט../images/Emo13.gif

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

 

[freak2100]

כן, זה באמת לאט...

תפוז לא קיימים כבר איזה 10 שנים?

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

 

[jan777]

אתה ניגש לשתי יחידות עיצוב תכנה השנה?

אם כן גם אני. הגעתם כ"כ מהר לרקורסיה? המורה שלך לא שבתה?

 

[idodo cohen]

או, שבתה בהחלט.

ובכל זאת מתקדמת בקצב רצחני. שוכחת שאנחנו לומדים *עוד* מקצועות. וחושבת שזה בסדר. יש לי ברירה? דווקא פרולוג נראה לי די מגניב. נחכה ונראהP:

 

[jan777]

אצלנו דווקא לא

אנחנו בדיוק סיימנו טנ"מ רשימה. יש לנו 6 שעות שבועיות כמה לכם?

 

[rm331]

אם כבר פתחתם אשכול על זה, אשמח לעזרה ברקורסיה

נתונה הסידרה ...0,1,1,2,5,29 בסידרה זו האיבר הראשון 0 והאיבר השני 1, וכל איבר אחר בסידרה הוא סכום ריבועי שני האיברים שלפניו. א)כתוב פונקציה רקורסיבית המקבלת מספר סידורי של איבר, ומחזירה את ערכו ב)כתוב פונקציה רקורסיבית המקבלת מספר סידורי n , ומחזירה את סכום n האיברים הראשונים בסידרה. אשמח לקבל עזרה/הדרכה/פתרון אלגוריתמי/פקסל אגב, אני חדש פה בפורום ואשמח נורא מעכשיו לכתוב פה קבוע ולנסות לעזור גם כן... תודה