Tip:
Highlight text to annotate it
X
מה הוא אלגוריתם?
במדעי המחשב,
אלגוריתם הוא סט של הוראות
לפתירת בעיה, שלב אחרי שלב.
בדרך כלל, אלגוריתמים מופעלים על מחשבים,
אבל לנו האנשים יש גם אלגוריתמים.
לדוגמה, איך הייתם סופרים
את מספר האנשים בחדר?
ובכן, אם הייתם כמוני,
אתם כנראה הייתם מצביעים על כל אדם,
אחד אחרי השני,
וסופרים מ 0:
1,2,3,4 וכך הלאה.
ובכן, זה אלגוריתם.
למעשה, בואו ננסה לבטא אותו
בצורה קצת יותר פורמלית בפסואודו קוד,
בדומה לשפת דיבור
שמדמה שפת תכנות.
ניצור n ששווה ל 0.
לכל אדם בחדר, נציב n=n+1.
איך נתרגם את זה בפסואודו קוד?
ובכן, שורה 1 מגדירה אפשר להגיד,
משתנה שנקרא n
ומאתחלת אותו עם הערך 0.
זה רק אומר שבהתחלה של האלגוריתם שלנו,
הדבר שאיתו אנחנו סופרים
יש לו ערך של 0.
אחרי הכל, לפני שהתחלנו לספור,
לא ספרנו כלום עדיין.
לקרוא למשתנה הזה n זו פשוט מוסכמה.
הייתי יכול לקרוא לו כמעט בכל שם.
עכשיו, שורה 2 מסמנת את תחילתה של הלולאה,
רצף של צעדים שיחזרו מספר פעמים.
אז, בדוגמה שלנו, הצעד שאנחנו עושים
הוא לספור אנשים בחדר.
מתחת לשורה 2 בשורה 3,
שמתארת בדיוק איך אנחנו נספור.
ההזחה מציינת שזו שורה 3
שתחזור על עצמה.
אז, מה שהפסואודו קוד אומר
זה שאחרי שמתחילים באפס,
לכל אדם בחדר,
אנחנו נגדיל את n ב 1.
עכשיו, האם האלגוריתם נכון?
ובכן, בואו נחשוב על זה קצת.
האם זה עובד אם יש שני אנשים בחדר?
בואו נראה.
בשורה 1, אנחנו מאתחלים את n באפס.
לכל אחד משני האנשים האלה,
אנחנו נגדיל את n ב 1.
אז, במעבר הראשון בלולאה,
אנחנו מעדכנים את n מ 0 ל 1,
במעבר השני באותה לולאה,
אנחנו מעדכנים את n מ 1 ל 2.
וכך, בסיום האלגוריתם, n הוא 2,
שבאמת תואם את מספר האנשים בחדר.
עד עכשיו, הכל טוב.
אבל מה עם מקרי קצה?
נניח שיש אפס אנשים בחדר,
חוץ ממני, שסופר.
בשורה 1 אנחנו מאתחלים את n לאפס.
הפעם, עם זאת, שורה 3 לא מתבצעת בכלל
מאחר ואין אנשים בחדר,
וכך, n נשאר אפס,
שזו באמת תואם למספר האנשים בחדר.
די פשוט, נכון?
אבל לספור אנשים אחד אחד זה די לא יעיל, נכון?
בטוח שאפשר להצליח יותר!
למה לא לספור שני אנשים כל פעם?
במקום לספור 1,2,3,4,5,6,7,8 וכך הלאה,
למה לא לספור
2,4,6,8 וכך הלאה?
זה אפילו נשמע מהיר יותר, וזה בטוח כך.
בואו נבטא את הטיוב הזה בפסואודו קוד
נצהיר על n שווה אפס.
לכל זוג אנשים בחדר,
נציב n=n+2.
שינוי די פשוט, נכון?
במקום לספור אנשים אחד אחד,
אנחנו סופרים במקום שניים כל פעם.
האלגוריתם הזה מהיר לכן פי שניים מהקודם.
אבל האם הוא נכון?
בואו נראה.
האם זה עובד כשיש שני אנשים בחדר?
בשורה 1, אנחנו מאתחלים את n ל 0.
לזוג האנשים הזה, אנחנו מגדילים את n ב 2.
וכך, בסוף האלגוריתם הזה, n הוא 2,
שזו באמת מתאים למספר האנשים בחדר.
נניח אז שיש אפס אנשים בחדר.
בשורה 1, אנחנו מאתחלים את n לאפס.
כמו קודם, שורה 3 לא מתבצעת בכלל
מאחר ואין זוגות אנשים בחדר,
וכך, n נשאר אפס,
שבאמת תואם את מספר האנשים בחדר.
אבל מה אם היו 3 אנשים בחדר?
איך האלגוריתם הזה מצליח?
בואו נראה.
בשורה 1 מאתחלים את n לאפס.
לזוג מהאנשים האלה,
אנחנו מעלים את n ב 2,
אבל אז מה?
אין עוד זוג מלא של אנשים בחדר,
אז שורה 2 לא רלוונטית יותר.
וכך, בסופו אל האלגוריתם הזה,
n הוא עדיין 2, מה שלא נכון.
באמת האלגוריתם הזה לא תקין
מפני שיש לו שגיאה.
בואו נתקן עם פסואודו קוד נוסף.
נצהיר על n שווה לאפס.
לכל זוג של אנשים בחדר,
נציב n=n+2
אם אדם אחד נשאר ללא זוג,
נציב n=n+1.
כדי לפתור את הבעיה הזו,
אנחנו מציגים בשורה 4 תנאי,
שידוע אחרת כענף,
שמבוצע רק אם יש אדם אחד
שאי אפשר לחבר לאחר.
אז עכשיו, בין אם יש 1 או 3
או כל מספר אי זוגי של אנשים בחדר,
האלגוריתם הזה יספור אותם עכשיו.
האם אנחנו יכולים להצליח יותר?
ובכן, אנחנו יכולים לספור בקפיצות של 3, 4 או אפילו 5 ו 10,
אבל מעבר לזה זה יעשה
מעט קשה יותר להצביע.
בסופו של יום,
בין אם יופעל על ידי מחשב או אדם,
אלגוריתמים הם רק סט של הוראות
איתם ניתן לפתור את הבעיות.
אלה היו רק שלושה.
איזה בעיה אתם הייתם פותרים עם אלגוריתם?