ג'ייסון הירשהורן: ברוכים הבאים לשלושה בשבוע, כולם. יש לנו עסוק אך מרגש סעיף לפנינו. אז קודם כל, בגלל שאנחנו עשינו כמה התקדמות עם, כמובן, אבל אנחנו עדיין יש הרבה למידה שנותר לעשות, אני הולך להראות לכם חבר 'ה כמה משאבים שצריך להוכיח להיות מאוד מועיל כאשר אתה מתקרב לא רק שלך בעיה קובעת, אלא גם לעכל את כל את החומר אנחנו נותנים לכם חבר 'ה ב הרצאות ומכנסיים קצרים וחתך. 

ואז אנחנו הולכים לבלות את 20 הראשונים ל25 דקות של הקטע הולך על GDB, שאתה יכול או לא יכול להיות משמש בשלב זה, אבל זה כלי מועיל מאוד שיהיה לעזור לך באגים בתוכניות שלך. הרבה ייתכן שהשתמש בprintf אמצע התכנית שלך כדי להבין מה משתנה שווה. GDB הוא אפילו טוב יותר מאשר printf ו לא לדפוק את הקוד שלך, כי אתה להריץ אותו על קובץ הפעלה. אז אנחנו מתכוונים לעבור על 10 מועילים ביותר פקודות שאתה צריך בשביל GDB, ואנחנו הולך על תרגיל יחד כך בבעיה להגדיר שלוש ומעבר, לך ניתן להשתמש GDB כדי לעזור באגים התוכניות שלך. ולבסוף, אנחנו הולכים לעבור על כמה מיון וחיפוש אלגוריתמים שראית בהרצאה, ואנחנו הולך בעצם קוד, ולא רק חיפוש בינארי pseudocode, אבל קוד, מיון בועות, ומיון בחירה. 

אז קודם כל, אני רוצה ללכת על המשאבים. זו רשימה מקיפה, וזה גופן קטן יותר כי היה לי הרבה מה תתאים כאן. אבל אלה לא רק יעזרו לך, שוב, עם סטי הבעיה ו מידע לעכל שלמדת, אבל בהחלט, הגיע זמן חידון, יהיו אלה להיות מועיל מאוד. אז קודם כל, סיכומים. אם אתה הולך לcs50.net/lectures ו לגלול לשבוע הספציפי ויום, אתה תראה שיש הערות לכל הרצאה, שהוא לא פשוט תמליל, אך גרסה ערוכה של מה היה מכוסה בהרצאה עם קוד קטעים ופיסות מועילות אחרות. אני מאוד ממליץ ללכת על פני אלה. ואז, כמו גם, יש קוד המקור זמין מכל הרצאה. ושוב, מגלשות אלה תהיינה גם זמין באופן מקוון ב cs50.net/sections בערב זה. 

אז שני הם המכנסיים הקצרים בכל שבוע כי נושאי כיסוי, בדרך כלל 5 עד 15 דקות אורך. ואלה אני מקווה שינתנו לך פריימר הגדול בנושאים שונים. שלישי - וזה זה מותג החדש שנה - הוא study.cs50.net. אם לא בדק את זה, אני מאוד ממליץ לך לעשות זאת. אתה מקבל לבחור נושא. יש לנו עשרות נושאים על שם. כך למשל, אתה בוחר פונקציות. זה נותן לך כמה שקופיות ומציין בפונקציות. אלה הם למעשה את השקופיות שTFS מוזמנים להשתמש בנו מצגות בסעיף. יש גם טיפים וטריקים להתמודדות עם פונקציות, ויש בעיות בפועל שתעזורנה אתה עובד עם פונקציות. גם אנחנו נותנים לך קישורים לקצרים על פונקציות ופעמים שפונקציות יש לבוא בהרצאה. אז study.cs50.net, מותג חדש שנה, משאב נפלא. 

בשלב הבא, יש לי אדם, שהוא המדריך הפקודה שאתה יכול לרוץ ב שורת הפקודה. אז אם יש לך שאלות כלשהן על הפקודה, למשל, rand, שבו אנו נתקל בשבוע שעבר בסעיף ויש לך סיכוי נתקל ב הבעיה שלך להגדיר כאשר עובר ליצור קוד, אבל אם תקליד אדם rand, תקבל את הדף ש מספר לך על כל rand. זה נותן לך את מה שנדרש, פרמטרים שנדרש, כמו גם תשואה סוג ותיאור קצר של פונקציה. 

אז לבדוק rand. זה יכול להיות קצת מלל ומבלבל, אז לפעמים אני מוצא את זה פשוט Googling את מה שאני רוצה לדעת הוא הדרך הטובה ביותר למצוא את התשובה. אז להתאמן עם גוגל. קבל טוב בגוגל. זה יהפוך לחבר הכי טוב שלך. 

כמו גם גוגל, אם אתה לא יכול למצוא אותו בגוגל, cs50.net/discuss, זה הדיון בפורום. רוב הסיכויים שאם יש לך שאלה, אחד 700 + בני גילך יש גם ש שאלה ואולי ביקשתי זה כבר בלדון פורומים ויש לו תשובה. אז אם יש לכם שאלה או משותפת יש לך שאלה שאתה חושב אולי אנשים אחרים אולי נתקל, לבדוק את cs50.net/discuss. 

לבסוף, שני האחרונים, אם אתה רוצה לדבר עם בן, משרד אמיתי אנושי שעות בימים שני עד שישי. יש גם שעתי עבודה באינטרנט לתלמידי ארכה. ואחרון אך לא פחות חשוב, לי, סימן קריאה. לכולכם יש את פרטי הקשר שלי. אם אתה צריך משהו, בבקשה לא תהסס לפנות אלי. תמיד מרגיש חופשי לעשות זאת. מעטים מאוד שהוספתם אותי בGchat, כך שהיה מאכזב, אבל אני מקווה שאשנה בין זה והסעיף הבא. כל שאלות עד כה על המשאבים? גדול. 

לבסוף, תקע נוסף עבור משוב, sayat.me/cs50. אתה יכול לתת לי משוב בעילום שם על איך שאני עושה. זה היה באמת מועיל בשבוע שעבר. יש לי כמה הערות ממך חבר 'ה מייד אחרי סעיף, בתוספת מ תלמידים אחרים שצפו בו במהלך השבוע, וזה היה עוזר לנו מאוד. אני הולך לנסות ולהגביל את השימוש שלי המילה "מתוקה", אבל אני אראה לי התלהבות והתרגשות בדרכים אחרות. אבל היו נוסף אחרים פידבקים מהותיים, שני פלוסים ודלתא. אז בבקשה, אני נותן לך החבר 'ה משוב על קבוצות הבעיה שלך. אתה מוזמן לתת לי משוב בהוראה שלי. אני כאן בשבילכם. 

גדול. זה כל מה שיש לי בשביל החלק הראשון. האם יש למישהו כל שאלות עד כה? ויש לי פתק עבור מרכז השליטה והבקרה. הסטודנטים הארכה לא שלחו הודעה לי אומר שהם לא מקבלים שום אודיו, אבל זה מחוץ לכחיי לתקן. כך אני מקווה, שמקבל נפתר תוך זמן קצר. אם אתה צופה באינטרנט, היי, אבל אתה לא יכול לשמוע אותי. 

אז קודם כל, אנחנו הולכים לעבור GDB. GDB, כפי שרמזתי בקודם לכן, הוא כלי ניפוי שגיאות הרבה יותר טוב מאשר printf. אז כדי להתחיל לעבוד עם GDB, חבר 'ה, אם אתה רוצה לפתוח את המכשיר שלך ולקחת את הקובץ שאני אליך קודם לכן - בקובץ זה יהיה גם זמין באינטרנט בקצת - ולהפעיל GDB. / את השם של הקובץ. ראשית, כמובן, אתה צריך לקמפל להגיש בגלל GDB עובד על רק קבצי הפעלה. 

אבל אם אי פעם אתה רוצה להתחיל GDB, הדבר הראשון שאתה עושה, אתה מפעיל GDB. / קיסר. אז זה השם של התכנית שאנחנו הולך עם זה עכשיו. אז אני הולך לכתוב להפוך את הקיסר, אשר ייתן לי קובץ הפעלה כאן מודגש בירוק. ולאחר מכן אני הולך לרוץ GDB. / סזאר. 

והנה לך. אתה רואה שיש לנו חלק מטקסט אומר לי על הגרסה של GDB, נותנת לי כמה מידע על אחריות, ואז אנחנו יש הפקודה התמ"ג, שנראית מין כמו הפקודה שורת הפקודה שלנו, אבל אתה רואה שזה פתוח פארן, GDB, paren קרוב. לפני שנמשיך וניפוי שגיאות בקובץ זה שנשלחתי לכולכם, בואו נסתכל על כמה פקודות שימושיות כל כך יש לנו תחושה של מה שאנחנו הולכים לכסות. 

פקודות אלה מופיעות כאן ב הסדר שבו אני בדרך כלל להשתמש בם. אז אני מתחיל את התכנית שלי על ידי הפעלה GBD. / שמה של התכנית, במקרה זה, קיסר. ואז הדבר הראשון שאני עושה 99.9% של זמן הפסקת הסוג מתכוונת. שקובע נקודת הפסקה בראשית. בעיקרו של דבר, מה שאתה עושה שם היא התכנית הוא הולכת לעצור ב עיקרי, כך שאתה יכול להתחיל לבחון אותו בתור על ידי קו, ולא פועל בכל הדרך. אתה יכול לשבור בנקודות שונות ב הקוד שלך, אבל עיקרי הוא בדרך כלל מקום טוב להתחיל בו. 

הפקודה הבאה אני רץ היא ארוך. שמתחיל הריצה התכנית, ו אם אתה צריך להיכנס לשורת הפקודה טיעונים, אתה מפעיל אותו פיקוד ש. לרוץ עם הטיעונים. אז מאז אנחנו הולכים על גרסה של C, המהווה את תכניתכם כתבתי לpset שתי - זה, כמובן יש לו, כמה באגים בזה שאני מקווה שנמצא - אנחנו הולכים לרוץ ריצה עם כמה פקודת טיעוני שורה כי קיסר, כמו שאתם יודעים לכל הבעיה להגדיר מפרט, לוקח קצת טיעוני שורת הפקודה. 

הזוג הבא של פקודות, הבא אחד נקרא למעשה הבא. אחד שלוקח קו אתה בקו באמצעות התכנית שלך. אז להכות n אז על Enter לוקח אותך לשורה הבאה, ביצוע השורה הקודמת. שלב לוקח אותך לא רק כדי השורה הבאה, אבל זה לוקח אותך פונקציות בפנים. אז אם יש לך כתב פונקציה ב הקוד או שלך, אם אתה רוצה לחקור ל i, למשל, אתה יכול להכות ים, ו ולא הולכים לשורה הבאה של את הקובץ שאתם עוברים תקין עכשיו, אתה בעצם להיכנס פונקציה זו ולראות את הקוד שלה. 

