Thảo luận và tìm hiểu ý tưởng thực hiện các tính toán bằng kĩ thuật đệ quy

Giải Chuyên đề Tin 11 Bài 2: Thiết kế thuật toán đệ quy - Kết nối tri thức

Hoạt động 1 trang 11 Chuyên đề Tin học 11: Trao đổi, thảo luận và tìm hiểu ý tưởng thực hiện các tính toán sau bằng kĩ thuật đệ quy

Quảng cáo

1. Tính tổng S(n) = 1+2+3+…+n

2. Tính lũy thừa Thảo luận và tìm hiểu ý tưởng thực hiện các tính toán bằng kĩ thuật đệ quy

3. Tính n giai thừa n!= 1x2x3x…xn

Lời giải:

1. Tính tổng S(n) = 1+2+3+…+n

Bước 1. Bài toán yêu cầu tính tổng của n số nguyên từ 1 đến n. Cần thiết lập hàm S(n) trả về giá trị tổng cần tim.

Bước 2. Điều kiện n ≥ 0.

Với n = 0 ta có S(n) = 0. Đây là phần cơ sở cho điều kiện dừng của lời gọi đệ quy của hàm S(n).

Bước 3. Dễ thấy S(n) = n + S(n - 1) là công thức truy hồi của hàm S(n) và là cơ sở của lời gọi đệ quy của hàm.Chương trình như sau:

2. Tính lũy thừa Thảo luận và tìm hiểu ý tưởng thực hiện các tính toán bằng kĩ thuật đệ quy

Bước 1. Bài toán yêu cầu tính luỹ thừa $a^{n}$ . Cần thiết lập hàm exp(a,n) trả về giá trị $a^{n}$ .

Bước 2. Điều kiện là n ≥ 0 và theo quy ước thì exp(a,0) = 1 với mọi a. Đây chính là phần cơ sở cho điều kiện dừng của lời gọi đệ quy của hàm exp(a,n).

Bước 3. Ta có $a^{n} = a * a^{n - 1}$ suy ra exp(a,n) = a × exp(a,n-1), đây là công thức truy hồi tính exp(a,n). Từ đó có thể thiết lập lời gọi đệ quy của hàm này.

3. Tính n giai thừa n!=1 x 2 x 3 x … x n

Bước 1. Bài toán yêu cầu tính n giai thừa n!. Ta cần thiết lập hàm giaithua(n) trả về giá trị n!.

Bước 2. Điều kiện là n ≥ 0 và quy ước 0! = 1, tức là giaithua (0) = 1. Đây là cơ sở cho điều kiện dừng của lời gọi đệ quy của hàm giaithua(n).

Bước 3. Ta có công thức giaithua(n) = n × giaithua(n-1), đây là công thức truy hồi tính giaithua(n). Từ đó dễ dàng thiết lập lời gọi đệ quy cho hàm này.

Quảng cáo

Lời giải bài tập Chuyên đề Tin 11 Bài 2: Thiết kế thuật toán đệ quy hay, chi tiết khác: