[Bài 14] Thuật toán tham lam | Greedy algorithm

[@sangofficial720]

Slide dễ nhìn dễ tiếp thu. Giải thích cũng dễ hiểu

[@baoho1600]

Thật sự dễ hiểu sau khi xem video của anh

[@nopecoder]

@@

[@Xuan_Nhi__]

dễ hiểu lắm thầy, cảm ơn thầy

[@thuongnguyen3748]

Bài toán bốc đá là một bài toán thuộc lĩnh vực lý thuyết trò chơi, thường được dùng để rèn luyện tư duy logic. Để giải thích rõ ràng, ta bắt đầu với định nghĩa cơ bản: Định nghĩa bài toán bốc đá: Có một đống đá gồm viên (số lượng tùy ý). Hai người chơi lần lượt bốc đá. Mỗi lượt, một người chơi có thể bốc từ 1 đến k viên (với là số lượng tối đa được quy định). Người chơi nào không thể bốc được viên đá nào (đến lượt mà đống đá trống) sẽ thua. Mục tiêu: Mỗi người chơi cần suy nghĩ chiến lược để ép đối phương thua. --- Ví dụ cụ thể: Giả sử có 10 viên đá () và mỗi lượt bốc tối đa viên. Hai người chơi là A và B: 1. Lượt 1 (A): A bốc 2 viên → còn 8 viên. 2. Lượt 2 (B): B bốc 3 viên → còn 5 viên. 3. Lượt 3 (A): A bốc 1 viên → còn 4 viên. 4. Lượt 4 (B): B bốc 3 viên → còn 1 viên. 5. Lượt 5 (A): A bốc 1 viên → hết đá. B thua. --- Cách giải bài toán bốc đá: 1. Phân tích trạng thái "thắng" và "thua": Nếu số viên đá còn lại là , người chơi đang đến lượt sẽ thua. Nếu số viên đá còn lại là và bạn có thể làm đối thủ rơi vào trạng thái trong lượt kế tiếp, bạn sẽ thắng. 2. Chiến lược: Nếu bạn để lại số viên đá là bội số của (tức là ), bạn sẽ đẩy đối thủ vào thế bất lợi. Ví dụ: Nếu , bạn muốn để lại . 3. Ứng dụng vào bài toán: Lượt đầu, cố gắng bốc sao cho sau lượt bốc còn lại số đá là bội số của . --- Nếu bạn cần giải thích chi tiết hơn hoặc có ví dụ cụ thể, cứ hỏi nhé!

[@nopecoder]

cảm ơn bạn đã chia sẽ nhé!

[@Soang69]

cảm ơn anh rất nhiều

[@tienho123]

4:45 ở vòng lặp 1, điều kiện dừng n - 1 nữa sẽ tối ưu hơn

[@ucHoang-fd5bk]

Hi anh. Ở bài toán bốc sỏi hàm UserPlay nếu người dùng nhập sai số đá thì n sẽ trừ cả số lần nhập sai và số lần đúng vì anh đang gọi lại UserPlay. Sử dụng while thay thế cho if gọi lại hàm có lẽ hợp lý hơn. Anh thử kiểm tra lại nhé!

[@vantang8839]

Hmm, mình nghĩ if là hợp lý á bạn, tại dùng đệ quy á, nên lặp đến khi không sai nữa thì thui

[@ucHoang-fd5bk]

@@vantang8839 đúng là nó sẽ lặp cho đến khi không sai nữa nhưng mà trước khi lặp nó sẽ trừ đi số đá đã nhập sai. nếu bạn chưa hiểu có thể ib mình giải thích ^^

[@traiphucdep7427]

Nhập vào số đá mà bạn muốn chơi )) học hiểu mà cười vaii ad ạ

[@nopecoder]

chúng ta trong sáng lên nào :)

[@mykun8737]

bạn làm thêm thuật toán nhánh cận được ko, slide bạn làm chỉn chu

[@vietdungngo1437]