רשימה מראה לך, במאוד ידידותית למשתמש פורמט, 10 או כך הקווים סביב שבו אתה נמצא כעת בקוד שלך כך שאתה ממש יכול לראות את הקובץ ולא שיש להחליף בחזרה ו שוב בין תצוגות שונות. הדפסה היא כמו printf, כפי ששמתי מרמז. זה מראה לך מה שווים משתנה. 

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

לבסוף, להמשיך. הקלדת הפסקה עוצרת אותך בנקודת ההפסקה. אתה יכול ללכת דרך קו על ידי קו עם הבא וצעד. המשך מפעילה את התכנית לבאה שלך לשבור נקודה או עד להשלמה אם אין יותר נקודות הפסקה. השבת מסירה נקודות הפסקה אם אתה החליט ההפסקה במרכזית הייתה בלתי הולם, אתה רוצה להגדיר את זה במקום אחר. ולבסוף q, לפרוש, יוצא מGDB. 

אז תכנית זו,. / קיסר, אנחנו הולכים להסתכל דרך עכשיו ואנחנו הולכים להשתמש GDB למצוא באגים בתכנית זו. רצתי בתכנית זו קודם לכן עם בדוק 50, ויש לי קמט אחד. כל מה שקיים, זה הידור, זה עברתי הרבה בדיקות, אבל עבור משום מה, זה לא עבר חמישי בדיקה, מפנה BARFOO, כל כמוסות, לתוך E-D-U-I-R-R, כל כמוסות, באמצעות שלושה כמפתח. יש לי די קרוב. ירדתי על ידי אות אחת. אז יש איזו טעות קטנה לכאן. אני כבר הסתכלתי דרך הקוד שלי. אני לא יכול להבין את זה. יש לקוות, שאתם יכולים לעזור לי להבין מה הוא הבאג הזה. 

אז זה הטעות אנחנו מחפש. בואו נעבור לGDB. שוב, אני כבר להפעיל GDB. / קיסר, אז עכשיו אנחנו בGDB. ומה הוא הראשון דבר שאני צריך לעשות? אני פשוט נכנסתי GDB. מישהו ייתן לי טוב הפקודה להיכנס. 

סטודנט: לשבור ראשי. 

ג'ייסון הירשהורן: לשבור ראשי. פנטסטי. בואו נקליד שבי אתם יכולים לצפות כאן למעלה או בצעו יחד במחשבים שלך. לשבור ראשי, ותראה נקודת פריצה נקבעה ל - זה נותן לי קצת מוזר כתובת זיכרון, וזה גם נותן לי את מספר הקו. אם הייתי מסתכל אחורה על קובץ זה, אני מבין עיקרי ש קרה על קו 21. מה אני צריך לרוץ הלאה? האם התכנית שלי פועלת? לא. אז מה אני צריך לרוץ הלאה? 

תלמיד: הפעל. 

ג'ייסון הירשהורן: הפעל. אני צריך רק לרוץ לרוץ, או צריך אני מוסיף עוד כמה דברים ב? 

תלמיד: הפעל עם הוויכוח. 

ג'ייסון הירשהורן: הפעל עם פקודת הטיעונים. ומאז אני באגים מאוד ספציפי מקרה, אני צריך להיכנס כי ויכוח שורת הפקודה. אז אל אני ארוץ שלוש, שהוא, שוב, התפוקה שקיבלתי מעזיבה 50. הפעלת תכנית. אנחנו עוברים שתי שורות. כעת יראו שאנחנו על קו 21. איך אני יודע שאנחנו על קו 21? כי אם אתה מסתכל לצד השמאל של חלון המסוף שלי, יש זה אומר שורה 21. וזה נותן לי, בעצם, קוד שהוא בשורה 21. אז אני misspoke קודם לכן. העיקרי הוא לא ממש בשורה 21. העיקרי הוא כמה שורות מעל 21. אבל בשורה 21, זה לאן אנחנו שבירה. קו זה של קוד יש עדיין לא בוצע. זה חשוב. השורה שאתה רואה יש לא בוצע עדיין. זו השורה הבאה של קוד אתה עומד לבצע. 

אז השורה הבאה, כפי שאתם בטח מכיר, היא זו מצב בדיקה כדי לראות אם יש לי נכנס טיעון שורת הפקודה. וכדי שאני, מה הוא שני חלק מזה עושה? מהו ל i? 

סטודנט: שינוי אותו למספר שלם. 

ג'ייסון הירשהורן: סליחה? 

תלמיד: זה משתנה טיעון למספר שלם. 

ג'ייסון הירשהורן: אז כדי שאני משנה ARG v1 ממחרוזת למספר שלם. ואז מה זה בודק? 

תלמיד: אם יש שני ויכוח שורת הפקודה, בצד מהפעלת התכנית. 

ג'ייסון הירשהורן: ומה המחצית השנייה של ביטוי בוליאני בדיקה? חלק זה לכאן, כדי שאני? 

תלמיד: אם זה שלילי. 

ג'ייסון הירשהורן: הפיכת מה שבטוח? 

סטודנט: ביצוע זה בטוח זהו, למעשה, חיובי. 

ג'ייסון הירשהורן: בדיוק. זו בדיקה כדי לראות אם זה שלילי, ואם הוא שלילי, אני יש לי תחושת כוח השורה הבאה להיות לי לצעוק על המשתמש. אז בואו פגעו סוף לבצע את הקו הזה. אנחנו לא רואים את הקו הזה שאתם אולי ציפיתי לראות צועקים על משתמש ולאחר מכן חזר, כי הקו הזה לא בצע. אני נכנסתי 3. אז אני לא, למעשה, להיכנס לשתי הפקודה טיעוני קו, ו -3 הוא גדול מאפס. אז שראינו כי קו, אנחנו להורג, אבל אנחנו לא לדרוך בתוך אם המצב. 

אז עכשיו, הבא, אני רואה שאני הגדרה מפתח int שווה ל i ARG v1. אז זה יצירת מפתח משתנה. אז אם אני מדפיס את מפתח עכשיו, כי המאפשר לך לראות את ערך בתוך משתנה, מפתח שווה 47. זה מוזר, אבל כמובן, זה בגלל שאין לי להורג קו שעדיין. אז עכשיו אם אני מכה n, לבצע את הקו, ולעשות מפתח הדפסה, המפתח יהיה שווה 3, וזה מה שאנחנו מצפים שזה שווה. 

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

בואו לראות בעזיבה שלי 50, אני הכנס BARFOO כל כמוסות, ולכן זה מה שאני נכנסים. אם אני עכשיו להדפיס טקסט רגיל. אתה תראה שזה שווה מחרוזת. זה נותן לי קצת מוזר הקסדצימלי אחר מספר, אך היא עושה ב למעשה אומרים שהמחרוזת שלי היא BARFOO. אם אני רוצה לראות מה מפתח שווה ב שלב זה, איך אני יכול לבדוק את המפתח? 

תלמיד: מפתח הדפסה. 

ג'ייסון הירשהורן: מפתח הדפסה, בדיוק. ולמעשה, יש קיצור. אם נמאס לך להקליד הדפסה, אתה יכול פשוט להקליד p. אז מקש p עושה את אותו דבר בדיוק. ושוב, אני רואה את זה שווה 3. 

אם אני רוצה לברר מה הן מפתח וBARFOO שווה באותו הזמן אבל היה עייף של הקלדה כולי אחד מתוך בנפרד, אני יכול להקליד המקומיים מידע. זה נותן לי שווים מפתח 3. טקסט רגיל שווה BARFOO. זה גם נותן לי שני דברים מוזרים האלה בחלק העליון, משתנה זה אני ו n משתנה זה. 

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

אז אני הולך לבצע את הקו הזה, שורה 34, ללולאה. אנחנו הולכים לקפוץ לתוך ללולאה על ידי להכות n. ואנחנו בתוך הלולאה for. אנחנו בבדיקה הראשונה שלנו. ושוב, אלה צריכים סוג של נראים מוכר לך, כי זה היה תכנית הקיסר שנכתבה, אבל שוב, יש לו איזה באג. 

ועכשיו אם אני עושה את המקומיים מידע, בגלל שאני בתוך כך ללולאה, תוכל לראות כי אני שווה אפס, כפי שאנו מצפים. זה מה שאנחנו מגדירים את זה ואותחלנו זה ללולאה. n שווה ל -6. זה גם הגיוני, כי אנו קובעים זה לstrlen של טקסט רגיל. אז אני רוצה לעשות את המקומיים מידע או הדפסה למשתנה לעתים קרובות כדי לוודא ש הכל תמיד מה אני מצפה שזה שווה. במקרה זה, כל מה שהוא מה שאני מצפה שזה שווה. 

אז בואו נתחיל לנוע דרך זה ללולאה. השורה אני בהיא קו 36, אם רגיל הוא אני טקסט גדול וממישור אני טקסט הוא פחות או שווה ל z. אני יודע שהבעיה שלי היא לא עם הראשון שלי מכתב, זה באות השנייה. אם אנחנו מסתכלים אחורה על עזיבה 50, לינה הולכת לE בסדר. אני לוקח ומשאיר אותו כמו , לא משנה אותו לד אז משהו לא בסדר עם המכתב השני. אז אני הולך לעבור יש בשנייה. 

אבל אם אני לא רוצה לבדוק את מה שרגיל טקסט שהשתוויתי בזה בפרט מקרה, אני חושב שזה צריך להיות מה? מה צריך טקסט רגיל אני שווה בזה הסיבוב ראשון בלולאה for? 

סטודנט: אפס? 

ג'ייסון הירשהורן: טקסט רגיל שלי? כך זה צריך להיות ב 'הוני, כמובן, שווה אפס, אבל טקסט רגיל אפס סוגר סגור סוגריים שווים B בגלל מיתרים, כפי שראינו בשבוע שעבר, הם מערך, ולכן אנחנו מקבלים את תו ראשון מזה. אז שוב, אם אני הדפסתי טקסט רגיל של אני, אני, למעשה, לקבל את התו ב 'וזה מסודר, נכון? בעצם אין לי I. טקסט רגיל זה לא אחד מהמשתנים שנקבעתי או אותחל, אבל אתה יכול להדפיס מתוך שורה של דברים שלמות אם אתה רוצה. 

אבל בואו נעבור דרכו. אם אני טקסט רגיל הוא גדול יותר ומ אני טקסט רגיל הוא פחות או שווה ל Z, כי ברור הוא נכון, כי יש לנו ב הון אני הולך לרוץ כמה פיקוד עליו. ראינו במתמטיקה כי בשבוע שעבר, אז אנחנו לקחת את זה כמובן מאליו שזה עובד נכון בהתאם להגעת 50. 

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

