[השמעת מוסיקה] 

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

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

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

אבל אנחנו יכולים לעשות טובים יותר מחמש מטבעות? האם אנחנו יכולים להיות אפילו חמדניים? ייתכן מאוד. 

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

חזור לנו .32 $. אנו יכולים להשתמש ברבע לתת הלקוחות 0.32 $? כן. שתעזוב אותנו עם $ 0.07 עזבו. 

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

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

אז המטבע הבא בגודל נגיש לנו הוא ניקל. אנו יכולים להשתמש בניקל? כן. ואז היינו צריכים 0.02 $ שנשארו. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שישה מודולו חמש, גם חמישה הולך לשש פעם אחת. ואז זה אחד שנשאר. אז שישה מודולו חמש הוא אחד. 

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

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

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

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

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

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

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

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

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

מיטב של מזל עם p-הסט. ותודה על צפייה. זה היה חמדן. 

[השמעת מוסיקה]