[მუსიკის დაკვრა] Zamyla CHAN: ახლა მოდით დაძლევის Greedy. ამბობენ, რომ თქვენ მოლარე, და თქვენ უნდა მისცეს თქვენს მომხმარებელს გარკვეული ცვლილება. ასევე, თუ თქვენ ხარბ მოლარე, ნეტავ მინდა შენარჩუნება ყველა მონეტები საკუთარ თავს. ასე ნეტავ მისცეს მომხმარებელს მათი ცვლილება გამოყენებით, როგორც რამდენიმე მონეტები, რაც შეიძლება. თქვენი ამოცანაა ამ p-set განხორციელება Greedy, პროგრამა, რომელიც ითვლის მინიმალური რაოდენობა მონეტები გამოყენებულ იქნას, რათა ნებისმიერი მოცემული რაოდენობის ცვლილება. ადრე diving შევიდა პროგრამირების ცნებები და C სინტაქსი Greedy, მოდით პირველ განხილვა მეშვეობით Greedy პროგრამა, და თუ ჩვენ შეუძლია ალგორითმი. გახსოვდეთ, რომ ალგორითმი არის მხოლოდ კომპლექტი ინსტრუქციები პრობლემის გადაჭრის. ალგორითმი Greedy იქნებოდა მხოლოდ მითითებული ლოგიკური წესები და ნაბიჯები, ჩვენ შეგვიძლია მივყვეთ. და ისინი ყოველთვის გამოიღო მინიმალური რაოდენობის მონეტები საჭირო. პირველი, რაც ნეტავ უნდა ვიცი რამდენად შეცვლის კუთვნილს მომხმარებელს. ამ მაგალითად, ვთქვათ, $ 0.32. არსებობს უამრავი გზა დავუბრუნდეთ $ 0.32. თქვენ შეიძლება გამოიყენოთ, მაგალითად, 32 pennies. თუ, თქვენ ცოტა greedier in არჩევის თქვენი მონეტები, თქვენ შეიძლება გამოიყენოთ ხუთი მონეტა ნაცვლად 32 მიცემის მომხმარებელს სამი dimes - $ 0.10 ყოველ - და ორი pennies - $ 0.01 ყოველ. მაგრამ შეგვიძლია გავაკეთოთ უკეთესია, ვიდრე ხუთი მონეტა? შეგვიძლია კი greedier? საკმაოდ შესაძლოა. მოდით, გავაგრძელოთ გავლით Greedy პროგრამა, და ვხედავ. იმ შემთხვევაში, თუ თქვენი საბოლოო მიზანი არის გამოიყენოს რამდენიმე მონეტები ეს შესაძლებელია, მაშინ ეს იქნება ყველაზე გონივრული გამოყენება უდიდესი შესაძლო მონეტები. ნეტავ მისცეს ერთი მეოთხედი უკან - $ 0.25 ყოველ - ვიდრე ხუთი nickels - $ 0.05 ყოველ. ასე რომ, ალბათ, ჩვენი მმართველი წესი Greedy შეიძლება ყოველთვის გამოიყენოს უდიდესი მონეტა შესაძლებელი. აქედან მეოთხედი, dimes, nickels, და pennies, ჩვენი უდიდესი მონეტა კვარტალში. ამიტომ ჩვენ ვცდილობთ გამოვიყენოთ მათ პირველი. უკან ჩვენი $ 0.32. შეგვიძლია გამოვიყენოთ მეოთხედი მისცეს მომხმარებელს $ 0.32? დიახ. რომ დატოვებენ ჩვენს $ 0.07 დატოვა. შეგვიძლია გამოვიყენოთ მეორე კვარტალში? არა, რადგან 25 მეტია შვიდი. ჩვენ არ გვინდა, რათა მომხმარებელს მეტი, ვიდრე ჩვენ ვალში მათ. ყველა უფლება. ახლა, როდესაც ჩვენ ამოწურა ჩვენი კვარტლები, მოდით გადაადგილება, რათა მომდევნო უდიდესი მონეტა, dime. შეგვიძლია გამოვიყენოთ dime მისცეს მომხმარებელს მათი $ 0.07 უკან? არა, რადგან 10 არის უფრო მეტი, ვიდრე შვიდი. ასე რომ მომდევნო უდიდესი მონეტა ხელმისაწვდომი ჩვენთვის არის ნიკელს. შეგვიძლია გამოვიყენოთ ნიკელის? დიახ. და მაშინ ჩვენ ავღნიშნო აქვს $ 0.02 დარჩენილი. ჩვენ არ შეგვიძლია გამოვიყენოთ ნიკელის დაბრუნების $ 0.02. ასე რომ, ჩვენ გადავიდა უკანასკნელი მონეტა at ჩვენს ხელთ - Penny. და შემდეგ გამოყენებით ორი pennies, ჩვენ მინდა იყოს მარცხენა ნულოვანი ცენტი, რაც იმას ნიშნავს, ჩვენ წარმატებით გადახდილი უკან მომხმარებელს მათი ცვლილება კუთვნილს იყენებს მხოლოდ ოთხი მონეტები - ერთი მეოთხედი, ერთი ნიკელის, და ორი pennies. თქვენ შეგიძლიათ აწარმოებს პერსონალის გადაწყვეტა თუ ჩვენი ხელმძღვანელი წესი და პროცესში მისცა us სწორი პასუხი. ყველაზე პრობლემა კომპლექტი, თქვენ გექნებათ აწარმოებს პერსონალის გადაწყვეტა, თუ რამდენად საკუთარი პროგრამა უნდა იმუშაოს. და კონკრეტული მითითებები იყოს პრობლემა კომპლექტი specs. მას შემდეგ, რაც ჩვენ აწარმოებს პერსონალის გადაწყვეტა, ეს თხოვს us რამდენად შეცვლის კუთვნილს აღნიშნავენ, რომ ითხოვს თანხა დოლარი. ჩვენ input $ 0.32, 0.32. იგი გვეუბნება, რომ ოთხი მონეტები კუთვნილს, შეესაბამება ჩვენი პასუხი. Fantastic. ახლა მოდით დავიწყოთ ეძებს at განხორციელების საქართველოს ხარბ ალგორითმი. ჩვენ ვიცით, რამდენიმე რამ. ერთი, რომ ჩვენ უნდა უბიძგონ პროფაილი თანხის ცვლილება. ორი, რომ ჩვენ გვინდა, რომ დაიცვას ჩვენი მმართველობის წესის ყოველთვის გამოიყენოს უდიდესი მონეტა შესაძლებელი. და სამი, რომ ჩვენ უნდა ტრეკზე რამდენი მონეტები ვიყენებთ. იმის გამო, რომ ბოლოს, ჩვენ უნდა ბეჭდვა რაოდენობის მონეტები, რომ ჩვენ. პირველი, რითაც შესახებ ამისთვის თანხის ცვლილება. როდესაც თქვენ გაუმკლავდეთ მომხმარებლის input, რათა დარწმუნდით, რომ თქვენ ვფიქრობ ყველა მოთხოვნები input, და მხოლოდ მიიღოს შეყვანის რომელიც აკმაყოფილებს იმ მოთხოვნები. ამ შემთხვევაში, ჩვენ გვინდა, რომ გაუმკლავდეთ ფულადი ღირებულების დოლარი. GetFloat და GetInt ფუნქციების უზრუნველსაყოფად რომ შეყვანის numeric. მაგრამ მომხმარებელს შეუძლია შეყვანის უარყოფითი რიცხვითი ღირებულებებს. ასე მახსოვს, მხოლოდ არასამთავრობო უარყოფითი პორტები, რომელიც მოიცავს ყველა უარყოფითი ციფრები და ნულოვანი. ამ შემთხვევაში, შემავალი უნდა იყოს float. სხვა სიტყვებით, ათობითი რიცხვი. იმის გამო, რომ პრობლემა კომპლექტი სპეც მოითხოვს თქვენ მოითხოვოს შეყვანის დოლარი. მაგრამ C, მცურავი პუნქტიანი ღირებულებებს ვერ წარმოდგენილი იქნება ზუსტად. რადგან არსებობს სასრული რაოდენობის ბიტი, რომელიც წარმოადგენს უსასრულო ღირებულებებს. მიიღეთ ნომერი 0.1. მე რომ გთხოვოთ, რომ წერენ 0.1 by ხელი მეასედ ათობითი ადგილი, თქვენ უნდა დაწეროთ 1, მოყვება 99 zeroes. ჩვენ მინდა ველით, რომ ჩვენი კომპიუტერი იქნება ბეჭდვა ზუსტად იგივე რამ თუ ჩვენ ვთხოვეთ მას. მოდით ვნახოთ, თუ რას აკეთებს. მე განიხილავს ბეჭდვა ფასეულობების მიმართ ბოლოს გავლა. ახლა, აქ რომ f% არის placeholder for მცურავი წერტილი. მაგრამ ჩვენ მიუთითოთ წინასწარ, რომ ჩვენ გვინდა 100 decimals ნაჩვენები, და შემდეგ ახალი ხაზი გავალამაზოთ გაფორმებით. მას შემდეგ, string, ვირჩევთ 0.1 როგორც ათწილადი, რომ ჩვენ გვინდა ამობეჭდოთ. და შედეგი, ერთი, რასაც ზოგიერთი zeros, მაგრამ შემდეგ მთელი bunch of ნომრები. რა თქმა უნდა, არ არის, როგორც მოსალოდნელი იყო. მცურავი პუნქტიანი ორაზროვნება შეუძლია გააცნოს დამრგვალება შეცდომები თქვენს გათვლებით, რომ თქვენ აუცილებლად გვინდა თავიდან ავიცილოთ. თუ გვინდა, რომ მეტი მაგალითები, თქვენ შეგიძლიათ ჩამოტვირთოთ imprecision.ce საწყისი გავლა კოდი, რომელიც არის მარტივი პროგრამა, რომელიც სთხოვს float და ბეჭდავს ეს უკან მეასედ ათობითი ადგილი. რა თქმა უნდა, თუ გსურთ ნახოთ მეტნაკლებად ათობითი ადგილებში თქვენ შეგიძლიათ შეცვალოთ საკუთარ თავს. როგორც თქვენ ნახავთ, რომ განსხვავება ორ არის პატარა, როდესაც თქვენ to გამრავლებით და დასძინა, მოძრავი, რომ განსხვავება შეიძლება საბოლოოდ დაამატოთ მდე. დასაწყისზე Greedy. ჩვენ გვინდა, რომ თავიდან ავიცილოთ დამრგვალება შეცდომები by საქმე მთელი ნომრები. ასე რომ, შემდეგ მივიღებთ ძალაშია შეიტანენ შესახებ, მოდით გადაიყვანოთ ამ დოლარი ღირებულება ცენტი. გონებრივად ჩვენ ამისათვის გამრავლებით დოლარის ღირებულების 100. მაგრამ მახსოვს, იმიტომ, რომ მცურავი წერტილი ორაზროვნება, ჩვენ გვსურს დარწმუნებული ვარ, რომ ჩვენ იყენებთ სწორი მნიშვნელობა. გამრავლებით 100 არსებითად გადავა ათობითი ადგილზე ორი ფართები მარჯვენა, chopping off ან truncating არაფერი შემდეგ. თუ თქვენ ითამაშოს გარშემო კიდევ რამდენიმე მაგალითები, თქვენ ნახავთ, რომ თქვენ არ ყოველთვის მაქვს უფლება, თუ თქვენ ამ მეთოდის გამოყენება truncating. მაგალითად, 12.59 ბეჭდური 100 ათობითი ადგილებში, რომელიც გაძლევთ 12,5899, et cetera. ნეტავ კიდევ 12,58 თუ truncated, არ 12.59, ისევე, როგორც თქვენ გჭირდებათ. სამაგიეროდ, ეს საუკეთესო გარშემო პირველი ნომერი. საბედნიეროდ, C გააჩნია ფუნქცია მოუწოდა რაუნდი. ეს არის მათემატიკის ბიბლიოთეკაში. თუ გსურთ ვიცით, როგორ გამოვიყენოთ რაუნდი, მაშინ თქვენ შეგიძლიათ ზრდიან სახელმძღვანელო, ან კაცი გვერდზე რომ ფუნქცია. თქვენ ამ აკრეფით კაცი, მოკლე სახელმძღვანელო, და შემდეგ ფუნქცია, რომ თქვენ გვინდა გამოიყურებოდეს up. ასე აკრეფით კაცი რაუნდი შევიდა ტერმინალში ბრძანების გამოიტანს სახელმძღვანელო. ეს შეიძლება იყოს ცოტა რთულია decipher, მაგრამ საბოლოოდ თქვენ შეეგუონ მას. კაცი გვერდებზე ნახოთ თუ რა ფუნქცია აკეთებს, და შემდეგ რამდენიმე შესაძლო გამოყენებისათვის იგი. მე დატოვება თქვენ შეისწავლონ კაცი გვერდზე რაუნდი. მაგრამ ვიცით, რომ თქვენ შეგიძლიათ გამოიყენოთ ის გარშემო ღირებულება დროს კონვერტაცია დოლარი ცენტი. მრგვალი მოგცემთ უკან ნომერი მონაცემთა type ორმაგი. და თქვენ შეგიძლიათ გადაიყვანოთ ან მსახიობი მას int შემდეგ. დიდი. ახლა ჩვენ აიძულა შესახებ ამისთვის ფულადი თანხა, და გადაიყვანება ის ცენტი. ახლა ჩვენ შეგვიძლია განახორციელოს ალგორითმი რომ ყოველთვის იყენებს ყველაზე დიდი მონეტა შესაძლებელი. გაითვალისწინეთ, რომ არსებობს მრავალი როგორ უნდა განხორციელდეს Greedy, ისევე, როგორც არსებობს მრავალი გზა მიახლოება ყველა კომპიუტერულ მეცნიერებათა პრობლემა. მოძიებაში ყველაზე უფრო ელეგანტურ გზა, რომ fun ნაწილი. მთელი ამ p-კომპლექტი, თუ თქვენი პროგრამა ზუსტად არ ემთხვევა ჩემი ახსნა walkthroughs, რომ კარგადაა. მაგრამ უბრალოდ დარწმუნდით, რომ ის გადის შემოწმება 50, აკმაყოფილებს ყველა მოთხოვნების ჩამოყალიბება სპეციფიკაციები, და რომ თქვენ განიხილოს თუ არა თქვენი მიდგომა აქვს კარგი დიზაინი. სხვა სიტყვებით, თუ რამდენად ეფექტური არის ეს? მაგალითად, თუ ჩაწერეთ განმეორებითი კოდი ხაზები, ნაცვლად გამოყენებით loop? წერა კოდი უკეთესი დიზაინი მოდის გამოცდილება, როგორც თქვენ პროგრესის მეშვეობით რა თქმა უნდა. ამ გავლა, მე წასვლა მეტი ორი მეთოდები, რომ შეიძლება გამოყენებულ იქნას შეავსოთ Greedy. პირველი მეთოდი არის მეთოდი მარყუჟების და გამოკლება. ადრე, როდესაც ჩვენ ვისაუბრეთ მეშვეობით Greedy პროცესი, ჩვენ მუდმივად შემოწმდება თუ არა ჩვენ შეგვიძლია გამოვიყენოთ კვარტალში, და გამოიყენება მეოთხედი სანამ ღირებულება დარჩენილი ნაკლები იყო $ 0.25. ეს ითარგმნება კარგად ხოლო loop სტრუქტურა. მიუხედავად იმისა, რომ შეგიძლიათ კვლავ გამოიყენოთ კვარტალში, გამოიყენოთ ერთი. რომ სანამ loop უნდა შეასრულოს მანამ, როგორც დარჩენილი მნიშვნელობა მეტია ან ტოლია კვარტლის cent ღირებულება. ეს იმას ნიშნავს, რომ თქვენ ასევე მინდა ტრეკზე დარჩენილი ნაღდი ღირებულება, და განახლება ყოველ დრო, რომ გამოიყენოთ მონეტა. ასევე გახსოვდეთ, რომ დასასრულს, თქვენი გამომავალი რაოდენობის მონეტები გამოიყენება. ასე რომ, კიდევ ერთი რამ ტრეკზე არის რაოდენობის მონეტები, რომ გამოიყენოთ. თქვენ შეგიძლიათ შეინახოთ სიმღერა ამ გამოყენებით კარგად დაასახელა ცვლადები. და შიგნით ორგანოს თქვენი loop იქნება იქნება განახლება იმ ცვლადების. მას შემდეგ, რაც მარყუჟის კვარტალში დასრულდება, თქვენ შეგიძლიათ გამოიყენოთ მსგავსი ერთი dimes, და ასე შემდეგ და ასე შემდეგ, სანამ თქვენ დაბრუნდა ყველა ნაღდი. მე დაწერილი ზოგიერთი ფსევდო კოდი აქ დაგეხმარებათ ვიზუალიზაციისთვის, თუ რამდენად პროცესი განვიხილეთ შეიძლება თარგმნოს C. როგორც ხედავთ აქ, მე ჯერ კიდევ გამოყენებით ინგლისური სიტყვა. ეს არ არის C არავის გაუკეთებია. მაგრამ მე დაიწყო აბზაცის რამ. მე დააყენა პირობებში შიგნით ჩემი ფრჩხილებში. ის იწყებს გამოიყურებოდეს პატარა ცოტა მოსწონს პროგრამირების კოდი. ფსევდო კოდი არის დიდი გზა მისაღებად დაიწყო. ვიზუალიზაციისთვის თქვენი კოდი ადრე თქვენ ეძებოთ სინტაქსი. რადგან ხშირად უმძიმესი ნაწილი შესახებ პრობლემა მართლაც გაგება, თუ რა ზუსტად თქვენ უნდა გავაკეთოთ. მას შემდეგ წერთ, რომ ქვემოთ, მაშინ ის ბევრი ადვილია ეძებოთ ფუნქციები და სინტაქსის სპეციფიკური თქვენი ონლაინ ფსევდო კოდი გაითვალისწინეთ, რომ ეს არ შეიძლება იყოს იდენტური სახის ჩონჩხი თქვენი კოდი რომ წერთ. ყოველთვის არსებობს ოპტიმიზაციით უნდა განხორციელდეს. და, განსაკუთრებით, ჩემი ფსევდო კოდი აქ, თუ შეგიძლიათ მიხვდებიან, რაშია საქმე. მაგრამ არსებითად პროცესი და აზროვნებას ისევე, როგორც ჩვენ განვიხილეთ. პირველი ხაზი გვეუბნება, რომ მიიღოს გარკვეული თანხის დოლარი. და მეორე გვეუბნება გადაიყვანოთ იგი ცენტი. და შემდეგ, ხოლო მეოთხედი შეიძლება გამოყენებულ იქნას, ჩვენ გსურთ გაზარდოთ მონეტის რაოდენობა და შემცირდება ფულადი თანხა. იგივე ეხება dimes, nickels, და pennies. და ბოლოს, ჩვენ გითხრათ შესახებ რამდენი მონეტები გამოვიყენეთ. დიდი. ასე რომ, ასკვნის loop მეთოდით. ახლა მოდით ვისაუბროთ მოდულარული მეთოდი, რაც უფრო გაყოფა. ჩვენ ყველა იცნობს პლუს, მინუს, გამრავლება და გაყოფა ოპერატორები ჩვენს ხელთ არსებული. C აქვს ოთხივე იმ, მაგრამ ასევე აქვს modulo ოპერატორი, რომელსაც წარმოადგენს პროცენტი ნიშანი. Modulo მართლაც სისუფთავე. ეს გაძლევთ დარჩენილი დან გამყოფი ორი ნომერი. დამახსოვრება ხანგრძლივი სამმართველოს როდესაც თქვენ დაყოფის, ვთქვათ, 74 სამი? დაწყებული ათობით ადგილი, თქვენ ვიცი, რომ 3 გადადის შვიდი ორჯერ, რათა ექვსი დარჩენილი ერთი. ნეტავ დაწერა ორი ზედა, და შემდეგ სხვაობა 6 შვიდი, ტარების მეტი დარჩენილი 14 ვიმეორებ პროცესში. სამი გადადის 14 ოთხჯერ მიიღოს 12, დანარჩენი ორი. და ორი არ განახორციელოს მეტი აღარ. ასე რომ, ორი იქნება დატოვეს ბოლოში დარჩენილი. და ეს რა modulo იძლევა, თქვენ რომ ნომერი ბოლოში. ასე რომ 74 modulo სამი მისცემს თქვენ ორი. 10 Modulo ორი, ისე, რომ მისცემს თქვენ ნულოვანი. იმის გამო, რომ არ არსებობს რაიმე ნაშთი როდესაც თქვენ დაყოფის 10 ორი. ექვსი modulo ხუთი, კარგად ხუთ გადადის ექვსი ერთხელ. და მერე უკვე ერთი დარჩენილი. ასე ექვსი modulo ხუთ ერთი. თუ თქვენ გაქვთ შვიდი modulo ცხრა, ნეტავ კიდევ შვიდი. იმის გამო, რომ ცხრა მეტია, ვიდრე შვიდი. ასე რომ არ ყოფს მას ყველა შევიდა შვიდი, ტოვებს შვიდი რადგან თქვენი პასუხი. თუ ფიქრობთ Modulo ცოტა მეტი, გახსოვდეთ, რომ იგი გაძლევთ დანარჩენი შემდეგ თქვენ გაყოფა რაღაც. ვიფიქროთ, თუ როგორ შეიძლება შეუძლია გამოიყენოს იგი ხარბ. ვთქვათ პროფაილი სთხოვს for $ 400,11. რა გზა გაერკვნენ, თუ რამდენი მეოთხედი გჭირდებათ გარეშე იმედი თითოეული? ერთხელ თქვენ გაერკვნენ, თუ რამდენი მეოთხედი თქვენ შეგიძლიათ გამოიყენოთ, რათა $ 400,11, რამდენად შეცვლის ნაშთები? ალბათ კომბინაცია აქ შორის modulo და გაყოფა მოვიდოდა მოსახერხებელი გადმოგცეთ მაგარი, დახვეწილი მიუახლოვდნენ Greedy პრობლემა. მაგრამ გვახსოვდეს, რომ მმართველი წესი მაინც ვრცელდება. ყოველთვის გამოიყენეთ უდიდესი მონეტა შესაძლებელი. ერთხელ თქვენ კეთდება გაანგარიშება როგორ ბევრი მონეტები გამოყენება, ბოლო ნაბიჯი არის ამობეჭდოთ ნომერი მონეტები, რომ თქვენ გათვლილი. ჯერჯერობით, ჩვენ უკვე გამოყენებით printf ფუნქციონირებს მხოლოდ სიმები. მაგრამ როდესაც თქვენ გსურთ ამობეჭდოთ, ან უბრალოდ ნებისმიერი სახის მონაცემები, რომელიც ინახება ცვლადი, თქვენ უნდა მიუთითოს რომ გამოყენებით placeholder. აქ მე შედის მხოლოდ რამდენიმე რჩევა როგორ უნდა ამობეჭდოთ ღირებულებებს. თუ თქვენ გაქვთ რიცხვი, თქვენ ამას დაწერეთ თქვენი string გამოყენებით% d, როგორც placeholder. დახურვის შემდეგ ციტატა მარკა, შეიყვანეთ მძიმით. და შემდეგ დააყენა მთელი რიცხვი, რომელიც მიიღოს ადგილის% d როდესაც იბეჭდება. ამიტომ მას შემდეგ, ჩვენებისას ნომერი მონეტები გამოყენებული, თქვენ დასრულდა Greedy. დარწმუნდით, რომ შეამოწმოს ყველა კუთხეში შემთხვევაში, tidy up თქვენი სტილი ცოტა, და თქვენ ყველა მითითებული წარმოადგინოს. ბოლოს, ეს პრობლემა კომპლექტი, თქვენ იყოს უფრო იცნობს CS50 მოწყობილობების, ტერმინალში და loop კონსტრუქციები და ცვლადები in C. თქვენ კარგად თქვენს გზა. სასწავლო მრუდი შეიძლება ჩანს მკაცრი. ასე რომ, ეტაპობრივად. დარწმუნდით, რომ თქვენ წერენ გარეთ ფსევდო კოდი ადრე diving ძალიან ღრმა თარგმნეს უცხო სინტაქსი. მიიღოს გავაკეთოთ სია, და გაწყვეტის დავალება შევიდა პატარა, უფრო მართვადი ამოცანები. შეისწავლონ ყველა CS50 რესურსები. გარდა იმისა, რომ ლექციის rewatch ამ გავლა. გადაიხადოს ყურადღებას მონაკვეთზე. შეამოწმეთ შორტები. წავიკითხე თქვენი თანაკლასელები კითხვებს on საუბარი, და გამოაქვეყნოთ თქვენი საკუთარი. საუკეთესო გისურვებთ p-set. და მადლობა თვალს. ეს იყო Greedy. [მუსიკის დაკვრა]