אז אנחנו באיטרציה השנייה של ללולאה שלנו. אני שווה 1, שבו אנו מצפים. N שווה 6, שבו אנו מצפים. מפתח שווה 3, שבו אנו מצפים. וטקסט רגיל, תראה, שווה EARFOO עכשיו, לא BARFOO יותר, כי באיטרציה הקודמת שלנו, ב 'היה השתנו להון E. אז אנחנו עומדים להיתקל בבעיה, אז זה מקום שבו אנחנו הולכים לצלול לתוך איתור באגים. אבל האם למישהו יש שאלות על מה שעשינו עד כה? פנטסטי. 

אז אנחנו עומדים לבצע את זה אם מצב, סוגר טקסט רגיל סגרתי סוגר גדול יותר ואני טקסט רגיל קטן או שווה לז' אבל לפני אני נכנסתי לזה, כי זה המקום שבי אני יודע שהטעות שלי היא, אני רוצה לציין מתוך טקסט רגיל של I. אז בואו נשים את הדפסה. הוא עושה שווה את הדמות, כך ש נראה עד כה, הכל טוב ויפה. 

אז אני מצפה את הקו הזה להיגיון שלי, קו זה צריך להיות אמיתי. זה באות גדולה. אבל אם אני מכה n, אנחנו מבינים שזה קו, למעשה, לא בצע. קפצתי לאחר אם. למה זה קרה? 

תלמיד: כי יש לך את המצב שלך של טקסט רגיל הוא גדול יותר מ, לא שווה או גדול מ. 

ג'ייסון הירשהורן: אז היה לי הטקסט רגיל שלי אני עולה, לא יותר או שווה ל. אז ברור, הבירה לא תפעיל את זה אם מצב, ושעשינו לא להיכנס לזה, ושעשינו לא לעשות את השינוי הדרוש. אז זהו, בעצם. אני הבנתי את הבאג שלי. אני יכול לחזור בקובץ המקור שלי, לשנות את זה, ולעדכן אותו ו להפעיל בדקו 50 שוב. 

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

אז שוב, אנו מדובג השגיאה שלנו. אנחנו הבנו שיש קצת היגיון החסר. ואנחנו מדובג זה מבעוד מועד לפני שמבצע בפועל את הקו, אבל היית שם לב שהיו לנו רק להיט הבא ולקפוץ לכי אחר אם, זה אומר שאם מצב לא היה נכון. לא, למעשה, לקבל התוצאה שציפינו. אז היינו יכול היה מתבקש, היה אנחנו לא היו כל כך נבונים, להסתכל על שאם מצב ולבדוק אם, למעשה, המצב שלנו צריך להעריך ל אמיתי בהקשר הנוכחי. 

זה הכל לניפוי שגיאות בתכנית זו. האם יש למישהו שאלות? מה הפקודה שאני יכול להכות להפסיק GDB? ש: ואז אני תתבקש, להפסיק בכל מקרה? כן או לא. אני אכה כן, ואני אצטרך להפסיק GDB. 

אז זה היה פריימר מהיר לGDB. למעשה, בתרחיש אמיתי, עשיתי את זה בשעתי עבודה. אני GDBed התכנית הזה בדיוק, ב שעתי עבודה עם תלמידים. ואם נחזור לפקודות שראינו לפני כן, היינו עיקרי הפסקה, ראשון דבר שעשינו. נהגנו לרוץ עם טיעוני שורת הפקודה, דבר שני שעשינו. אנו משמשים הבאים הרבה לעבור שלנו דרך קווים. ושוב, גרסה הקצרה של הבא הוא n. זה בסוגריים באפור בשקופית. 

אנחנו לא השתמשנו בצעד, אבל אנחנו לא בהכרח צריך למקרה זה. אבל אולי אנחנו משתמשים בו בקצת מאוחר יותר היום אם אנחנו באגים, ל דוגמא, חיפוש בינארי כאשר בינארי חיפוש נקרא בנפרד פונקציה אבל יש שגיאה כלשהי עם זה. אנחנו הולכים לרוצים להיכנס הקריאה לחיפוש בינארי ו למעשה באגים זה. רשימה אנחנו גם לא השתמשנו כי היו לנו תחושה של הקוד שלנו טובה, אבל אם אני לא רוצה לקבל את תחושה של מה שאני קוד היה בסביבה, אני יכול פשוט להשתמש ברשימה. 

הדפסה השתמשנו, מקומיים מידע השתמשנו. המשך אנחנו לא צריכים להשתמש בזה מקרה, גם לא אנחנו צריכים להשתמש שימוש להשבית, אבל עשו להפסיק. שוב, 10 פקודות אלה, לתרגל אותם. אם אתה מבין 10 פקודות אלה, אתה צריך להיות מוגדר לאיתור באגים כל בעיה עם GDB. 

אז אנחנו עומדים לצאת, שוב, כדי עיקרו של סעיף היום, הולכים על אלה מיון וחיפוש אלגוריתמים. לפני שאנחנו עושים זאת, שוב, על כל שאלה, הערות, חששות לGDB? אז הוא כולם הולכים להשתמש GDB לא printf? אז כולם, למען לצמיתות, כולם מהנהנים בראשם תקין עכשיו, אז אני אראה אותך בשעתי עבודה וכל TFS יראה אותך ו הם יגידו, יראו לי איך להשתמש GDB, ותוכל כדי להראות להם, נכון? סוג של? אולי בתקווה. מגניב. 

אז אנחנו הולכים לעבור ל מיון וחיפוש. תראה יש לי רשימה כבר מסודרים עבורנו, אבל זה לא הולך להיות המקרה תמיד. אז בבעיה להגדיר מפרט בעיה להגדיר שלוש, יש לך מכנסיים קצרים שאתה יכול לצפות, וזה ממש שואל אותך לצפות במכנסים האלה. כמו כן, בהרצאה בשבוע שעבר, הלכנו על הרבה האלגוריתמים האלה, ולכן אני לא הולך לבלות את הזמן בכיתה הולך על האלגוריתמים האלה שוב או ציור תמונות לכיצד אלה אלגוריתמים עובדים. שוב, זה מידע שאתה יכול מחדש את שעון הרצאה, או מידע ש הוא נתפס יוצאת מן הכלל במכנסיים הקצרים לחיפושים הללו, כל אשר זמינים בcs50.net. 

אז במקום, מה אנחנו הולכים לעשות הוא לכתוב תוכניות אלה. יש לנו תחושה, מודל המנטלי, של איך הם עובדים, ואז מה שאנחנו הולכים לעשות הוא לקודד אותם לאמיתית. אנחנו הולכים להפוך את זה מודל המנטלי, תמונה, אם תרצה, ל קוד בפועל. ואם הייתם קצת מבולבלים או מעורפל על המודל המנטלי, אני לגמרי להבין. 

אנחנו לא באמת הולכים לקפוץ ישר קוד. אז בזמן שהפקודה הזאת בשקופית זו שואלת לך קוד חיפוש בינארי, ו למעשה, גרסה חוזרת ונשנית של החיפוש בינארי, הדבר הראשון שאני באמת רוצה לעשות הוא לכתוב כמה pseudocode. אז יש לך מודל המנטלי הזה כיצד בינארי עבודות חיפוש. קח את גיליון נייר אם יש לך אחד זמין, או לפתוח את עורך טקסט, ואני רוצה כולם לכתוב. קח ארבע דקות כדי לכתוב את pseudocode לחיפוש בינארי. 

שוב, תחשוב על זה מודל המנטלי. אני אבוא מסביב אם יש לך שאלות ואנחנו יכולים לצייר את התמונה. אבל קודם כל, לפני שאנחנו מתחילים בתכנות, אני רוצה לכתוב pseudocode לחיפוש בינארי ולכן כאשר אנו לצלול פנימה, יש לנו כמה כיוון כמו לשם אנחנו צריכים בראש. 

תלמיד: האם אנחנו יכולים להניח את המערך של ערכים שאנו מקבלים כבר ממוינים? 

ג'ייסון הירשהורן: אז לחיפוש בינארי לעבודה - שאלה מצוינת - לך צריך לקחת בממוין מערך של ערכים. אז תניח שזה יעבוד. אנחנו נחזור לשקופית זו. אתה תראה בסגול הפונקציה הכרזה היא int binary_search bool ערך, ערכי int, n int. זה צריך להיראות מוכר אם יש לך כבר פנו או קבל ידיים מלוכלכות עם סט הבעיה. 

אבל זה ההצהרה על הפונקציה שלך. שוב, אין צורך לדאוג כל כך הרבה בשלב זה. מה אני באמת רוצה לעשות זה לקחת ארבע דקות לינארי pseudocode חיפוש, ואחר כך נלך על זה כקבוצה. ואני אבוא בסביבה. אם יש לך שאלות, מרגיש חופשי להרים את היד שלך. 

למה אתה לא לוקח שתי דקות נוספות כדי לסיים את pseudocode? אני יודע שזה אולי נראה מגוחך, כי אנחנו מבלים כל כך הרבה זמן על משהו שהוא אפילו לא ממש ב C, אך במיוחד עבור אלה יותר אלגוריתמים והבעיה מאתגרים סטים שיש לנו כדי להבין, מתחיל בpseudocode לא לדאוג על התחביר, רק לדאוג ההיגיון, הוא מועיל מאוד. וככה, אתה לא לפתרון שני בעיות קשות מאוד ובעונה אחת. אתה פשוט מתמקד בהיגיון, ו אז אתה לעבור לתחביר. 

על אישור. בואו נתחיל עובר pseudocode. שכתבתי עד כאן, בינארי pseudocode חיפוש. אנחנו כותבים את זה על לעלות ביחד. או שאני אכתוב את זה, ואתה תיתן לי שלי את ההנחיות שאני צריך. אז מישהו יכול לתת לי את הראשון קו של pseudocode כתב לחיפוש בינארי? כן, אנני? 

תלמיד: בעוד שאורכו של הרשימה היא גדולה מאפס. 

ג'ייסון הירשהורן: בעוד אורך רשימה גדולה מאפס. ושוב, אנו רואים כמה C-מחפשים דברים תחביריים כאן. אבל יותר מזה הוא באנגלית. האם למישהו יש שורה הם שמו לפני זה בפסאודו הקוד שלהם? 

תלמיד: קבל מערך של מסודרים מספרים. 

ג'ייסון הירשהורן: אתה כתב "לקבל מערך של מספרים ממוינים. "Per הצהרה על פונקציה, אנחנו נהיה עוברים מערך של מספרי מיון. 

תלמיד: [לא ברור]. 

