שתי שאלות בשפת C

[shinshin]

../images/Emo13.gifשתי שאלות בשפת C

אני תלמיד תיכון הלומד במגמת מחשבים. כחלק מעבודות הבית הניתנות לנו קיבלתי 2 שאלות שרציתי לדעת אם למישהו יש רעיון בנוגע לפיתרונן (הפתרון לשאלה הראשונה צריך להעשות ברקורסיה והפתרון השני - ניתן לפתור בכל דרך) 1) עכבר צריך להגיע מהנקודה השמאלית-עליונה ביותר בלוח של 100X100 לנקודה התחתונה-ימנית ביותר באותו לוח ע"י תזוזה אך ורק ימינה ולמטה. כלומר הוא יכול לזוז שתי משבצות ימינה, אח"כ עד הסוף למטה ואת כל השאר ימינה. הוא יכול לעשות את כל הלוח בצורת "מדרגות" ימינה אחד למטה אחד ימינה אחד למטה אחד וכו´. השאלה היא: כמה מסלולים שונים אפשריים ע"פ נתוני שאלה זו לעכבר? 2) ישנו כספומט הנותן שטרות אך ורק של 20 ש"ח ושל 50 ש"ח. העקרון הוא לתת את מספר השטרות המינימלי תמיד. השאלה היא איך לבנות תוכנית שתבצע זאת בהתחשב בעובדה שהעדיפות משתנה. כלומר אם אדם דורש 140 ש"ח העדיפות היא לתת לו קודם כל שטרות של 50 ש"ח (שניים במקרה זה) ורק אז לפנות לאופציה היותר בשבזנית בכמות שטרות, כלומר לאופציה של נתינת שטרות של 20 ש"ח. לעומת זאת, אשם הדורש 130 ש"ח יאלץ לקבל 4 שטרות של 20 ש"ח ושטר אחד של 50 ש"ח, כלומר תנתן עדיפות למתן שטרות של 20 ש"ח, למרות שזה יותר "בזבזני" בכמות שטרות. אם כן מה עושים? אשמח לשמוע פתרונות כלליים או ממש בקוד תודה מראש ומקווה שהחידות יעניינו אתכם שינשין

 

[אלדד27]

טוב, רעיון לשאלה הראשונה.

יש לך 100 אפשרויות לצעד הראשון (ימינה). אחרי הצעד הראשון הזה, יש לך... X אפשרויות לזוז למטה (כמה אפשרויות? תחשוב), ואז יש לך Y אפשרויות ימינה וכן הלאה. תבדוק את התלות בין כל צעד לזה שאחריו, ותבין.

 

[jolp]

השאלה הראשונה..

מן הסתם, הפתרון מתאים יותר להיות רקורסיבי כפי שהמורה שלך ציינה. עליך לבנות פונקציה פשוטה (על-פי הערכתי לא יותר מ-15 שורות), המקבלת שני ערכי X ו- Y בהתאם למיקום הנוכחי בלוח ומחזירה ערך int בהתאם למספר המסלולים האפשריים מנקודה זו בהתאם לכללים (רק ימינה ולמטה). הפונקציה תחל בבדיקה למניעת חזרה אינסופית. זוהי- האם הגענו למיקום הרצוי: (100,100), אם כן עליה להחזיר אחד, שכן, מצאנו מסלול אפשרי. אחרת, על הפונקציה לבדוק באם X עדיין קטן מ- 100 (עדיף להשתמש בקבועים ולא לכתוב ערך מספרי). אם כן, היא תקרא לעצמה עבור X+1 ואותו ערך ה- Y ותוסיף את ערך החזרה למשתנה סכום כללי. בנוסף, על הפונקציה לבדוק באם Y עדיין קטן מ- 100. אם כן, היא תקרא לעצמה עבור אותו ערך ה- X ו- Y+1 ותוסיף את ערך החזרה למשתנה סכום כללי. על הפונקציה להחזיר את משתנה הסכום הכללי. זהו זה. התוכנית הראשית אמורה לקרוא לפונקציה עם הערכים (1,1). ההמלצה שלי היא לנסות את התוכנית שלך על לוח קטן יותר- נגיד 3x3 שבו קל יותר לחשב את מספר המסלולים האפשריים בכדי לבדוק את נכונות הערך המוחזר מן הפונקציה. בהצלחה!

 

[shinshin]

ומה לגבי השאלה השנייה?

 

[shinshin]

ותודה לשניים שענו!

 

[jolp]

יש לי שם!

 

[NightFears]

קוד

אני ממליץ לך לקרוא את הקוד ולנסות להבין שני דברים: 1. מדוע היא מהווה פטרון. 2. מדוע זאת הדרך הכי יעילה לפטור את הבעייה const int x_size = 100; const int y_size = 100; int calc_paths(int x, int y){ if( (x == x_size-1) || (y == y_size-1) ) return 1; return calc_paths(x+1, y) + calc_paths(x, y+1); } int start_calc(){ return calc_paths(0,0); }

 

[NightFears]

קוד - שאלה 2

int amount = ...; if( (amount%10) || (amount<40 && amount!=20) ) //error: wrong amount ; int fifties = amount / 50; int spare = amount % 50; if(spare % 20){ --fifties; spare += 50; } int twenties = spare / 20;

 

[nfnf]

פתרון 2

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