שאלות דוגמה לתחרויות אזוריות

התחרויות האזוריות

· שאלון תחרויות אזוריות 2003

· שאלון תחרויות אזוריות 2006

שאלות תרגול

שאלה 1

א. כתוב תכנית שהקלט שלה הוא סדרה של תווים מן ה- abc המסתיימת בנקודה ('.'), והפלט שלה הוא מספר התת-סדרות (של תווים רצופים) המתחילות ב- a, מסתיימות ב- b, ולא כוללות אף c.
שים לב שאין הנחה מגבילה על אורך הסדרה. ייתכן ואורכה רב (למשל, 10,000,000), ולכן יש לקלוט את התווים אחד-אחד ולא ניתן להניח שאפשר לשמור בו-זמנית את כל הסדרה בזיכרון המחשב.
דוגמה: עבור הקלט dsacbsabxbxxa. יהיה הפלט 2 (התת-סדרות: ab, abxb).

ב. כתוב תכנית שהקלט שלה הוא כבסעיף-א, והפלט שלה הוא מספר התת-סדרות (של תווים רצופים) שכוללות בדיוק c אחד (ועשויות להתחיל ולהסתיים בכל תו שהוא, לאו דווקא a או b).

שאלה 2

א. כתוב תכנית שהקלט שלה הוא סדרה של מספרים שלמים חיוביים, אשר מסתיימת ב-1 ומתארת נקודות גובה על קו רכס, והפלט שלה הוא מספר המכתשים בקו הרכס. מכתש הינו קו אופקי המחבר שתיים או יותר נקודות בעלות גובה זהה, אשר נמוך מן הנקודות שלפניו ואחריו (מיד לפני הקו ומיד אחרי הקו האופקי). שים לב שאין הנחה מגבילה על אורך הקלט. ייתכן ולא ניתן לשמור את כולו בו-זמנית בזיכרון המחשב.
דוגמה: עבור הקלט 123 235 235 112 120 115 115 115 129. יהיה הפלט 1 (מכתש שגובהו 115).

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

שאלה 3

מעוניינים לרצף פס רצפה באורך n באמצעות אריחים משלושה סוגים - אריחים באורך a, אריחים באורך b ואריחים באורך c. כתוב תכנית שהקלט שלה הוא ארבעה מספרים שלמים חיוביים קטנים מ- 1000 המבטאים את האורכים ,b ,a ,n c, והפלט שלה הוא מספר הדרכים השונות לביצוע הריצוף (שים לב שיתכן והפלט יהיה 0).
דוגמאות: עבור הקלט 10 9 2 4 יהיה הפלט 3 (אפשר 2-2-2-2-2 או 4-2-2-2 או 4-4-2; אי-אפשר להשתמש באריח שאורכו 9), ועבור הקלט 10 9 3 6 יהיה הפלט 0.

שאלה 4

נתונות n תכניות זהות אשר יש להריץ. לצורך ההרצה ניתן להשתמש ב-mאו פחות מחשבים נתונים, שמהירויותיהם להרצת תכנית שונות, וניתן להפעילם במקביל. כתוב תכנית שהקלט שלה הוא הגודל n, הגודל m והמהירויות של m המחשבים, כאשר מהירויות המחשבים הן מספרים ממשיים חיוביים קטנים מ- 1000, והפלט שלה הוא הזמן המינימלי לסיום הרצת כל התכניות (שים לב שאין הכרח להשתמש בכל המחשבים).
דוגמה: עבור הקלט 3 (מספר התכניות) 3 (מספר המחשבים) 11.0 7.0 5.0 (מהירויות המחשבים להרצת תכנית) יהיה הפלט 10.0 כיון שניתן להריץ שתי תכניות (אחת אחרי השניה) על המחשב שמהירותו 5.0 (ולסיימן בזמן 10.0) ותכנית נוספת על המחשב שמהירותו 7.0 (ולסיימה בזמן 7.0), ואין להשתמש במעבד שמהירותו 11.0.

שאלה 5

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

שאלה 6

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

שאלה 7

כתוב תכנית אשר מקבלת כקלט רשימה של N מספרים כלשהם (חיוביים ושליליים), והפלט שלה הוא סכום התת-סדרה שערכה הוא הגדול ביותר. על התכנית להיות נכונה ויעילה הן מבחינת זמן ביצוע והן מבחינת מקום בזיכרון. אין להניח מגבלת גודל על N.
דוגמה: עבור הקלט 17- 16 5 10- 1 2 יהיה הפלט 21.

שאלה 8

כתוב תכנית אשר מקבלת כקלט רשימה של N זוגות מספרים שלמים חיוביים, אשר כל אחד מציין זמן התחלה ומשך ריצה של ג'וב במחשב, והפלט שלה הוא מספר הג'ובים המרבי שניתן להריץ כך שלא יהיו שני ג'ובים המורצים בו-זמנית. הנח ש-N קטן מ-1000.
דוגמה: עבור הקלט 7 4 3 1 5 2 יהיה הפלט 2.

שאלה 9

כתוב תכנית אשר מקבלת כקלט רשימה של N זוגות מספרים שלמים חיוביים, אשר כל אחד מציין שנת תחילת עבודה ושנת סיום עבודה של פרשן תנ"ך, והפלט שלה הוא שנה בה פעל מספר מרבי של פרשני תנ"ך. הנח ש-N קטן מ-1000. (במידה וישנה יותר משנה אחת כזו, מספיק להציג אחת.)
דוגמה: עבור הקלט 7 4 9 1 5 2 יהיה הפלט 4 (גם 5 אפשרי כפלט).

שאלה 10

כתוב תכנית אשר מקבלת כקלט רשימה של N מספרים שלמים חיוביים קטנים מ-100, אשר כל אחד מבטא אורך של קופסא, והפלט שלה הוא מספר זוגות הקופסאות המרבי שניתן ליצור כך שגודל כל זוג (שהוא סכום גדלי שתי הקופסאות המחוברות) יהיה 100 או יותר. (ניתן להשתמש בכל קופסא לכל היותר לחיבור אחד.) הנח ש-N קטן
מ- 1000.
דוגמה: עבור הקלט 60 26 17 72 75 39 יהיה הפלט 2.