ג'ייסון הירשהורן: אז תהיה לנו את זה. אבל כן, אם לא היה לנו את זה, אנחנו היית צריך למיין את המערך שלנו מספרים, כי חיפוש בינארי עובד רק על מערכים ממוינים. אז בזמן שאורך של רשימה שווה אפס, אני הולך לשים בחלק סוגריים מסולסלים כדי לגרום לזה להיראות קצת יותר כמו נראה C. אבל זמן מה, למפה על תוך לולאה, ולכן בתוך הזמן הזה לולאה מה שאנחנו צריכים לעשות כדי לעשות לחיפוש בינארי? 

מישהו אחר שלא נתן לי תשובה עדיין, אבל מי כתב את זה? 

תלמיד: לכו לאמצע הרשימה. 

ג'ייסון הירשהורן: טום. עבור לאמצע הרשימה. ושאלת המעקב, מה אנחנו עושים ברגע שאנחנו נמצאים בבית אמצע הרשימה? 

תלמיד: האם לבדוק אם זה המספר שאתה מחפש. 

ג'ייסון הירשהורן: מצוין. לכו אמצע הרשימה ולבדוק אם הערך שלנו נמצא שם - פנטסטי. האם יש למישהו כל דבר אחר זה היה שונה מזה? זה בדיוק נכון. 

הדבר הראשון שאנחנו עושים בחיפוש בינארי הוא הולך לאמצע הרשימה ו לבדוק אם הערך שלנו הוא שם. אז אני מניח שאם הערך שלנו הוא שם, מה אנחנו עושים? 

תלמיד: אנחנו חוזרים אפס [לא ברורים]. 

ג'ייסון הירשהורן: כן, אם הערך הוא שם, מצאנו אותו. אז אנחנו יכולים לספר לי דרך כלשהי, אולם זה פונקציה מוגדרת, אנו אומרים לי המשתמש אנחנו מצאנו אותו. אם זה לא שם, אם כי, זה שבו זה נהיה מסובך. אז אם זה לא שם, מישהו אחר ש היה עובד על חיפוש או בינארי יש רעיון עכשיו, מה אנחנו עושים? 

תלמיד: שאלה. 

ג'ייסון הירשהורן: כן? 

סטודנט: האם המערך כבר ממוין? 

ג'ייסון הירשהורן: כן, אנחנו מניחים המערך כבר ממוין. 

תלמיד: אז אתה צריך לבדוק אם הערך שאתה רואה הוא גדול יותר מאשר את הערך שאתה רוצה, אתה יכול להזיז באמצע המחצית השנייה. 

ג'ייסון הירשהורן: אז אם באמצע הרשימה היא גדולה יותר ממה שאנחנו מחפש, אז אנחנו עושים מה? אנחנו עוברים בו? 

סטודנט: אתה רוצה לעבור ל מחצית מהרשימה עם מספרים נמוכים מזה. 

ג'ייסון הירשהורן: אז אנחנו קורא לזה השמאל. אז אם האמצע הוא גדול יותר, אנחנו יכולים לחפש המחצית השמאלית של הרשימה. ולאחר מכן על ידי חיפוש, מה אני מתכוון בחיפוש? 

תלמיד: [לא ברור]. 

ג'ייסון הירשהורן: אנחנו הולכים לאמצע. אנחנו בעצם חוזרים על הדבר הזה. אנחנו חוזרים דרך הלולאה בזמננו. אני אתן לך את האחרון - אחר, אם, באמצע הוא פחות ממה שאנחנו עושים, מה אנחנו עושים כאן? 

תלמיד: לכו לצד ימין. 

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

אם באמצע הוא גדול יותר, אנחנו הולכים חיפוש שמאלה, אחר אם האמצע הוא פחות, אנחנו הולכים לחפש את הזכות. אז יש את כל שהיו לנו היכרות מסוימת עם המונחים שהשתמשנו במדעי מחשב ואת הכלים שיש לנו. אבל אתה כבר שם לב שהיינו מדבר באנגלית, אבל מצאנו הרבה דברים שנראו למפה על כלים שיש לנו בערכת כלי עבודת הקידוד שלנו. אז מייד את הבת, אנחנו לא הולך לקודד למעשה עדיין. 

מה אנחנו רואים כאן באנגלית שמפות לדברים שאנחנו יכולים לכתוב ב-C? 

תלמיד: בעוד. 

ג'ייסון הירשהורן: בעוד. אז בזמן שזה ממש כאן מפות על מה? 

תלמיד: לולאה בזמן. 

ג'ייסון הירשהורן: לולאה בזמן? או כנראה, באופן כללי יותר, לולאה. אנחנו רוצים לעשות משהו שוב ושוב. אז אנחנו הולכים לקוד לולאה. ואנחנו כבר יודעים, כי מה שעשינו זה כמה פעמים ואנחנו יש שפע של דוגמאות שם בחוץ, איך בעצם לכתוב מדד זה ללולאה. אז זה צריך להיות די קל. אנחנו צריכים להיות מסוגלים לקבל את זה התחיל די מהר. 

מה עוד שאנו רואים כאן? מה אחר מבני תחביר, דברים שאנחנו מכירים ב-C, לעשות לנו כבר יש תחושה מבוססת הנחה של המילים שאנחנו משתמשים בה? כן, אנה? [לא ברור] סתם, בצחוק. אנה, קדימה. 

תלמיד: אם ואחר. 

ג'ייסון הירשהורן: אם ו אחר - ממש כאן. אז מה אלה נראים? 

תלמיד: אם הצהרה אחרת. 

ג'ייסון הירשהורן: כן, תנאים, נכון? אז אנחנו בטח צריכים לכתוב כמה תנאים. ושוב, אם כי אולי מבלבל ב , בדרך כלל יש לנו תחושה הראשונה עכשיו של איך לכתוב תנאים ו התחביר לתנאים. ואם לא אנחנו, אנחנו רק להסתכל למעלה תחביר לתנאים, לגזור ולהדביק את זה, כי אנחנו יודעים שאנחנו צריך מצב כאן. כל דברים אחרים שאנחנו רואים מפה שעל גבי דברים שאולי צריך לעשות ב-C? כן, שלמה ע"ה? 

תלמיד: זה יכול להיות מובן מאליו, רק על ידי בדיקה אם ערך שווה משהו. 

ג'ייסון הירשהורן: אז איך לבדוק ועל - כן ללכת לאמצע הרשימה ולבדוק אם הערך שלנו הוא שם? איך אנחנו עושים את זה ב-C? מה התחביר לזה? 

סטודנט: שווה, שווה. 

ג'ייסון הירשהורן: שווה, שווה. אז סימון זו כנראה הולך להיות שווה, שווה. אז נדע שאנחנו צריכים מקום ש. ולמעשה, רק בכתיבתו, אנו רואים דברים אחרים. אנחנו הולכים לעשות קצת מפעילי השוואה לשם - פנטסטי. אז זה באמת נראה, על ידי ו גדול, יש לנו לא כתובים מילה של קוד C עדיין. אבל יש לנו את המודל המנטלי למטה באמצעות הרצאות ומכנסיים קצרים אלה. 

כתבנו פסאודו קוד כקבוצה. וכבר, יש לנו 80% אם לא 90% ממה שאנחנו צריכים לעשות. עכשיו, אנחנו רק צריכים לקודד זה, שבו שוב, הוא בעיה לא טריוויאלית לפתרון. אבל לפחות אנחנו תקועים בהיגיון. לפחות עכשיו, כאשר אנחנו הולכים לשעתי עבודה, אני יכול להגיד, אני יודע מה אני צריך לעשות, אבל אתה יכול להזכיר לי לי את התחביר? או אפילו אם שעתי עבודה עמוסות, אתה יכול לגגל לתחביר, ולא מאשר להיות תקוע בהיגיון. 

ושוב, ולא מנסה לפתור ההיגיון ובעיות התחביר כל בבת אחת, הוא לעתים קרובות הרבה יותר טוב לנתק את שתי הבעיות קשות האלה לתוך שני יותר לניהול אלה ולעשות פסאודו קוד ראשון ולאחר מכן בג אז בואו תראה את מה שעשיתי עבור פסאודו קוד מבעוד מועד. 

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

שילבתי אותם שם. הייתי צריך להקשיב ל שלך בפעם הראשונה. אז זה פסאודו הקוד יש לנו. אם אתה רוצה עכשיו, סליחה, תלך תחזור לבעיה הראשונית שלנו. בואו binary.c קוד. אז ליישם גרסה חוזרת ונשנית של חיפוש בינארי באמצעות הפעולות הבאות הצהרה על פונקציה. 

ואתה לא צריך להעתיק את זה עדיין. בעצם אני הולך לפתוח עד כאן binary.c. אז יש את ההצהרה על הפונקציה באמצע המסך. ואתם תראו שלקחתי פסאודו הקוד משני צדיי, אבל כמעט זהה למה שכתבנו, ו לשים את זה בשבילך. אז עכשיו, בואו ניקח חמש דקות קוד בפונקציה זו. 

ושוב, אם יש לך שאלות, להרים את היד שלך, תודיע לי, אני לבוא מסביב. 

תלמיד: [לא ברור]. 

ג'ייסון הירשהורן: אז לקחתי את ינארי הגדרת חיפוש ב למעלה, על קו 12. זה מה שיש לי לשקופית שלי. ואז כל פסאודו הקוד הזה אני רק להעתיק ולהדביק מהשקופית, שקופיות פסאודו קוד. אני עדיין לא שמעתי [לא ברור]. 

אז אם יש לך סיימת יישום, אני רוצה לבדוק את זה. אני בדוא"ל לך את קובץ helpers.h מוקדם יותר במעמד הזה. והוא יהיה זמין באינטרנט, כמו גם להורדה עבור אנשים צופים זמן סעיף זה מתעכב. ואני רק השתמשתי בהפצה הגנרית קוד מpset3. אז לקחתי find.C, משתמש בקובץ helpers.h ולא את קובץ helpers.h שנתן בקוד ההפצה. 

והייתי צריך לעשות שינוי אחר באחד find.C ולא קוראים פשוט חיפוש, קורא binary_search. אז אם אתה רוצה לבדוק את הקוד שלך, יודע שזה הוא איך לעשות את זה. למעשה, כאשר אנחנו ננהל את הקוד הזה כרגע, אני פשוט עושה עותק של ספריית pset3 שלי, שוב, החליף את קבצי עוזרים ולאחר מכן עשו את זה לשנות בfind.C לקרוא binary_search ולא רק לחפש. 

ג'ייסון הירשהורן: כן. יש לך שאלה? 

תלמיד: Nevermind. 