A ơi cho e hỏi, trong bài toán mua sách, nếu đề bài cho thêm hình thức khuyến mại nữa là giảm tối đa một phần ba giá của từng sản phẩm và mỗi sản phẩm chỉ được chọn 1 hình thức khuyến mại thì làm như nào ạ?

[@mykun8737]

bạn cho mình hỏi, thuật toán tham lam, thì có phải có trường hợp không cho lời giải chính xác không, nếu có thì trường hợp ntn ạ?

[@nopecoder]

sẽ có trường hợp sai nhé bạn. Ví dụ như bài toán đổi tiền. Bạn có n tiền và cần đổi tiền lẻ 50 40 và 10. Nếu làm theo tham lam thì với 80 bạn cần 1-50 và 3-10 nhưng đáp án lại là 2-40. Đây chỉ là một ví dụ đơn giản hihi

[@MinhLe-bi5se]

Tham lam này có cần phải vét cạn toàn bộ không gian không ạ

[@nopecoder]

không em nhé

[@mylover1718]

thầy ơi thầy có thể cho em xin file code để em chuyển sang python dc ko ạ , huhu. em đang học python mà không tìm dc ng giảng mảng python ạ. em cảm ơn thầy nhiều

[@DatTran-xg7th]

Em có bài toán như này. Nhập vào 1 tam giác, tính tổng các số từ đỉnh xuống đáy tâm giác biết rằng khi xuống dưới 1 lớp có thể cộng cho số trái hoặc số phải. In ra tổng lớn nhất. Cái này dùng thuật toán nào anh😅

[@foxtran1212]

ok

[@Ve_thoi]

xin các extention anh xài 😁😁😁

[@nhatbao09hht]

d13 đúng hơn phải duyệt đến n-1 nha

[@nhatbao09hht]

tầm phút thứ 5

[@normiedaopho2003]

đều đúng, chỉ là n - 1 tiết kiệm hơn

[@uctinlemai6370]

ad nói không thì em hiểu nhưng mà tự nhiên xuống code bắt đầu em lú rồi //9, 6, 5, 3, 2, 2, 1 /* * 9 % 3 == 0 thì là 9 * 6 6 * ans = ans(0) + a[3] = 5 * 3 * ans = 5 + a[5] = 7 * ans = 7 + a[6] = 9 * ans = 9 + a[7] = 10 */ đúng là theo máy nó 21 nhưng em không hiểu tại sao khi e vẽ tay ra thì lại là 18 ???

[@uyletruong9091]

Cái 9%3 ở kia là bạn sai rồi đó là i%3 là số thứ tự của mảng ý bạn :V

[@hanhthien2948]

Chắc bạn chọn số bắt đầu mảng là 0 nếu v thì là (i+1)%3 mới đúng. À mà lấy số thứ tự mảng chia chứ ko lấy phần tử của mảng chia nha

[@thuongnguyen3748]

Đề bốc đá không đầy đủlafm khó hiểu

[@TuanAnhNguyen-cs8hz]

a cho e xin slide với ạ

[@normiedaopho2003]

nghe tiếng giống admin daisy chess ghê

[@nopecoder]

cùng 1 người bạn ạ :>

[@junxitran8374]

tham lam là có cái nịt nha kaka

[@nopecoder]

^^

[@taiphung3549]

sao không dùng sort ạ :))

[@DraWoOfficial]

Bạn phải là admin kênh Daisy cờ vua ko

[@nopecoder]

đúng rồi

[@phuocduong9094]

bốc mà anh sai chính tả sao sao ấy

[@vunguyenxuan8721]

nghe tiếng bàn phím khó chịu thật sự

[@hoangminhhung4627]

tiếng bàn phím hơi ồn á a @@

[@nopecoder]

hihi sorry em, anh đã đổi bàn phím rồi. nhưng mấy video sau vẫn con là bàn phím cũ :

[@hoangminhhung4627]

@@nopecoder vâng ạ