None (3_1) Flashcards
Làm cách nào để chúng ta xây dựng các thuật toán đệ quy của riêng mình
Và ý tưởng chia mọi thứ thành 1/2, 1/2, 1/2 là một logarit mà chúng ta cần gấp đôi số phần tử để thực hiện thêm một bước trong thuật toán
Và điều này là do, trong khoa học máy tính, chúng ta thường không cố gắng tìm kiếm một mảng gồm bảy phần tử
10:26
hoặc một mảng tám phần tử. Chúng tôi thường cố gắng tìm kiếm một mảng có thể có một tỷ phần tử hoặc một triệu phần tử.
Nếu chúng ta có thể thực hiện một số bước nhất định cho mọi phần tử,
34:06 Được rồi, vì vậy bây giờ chúng ta có thể sử dụng lại ý tưởng về ứng viên này trong suốt chương trình của mình vì chúng ta đã sử dụng typedef.
37:28
Vì vậy, chúng tôi đã sử dụng typedef ở đây, đó là từ khóa nói rằng, tất cả những gì sau đây nên được coi là có thể tái sử dụng trong chương trình của chúng tôi.
(Chỉ candidate sau typedef)
Hình ảnh
https://imgur.com/undefined
45:36 Vì vậy, đệ quy không nhất thiết phải là một thuật toán.
45:44 Nó giống như một cách tiếp cận để giải quyết vấn đề trong khoa học máy tính.
Không có thuật toán đệ quy duy nhất, nhưng có
45:51
những thuật toán sử dụng đệ quy. Vì vậy, đệ quy chỉ đơn giản là một cách để giải quyết vấn đề. Và đệ quy, cụ thể hơn, là giải quyết một vấn đề lớn, một vấn đề có vẻ hơi khó khăn và chia nhỏ nó thành những phần nhỏ hơn mà chúng ta biết rằng mình có thể giải quyết.
48:14 Vấn đề nhỏ hơn trong 4 giai thừa là gì?
Call stack
Cái này mình có thể tìm thấy như là một tính năng trong vscode 56:59
Đến một lúc nào đó, chúng ta phải dừng lại ở đây. Nếu không, chúng ta sẽ tiếp tục tìm ra những vấn đề ngày càng nhỏ hơn và không bao giờ kết thúc.
59:56 Vì vậy câu hỏi của bạn về việc, bạn biết cách thức hoạt động của đệ quy, nhưng làm thế nào để bạn biết liệu đệ quy có phải là một cách tiếp cận tốt cho một vấn đề hay không?
1:00:03 Và điều tôi khuyến khích bạn làm là thực sự cố gắng vẽ ra mọi thứ trước khi bạn kết thúc việc cố gắng viết mã một hàm đệ quy. (Nó có đi kèm với hình ảnh mình cho là minh họa (nó hơi giống với bài toán vẽ kim tự tháp trong mario) )
1:00:10Vì vậy, tương tự như vậy, nếu chúng ta quay lại đây, chúng ta sẽ thấy giai thừa đó là chúng ta đã rút ra mọi thứ.
1:00:17
Chúng ta đã thấy, này, tôi nhận thấy rằng 3 giai thừa được nhúng bên trong 4 giai thừa.
1:00:23
Vì vậy, có thể sử dụng tốt thuật toán đệ quy ở đây. Nếu bạn có thể tìm thấy một vấn đề và bạn tìm thấy vấn đề đó
1:00:30
được tạo thành từ một bài toán nhỏ hơn có thể được giải theo cùng một cách, đó là một gợi ý mà bạn có thể muốn sử dụng đệ quy trong trường hợp đó.
Viết cách tính của các trường hợp liên tiếp xem có thể giải quyết bằng đệ quy không (xem có thể mô phỏng cách tính lớn bằng cách tính nhỏ hơn không)(chưa thử nghiệm)
Cá nhân mình nghĩ nếu nhận thấy hàm n có thể mô phỏng bằng hàm n - 1 thì chúng ta có thể sử dụng đệ quy để giải quyết vấn đề
int factorial (int number)
{
if (number == 1)
{
return 1;
}
return number * factorial (number - 1);
}
Thiết kế hàm giai thừa với đệ quy
int factorial (int number)
{
if (number == 1)
{
return 1;
}
int solution = number;
for (int i = number - 1; i > 0; i--)
{
solution = solution * i;
}
return solution; }
Thiết kế hàm giai thừa với vòng lặp
1:03:27 Và một câu hỏi liên quan đến vấn đề này là, có thể viết lại tất cả các truy hồi dưới dạng vòng lặp không?
Tôi muốn nói rằng ít nhất một số trong số chúng có thể, như chúng tôi đã chứng minh ở đây.
1:03:38
Tôi nghĩ rằng có một số vấn đề mặc dù đệ quy thực sự sẽ hữu ích cho bạn bởi những gì đệ quy làm
1:03:44
là nó cho phép bạn có một vấn đề hoàn toàn mới nhỏ hơn để giải quyết và loại bỏ một phần lớn vấn đề đó
1:03:51
và làm việc với vấn đề nhỏ hơn đó. Vì vậy, trong khoa học máy tính, chúng ta thường muốn giải các bài toán lớn hơn bằng cách giải các bài toán nhỏ trước.
1:03:57
Và một vòng lặp có thể không phải lúc nào cũng mang lại cho bạn đòn bẩy giống như bạn có thể có bằng cách chia nhỏ một vấn đề lớn
1:04:02
và biến nó thành một vấn đề nhỏ hơn.
Được rồi, vậy là gần như đưa chúng ta đến phần cuối của phần này.
1:04:26
Chúng tôi đã nói về các thuật toán, cách chúng tôi so sánh chúng. Chúng tôi đã nói về các cấu trúc và cách chúng tôi có thể sử dụng chúng. Chúng ta đã nói về đệ quy, cách chúng ta có thể xác định đệ quy và cuối cùng là viết
1:04:34
các hàm đệ quy riêng của mình. Khi bạn bước sang tuần này, trên thực tế, bạn sẽ thực hiện loại thuật toán của riêng mình liên quan đến cấu trúc,
1:04:42
có thể liên quan đến đệ quy, có thể liên quan đến tất cả các phần tử khác nhau này.
Những kiến thức đã học