ג'ייסון הירשהורן: אין בעיה. ובכן, בואו נתחיל. אנו קוד זה כקבוצה. פתק אחד אחר. שוב, זה, יכול בקלות להיות מוחלף לבעית סט שלושה. יש לי קובץ helpers.h אשר, ולא מ helpers.h אנחנו נתון, מכריז חיפוש בינארי, בועה למיין ומיון בחירה. ובfind.c תוכל להבחין בקו, מה זה, קו 68, אנחנו קוראים לינארי חיפוש ולא חיפוש. אז שוב, את הקוד, כי הוא זמין באינטרנט או את הקוד שאתה יצירת עכשיו יכול להיות החליף בקלות לעמ להגדיר 3 כדי לבדוק את זה. 

אבל קודם, בואו קוד החיפוש בינארי. ההצהרה על הפונקציה שלנו, אנחנו חוזרים בול. אנחנו לוקחים את מספר שלם שנקרא ערך. אנחנו לוקחים את המערך של מספרים שלמים הנקרא ערכים, ואנחנו לוקחים את n להיות גודלו של המערך. על קו 10, ממש כאן, יש לי חדה כוללת stdbool.h. האם מישהו יודע למה זה שם? אז מה שורה זו של קוד לעשות? 

תלמיד: זה מאפשר לך להשתמש בסוג החזרת bool. 

ג'ייסון הירשהורן: בדיוק. 

תלמיד: או שזה ספרייה המאפשרת להשתמש בסוג החזרת bool. 

ג'ייסון הירשהורן: אז החד כולל שורת stdbool.h נותנת לי קצת הגדרות והצהרות לדברים שמותר לי להשתמש ב ספרייה זו. אז בין אלה שאומר שיש סוג זה נקרא בול, וזה יכול להיות אמת או שקר. אז זה מה שעושה את השורה. ואם לא היה לי קו שאני היית עושה להסתבך עבור כותב את זה מילה נכונה כאן, בול, בדיוק שם. בדיוק נכון. אז אני צריך את זה בקוד זה. על אישור. אז זה, שוב, הוא איטרטיבי גרסה, לא אחד רקורסיבית. אז בואו נתחיל. 

בואו נתחיל עם זה ראשון שורת קוד פסאודו. ובתקווה, גם אנחנו - או לא בתקווה. אנחנו הולכים להסתובב בחדר. נלך שורה אחרת שורה, ואני נעזור לי לך להבין את הקו שאנחנו צריכים כדי לכתוב ראשון. אז בזמן שאורך הרשימה הוא גדול מאפס. בואו נתחיל בחלק הקדמי. מה קו שאני צריך לכתוב כאן, בקוד? 

תלמיד: בעוד סוגריים n הוא גדול מ -0. 

ג'ייסון הירשהורן: בעוד n הוא גדול מ -0. אז n הוא בגודל של רשימה, ואנחנו בודקים אם - 

[קולות חציצה] 

ג'ייסון הירשהורן: - סליחה? 

תלמיד: איך אנחנו יודעים ש n הוא בגודל של הרשימה? 

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

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

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

אז האם מישהו יש לי לשנות את הקו הזה? רוב של קו זה הוא נכון באופן מושלם. האם יש עוד תוספת? האם אנחנו יכולים להחליף משהו עבור n ל להפוך את הקו הזה קצת יותר טוב? מ"מ-HM? 

סטודנט: אתה יכול לאתחל משתנה כמו אורך n שיהיו לאחר מכן ניתן להשתמש מאוחר יותר בפונקציה? 

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

תלמיד: האם זה לא הולך לקרות מאוחר יותר, כאשר אתה אומר, חיפוש עזב, חיפוש נכון? אתה מתכוון ללכת לשונה אזור שלך - 

ג'ייסון הירשהורן: אנחנו הולכים ללכת לאזור, אבל איך אנחנו יודעים אשר ללכת? אם יש לנו את המערך וזה רק n, איך אנחנו יודעים איפה ללכת במערך. בחלק האחורי, כן? 

תלמיד: האם יש לך, כמו, נמוך כפותים ומשתנה או כבול עליון משהו כזה? 

ג'ייסון הירשהורן: אישור. אז זה רעיון אחר. ולא רק שמירה על המסלול של גודל, אנו עוקבים אחר נמוכים ו משתנה כבול עליון. אז איך לחשב את הגודל מ חסם תחתון וחסם עליון? 

[קולות חציצה] 

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

תלמיד: האם זה עובד על ידי יצירת משתנה, אני, כי אז אתה רק משמרת העמדה שלי ביחס לשלה מיקום הנוכחי, והאורך, n? 

ג'ייסון הירשהורן: ומה אני? 

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

ג'ייסון הירשהורן: נכון. 

תלמיד: - עד - 

ג'ייסון הירשהורן: אז אני כמעט חיובי שיעבוד. אבל הנקודה הוא, שאתה צריך שני פיסות המידע כאן. אתה יכול לעשות את זה עם התחלה וסוף, או שאתה יכול לעשות את זה עם גודל, ולאחר מכן כמה סמן. אבל אתה צריך לעשות שתי חתיכות מידע כאן. אתה לא יכול להסתדר עם אחד בלבד. האם זה הגיוני? 

אז אנחנו הולכים לעבור, ו אנחנו הולכים לעשות [לא ברורים] וליצור כמה סמנים. אז מה שאתה כותב בקוד שלך? 

תלמיד: אני רק אמרתי int הכפות אחד שווה ל -0. 

ג'ייסון הירשהורן: בואו לקרוא int זה, מתחיל. 

סטודנט: אישור. 

ג'ייסון הירשהורן: זה הופך את יותר הגיוני בשבילי. ו? 

תלמיד: אני אמרתי, אני מניח, int מסתיים. 

ג'ייסון הירשהורן: int מסתיים. 

תלמיד: אני מניח, n מינוס 1, או משהו כזה. כמו, האלמנט האחרון. 

ג'ייסון הירשהורן: אז אתה כתב, int מתחיל שווה 0, פסיק, וint הסוף שווה n מינוס 1, פסיק. אז בעצם, מה שאנחנו עושים כאן, 0 המיקום הראשון. וכמו שאנחנו יודעים במערכים, הם לא הולכים עד n, הם הולכים עד n מינוס 1. אז יש לנו כמה גבולות של המערך שלנו. וגבולות אלה ראשוניים במקרה הגבולות הראשוניים של הבעיה שלנו. על אישור. אז זה נשמע טוב. אז אם נחזור לקו הזה, ואילו אורכה של הרשימה הוא גדול מ 0, מה, במקום n, צריך אנחנו מכניסים לכאן? 

תלמיד: כתוב שהסתיים תחילת מינוס. 

ג'ייסון הירשהורן: בעוד שהסתיים במינוס מתחיל הוא גדול מ 0? על אישור. ואנחנו יכולים, אם אנחנו רוצים לעשות את זה קצת יותר נחמד, מה עוד אנחנו יכולים לעשות? אם אנחנו רוצים לנקות קוד זה קצת? איך אנחנו יכולים להיפטר מ0? זוהי רק שאלת סגנון. זה נכון עכשיו. 

תלמיד: Ending לא תחילת שווה? 

ג'ייסון הירשהורן: אנחנו יכולים לעשות את מה? 

[קולות חציצה] 

סטודנט: סיום הוא גדול יותר? 

ג'ייסון הירשהורן: כן. אנחנו רק יכולים לעשות בזמן שהסתיים גדול מהתחלה. נכון. הוספנו בתחילת לצד השני על כך, ואנחנו נפטרנו מ0. אז זה פשוט נראה מנקה קצת. על אישור. אז, בזמן שאורך הרשימה הוא 0, שכתבנו כי בעוד שהסתיים הוא גדול יותר מהתחלה. אנחנו הולכים לשים בצורך שלנו סוגריים מסולסלים, ואז הדבר הראשון אנחנו רוצים לעשות זה להסתכל על אותם ברשימה קטנה. אתה? אתה יכול לתת לי - 

תלמיד: אם סוגריים סוגר מרובע ערך - 

ג'ייסון הירשהורן: אם סוגריים סוגר מרובע ערך. 

סטודנט: סיום חלקי 2. 

ג'ייסון הירשהורן: סיום? 

תלמיד: אני רואה בעיה עם שלך - 

ג'ייסון הירשהורן: אישור. ובכן, מסתכל על האמצע. איך אנחנו יודעים מה הוא אמצעי? כן. אז הרשה לי להסיר קוד זה. איך אנחנו יודעים מה הוא אמצעי? בכל דבר, כאשר יש לך ההתחלה וסופו של הדבר, איך אתה מוצא האמצע? 

סטודנט: אתה בממוצע. 

סטודנט: אתה מוסיף אותם ביחד ולאחר מכן - 

ג'ייסון הירשהורן: הוסף אותם ביחד ולאחר מכן? 

תלמיד: ואתה בממוצע. לחלק אותו על ידי 2. 

ג'ייסון הירשהורן: הוסף אותם יחד ומתחלקים על ידי 2. אז אמצע int שווה? טום, אתה יכול לתת לי את זה? 

תלמיד: החל מתוספת שהסתיים - 

ג'ייסון הירשהורן: התחלה בתוספת שהסתיים. 

סטודנט: כל, סוגר, מחולק על ידי 2. 

ג'ייסון הירשהורן: כל, בסוגריים, מחולק על ידי 2. אז זה נותן לי באמצע על שום דבר, נכון? 

תלמיד: אתה גם צריך לאסוף אותו. 

ג'ייסון הירשהורן: מה אתה עושה כלומר, אני צריך לאסוף אותו? 

[קולות חציצה] 

תלמיד: כי אם זה מוזר מספר, אז זה כמו - 

ג'ייסון הירשהורן: טוב, בסדר. כדי שאוכל להשלים את זה. אבל אם זה מספר אי זוגי, 5, אני יכול לוקח 1 מהאמצע. או אם זה מספר זוגי, ולא, זה מקרה טוב יותר. אם זה 4, יש לנו 4 בלבד, אני יכול לקחת "באמצע" הראשון, ציטוט, סוף ציטוט או אחד "באמצע". השני כך או יעבדו לחיפוש בינארי, אז אני לא באמת צריך כדי להשלים את זה. אבל יש לי דבר אחד נוסף צריך להסתכל על הקו הזה. אנחנו אולי לא מבינים את זה עדיין, אבל אנחנו עוד נחזור לזה. בגלל הקו הזה למעשה עדיין צריך עוד דבר אחד. 

אבל עד כה, שכתבנו ארבע שורות של קוד. יש לנו ההתחלה שלנו וכלה סמנים. יש לנו בזמן שהלולאה שלנו, הממפה באופן ישיר לpseudocode שלנו. אנחנו מסתכלים על האמצע הממפה ישירות על גבי pseudocode שלנו. הייתי אומר שזה הולך לאמצע מהרשימה, הקו הזה של קוד. ואז, ברגע שאנחנו הולכים לאמצע הרשימה, הדבר הבא שאנחנו צריכים לעשות הוא לבדוק אם הערך שלנו הוא שם בשביל pseudocode שכתבנו קודם לכן. 

