Bài tập và giải của giải thuật đệ quy

Đây là một quyển sách toán lớp 3, ở trong bìa sách có ba học sinh, trong đó có một học sinh lại cầm một quyển sách toán lớp ba khác. Và trong quyển sách đó lại có ba học sinh, và cũng có một học sinh cầm một quyển sách lớp 3. Đây chính là ví dụ cho một khái niệm rất căn bản trong bất kỳ ngôn ngữ lập trình nào - khái niệm "đệ quy".

Đệ quy là gì ?

Đệ quy có nghĩa là một hàm tự gọi lại chính nó.

Ví dụ:

void hello(int count)
{
  count++;
  if (count <= 5)
  {
    printf("hello %d\n", count);
    hello(count);
  }
}

Thành phần của một hàm đệ quy.

Một hàm đệ quy gồm 2 phần:

• Phần cơ sở: Điều kiện để thoát khỏi đệ quy. Nếu như không có phần này, hàm đệ quy sẽ thực hiện mãi mãi gây ra tràn bộ nhớ Stack.
• Phần đệ quy: Thân hàm có chứa phần gọi đệ quy, thực hiện cho đến khi thỏa mãn điều kiện ở phần cơ sở.

Ví dụ:

void hello(int count)
{
  count++;
  if (count <= 5) // điều kiện dừng
  {
    printf("hello %d\n", count);
    hello(count);
  }
}

Như ví dụ trên, nếu chúng ta không cài đặt điều kiện dừng thì chương trình sẽ chạy mãi mãi.

Bộ nhớ Stack.

Nguyên tắc hoạt động của bộ nhớ Stack là LIFO (Last in - First out hay còn gọi là vào sau - ra trước ). Khi một biến được khai báo trong hàm, nó sẽ được đẩy vào Stack, khi hàm đó kết thúc thì tất cả những biến đó sẽ được đẩy ra, giải phóng khỏi Stack. Hình dưới là minh họa cách hoạt động của bộ nhớ Stack.

Ưu điểm:

Thuận lợi cho việc biểu diễn bài toán, như ở ví dụ trên, nhìn vào hàm là chúng ta có thể thấy ngay nó biểu diễn dãy số fibonacci, hay tính giai thừa.

Nhược điểm:

Tốn nhiều bộ nhớ, nếu không phần cơ sở ( điểm dừng) thì sẽ gây ra việc tràn bộ nhớ stack. Bên cạnh đó việc sử dụng đệ quy tốn nhiều thời gian hơn vòng lặp.

Các ví dụ.

Tính tổng các số từ 1 đến n.

# include 
int sum(int n){
    if(n == 0) // điều kiện dừng (phần cơ sở)
      return 0;
    return n + sum(n-1);
}
int main(){
    int sum = sum(5);
    printf("Sum = %d", sum);
}

Kết quả.

Giải thích hàm đệ quy

Với n = 5

5 + sum(4)

5 + 4 + sum(3)

5 + 4 + 3 + sum(2)

5 + 4 + 3 + 2 + sum(1)

5 + 4 + 3 + 2 + 1 + 0

Dãy Fibonacci.

# include 
int fibonacci(int n)
{
  if ((n == 1) || (n == 2))
    return 1;
  return fibonacci(n-1) + fibonacci(n-2);
}
int main()
{
  printf("%d", fibonacci(30));
}

Kết quả.

Tính giai thừa

# include 
int factorial(int n)
{
  if (n == 1) 
    return 1;
  else return factorial(n-1)*n;
}
int main()
{
  printf("%d", factorial(5));
}

Kết quả.

Tạm kết

Đệ quy là một phương pháp cơ bản trong kỹ thuật lập trình. Trong lập trình Web hay Winform thường thì không sử dụng đệ quy nhưng nên học kỹ thuật này, vì nó không quá khó để nắm bắt. Việc sử dụng đệ quy vào các bài toán thì nên cân nhắc, mặc dù đệ quy khiến code chúng ta dễ đọc, nhưng rất khó cho việc debug.

Trên đây là khái niệm về đệ quy, hy vọng giúp ích cho mọi người mới tìm hiểu về kỹ thuật này, nếu có câu hỏi hay góp ý gì thì hãy bình luận ở bên dưới nhé. Chúc mọi người học tốt.

TÓM TẮT: Rút gọn thuộc tính là bài toán quan trọng trong bước tiền xử lý dữ liệu của quá trình khai phá dữ liệu và khám phá tri thức. Trong mấy năm gần đây, các nhà nghiên cứu đề xuất các phương pháp rút gọn thuộc tính trực tiếp trên bảng quyết định gốc theo tiếp cận tập thô mờ (Fuzzy Rough Set FRS) nhằm nâng cao độ chính xác mô hình phân lớp. Tuy nhiên, số lượng thuộc tính thu được theo tiếp cận FRS chưa tối ưu do ràng buộc giữa các đối tượng trong bảng quyết định chưa được xem xét đầy đủ. Trong bài báo này, chúng tôi đề xuất phương pháp rút gọn thuộc tính trực tiếp trên bảng quyết định gốc theo tiếp cận tập thô mờ trực cảm (Intuitionistic Fuzzy Rough Set IFRS) dựa trên các đề xuất mới về hàm thành viên và không thành viên. Kết quả thử nghiệm trên các bộ dữ liệu mẫu cho thấy, số lượng thuộc tính của tập rút gọn theo phương pháp đề xuất giảm đáng kể so với các phương pháp FRS và một số phương pháp IFRS khác.

