>> [MUSIC CHƠI]
>> ZAMYLA CHAN: Bây giờ chúng ta hãy giải quyết tham lam.
Giả sử bạn là một nhân viên thu ngân, và bạn cần phải cung cấp cho khách hàng của bạn một
số tiền nhất định của sự thay đổi.
Vâng, nếu bạn là một nhân viên thu ngân tham lam, bạn muốn giữ tất cả
các đồng tiền cho chính mình.
Vì vậy, bạn muốn cung cấp cho khách hàng của họ thay đổi sử dụng như là vài đồng xu càng tốt.
>> Nhiệm vụ của bạn cho điều này p-bộ là thực hiện Tham lam, một chương trình
tính toán số lượng tối thiểu đồng tiền được sử dụng để thực hiện bất kỳ
cho số lượng thay đổi.
Trước khi lặn vào các chương trình khái niệm và cú pháp C cho tham lam,
chúng ta hãy nói chuyện đầu tiên qua tham lam chương trình, và xem chúng ta
có thể xác định một thuật toán.
Hãy nhớ rằng một thuật toán chỉ là một tập hợp các
hướng dẫn giải quyết vấn đề.
Một thuật toán để tham lam sẽ chỉ được một thiết lập các quy tắc hợp lý và bước
chúng ta có thể làm theo.
Và họ sẽ luôn luôn mang lại tối thiểu số tiền cần thiết.
>> Điều đầu tiên bạn cần phải biết là bao nhiêu thay đổi
nợ cho khách hàng.
Trong ví dụ này, chúng ta hãy nói $ 0,32.
Có rất nhiều cách để lấy lại $ 0,32.
Bạn có thể sử dụng, ví dụ, 32 đồng xu.
Hoặc nếu bạn là một chút tham lam trong lựa chọn đồng tiền của bạn, bạn có thể sử dụng
năm tiền xu thay vì 32 bằng cách cho khách hàng ba dimes -
$ 0.10 mỗi - và hai đồng xu - $ 0,01 mỗi.
>> Nhưng chúng ta có thể làm tốt hơn so với năm tiền xu?
Chúng ta có thể thậm chí tham lam?
Hoàn toàn có thể.
>> Chúng ta hãy tiếp tục đi bộ qua chương trình tham lam, và nhìn thấy.
Nếu mục tiêu cuối cùng của bạn là sử dụng một vài đồng xu càng tốt, sau đó nó sẽ nhất
thận trọng để sử dụng lớn nhất đồng tiền có thể.
Bạn không muốn cung cấp cho một phần tư sao - 0,25 $ mỗi -
hơn năm nickels -
$ 0,05 mỗi.
Vì vậy, có lẽ quy tắc quản trị của chúng tôi cho Tham lam có thể luôn luôn sử dụng
đồng tiền lớn nhất có thể.
Ra các khu, dimes, nickels, và đồng xu, chúng tôi
đồng xu lớn nhất là quý.
Vì vậy chúng tôi sẽ cố gắng sử dụng chúng đầu tiên.
>> Sao để chúng tôi $ 0,32.
Chúng ta có thể sử dụng một phần để cung cấp cho khách hàng 0,32 $?
Vâng.
Mà sẽ để lại cho chúng tôi với 0,07 $ trái.
>> Chúng ta có thể sử dụng quý khác?
Không, bởi vì 25 lớn hơn bảy.
Chúng tôi không muốn cung cấp cho khách hàng bất kỳ nhiều hơn chúng ta nợ họ.
>> Được rồi.
Bây giờ chúng ta đã kiệt sức quý của chúng tôi, chúng ta hãy chuyển sang lớn nhất tiếp theo
đồng xu, đồng xu.
Chúng ta có thể sử dụng một xu để cung cấp cho các khách hàng của họ 0,07 $ trở lại?
Không, kể từ 10 lớn hơn bảy.
>> Vì vậy, sau đó là xu lớn nhất tiếp theo truy cập cho chúng tôi là niken.
Chúng ta có thể sử dụng một niken?
Vâng.
Và sau đó chúng ta sẽ có 0,02 $ còn sót lại.
>> Chúng ta không thể sử dụng một niken để trả lại $ 0,02.
Vì vậy, chúng tôi di chuyển đồng xu cuối cùng tại xử lý của chúng tôi - các penny.
Và sau khi sử dụng hai đồng xu, chúng tôi muốn được trái với không xu, có nghĩa là
chúng tôi đã thanh toán thành công trở lại người sử dụng thay đổi của họ còn nợ
sử dụng chỉ có bốn đồng tiền -
một phần tư, một niken, và hai đồng xu.
>> Bạn có thể chạy các giải pháp nhân viên để xem nguyên tắc quản trị của chúng tôi và quá trình đưa
chúng ta câu trả lời đúng.
Đối với hầu hết các bộ vấn đề, bạn sẽ có thể để chạy các giải pháp nhân viên để xem như thế nào
chương trình của bạn nên làm việc.
Và hướng dẫn cụ thể sẽ được trong vấn đề thiết lập thông số kỹ thuật.
>> Một khi chúng ta chạy các giải pháp, nhân viên nhắc nhở chúng ta cho bao nhiêu thay đổi được nợ
lưu ý rằng nó yêu cầu số tiền bằng đô la.
Chúng tôi đầu vào $ 0,32, 0,32.
Nó cho chúng ta biết rằng bốn đồng tiền đang nợ, phù hợp với câu trả lời của chúng tôi.
Tuyệt vời.
>> Vì vậy, bây giờ chúng ta hãy bắt đầu tìm kiếm vào thực hiện
của thuật toán tham lam.
Chúng tôi biết một vài điều.
Một, chúng ta sẽ cần phải nhắc nhở người người sử dụng cho một số lượng thay đổi.
>> Hai, chúng ta sẽ phải thực hiện của chúng tôi quản lý quy tắc để luôn luôn sử dụng
đồng tiền lớn nhất có thể.
Và ba, chúng ta cần phải theo dõi bao nhiêu tiền chúng tôi sử dụng.
Bởi vì cuối cùng, chúng ta cần phải in số tiền mà chúng tôi.
>> Đầu tiên, khiến người sử dụng cho một số lượng thay đổi.
Bất cứ khi nào bạn đối phó với người sử dụng, làm cho chắc chắn rằng bạn nghĩ về tất cả các
yêu cầu của đầu vào, và chỉ chấp nhận đầu vào đáp ứng những
yêu cầu.
Trong trường hợp này, chúng tôi muốn để đối phó với giá trị tiền tệ bằng đô la.
>> Các chức năng GetFloat và getInt đảm bảo mà đầu vào là số.
Nhưng người dùng có thể nhập giá trị số âm.
Vì vậy, hãy nhớ chỉ sử dụng không âm đầu vào, trong đó bao gồm tất cả các tiêu cực
số và số không.
>> Trong trường hợp này, các đầu vào nên được một phao.
Nói cách khác, một số thập phân.
Vì spec vấn đề thiết lập yêu cầu bạn yêu cầu đầu vào bằng đô la.
>> Nhưng trong C, giá trị dấu chấm động có thể không được đại diện một cách chính xác.
Bởi vì có một số hữu hạn bit mà để
đại diện cho các giá trị vô hạn.
Có số lượng 0.1.
Nếu tôi được yêu cầu bạn viết bằng 0.1 tay đến chữ số thập phân trăm,
bạn sẽ viết một 1, tiếp theo 99 zero.
Chúng tôi hy vọng rằng máy tính của chúng tôi sẽ in một điều chính xác
nếu chúng ta hỏi nó.
>> Vì vậy, chúng ta hãy xem những gì nó làm.
Tôi sẽ xem xét các giá trị in ấn theo hướng cuối này đi qua.
Bây giờ, thấy ở đây f% là giữ chỗ cho một điểm nổi.
Nhưng chúng tôi xác định trước mà chúng tôi muốn 100 chữ số thập phân hiển thị, và sau đó mới
dòng để định dạng đẹp hơn.
>> Sau chuỗi, chúng tôi chọn 0.1 là nổi mà chúng ta muốn in ra.
Và kết quả, một, tiếp theo một số số không, nhưng sau đó một
bó toàn bộ các con số.
Chắc chắn không như mong đợi.
>> Dấu chấm động không chính xác có thể giới thiệu làm tròn lỗi vào của bạn
tính toán rằng bạn sẽ chắc chắn muốn tránh.
Nếu bạn muốn xem thêm các ví dụ, bạn có có thể tải về từ imprecision.ce
đi bộ qua mã, mà là một đơn giản chương trình yêu cầu nổi và in nó
trở về vị trí số thập phân trăm.
Tất nhiên, nếu bạn muốn hiển thị ít nhiều chữ số thập phân
bạn có thể thay đổi chính mình.
>> Như bạn sẽ thấy, mặc dù sự khác biệt giữa hai là nhỏ, khi bạn nhận được
để nhân và thêm nổi, mà sự khác biệt cuối cùng có thể tăng lên.
Sao để tham lam.
Chúng tôi sẽ muốn tránh các lỗi làm tròn bằng cách giao dịch với các số nguyên.
Vì vậy, sau khi chúng tôi có được đầu vào có giá trị từ người sử dụng, chúng ta hãy chuyển đổi này
giá trị đồng đô la xu.
>> Tinh thần, chúng tôi làm điều này bằng cách nhân giá trị đồng đô la 100.
Nhưng hãy nhớ, vì điểm nổi không chính xác, chúng tôi muốn chắc
chắc chắn rằng chúng ta đang sử dụng giá trị quyền.
Nhân với 100 về cơ bản sẽ di chuyển số thập phân hai không gian để
bên phải, cắt bỏ hoặc cắt xén bất cứ điều gì sau đó.
>> Nếu bạn chơi xung quanh với một số chi tiết ví dụ, bạn sẽ thấy rằng bạn sẽ không
luôn luôn có số bên phải nếu bạn sử dụng phương pháp này cắt xén.
Ví dụ, 12,59 in đến 100 chữ số thập phân, cung cấp cho bạn
12,5899, vân vân.
Bạn sẽ nhận được 12,58 nếu bạn cắt ngắn, không 12.59, như bạn cần.
>> Thay vào đó, cách tốt nhất để làm tròn số đầu tiên.
May mắn thay, C đi kèm với các chức năng gọi là Vòng.
Đó là trong thư viện toán học.
>> Nếu bạn muốn biết làm thế nào để sử dụng Round, sau đó bạn có thể mang đến hướng dẫn hoặc
trang người đàn ông cho chức năng đó.
Bạn làm điều này bằng cách gõ người đàn ông, viết tắt dẫn sử dụng, và sau đó là chức năng mà bạn
muốn tìm.
Vì vậy việc đánh vòng người đàn ông vào nhà ga dòng lệnh sẽ mang đến hướng dẫn.
>> Nó có thể là một chút khó khăn để giải mã, nhưng cuối cùng bạn sẽ thấy
nhận được hang của nó.
Trang người đàn ông cho bạn những gì các chức năng không có gì, và sau đó một số
sử dụng có thể có của nó.
Tôi sẽ để lại cho bạn để khám phá trang người đàn ông cho tròn.
Nhưng biết rằng bạn có thể sử dụng nó để làm tròn giá trị trong quá trình chuyển đổi của bạn từ
đô la để xu.
>> Vòng sẽ cung cấp cho bạn lại một số của kiểu dữ liệu gấp đôi.
Và bạn có thể chuyển đổi hoặc diễn viên nó đến một int sau đó.
Tuyệt vời.
Bây giờ chúng tôi đã nhắc nhở người sử dụng cho một số lượng tiền tệ, và
chuyển đổi nó thành xu.
Bây giờ chúng ta có thể thực hiện một thuật toán mà luôn luôn sử dụng
đồng tiền lớn nhất có sẵn.
>> Hãy nhớ rằng có nhiều cách để thực hiện tham lam, giống như
có nhiều cách để tiếp cận mọi vấn đề khoa học máy tính.
Tìm cách thanh lịch nhất, đó là một phần thú vị.
Trong suốt những p-bộ, nếu chương trình của bạn không phù hợp chính xác của tôi
giải thích trong walkthroughs, đó là OK.
Nhưng chỉ cần đảm bảo rằng nó đi kiểm tra 50, đáp ứng tất cả các
yêu cầu hình thành các chi tiết kỹ thuật, và bạn xem xét liệu của bạn
phương pháp tiếp cận có thiết kế tốt.
>> Nói cách khác, làm thế nào hiệu quả không?
Ví dụ, bạn có gõ lặp đi lặp lại dòng mã, thay vì sử dụng một vòng lặp?
Viết mã với thiết kế tốt hơn sẽ đến kinh nghiệm khi bạn tiến bộ
thông qua khóa học.
>> Đối với điều này đi qua, tôi sẽ đi qua hai phương pháp có thể được sử dụng để
hoàn thành tham lam.
Phương pháp đầu tiên là một phương pháp sử dụng vòng và trừ.
Trước đó, khi chúng tôi nói chuyện qua Quá trình tham lam, chúng tôi liên tục
kiểm tra xem chúng tôi có thể sử dụng một phần tư, và sử dụng một phần tư cho đến khi
giá trị còn lại được ít hơn $ 0,25.
>> Dịch này cũng để một trong khi cấu trúc vòng lặp.
Trong khi chúng ta vẫn có thể sử dụng một phần tư, sử dụng nó.
Rằng vòng lặp trong khi phải thực hiện như lâu như giá trị còn lại lớn hơn
hoặc bằng giá trị của một phần tư xu.
Điều đó có nghĩa rằng bạn cũng sẽ muốn theo dõi số tiền còn lại
giá trị, và cập nhật tất cả thời gian mà bạn sử dụng một đồng xu.
>> Cũng nên nhớ rằng lúc kết thúc, của bạn đầu ra là số lượng tiền xu được sử dụng.
Vì vậy, một điều để theo dõi là số tiền mà bạn sử dụng.
Bạn có thể theo dõi các sử dụng cũng tên biến.
Và trong cơ thể của vòng lặp của bạn sẽ là một cập nhật cho các biến.
Sau khi vòng lặp cho quý kết thúc, bạn có thể sử dụng một cái tương tự vì mưu sinh,
vv và vv, cho đến khi bạn đã trả lại tất cả số tiền trên.
>> Tôi đã viết một số mã giả ở đây để giúp bạn hình dung chỉ cách các
quá trình chúng tôi đã thảo luận có thể dịch để C. Như bạn thấy ở đây, tôi vẫn còn sử dụng
Từ tiếng Anh.
Nó không phải là C được nêu ra.
Nhưng tôi đã bắt đầu điều indent.
Tôi đã đặt điều kiện bên trong dấu ngoặc đơn của tôi.
Nó bắt đầu để tìm một chút giống như mã lập trình.
>> Mã giả là một cách tuyệt vời để có được cho mình bắt đầu.
Hình dung mã của bạn trước khi bạn nhìn lên cú pháp.
Bởi vì thường là phần khó khăn nhất về một vấn đề thực sự hiểu biết những gì
chính xác bạn cần làm.
Một khi bạn viết đó xuống, thì đó là một dễ dàng hơn nhiều để tìm kiếm các chức năng
và cú pháp cụ thể để bạn dòng mã giả
>> Hãy ghi nhớ rằng điều này có thể không được giống với các loại xương của
mã của bạn mà bạn viết.
Luôn có những tối ưu hóa được thực hiện.
Và đặc biệt là trong mã giả của tôi ở đây, xem bạn có thể phát hiện nó.
>> Nhưng về cơ bản quá trình và cách suy nghĩ
chỉ khi chúng ta thảo luận.
Dòng đầu tiên cho chúng tôi để có được một số tiền nhất định bằng đô la.
Và thứ hai cho chúng ta để chuyển đổi nó sang xu.
>> Và sau đó, trong khi quý có thể được sử dụng, chúng tôi muốn tăng số tiền và
giảm lượng tiền mặt.
Cùng đi vì mưu sinh, đồng xu mạ kẽm, và đồng xu.
Và cuối cùng, chúng tôi cho người sử dụng bao nhiêu tiền chúng tôi sử dụng.
>> Tuyệt vời.
Để kết luận phương pháp vòng lặp.
Bây giờ hãy nói về phương pháp mô-đun, mà là nhiều hơn như phân chia.
>> Chúng ta đều quen thuộc với cộng, trừ, nhân, chia các nhà khai thác
sẵn cho chúng tôi.
C có tất cả bốn người trong số những người, nhưng cũng có các nhà điều hành modulo, đại diện bởi một
dấu phần trăm.
Modulo là thực sự gọn gàng.
Nó cung cấp cho bạn phần còn lại từ chia hai con số.
>> Nhớ những tin nhắn chia dài khi bạn chia, nói rằng, 74 ba?
Bắt đầu với vị trí hàng chục, bạn sẽ biết rằng 3 đi vào bảy
hai lần để thực hiện một sáu với còn lại một.
Bạn muốn viết hai ở đầu trang, và sau đó trừ 6 từ bảy, mang theo hơn
phần còn lại của 14 lặp lại quá trình.
>> Ba đi vào 14 bốn lần để làm cho 12, với phần còn lại hai.
Và hai không mang theo hơn nữa.
Vì vậy, hai sẽ được để lại phía dưới là phần còn lại.
>> Và đó là những gì modulo cho bạn con số ở phía dưới.
Vì vậy, 74 modulo ba sẽ cung cấp cho bạn hai.
Và 10 modulo hai, cũng có sẽ cung cấp cho bạn số không.
Bởi vì không có bất kỳ còn lại khi bạn chia 10 bởi hai.
>> Sáu modulo năm, cũng năm đi vào sáu lần.
Và sau đó nó đã một còn lại.
Vì vậy, sáu năm là một modulo.
>> Sau đó, nếu bạn có bảy modulo chín, bạn sẽ nhận được bảy.
Vì chín lớn hơn bảy.
Vì vậy, nó không phân chia tất cả thành bảy, còn để lại bảy là câu trả lời của bạn.
>> Nếu bạn nghĩ về modulo nhiều hơn một chút, hãy nhớ rằng nó mang lại cho bạn
còn lại sau khi bạn chia một cái gì đó.
Suy nghĩ về cách bạn có thể có thể sử dụng nó trong tham lam.
Hãy nói rằng người sử dụng yêu cầu $ 400,11.
Một cách để tìm ra những gì bao nhiêu quý bạn cần mà không cần phải
đếm từng một?
>> Khi bạn tìm ra bao nhiêu phần tư bạn có thể sử dụng để làm cho $ 400,11, bao nhiêu
thay đổi còn lại?
Có lẽ là một sự kết hợp giữa đây modulo và chia sẽ đến trong
tiện dụng để cung cấp cho bạn một mát mẻ, thanh lịch tiếp cận với vấn đề tham lam.
Nhưng hãy nhớ rằng quản quy tắc vẫn còn được áp dụng.
Luôn luôn sử dụng đồng tiền lớn nhất có thể.
>> Một khi bạn đã thực hiện các tính toán như thế nào nhiều tiền xu để sử dụng, bước cuối cùng
là để in ra các số đồng tiền mà bạn tính toán.
Cho đến nay, chúng tôi đã sử dụng printf chức năng chỉ duy nhất cho chuỗi.
Nhưng khi bạn muốn in ra một, or chỉ cần bất kỳ loại dữ liệu được lưu trữ
trong một biến, bạn phải chỉ ra rằng việc sử dụng một trình giữ chỗ.
>> Ở đây tôi đã bao gồm chỉ một số lời khuyên làm thế nào để in ra các giá trị.
Nếu bạn có một số nguyên, bạn sẽ viết chuỗi bằng cách sử dụng% d như một
giữ chỗ.
Sau khi báo giá đóng cửa nhãn hiệu, nhập một dấu phẩy.
Và sau đó đưa vào các số nguyên sẽ chiếm chỗ của% d khi in ra.
>> Vì vậy, sau khi hiển thị số tiền xu được sử dụng, bạn
kết thúc với tham lam.
Hãy chắc chắn để kiểm tra tất cả các trường hợp góc, dọn dẹp phong cách của bạn một chút, và bạn
tất cả các thiết lập để nộp.
Vào cuối vấn đề thiết lập này, bạn sẽ quen thuộc hơn với các CS50
thiết bị, thiết bị đầu cuối, và vòng lặp cấu trúc và các biến trong C.
>> Bạn tốt trên con đường của bạn.
Đường cong học tập có thể có vẻ khó khăn.
Vì vậy, mang nó từng bước.
Hãy chắc chắn rằng bạn viết ra mã giả trước khi lặn quá sâu
vào cú pháp quen thuộc.
>> Làm một việc cần làm, và phá vỡ các phân công thành nhỏ hơn, nhiều hơn
nhiệm vụ quản lý.
Khám phá tất cả các nguồn tài nguyên CS50.
Ngoài bài giảng, rewatch này đi qua.
>> Hãy chú ý đến phần.
Kiểm tra quần short.
Đọc những câu hỏi bạn cùng lớp của bạn ' Thảo luận trên, và gửi của riêng bạn.
>> Tốt nhất của may mắn với p-bộ.
Và cảm ơn cho xem.
Đây là tham lam.
>> [MUSIC CHƠI]