אז איך לבדוק אם הערך שלנו הוא באמצע הרשימה? שלך. למה אתה לא עושה את זה? 

תלמיד: אם הערך שלנו הוא באמצע הוא שווה כל מה שאנו קובעים - אני מתכוון שווה שווה ל - 

ג'ייסון הירשהורן: זה - על אישור. 

תלמיד: אני לא בטוח מה משתנה שאנחנו מחפשים לאם כי, הוא כי - 

[קולות חציצה] 

תלמיד: [לא ברור]. 

ג'ייסון הירשהורן: בדיוק. להצהרה על הפונקציה, אנחנו מחפשים ערך. אז אנחנו מחפשים את ערך במערך של ערכים. אז אתה בדיוק נכון. אתה תעשה, אם סוגר ערך paren הפתוח אמצע סגר שווים סוגר שווה ערך, ובפנים יש מה אנחנו צריכים לעשות? אם הערך שלנו שם, מה אנחנו צריכים לעשות? 

[קולות חציצה] 

סטודנטים: להחזיר אפס. 

ג'ייסון הירשהורן: החזר אמיתי. 

תלמיד: החזר אמיתי. 

ג'ייסון הירשהורן: מיכאל, מה הקו הזה עושה? 

תלמיד: [לא ברור] את התכנית יש להפעיל כמובן שלו, וכי הוא מעל, ו יש לך את מה שאתה צריך לעשות? 

ג'ייסון הירשהורן: התכנית או מה? במקרה זה? 

תלמיד: הפונקציה. 

ג'ייסון הירשהורן: הפונקציה. וכך, כדי לחזור לכל מה שנקרא שלו ולתת לו הערך, אמיתי. בדיוק נכון. ראשי. מה סוג ההחזרה מראשי, מייקל? 

תלמיד: int, מספר שלם? 

ג'ייסון הירשהורן: int, בדיוק. מספר שלם. זה היה רק ​​שאלה לוודא אתם כבר על גבי זה. מה זה בדרך כלל לחזור, אם כל הדברים עובדים היטב? 

סטודנט: אפס. 

ג'ייסון הירשהורן: אפס. בדיוק נכון. 

תלמיד: אם זה פשוט מחזיר אמת, אין שום מידע שניתנו על מה - אה, זה רק אומר שזה הערך נמצא בתוך המערך. 

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

תלמיד: לא שאנחנו צריכים כדי לשנות את המערך? זה צריך להיות ערכים, ולא ערך, נכון? 

ג'ייסון הירשהורן: מצטער. תודה. 

סטודנט: כן. 

ג'ייסון הירשהורן: שורה זו צריך להיות ערכים. בדיוק נכון. על אישור. אז בדקנו את הרשימה באמצע. אם תמורת מספר מצא נכון. ממשיך הלאה עם pseudocode שלנו, אם האמצע הוא גדול יותר, חיפוש מהשמאל. אז היה לי בפה, אם מספר גבוה יותר, חיפוש מהשמאל. קונסטנטין, אתה יכול לתת לי הקו הזה של קוד? 

תלמיד: אם ערך של אמצע - 

ג'ייסון הירשהורן: אז אם ערך - אם paren הפתוח ערכי סוגר סוגר קרוב אמצע - 

סטודנט: האם קטן יותר מהערך? 

ג'ייסון הירשהורן: האם פחות מ. 

תלמיד: פחות מהערך. 

ג'ייסון הירשהורן: ערך. טוב, בעצם, אתה רוצה לבדוק אם המספר - סליחה. זה קצת מבלבל. אבל אחר אם המספר ב אמצע הרשימה הוא גדול יותר. 

תלמיד: אה, אוקיי. 

ג'ייסון הירשהורן: אני תשנה את זה. אחר אם האמצע הוא גבוה יותר, אנחנו רוצה לחפש שמאל, בסדר? ומה אנחנו עושים בתוך זה אם מצב? 

תלמיד: האם אני יכול לעשות שינוי קטן כדי המצב, לשנות אותו אחר אם? 

ג'ייסון הירשהורן: Else אם? על אישור. אז את הקוד הזה יהיה לבצע בערך אותו הדבר. אבל הדבר נחמד על שימוש אם, אחר אם, אם, או אם אחר, אם אחר, אחר משמעות הדבר היא כי רק אחד מאותם הוא הולך להיבדק, לא כל שלושה מהם, פוטנציאלי. וזה עושה את זה קצת יותר נחמד במחשב זה הפעלת התכנית שלך. 

אז [? קונסטנטין,?] אנחנו בתוך הקו הזה, אחר אם ערכים, סוגר קרוב באמצע מדרגת גדול יותר מהערך. מה אנחנו צריכים לעשות? אנחנו צריכים לחפש בצד השמאל. איך אנחנו עושים את זה? אני הולך לתת לך התחלה. 

יש לנו שני הדברים האלה בשם מתחיל ומסתיים. אז מה צריך לקרות להתחלה? אם ברצונך לחפש בצד השמאל של רשימה, אנחנו מקבלים ההתחלה הנוכחית שלנו. מה אנחנו צריכים לעשות את זה? 

תלמיד: אנו קובעים את תחילת לאמצע ועוד 1. 

ג'ייסון הירשהורן: אז אם אנחנו חיפוש בשמאל? 

תלמיד: מצטער, מינוס באמצע - כל כך את הסוף יהיה אמצע מינוס 1 ותחילת - 

ג'ייסון הירשהורן: ומה קורה להתחלה? 

תלמיד: הוא נשאר אותו הדבר. 

ג'ייסון הירשהורן: אז משמעות נשארת זהה. אם אנחנו מחפשים שמאלי, אנחנו תוך שימוש באותה ההתחלה - בדיוק נכון. ואת הסוף? סליחה, מה עושה סיום שווה שוב? 

תלמיד: מינוס התיכון 1. 

ג'ייסון הירשהורן: מינוס התיכון 1. עכשיו, למה מינוס 1, ולא רק באמצע? 

תלמיד: באמצע הוא מתוך תמונה כבר, כי היו לנו בדק שזה יצא? 

ג'ייסון הירשהורן: זה בדיוק נכון. האמצע הוא מחוץ לתמונה. אנחנו כבר בדקנו את האמצע. אז אנחנו לא רוצים "האמצע", ציטוט סוף ציטוט, כדי להמשיך להיות ב מערך שאנחנו מחפשים. אז זה פנטסטי. 

אחר אם אמצע סוגר ערכים הוא גדול יותר מהערך שהסתיים בשוויון מינוס אמצע 1. ג'ף, מה עם השורה האחרונה זה? 

תלמיד: Else. אמצע ערכים הוא פחות מהערך? 

ג'ייסון הירשהורן: אנחנו אתה נותן לי אחר. אז אם אתה לא נותן לי - 

תלמיד: אז מתחיל יהיה בינונית בתוספת 1. 

ג'ייסון הירשהורן: שווים החל אמצע בתוספת 1, שוב, מאותה הסיבה שקונסטנטינוס נתן לנו קודם לכן. ובסופו של הדבר, שלא נתן שלי שורת קוד עדיין? בתמורת שווא, שלמה ע"ה, מה אנחנו כותבים כאן? 

תלמיד: בתמורת שווא. 

ג'ייסון הירשהורן: בתמורת שווא. ואנחנו צריכים לעשות את זה, כי אם לא מוצאים את זה, אנחנו צריכים לומר שאנחנו לא מצא אותו. ואנחנו אמרו שאנחנו הולכים לחזור bool, אז בהחלט יש לנו לחזור איפשהו bool. 

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

תלמיד: נקודה ופסיק. 

ג'ייסון הירשהורן: נקודה ופסיק ממש עד כאן. אני חושב שזה היה הקוד של טום. אז טום, [לא ברור]. סתם, בצחוק. בואו אל תעשו את כל זה שוב. 

תלמיד: ספריית Dropbox מה אנחנו צריכים להיות בזה? 

ג'ייסון הירשהורן: אז אתה יכול רק לצפות לזה קצת. אבל שוב, אם אתה רוצה להעביר את זה קוד לתוך ספריית pset3 לנסות את זה, זה מה שאני עשיתי. אם תשים לב כאן - מצטער, שאלה טובה. 

[? LS,?] יש לי כאן את קוד find.c מקוד ההפצה של השבוע. יש לי helpers.h. יש לי קובץ לעשות את זה אני ממש ערך קצת כדי לכלול חדש אלה קבצים שאנחנו כותבים. כל קוד שיהיה זמין, לא קוד ההפצה, אבל חדש להפוך את הקובץ, יהיה קובץ helpers.h החדש יהיה זמין באינטרנט להורדה. שוב, אז אלה הם קודים נוספים שיש לנו. 

אז להפוך את הכל, בכל שורה זו, עושה למצוא, בחירה בינארי, בועה - עושה שלושתם ומכינים ל למצוא את קוד הפעלה זו. אז בדרך כלל, אנחנו לא רוצים כדי ישר לcheck50. אנחנו רוצים להריץ כמה בדיקות על שלנו. אבל רק כדי שנוכל לזרז את זה קצת, pset3.find 2013 check50 יעבור בhelpers.c-- רע. 

אין לי את זה עכשיו. אז אנחנו בעצם הולכים להפעיל את הקוד אמיתי. Usage.find /, אתה יודע מה זה אומר? 

סטודנט: אתה צריך שני שורת הפקודה עליו. 

ג'ייסון הירשהורן: אני צריך שורת הפקודה שנייה. ולפי המפרט, אני צריך להיכנס למה שאנחנו מחפשים. אז בואו נסתכל ל42. אנחנו נשמור אותו במיון, כי אנחנו לא כתב פונקציה מסוג עדיין - 42, 43, 44. 

והבקרה D לא מצא מחט בערימת השחת. זה רע. זה בהחלט שם. בואו ננסה משהו אחר. אולי זה בגלל שאני שם זה בהתחלה. 

בואו נעשה 41, 42, 43. הנה. הוא מצא אותו. בואו תגידו את זה בסוף עכשיו, רק כדי שנוכל להיות יסודי - 40, 41, 42. לא מצא את המחט. אז הזכרתי את זה קודם לכן. לרוע המזל, ידעתי שזה עומד לקרות. 

אבל למטרות פדגוגיות, זה טוב כדי לחקור אותו. זה לא עובד. מסיבה כלשהי, זה לא יכול למצוא אותו. אנחנו יודעים מה יש שם, אבל אנחנו לא מוצאים את זה. אז דבר אחד שאנחנו יכולים לעשות הוא לעבור GDB כדי למצוא אותו, אבל עושה לאף אחד, מבלי לעבור דרך GDB, יש לי תחושה של איפה אנחנו דפוקים? [? Madu? ?] 