Văn học Việt Nam nửa đầu thế kỉ XX được xem là giai đoạn “giao thời”, với sự đấu tranh giữa thơ Cũ và thơ Mới, giữa truyền thống và cách tân, tồn tại nhiều khuynh hướng, dòng phái khác nhau. Từ góc độ thể loại, không ít người cho đây là thời điểm thơ tự do thắng thế, thơ Đường luật nói chung bị xem là hết mùa, lỗi thời. Song vẫn còn đó một minh chứng hùng hồn cho sự hiện diện của thơ Nôm Đường luật Việt Nam ở nửa đầu thế kỉ XX, đó là Nôm Đường luật Phan Bội Châu. Bài viết trên cơ sở chỉ ra một vài đặc điểm về ngôn ngữ trong thơ Nôm Đường luật Phan Bội Châu thời kỳ ở Huế, từ đó cho thấy những đổi mới, cách tân của Phan Sào Nam trong việc sử dụng thể thơ truyền thống của dân tộc.

Mục tiêu của bài viết này nhằm phân tích hiệu quả hiệu quả lợi nhuận sản xuất nông nghiệp mà cụ thể là phân tích hiệu quả lợi nhuận của hộ trồng cam sành ở Hàm Yên tỉnh Tuyên Quang bằng cách tiếp cận phương pháp hồi quy. Số liệu sơ cấp của đề tài được thu thập bằng cách phỏng vấn trực tiếp 200 nông hộ trồng cam sành theo phương pháp chọn ngẫu nhiên vào thời điểm tháng 5 năm 2022. Trong giai đoạn đầu chúng tôi sử dụng phương pháp bao dữ liệu (DEA) để tính toán hiệu quả kĩ thuật của các nông hộ trồng cam sành. Ở giai đoạn 2, để khắc phục hạn chế của phương pháp bao dữ liệu nghiên cứu sử dụng mô hình hồi quy bootstrap truncated để xác định các yếu tố ảnh hưởng đến hiệu quả lợi nhuận của các hộ nói trên. Kết quả phân tích cho thấy hiệu quả lợi nhuận trung bình của các hộ sản xuất cam sành được khảo sát là 0,486, nó dao động từ 0,034 đến 1,000. Điều đó có nghĩa rằng các nông hộ có nhiều tiềm năng để cải thiện hiệu quả của lợi nhuận sản ...

Hiện nay, tại chùa Bảo Ninh Sùng Phúc (huyện Chiêm Hóa, Tuyên Quang) còn lưu giữ được tấm bia cổ duy nhất thuộc các tỉnh miền núi phía Bắc nước ta có niên đại từ thời nhà Lý. Nội dung văn bia chép về dòng họ Hà và những đóng góp của dòng họ này đối với vùng đất Vị Long nói riêng và đất nước nói chung ở thế kỷ XI - XII. Trong đó phải kể đến công lao to lớn của nhân vật lịch sử Hà Di Khánh.

Đặt vấn đề: Bên cạnh y đức, tính chuyên nghiệp trong y khoa là một trong những năng lực cốt lõi của Điều Dưỡng tác động trực tiếp đến hiệu quả chăm sóc quản lý người bệnh. Do đó, việc xác định mức độ nhận thức của điều dưỡng về tính chuyên nghiệp là nhu cầu cấp thiết trong xây dựng chương trình huấn luyện tính chuyên nghiệp cho điều dưỡng hiệu quả và hội nhập khu vực. Mục tiêu: Xác định mức độ nhận thức của sinh viên và cựu sinh viên với các giá trị cốt lõi tính chuyên nghiệp và sự khác biệt về mức độ nhận thức về giá trị cốt lõi tính chuyên nghiệp trong hai nhóm. Phương pháp nghiên cứu: thiết kế mô tả cắt ngang từ 01/10/2020 đến 20/02/2021, thực hiện trên 208 sinh viên và 88 cựu sinh viên khoa Điều Dưỡng tại trường Đại Học Quốc Tế Miền Đông, tỉnh Bình Dương sử dụng bảng câu hỏi tính chuyên nghiệp trong y khoa áp dụng thang likert 1-5 gồm 6 thành tố đo lường tính chuyên nghiệp. Hệ số Cronbach’s Alpha của toàn thang đo 0,91 để đánh giá nhận thức các giá trị cốt lõi tính chuyên nghiệp...