09-10-2006, 21:18
|
|
|
חבר מתאריך: 11.11.05
הודעות: 66
|
|
שאלה מעניינת ולא קלה במדעי המחשב
המטרה היא לכתוב תוכנית אשר קולטת מספרים עד שנקלט 1- ולהדפיס את המספרים שמעל לממוצע הסופי.
אסור להשתמש במערכים, רשימה,מחסנית\ערימה ולא תור ובכלל ללא הקצאות דינאמיות למיניהן כלומר רק משתנים. קולטים את המספרים אחד אחד.
האם הבעיה בכלל ניתנת לפתרון? אם כן אז תנסו למצוא אותו(אני אישית לא מצאתי) ואם לא אז אם אפשר תוכיחו מתמטית ולא ישר להגיד שאין לזה פתרון.
אני חושב שניתן ישר לשלול את הפתרון הרקורסיבי מכיוון שיש כאן שימוש במחסנית הקריאות.
והפתרון אמור להתבצע ב CONSTANT SPACE כלומר O(1)
אני אתן דוגמא:
אם נקלט 1-,1,2,3,4,5,6,7,8
אז יודפס 6,7,8 כי רק הם מעל הממוצע שהוא 5("מינוס אחד" לא נכלל בממוצע!).
תנסו
שאלתי את זה בכמה מקומות אבל לא מצאתי תשובה אולי אתם תוכלו למצוא.
_____________________________________
חתימתכם הוסרה כיוון שלא עמדה בחוקי האתר. לפרטים נוספים לחצו כאן. תוכלו לקבל עזרה להתאמת החתימה לחוקים בפורום חתימות וצלמיות.
|