תלמיד: אני חושב שזה יכול להיות כאשר מסתיים שווה להתחלה, וזה רק רשימה אחת אלמנט. אז זה פשוט מתעלם ממנה במקום של ממש בודק את זה. 

ג'ייסון הירשהורן: זה בדיוק נכון. כאשר סיום שווה התחלה, אנחנו עדיין יש אלמנט ברשימה שלנו? 

סטודנט: כן. 

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

אבל אם מסתיימים שווה להתחלה, אין תוך לולאה זו לבצע? זה לא. והיינו יכול לבדוק ששוב דרך GDB. אז איך אנחנו יכולים לתקן את הקוד הזה, כי כאשר בזמן הסיום הוא שווה מתחיל, אנחנו גם רוצים את זה בעוד לולאה לרוץ. 

אז מה תיקון שאנחנו יכולים לעשות בשורה 18? 

תלמיד: [לא ברור] הוא גדול יותר או שווה ל. 

ג'ייסון הירשהורן: בדיוק נכון. אמנם הסוף הוא גדול יותר מאשר או שווה להתחלה. אז עכשיו, אנו מקפידים לקבל את זה מקרה פינה בסוף. ובואו נראה. בואו לרוץ עוד פעם אחת זה. 

בואו נעשה את הכל. שוב, יהיה לך רק פעל יחד כאן. מצא 41 הפעם. רק לשמור את זה בקנה אחד. 

מצא 42. בואו תגידו את זה בהתחלה - 42, 43, 44. אנחנו מצאנו אותו. כך שאכן היה השינוי אנחנו צריכים לעשות. 

זה היה הרבה קידודנו פשוט עשה את זה, חיפוש בינארי. האם יש למישהו שאלות לפני אני לעבור לשורות שכתבנו ב חיפוש בינארי או איך שחשבנו מה אנחנו לא להבין? לפני שאנחנו עוברים, אני גם רוצה לציין כי על פי רוב, אנו ממופים פסאודו הקוד שלנו אחד ל אחת על גבי הקוד שלנו. 

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

ואני מוכן להתערב שאתם היה כל הבין את זה די מהר, כי אתה צריך לשים איזשהו סמן לשם כדי להבין איפה אתה היה. כי שוב, הוא בכח של עשייה פסאודו קוד מבעוד מועד. אז אנחנו יכולים לעשות את ההיגיון ראשון, ולאחר מכן אנחנו יכולים לדאוג לתחביר. 

לו הייתי מבולבל לגבי ההיגיון בעת שניסיתי לכתוב את הקוד הזה ב-C, היינו מקבל את כל פישלתי. ואז היינו שואל שאלות על היגיון ותחביר והתמזגות את כולם יחד. ואנחנו היו מקבלים אבודים במה שיכול להפוך במהירות בעיה קשה מאוד. אז בואו נעבור כעת למיון בחירה. 

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

שוב, זה לקוח מתוך בעיה להגדיר מפרט. ערכי int הוא בסוגריים, הוא מערך של מספרים שלמים. וint.n הוא בגודל של מערך זה. מיון בחירה הולך למיין את המערך הזה. 

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

אבל לפני שאנחנו עושים את הקוד כתובענה ב חמש דקות, אנחנו הולכים לכתוב פסאודו קוד, כך שיש לנו איזו תחושה של לאן אנחנו הולכים. אז תנסה לכתוב פסאודו קוד בעצמך. ולאחר מכן תנסה להפוך את זה פסאודו קוד לקוד. אנחנו נעשה את זה כקבוצה בחמש דקות. 

וכמובן, תן לי לדעת אם יש לך שאלות. 

סטודנט: זה זה? 

ג'ייסון הירשהורן: לראות כמה רחוק אתה ניתן לקבל בשתי דקות נוספות. אני מבין שאתה לא יהיה תוכל לסיים. אבל אנחנו נלך על זה כקבוצה. 

אתה כל קידוד כל כך [לא ברור], ולכן אני מצטער להשהות את מה שאתה עושה. אבל בואו נעבור את זה כקבוצה. ושוב, חיפוש בינארי, כל מה שאתה נותן לי אחד לא אם יותר שורות קוד. תודה לך על זה. אנחנו הולכים לעשות את אותו הדבר כאן, קוד יחד כקבוצה. 

אז מיון בחירה - בואו נכתוב כמה פסאודו קוד מהיר. למודל המנטלי, מישהו יכול לתת לי השורה הראשונה של פסאודו קוד, בבקשה? מה אני רוצה לעשות? 

תלמיד: בעוד הרשימה הוא מקולקל. 

ג'ייסון הירשהורן: על אישור, ואילו הרשימה היא לא לפי סדר. ומה זאת אומרת "מקולקל?" 

תלמיד: בעוד [לא ברור] לא עבר מיון. 

ג'ייסון הירשהורן: בעוד הרשימה הוא מקולקל, מה אנחנו עושים? תן לי את השורה השנייה, בבקשה, מרקוס. 

תלמיד: אז למצוא הבא המספר הקטן ביותר. זה יהיה באופן מדורג. 

ג'ייסון הירשהורן: אז למצוא את ליד המספר הקטן ביותר. ואז מישהו אחר? ברגע שאנו מוצאים הבאים הקטנים ביותר מספר, מה אנחנו עושים? אני הולך לומר למצוא המספר הקטן ביותר. זה מה שאנחנו רוצים לעשות. 

אז למצוא את המספר הקטן ביותר. אז מה אנחנו עושים? 

תלמיד: [לא ברור] להתחלה. 

ג'ייסון הירשהורן: סליחה? 

תלמיד: מניחים אותו ב תחילתה של הרשימה. 

ג'ייסון הירשהורן: אז למקם אותו ב תחילתה של הרשימה. ומה שאנחנו עושים את הדבר זה היה בתחילת של הרשימה, נכון? אנחנו להחליף משהו. אז איפה אנחנו שמים את זה? כן, אנה? 

תלמיד: איפה הכי קטן מספר היה? 

ג'ייסון הירשהורן: אז הכניס את תחילת מהרשימה שבה המספר הקטן ביותר היה. אז בזמן שהרשימה היא לא לפי סדר, למצוא המספר הקטן ביותר, למקם אותו תחילתה של הרשימה, לשים את תחילתה של הרשימה שבי המספר הקטן ביותר היה. מרקוס, אתה יכול לנסח מחדש את הקו הזה בעוד שהרשימה היא מקולקל? 

תלמיד: בעוד המספרים לא היה מסודרים? 

ג'ייסון הירשהורן: אוקיי, אז על מנת יודע שהמספרים לא היו מסודרים, מה אנחנו צריכים לעשות? כמה אנחנו צריכים לעבור את הרשימה הזאת? 

תלמיד: אז אני מניח ללולאה, או בזמן, ואילו מספרים שבדקו הוא פחות מאורכה של הרשימה? 

ג'ייסון הירשהורן: בסדר, זה טוב. אני חושב שאני misphrased השאלה שלי בצורה גרועה. אני רק מנסה להגיע אל אנחנו הולכים צריכים ללכת באמצעות כל הרשימה. אז בזמן שהרשימה היא לא לפי סדר, בשבילי, קשה למפה הלאה. אבל בעיקרון, ככה אני חושב על זה. לעבור את כל הרשימה, למצוא את המספר הקטן ביותר, למקם אותו מתחיל - למעשה, אתה צודק. בואו נשים את שניהם. 

אז בזמן שהרשימה היא לא לפי סדר, אנחנו צריך לעבור את כל הרשימה פעם אחת, למצוא את המספר, המקום הקטן ביותר זה בתחילת הרשימה, לשים תחילתה של הרשימה שבי המספר הקטן ביותר היה, ואז אם רשימה היא עדיין מקולקל, יש לנו יש לעבור את זה תהליך שוב, נכון? בגלל זה מיון בחירה, ריצה Big-O של מיון בחירה, מישהו? 

תלמיד: n בריבוע. 

ג'ייסון הירשהורן: n בריבוע. כי כמו מרקוס ורק עכשיו הבינו כאן, אנחנו הולכים צריכים לעבור על רשימת הרשימה מספר פעמים. אז עובר משהו של אורך n מספר הפעמים n הוא למעשה ריבוע n. 

אז זה pseudocode שלנו. זה נראה טוב מאוד. האם יש למישהו שאלות על pseudocode? משום שלמעשה מיון בחירה צריך כנראה מגיע אחד לאחד, את קוד מ pseudocode. אז כל שאלות על היגיון של pseudocode? אנא שאל אותו כעת. 

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

תלמיד: זה ללולאה. 

ג'ייסון הירשהורן: זה נשמע רוצה ללולאה. אוקיי, אתה יכול לתת לי ללולאה? ל-- 

תלמיד: אני שווה 0. 

ג'ייסון הירשהורן: אני או - מה חסר לנו? מה הולך כאן? 

תלמיד: Int. 

ג'ייסון הירשהורן: בדיוק. (אני int = 0; - 

תלמיד: i <n: אני + +). 

ג'ייסון הירשהורן: קטל אותו, ג'ף. אנחנו הולכים ברשימה, נכון? ראינו קוד שלפני כן. מושלם. אז בואו לשים הסוגריים המסולסלים שלנו כאן. אני הולך לשים כמה סוגריים מסולסלים כאן. 

אז בזמן שהוא 0, אנחנו צריכים ללכת דרך את הרשימה כולה. אז בכל פעם שאנו עוברים את הרשימה, מה שאנחנו רוצים לעקוב אחר? 

תלמיד: אם כל חילופים הם עשו. 

ג'ייסון הירשהורן: מצא המספר הקטן ביותר. אז אנחנו כנראה צריכים לעקוב אחר המספר הקטן ביותר בכל פעם. אז קו שאני יכול לעשות כדי לשמור על מסלול של המספר הקטן ביותר? שלמה ע"ה, איך אני יכול לשמור על אחר משהו? 

תלמיד: התחל משתנים חדש. 

ג'ייסון הירשהורן: התחל משתנים חדש. אז בואו ליצור משתנה. איזה סוג? 

תלמיד: Int. 

ג'ייסון הירשהורן: Int. בואו נקראים לזה הקטן ביותר. ומה עושה את זה שווה כש אנחנו רק בתחילת דרך? יש לנו לא עברתי את הרשימה עדיין. אנחנו בחלק הראשון של רשימה בפעם הראשונה שלנו דרך. מה זה שווה, המספר הקטן ביותר? 

סטודנט: ערכי i. 

