Luyện Tập đệ Quy (phần 2) - Phuong's Blog

Trang chủ » đệ Quy Và Mảng » Luyện Tập đệ Quy (phần 2) - Phuong's Blog

Có thể bạn quan tâm

Một số bài luyện tập đệ quy với mảng một chiều

Bài 1: Tính tổng một mảng bằng đệ quy

  • Nếu mảng có 1 phần tử: tổng chính là giá trị phần tử đó.
  • Nếu mảng có n phần tử (n>1), ta tính tổng của (n-1) phần tử đầu, sau đó cộng vơi phần tử cuối cùng.
int Tong(int a[], int n) { if (n == 1) return a[0]; return Tong(a, n-1) + a[n-1]; }

Bài 2: Tìm giá trị max của một mảng bằng đệ quy

Tương tự như trên, ta có:

  • Nếu mảng có 1 phần tử: max chính là phần tử đó.
  • Nếu mảng có n phần tử (n>1), ta tìm max trong số (n-1) phần tử đầu, so sánh với phần tử cuối cùng để tìm ra max trên toàn mảng.
int Max(int a[], int n) { if (n == 1) return a[0]; if (Max(a, n-1) > a[n-1]) return Max(a, n-1); else return a[n-1]; }

Đoạn code trên có một điểm không tốt là hàm Max(a, n-1) được gọi 2 lần và chúng đều thực thi giống hệt. Và trong những mức đệ quy sâu hơn cũng xảy ra tình trạng này. Điều này là không nên, vì nó làm cho hàm đệ quy phải gọi càng nhiều lần hơn, do đó, ta chỉ nên gọi 1 lần và lưu giá trị max tạm trong một biến

int Max(int a[], int n) { if (n == 1) return a[0]; int tempMax = Max(a, n-1); if (tempMax > a[n-1]) return tempMax; else return a[n-1]; }

Bài 3: Viết hàm đệ quy xuất ngược một mảng

  • Nếu mảng có một phần tử, xuất nó ra.
  • Nếu mảng có n phần tử (n>1), xuất phần tử cuối cùng trước, sau đó gọi đệ quy xuất (n-1) phần tử còn lại.
void XuatNguoc(int a[], int n) { if (n == 1) printf("%d ", a[0]); else { printf("%d ", a[n-1]); XuatNguoc(a, n-1); } }

Bài 4: Đếm số lượng các phần tử phân biệt trong một mảng.

  • Nếu mảng có một phần tử, số phần tử phân biệt là 1.
  • Nếu mảng có n phẩn tử (n>1):
    • Đến số lượng phần tử phân biệt trong mảng (n-1) phần tử.
    • Kiểm tra xem phần tử a[n-1] có xuất hiện trong mảng trước hay không. Nếu có tăng số lượng thêm 1, ngược lại trả về số lượng ở trên.

– Ta cần viết một hàm IsInArray để kiểm tra xem giá trị k có xuất hiện trong mảng a hay không. Hàm này dùng để  hỗ trợ cho hàm DemPhanBiet. Hàm IsInArray dưới đây được viết dạng vòng lặp, nếu bạn muốn có thể tự cài đặt theo kiểu đệ quy. Tuy nhiên, đừng lạm dụng đệ quy quá nhé. Mình đang học thì có thể áp dụng cho quen thôi, không nên lạm dụng.

bool IsInArray(int a[], int n, int k) { for (int i = 0; i < n; i++) if (a[i] == k) return true; return false; } int DemPhanBiet(int a[], int n) { if (n == 1) return 1; int dem = DemPhanBiet(a, n-1); if (IsInArray(a, n-1, a[n-1]) == true) return dem; else return dem + 1; }

Chia sẻ:

  • Tweet
Thích Đang tải...

Có liên quan

Từ khóa » đệ Quy Và Mảng