בכיתה
בשיעורים הקודמים
1. מיון מערך בשיטת מיון-בחירה - Selection-sort
מיון זה מתבסס על בחירה (איתור) בכל שלב של הערך המינימלי מבין הערכים שעוד לא מוינו והעברתו
למקומו. בשלב הראשון יימצא המינימלי מבין הערכים בכל המערך ויושם בתא הראשון. בשלב השני יימצא
המינימלי מבין הערכים שנותרו, החל מן המקום המקום השני (כי הראשון כבר במקמו) והוא יושם בתא השני
וכך הלאה. בסוף התהליך כל איבר יהיה במקומו ויתקבל מערך ממוין.
מיון זה מתבסס על בחירה (איתור) בכל שלב של הערך המינימלי מבין הערכים שעוד לא מוינו והעברתו
למקומו. בשלב הראשון יימצא המינימלי מבין הערכים בכל המערך ויושם בתא הראשון. בשלב השני יימצא
המינימלי מבין הערכים שנותרו, החל מן המקום המקום השני (כי הראשון כבר במקמו) והוא יושם בתא השני
וכך הלאה. בסוף התהליך כל איבר יהיה במקומו ויתקבל מערך ממוין.
2. מיון מערך בשיטת מיון-בועות - Bubble-sort
מיון זה מתבסס על סריקת המערך והשוואה של כל זוג איברים צמודים. אם זוג איברים אינו מסודר בסדר
הרצוי יש להחליף ביניהם. מיון זה נקרא גם בשם מיון החלפת שכנים, כי מחליפים בין איברים שכנים
(צמודים). בסיום איטרציה אחת של הלולאה החיצונית מובטח כי הערך הגבוה ביותר נמצא בתא האחרון
במערך. בסיום האיטרציה השניה של הלולאה החיצונית מובטח כי הערך המהווה את סגנו של מקס יימצא
בתא הלפני אחרון במערך.
מיון זה מתבסס על סריקת המערך והשוואה של כל זוג איברים צמודים. אם זוג איברים אינו מסודר בסדר
הרצוי יש להחליף ביניהם. מיון זה נקרא גם בשם מיון החלפת שכנים, כי מחליפים בין איברים שכנים
(צמודים). בסיום איטרציה אחת של הלולאה החיצונית מובטח כי הערך הגבוה ביותר נמצא בתא האחרון
במערך. בסיום האיטרציה השניה של הלולאה החיצונית מובטח כי הערך המהווה את סגנו של מקס יימצא
בתא הלפני אחרון במערך.
3. מה הספקנו עד כה בנושא מערך
א. הגדרה - מהו מערך?
ב. הסבר מפורט - מערך מהו.
ג. שינוי גודל מערך, האם אפשרי?
ד. הגדרת גודל מערך באמצעות משתנה מספרי.
ה. כל איבר במערך כמשתנה עצמאי.
ו. התכונה Length.
ז. דוגמת מערך מחרוזתי.
ח. שיטות לאתחול מערך.
ט. הצהרה על משתנה מטיפוס מערך שלמים ויצירת מערך שלמים. מה ההבדל בין שני הדברים?
י. לולאה להדפסת איברי המערך.
יא. יצירת פעולה המקבלת מערך-שלמים ומדפיסה את איבריו.
ב. הסבר מפורט - מערך מהו.
ג. שינוי גודל מערך, האם אפשרי?
ד. הגדרת גודל מערך באמצעות משתנה מספרי.
ה. כל איבר במערך כמשתנה עצמאי.
ו. התכונה Length.
ז. דוגמת מערך מחרוזתי.
ח. שיטות לאתחול מערך.
ט. הצהרה על משתנה מטיפוס מערך שלמים ויצירת מערך שלמים. מה ההבדל בין שני הדברים?
י. לולאה להדפסת איברי המערך.
יא. יצירת פעולה המקבלת מערך-שלמים ומדפיסה את איבריו.
יב. לולאה לאתחול איברי המערך.
יג. לולאה לביצוע מניפולציה (שינוי ערך) על איברי המערך.
יד. קבלת מערך מפעולה.
יד. קבלת מערך מפעולה.
4. יעילות
א. הגדרה של יעילות אלגוריתמית
* יעילות אלגוריתמית מתייחסת לכמות צריכת המשאבים, ובפרט למשאב זמן ביצוע האלגוריתם.
* יעילות אלגוריתמית מתייחסת לכמות צריכת המשאבים, ובפרט למשאב זמן ביצוע האלגוריתם.
ב. מתי לא נידרש ליעילות אלגוריתמית
* נושא היעילות לא בהכרח חשוב כיום בעת תכנונם של יישומים רבים, וזאת כיוון שהמחשבים של היום
מהירים ביותר. מהירויות אלה ממשיכות לגדול.
* לא נידרש כמעט לנושא היעילות בעת כתיבת קוד של תרגילים בכיתה י', ולא בעת כתיבת
אפליקציות משרדיות ואחרות.
מהירים ביותר. מהירויות אלה ממשיכות לגדול.
* לא נידרש כמעט לנושא היעילות בעת כתיבת קוד של תרגילים בכיתה י', ולא בעת כתיבת
אפליקציות משרדיות ואחרות.
ג. האם יעילות של אלגוריתם צריכה עדיין להטריד אותנו?
* תשובה: יותר מתמיד!
* ככל שביצועי המחשבים גדולו, כך הדרישות שלנו מהם גדול עוד יותר.
* מחשבים מעבדים תמונות עם מיליוני פיקסלים לתמונה.
* למערכות של היום נדרשים זמני עיבוד ומהירות עיבוד פי אלפי מונים בהשוואה ליישומי מחשב מלפי
עשור ויותר.
* לחברות כמו Google ו- Facebook יש מיליוני לקוחות שכל אחד מהם מבצע מאות ואלפי פעולות.
חשוב שכל פעולה תתבצע במהירות האפשרית. חשבו על חיפוש בגוגל כמה חשוב שתתקבל תשובה
במהירות האפשרית.
עשור ויותר.
* לחברות כמו Google ו- Facebook יש מיליוני לקוחות שכל אחד מהם מבצע מאות ואלפי פעולות.
חשוב שכל פעולה תתבצע במהירות האפשרית. חשבו על חיפוש בגוגל כמה חשוב שתתקבל תשובה
במהירות האפשרית.
* דוגמאות למערכות נוספות הדורשות יעילותר בה: אלגוריתם חיפוש בגוגל, מערכות חיזוי מזג-אוויר,
מערכות בקרה על מסחר בבורסה, משחקי מחשב בעלי גרפיקה תלת-ממדית באיכויות ריאליסטיות
כולל עם אלפי אנשים המשחקים במקביל בזמן אמת (און-ליין), מערכות צבאיות (מטוסים, טילים...).
מערכות בקרה על מסחר בבורסה, משחקי מחשב בעלי גרפיקה תלת-ממדית באיכויות ריאליסטיות
כולל עם אלפי אנשים המשחקים במקביל בזמן אמת (און-ליין), מערכות צבאיות (מטוסים, טילים...).
ד. אודות אלגוריתמים יעילים
* אלגוריתם יעיל הינו אלגוריתם בעל זמן ריצה סביר.
* האם קיימות בעיות אלגוריתמיות שלהן אין אלגוריתם יעיל (בעיות שזמן פתרונן ארוך במידה לא
פרקטית)? התשובה היא שאכן כן. שאלת יעילותם של אלגוריתמים היא מרכזית, והקשר בינה לבין אופן
המימוש הנבחר הוא קשר מרכזי ומהווה רעיון חשוב בו נעסוק ביתר פירוט בעתיד.
פרקטית)? התשובה היא שאכן כן. שאלת יעילותם של אלגוריתמים היא מרכזית, והקשר בינה לבין אופן
המימוש הנבחר הוא קשר מרכזי ומהווה רעיון חשוב בו נעסוק ביתר פירוט בעתיד.
ה. פונקציית זמן ריצה של אלגוריתם לעומת סדר גודל זמן ריצה של אלגוריתם
* פונקציית זמן ריצה היא ביטוי אלגברי שמתאר את מספר יחידות הזמן שאורך האלגוריתם.
מדוע זה חשוב? כדי שנדע כמה זמן יידרש לביצוע הקוד.
מדוע זה חשוב? כדי שנדע כמה זמן יידרש לביצוע הקוד.
* פונקציית זמן ריצה מחושבת תמיד עבור המקרה הגרוע ביותר (Worst case), גם אם בדרך כלל
האלגוריתם מבצע את פעולתו בזמן ממוצע קצר יותר.
דוגמה-א - המקרה הטוב ביותר
אם אנו מחפשים מספר במערך שלמים, זמן הריצה יהיה קצר מאד אם הערך שאנו מחפשים נמצא בתא
הראשון במערך.
האלגוריתם מבצע את פעולתו בזמן ממוצע קצר יותר.
דוגמה-א - המקרה הטוב ביותר
אם אנו מחפשים מספר במערך שלמים, זמן הריצה יהיה קצר מאד אם הערך שאנו מחפשים נמצא בתא
הראשון במערך.
דוגמה-ב - זמן ממוצע
פונקציית זמן הריצה תתבסס על n/2 אם הערך אותו אנו מחפשים נמצא איפשהו באמצע המערך.
דוגמה-ג - המקרה הגרוע ביותר
זמן הריצה יהיה n אם הערך נמצא בתא האחרון במערך או שהערך לא נמצא במערך (גם במקרה זה
צריך לעבור על כל תאי המערך בטרם ייקבע כי הערך לא נמצא בו).
מהו הגורם העיקרי לקביעת סדר הגודל של זמן הריצה?
בדוגמה זו, של חיפוש האם ערך קיים במערך, פונקציית זמן הריצה תהיה תלויה בעיקרה באורך
המערך.
צריך לעבור על כל תאי המערך בטרם ייקבע כי הערך לא נמצא בו).
מהו הגורם העיקרי לקביעת סדר הגודל של זמן הריצה?
בדוגמה זו, של חיפוש האם ערך קיים במערך, פונקציית זמן הריצה תהיה תלויה בעיקרה באורך
המערך.
פונקציית זמן ריצה נוסחה מדויקת ומפורטת, אך אנו מעוניינים השנה לדעת אך ורק מהו סדר הגודל
הכללי של הזמן הדרוש לריצת האלגוריתם. ומכיוון שהגורם העיקרי לקביעת זמן זה הינו אורך המערך,
הכללי של הזמן הדרוש לריצת האלגוריתם. ומכיוון שהגורם העיקרי לקביעת זמן זה הינו אורך המערך,
נוכל להגיד שסדר זמן הריצה של אלגוריתם החיפוש הסדרתי שלנו הוא (n)O.
כדי לעבור על תאי המערך אנו משתמשים בלולאה. בכדי לקבוע את סדר הגודל של זמן הריצה,
הדבר החשוב ביותר הוא: לכמה איטרציות תידרש הלולאה.
הדבר החשוב ביותר הוא: לכמה איטרציות תידרש הלולאה.
ו. אורך הקלט
* אורך הקלט של אלגוריתם הינו מדד על "כמות העבודה" שהאלגוריתם יבצע.
* כאשר קיימת באלגוריתם לולאה, משך ביצוע הלולאה (כמות האיטרציות שתתבצענה) תלוי באורך
הקלט.
* במלים אחרות: מספר הפעמים שהלולאה תתבצע בזמן-ריצה תלוי באורך הקלט, והוא המשפיע העיקרי
על משך הביצוע של כלל האלגוריתם.
* דוגמה1: אלגוריתם לחישוב ממוצע של 100 מספרים חייב לבצע מעבר על כל אחד מ- 100 המספרים
הללו, ולכן הוא יעבוד מהר יותר מאשר אלגוריתם לחישוב ממוצע של 10,000 מספרים.
אורך הקלט במקרה הראשון יהיה תוך התייחסות ל- n שערכו 100, ובשני ל- n שערכו 10,000.
* דוגמה2: כאשר אנו רוצים להדפיס "Hello World" בדיוק חמש פעמים, למרות שיש לולאה, הרי שהיא
תרוץ באותו משך זמן קבוע בכל הרצה של התכנית.
אם בדוגמה1 משך זמן ריצת האלגוריתם אינו קבוע (תלוי באורך הקלט, כלומר בכמות המספרים עליהם
רוצים לבצע חישוב של ממוצע), הרי שבדוגמה2 משך זמן הריצה יהיה קבוע בכל פעם.
הקלט.
* במלים אחרות: מספר הפעמים שהלולאה תתבצע בזמן-ריצה תלוי באורך הקלט, והוא המשפיע העיקרי
על משך הביצוע של כלל האלגוריתם.
* דוגמה1: אלגוריתם לחישוב ממוצע של 100 מספרים חייב לבצע מעבר על כל אחד מ- 100 המספרים
הללו, ולכן הוא יעבוד מהר יותר מאשר אלגוריתם לחישוב ממוצע של 10,000 מספרים.
אורך הקלט במקרה הראשון יהיה תוך התייחסות ל- n שערכו 100, ובשני ל- n שערכו 10,000.
* דוגמה2: כאשר אנו רוצים להדפיס "Hello World" בדיוק חמש פעמים, למרות שיש לולאה, הרי שהיא
תרוץ באותו משך זמן קבוע בכל הרצה של התכנית.
אם בדוגמה1 משך זמן ריצת האלגוריתם אינו קבוע (תלוי באורך הקלט, כלומר בכמות המספרים עליהם
רוצים לבצע חישוב של ממוצע), הרי שבדוגמה2 משך זמן הריצה יהיה קבוע בכל פעם.
* דוגמה3: כאשר אנו רוצים להדפיס את כל המספרים בין 0 ל- num כלשהו המתקבל כפרמטר, אורך
הקלט הוא n=num וסדר הגודל של זמן ריצת האלגוריתם הוא (n)O.
הקלט הוא n=num וסדר הגודל של זמן ריצת האלגוריתם הוא (n)O.
* דוגמה4: כאשר אנו רוצים לבצע חיפוש בינארי (חיפוש בשיטת אריה במדבר) במערך באורך length,
הרי ש- n=length, והיעילות היא (log2n)O. מדוע? כיוון שלמרות שאורך המערך הוא length כלשהו,
הרי שבחיפוש בינארי אנו מבטלים בכל איטרצה חצי מכמות התאים עליהם יש לעבור לצורך החיפוש.
הרי שבחיפוש בינארי אנו מבטלים בכל איטרצה חצי מכמות התאים עליהם יש לעבור לצורך החיפוש.
5. שלושה סוגים של חיפוש
א. חיפוש סדרתי במערך שאינו ממוין. הכי פחות יעיל.
ב. חיפוש סדרתי במערך ממוין. קצת יותר יעיל.
ג. חיפוש במערך ממוין בשיטה הבינארית (אריה במדבר). היעיל ביותר.
6. מערך מונים (ראו עמ' 57-59 בספר)
תרגיל אירוויזיון: כתיבת פעולה המחזירה מערך מונים המציין את כמות הפעמים שהיה שימוש
בדירוג מסוים (0-12 נקודות) בהינתן שהשתתפו 40 מדינות (40 שירים). כל מדינה מבצעת 39 הצבעות
כיוון שמדינה לא יכולה להצביע עבור עצמה. ניתן לפתור התרגיל באמצעות לולאה אחת או לולאה מקוננת.
בדירוג מסוים (0-12 נקודות) בהינתן שהשתתפו 40 מדינות (40 שירים). כל מדינה מבצעת 39 הצבעות
כיוון שמדינה לא יכולה להצביע עבור עצמה. ניתן לפתור התרגיל באמצעות לולאה אחת או לולאה מקוננת.
* נושא זה של "מערך-מונים" יופיע במבדק ש.ב ביום ה' ה- 29.2.2024.
7. מיון-הכנסה - Insertion-sort (עמ' 129-130 בספר)
מיון בו בכל שלב מוכנס איבר אחד למערך ממוין כך שנשמר סדר המיון במערך.
מיון בו בכל שלב מוכנס איבר אחד למערך ממוין כך שנשמר סדר המיון במערך.
* נושא זה של "מיון-הכנסה" יופיע במבדק ש.ב ביום ה' ה- 29.2.2024.
8. פעולות על מחרוזות
א. הצהרה על משתנה מחרוזתי.
ב. השמה למשתנה מחרוזתי.
ג. אתחול משתנה מחרוזתי במחרוזת ריקה (ללא שימוש בתו רווח).
ד. קלט מהמשתמש למשתנה מחרוזתי.
ה. אופרטור* השרשור + במחרוזות.
*אופרטור = פעולה.
ו. התכונה Length של הטיפוס string (עמ' 17).
ז. הפעולה Equals (עמ' 17).
ח. הפעולות IndexOf ו- LastIndexOf (עמ' 22).
ט. הפעולה CompareTo (עמ' 18).
י. איתור תו במחרוזת (עמ' 19).
יא. הפעולה Substring (עמ' 23).
יב. הפעולה Replace (עמ' 23).
א. הצהרה על משתנה מחרוזתי.
ב. השמה למשתנה מחרוזתי.
ג. אתחול משתנה מחרוזתי במחרוזת ריקה (ללא שימוש בתו רווח).
ד. קלט מהמשתמש למשתנה מחרוזתי.
ה. אופרטור* השרשור + במחרוזות.
*אופרטור = פעולה.
ו. התכונה Length של הטיפוס string (עמ' 17).
ז. הפעולה Equals (עמ' 17).
ח. הפעולות IndexOf ו- LastIndexOf (עמ' 22).
ט. הפעולה CompareTo (עמ' 18).
י. איתור תו במחרוזת (עמ' 19).
יא. הפעולה Substring (עמ' 23).
יב. הפעולה Replace (עמ' 23).
יג. הפעולה Insert (עמ' 23).
יד. הפעולה Remove (עמ' 23).
* נושא זה של "פעולות על מחרוזות" יופיע במבדק ש.ב ביום ה' ה- 29.2.2024.
לבית
ש.ב מיום ג', ה- 20.2.24 ליום ה', ה- 22.2.24:
1. כתבו פעולה המקבלת כפרמטר מספר שלם num המייצג כמות הטלות של קוביה. הפעולה תחזיר מערך
מונים (מערך שלמים) המהווה סיכום סטטיסטי לגבי כמה פעמים הוגרל כל אחד מששת המספרים
האפשריים בהטלת קוביה. בגוף הפעולה עליכם להגריל num מספרים שכל אחד מהם בטווח 1-6.
לאחר כל הגרלה של מספר יש לקדם במערך המונים את ערך האינדקס המתאים בכך שמוסיפים
לו את הערך 1. גודלו של מערך המונים יכול להיות 6 או 7 (למען נוחות התכנות שלכם).
ש.ב מיום ג', ה- 20.2.24 ליום ה', ה- 22.2.24:
1. כתבו פעולה המקבלת כפרמטר מספר שלם num המייצג כמות הטלות של קוביה. הפעולה תחזיר מערך
מונים (מערך שלמים) המהווה סיכום סטטיסטי לגבי כמה פעמים הוגרל כל אחד מששת המספרים
האפשריים בהטלת קוביה. בגוף הפעולה עליכם להגריל num מספרים שכל אחד מהם בטווח 1-6.
לאחר כל הגרלה של מספר יש לקדם במערך המונים את ערך האינדקס המתאים בכך שמוסיפים
לו את הערך 1. גודלו של מערך המונים יכול להיות 6 או 7 (למען נוחות התכנות שלכם).
ש.ב מיום ה', ה- 22.2.24 ליום ב', ה- 26.2.24:
2. קראו מבוא למחרוזות בעמודים 13-16 (בספר האדום).
3. קראו אודות התכונה Length ואודות הפעולה Equals (בעמוד 17).
2. קראו מבוא למחרוזות בעמודים 13-16 (בספר האדום).
3. קראו אודות התכונה Length ואודות הפעולה Equals (בעמוד 17).
4. קראו אודות הפעולה CompareTo עליה לא דיברנו בכיתה (עמ' 18).
ודאו כי אתם מבינים מה היא עושה.
ודאו כי אתם מבינים מה היא עושה.
5. קראו אודות איתור תו במחרוזת בעזרת [ ] (גישה לתו בודד על פי ערך האינדקס של מיקומו במחרוזת)
(עמ' 19).
(עמ' 19).
6. בצעו התרגילים 1-7 בעמ' 21.
הערות: בתרגיל 2, יש לבדוק לאחר כל קליטה אם אורך המחרוזת זוגי ולפעול בהתאם.
בתרגיל 3, חשבו על פתרון באמצעות לולאה מקוננת, כאשר טיפוס האינדקס בלולאה
הפנימית יהיה מטיפוס char.
הערות: בתרגיל 2, יש לבדוק לאחר כל קליטה אם אורך המחרוזת זוגי ולפעול בהתאם.
בתרגיל 3, חשבו על פתרון באמצעות לולאה מקוננת, כאשר טיפוס האינדקס בלולאה
הפנימית יהיה מטיפוס char.
בתרגיל 4, יש להשתמש ב- IndexOf וגם ב- LastIndexOf.
בתרגיל 6, יש ליצור לולאה לקליטת סיסמה מהמשתמש. היציאה מהלולאה תתבצע רק
כאשר המשתמש הקליד סיסמה תקינה.
כאשר המשתמש הקליד סיסמה תקינה.
7. רשות: בצעו תרגיל 8 בעמוד 22 ("רצפים זהים ***).
בשיעורים הבאים
1. תרגול נוסף בנושא מערך מונים.
2. ביום ב' הקרוב מובטח: העמסת פעולות (Overloading).