ג'ייסון הירשהורן: ערכי i. זה נשמע בדיוק כמו שצריך, נכון? המספר הקטן ביותר בתחילת מקום שבו אנחנו נמצאים. אז עכשיו יש לנו הקטן ביותר שלנו, ואנחנו צריכים לעבור את כל הרשימה ו להשוות את זה הקטן ביותר לכל דבר אחר. אז אנחנו עוברים על הרשימה שוב? מייקל? 

סטודנט: אתה צריך לעשות נוסף ללולאה. 

ג'ייסון הירשהורן: נוסף ללולאה. בואו נעשה את זה. תן לי קצת קוד. 

תלמיד: ללולאה - לקטן ביותר - רק Int J, אתה יכול להגיד? = 0; כזה ש-- 

ג'ייסון הירשהורן: ובכן, אם אנחנו רוצים לעבור את כל הרשימה - 

תלמיד: j <n, j + +). 

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

תלמיד: אנחנו יכולים לבדוק אם הקטנים ביותר יש לנו מספר גדול מ ערכי j סוגר. 

ג'ייסון הירשהורן: אז אם הקטן ביותר הוא גדול מ j סוגר ערכים. אז אם הנוכחי הקטן ביותר שלנו גדול מ - אני הולך להעביר את שני הקווים הללו קוד שם בשביל שני. כי לפני שאנחנו עושים בכל החלפה, אנחנו צריך לעבור את כל הרשימה. אז pseudocode זה בעצם צריך להיות מחוץ שפנימי ללולאה. אז לעבור את כל הרשימה. אם הקטן ביותר הוא גדול יותר מאשר j ערכים אז מה? 

תלמיד: ואז הקטן ביותר שווה j ערכים. 

ג'ייסון הירשהורן: מעולה. שאלה אחת מהירה - הפעם הראשונה שאנחנו עוברים את זה לולאה, אני הולך להיות שווה 0, j הולך שווה 0 ברגע שנכנסנו לכאן. אז אנחנו הולכים להיות השוואה מספר לעצמו. האם זה יעיל? לא, זה לא ממש יעיל. אז האם j שלנו צריך ללכת מ -0 עד n בכל פעם? האם אנו תמיד צריכים לבדוק דרך את הרשימה כולה? [לא ברור]? 

תלמיד: התחל עם i במקום. 

ג'ייסון הירשהורן: פחית j להתחיל עם מה? 

תלמיד: i. 

ג'ייסון הירשהורן: j יכול להתחיל עם i. אז עכשיו אנו משווים מתחילים עם אחד אנחנו ב. אבל אפילו אז, הוא שככל יעיל ככל האפשר? 

תלמיד: i + 1. 

נראה אני + 1 להיות: ג'ייסון הירשהורן היעילה ביותר, משום שאנו כבר יש לי. אנחנו לפיו כל הקטן ביותר בשורה 15. אנחנו הולכים להתחיל עם הבא באופן אוטומטי. אז אנחנו עוברים ללולאה. נלך דרך כל זמן. נלך דרך מספר הפעמים. עכשיו אנחנו כבר gotten דרך זה פנימי ללולאה. יש לנו שומר את הערך הקטן ביותר. אנחנו צריכים למקם אותו ב תחילתה של הרשימה. אז איך אני יכול למקם אותו ב תחילתה של הרשימה? מהו משתנה המתייחס לתחילתה של הרשימה? אנחנו בזה מחוץ ללולאה, אז מה מתייחס תחילתה של הרשימה? 

סטודנט: ערכי i. 

ג'ייסון הירשהורן: בדיוק נכון. ערכים היא i תחילת - או מצטער, לא בהתחלה. זה היה מבלבל. זה שבו אנו נמצאים בתחילתו של החלק לא הממוין של הרשימה. אז ערכים שאני. ומה זה שווה? 

תלמיד: הקטן ביותר. 

ג'ייסון הירשהורן: ערכים שאני שווה מה? 

תלמיד: הקטן ביותר. 

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

תלמיד: 0. 

ג'ייסון הירשהורן: קטן מספר זה על 0? 

סטודנט: כן. 

ג'ייסון הירשהורן: מה אם הקטן ביותר מספר היה בסוף רשימה לא ממוינת זה? 

סטודנט: סליחה, מה הייתה השאלה? 

ג'ייסון הירשהורן: איפה הוא המספר הקטן ביותר? לקחנו את הכי קטן ולשים אותו ב מתחיל, עם קו זה ממש כאן. 

תלמיד: זה צריך להיות אוחסן בכמה - 

סטודנט: ערכי j. 

ג'ייסון הירשהורן: ובכן, זה לא בהכרח ערכי j. זה אפילו לא קיים בשלב זה. 

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

ג'ייסון הירשהורן: אז יכול אתה אומר את זה שוב? 

תלמיד: אז איפה אתה הכריז int הקטן ביותר, אתה צריך גם להצהיר על int המדד הקטן ביותר = i, או משהו כזה. 

ג'ייסון הירשהורן: אז איפה אני int הקטן ביותר, אני צריך לעקוב לא רק של הערך אלא המיקום. int smallest_location = בזה מקרה, אנחנו פשוט עושים לי. אנחנו צריכים לדעת איפה זה. יש לנו בסופו של הקוד, ואנחנו הבנתי שיש לנו מושג איפה הוא. וכך שוב, אנחנו מיפוי זה על אחד לאחד. אתם קידוד זה ברצון שלך כנראה להגיע לאותה הבעיה. איך לעזאזל אני מוצא אותו? ואז אתה מבין, חכה, אני צריך לעקוב אחר זה. 

אז אם הקטן ביותר הוא גדול יותר מ י ערכים. אנו קובעים קטן שווים ל j ערכים. מה עוד אנחנו צריכים לשנות? קונסטנטין, מה עוד לעשות אנחנו צריכים לשנות? 

תלמיד: המיקום. 

ג'ייסון הירשהורן: בדיוק. אז תן לי את השורה הזאת בקוד. 

תלמיד: smallest_location = j. 

ג'ייסון הירשהורן: בדיוק. ולאחר מכן נחלש בסוף, אם אנחנו רוצים לשים את תחילתה של הרשימה שבי המספר הקטן ביותר היה, איך אין אנו מתייחסים למקום שבי המספר הקטן ביותר היה? מרקוס? 

תלמיד: המספר הקטן ביותר היה ממוקם במיקום הקטן ביותר. 

ג'ייסון הירשהורן: אז בערכים smallest_location. ומה שאנחנו יכולים לשים שם? תחילת רשימה, מה זה? 

תלמיד: טוב, אנחנו לא באמת יודעים יותר בגלל שאנחנו החלפנו את. אז זה במקומות החליפו משני הקווים האלה? אם תעבור את שני הקווים האלה מסביב. 

ג'ייסון הירשהורן: אוקיי, אז אנחנו לא יותר, כי יש לנו לאפס את השורה לפני ערכי i לקטנה ביותר. אז הפסדנו כי ערך ראשוני. אז אתה אמר החלפת שתי שורות אלה. אז עכשיו לשים את תחילתה של הרשימה שבו המספר הקטן ביותר היה. אז smallest_location שווה ערכי i. זה שזז תחילת חלק לא ממוין של הרשימה כדי המיקום הקטן ביותר. ולאחר מכן לערכים i אנו נעים שהמספר הקטן ביותר. 

האם זה הגיוני למה שאנו נאלץ לבצע החלפה ש? היינו מוחלף ערך ש-- עוד דבר שכנראה יש לך הבין ומצאו בתוצר. אז יש לנו לטפל בן כל pseudocode. האם יש עוד משהו שאנחנו צריך לכתוב כאן? מישהו יכול לחשוב על שום דבר? 

תלמיד: איך אתה יודע כשתסיים? 

ג'ייסון הירשהורן: איך אנחנו יודעים מתי תסיים? שאלה גדולה. אז איך אנחנו יודעים מתי אנחנו סיימנו. 

סטודנט: יצירה משתנה כדי לשמור על ספירה של אם יש החלפה שנעשתה או לא ולעבור את מעבר. 

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

תלמיד: אנחנו יכולים פשוט ללכת עד שזה נגמר. 

ג'ייסון הירשהורן: אנחנו יכולים רק ללכת עד שזה נגמר. במיון בועות, אתה בדיוק נכון, ג'ף ושלמה ע"ה, עם הפתרון שלך - זה נהדר כדי לעקוב אחר כמה חילופים שבצעת, משום שבבועה סוג שהוא, אם אתה עושה למעשה לא עושה שום עסקות החלף, תסיים ואולי אתה יכול לחתוך שלך בעיה קצת למטה. אבל למיון בחירה, יש לך באמת יש לעבור לסוף רשימה כל זמן בסביבה. 

אז זה זה. יש לנו שתי דקות לסיום. בואו נעשה את הכל. תן לי רק פתוח מצא כאן ולעשות בטוח שאני למעשה קורא את - אני לא קורא מיון בועות. בואו תשנה את זה למיון בחירה. לעשות את כל. / למצוא. בואו למצוא 42. הפעם אנחנו הולכים לעבור רשימה לא ממוינת, משום שהוא צריך למיין הראשון, לקוד למצוא - צריך למיין באמצעות הפונקציה ראשונה מהסוג שלנו ולאחר מכן לחפש משהו. אני מחזיק אצבעות לכולם. 

אלוהים אדירים. וואו, הלב שלי דפק. אז זה נכון. למעשה, אם רצנו את זה יותר בהרחבה, את הקוד, עד כמה שאני יכול תגיד, זה נכון באופן מושלם. יש כמה הצעות שיהיה לי בשבילך. לדוגמא, 15 ו16 נראים מיותר קצת. זה נראה כאילו אתה לא בהכרח צריך להציל את שני אלה. אם יש לך את מיקומו הקטן ביותר, אתה בקלות יכול למצוא את הערך הקטן ביותר על ידי פשוט להקליד ערכים של i. 

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

אז לצערנו אנחנו לא להגיע למיון בועות. אני מצטער על זה. עשינו את מיון בחירת גימור. האם יש למישהו שאלות סופיות על מיון בחירה? 

אוקיי, לפני שאנחנו יוצאים, אני רוצה אותך כדי לפתוח את דפדפן Chrome שלך. סליחה, זה היה רק ​​תקע בוטה לסוג אחד של דפדפן אינטרנט. אתה יכול לפתוח כל סוג של דפדפן, אבל זה בטח אהיה Chrome. וללכת לאתר זה הבא - sayat.me/cs50. אם אתה לא מקליד במחשב שלך עכשיו, אתה באופן ברור לא עושה את זה, טום. 

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

ועם דקה אחת שמאלה, זה היה שבוע שלושה. אני אעמוד מחוץ לקצת אם יש לך שאלות. אני אראה לך חבר 'ה ב להרצות מחר.