Thuc Hanh Bai So 2 Lap Trinh De Quy Voi Danh Sach - Tài Liệu Text

Tải bản đầy đủ (.docx) (2 trang)

1. Trang chủ
>>
2. Công Nghệ Thông Tin
>>
3. Kỹ thuật lập trình

Thuc hanh bai so 2 lap trinh de quy voi danh sach

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (69.98 KB, 2 trang )

Kỹ thuật lập trình :: Bài thực hành số 2 :: Lập trình đệ quy với cấu trúc dữ liệu là danh sách đặc.Mục tiêu:1. Diễn đạt và hiện thực tác vụ hướng đệ quy.2. Đệ quy với cấu trúc dữ liệu là danh sách đặc3. So sánh thời gian thực hiện các tác vụ trên danh sách đặc(array) với 2 kỹ thuậtduyệt tuần tự và đệ quy.Vấn đề 4: Lãi suất képNgân hàng A có lãi suất cố định là x%. Đem khoản tiền y gửi vào ngân hàng A trong khoảng thờigian n năm. Tính số tiền thu được (vốn + lãi).Yêu cầu:1. Gọi P(n) là số tiền thu được sau n năm gửi số tiền y vào A. Lập công thức đệ quy tính P(n)2. Cài đặt các hàm đệ quy float lai_kep(float y, int n); trả về số tiền thu được sau n năm3. Cài đặt chương trình hiện thực vấn đề 4 bằng hàm int main(); để kiểm tra tính đúng bằngthực nghiệm.1. Nhập dữ liệu hợp lệ cho n và y2. Hiển thị giá trị của P(n) trên màn hình tương ứng với dữ liệu vào n và y từ bản phímTest:InputOutputn=0y=0n=1y =10n = 104y =10n = 106y =10Vấn đề 5 : Đệ quy trên mảngDãy Q gồm n số nguyên không có thứ tự. Q được lưu trữ ở bộ nhớ trong bằng mảng int Q[n].Yêu cầu:4. Cài đặt hàm void input(int Q[], int &n) để sinh ngẫu nhiên n phần tử (1≤n≤10 6) và lưu vàomãng Q[].5. Cài đặt hàm void output(int Q[], int n) để hiển thị các phần tử của Q[] lên màn hình.6. Dưới đây là gợi ý xây dựng định nghĩa đệ quy để tính tổng n phần tử của dãy Q.Sum(q,n) = q[0] + q[1] + q[2] + ... + q[n-2] +q[n-1]Sum(q,n-1)7. Cài đặt hàm long sum_rec(int Q[], int n) trả về tổng các phần tử của dãy số Q bằng kỹthuật đệ quy được mô tả ở 6.Page 1/2Kỹ thuật lập trình :: Bài thực hành số 2 :: Lập trình đệ quy với cấu trúc dữ liệu là danh sách đặc.8. Dưới đây là gợi ý để xây dựng định nghĩa đệ quy tìm phần tử lớn nhất của mảng Q. Điều kiện biên: Mảng 1 phần tử thì trị lớn nhất là q[0]. Giải thuật chung:o Max(q,n) = q[0] , q[1] , q[2] , ... , q[n-2] , q[n-1]o Max(q,n-1)o9. Cài đặt hàm int max_rec(int Q[], int n) trả về giá trị lớn nhất của dãy số Q bằng kỹ thuậtđệ quy được mô tả ở 8.10. Định nghĩa đệ quy cho tác vụ tìm phần tử có giá trị nhỏ nhất trong dãy số Q. Từ đó cài đặthàm int min_rec(int Q[], int n) trả về giá trị bé nhất của dãy số Q bằng kỹ thuật đệ quy.11. Cài đặt hàm long sum(int Q[], int n) trả về tổng các phần tử của dãy số Q bằng phươngpháp duyệt tuần tự trên mảng Q.12. Cài đặt chương trình hiện thực vấn đề 5 bằng hàm int main(); Tạo dãy số Q gồm n số bằng cách sinh ngẫu nhiên (1≤n≤100) Hiển thị các phần tử của dãy Q Hiển thị phần tử lớn nhất và nhỏ nhất của dãy Q. Tạo dãy số Q gồm n phần tử bằng cách sinh ngẫu nhiên (104≤n≤109). Thực hiện tínhtổng của Q theo hai cách Đệ quy và Không đệ quy và so sánh thời gian thực hiện củamỗi giải thuật với cùng bộ dữ liệu Q(n). Lập báo cáo theo mẫu sau:sumsum_recn=104…(s)…(s)n=105…(s)…(s)n=106…(s)…(s)n=107…(s)…(s)n=109…(s)…(s)Đoạn chương trình hướng dẫn kỹ thuật đo thời gian:#include<iostream>#include<time.h>#include <stdlib.h>using namespace std;long sum_rec(int Q[], int n) ;long sum(int Q[], int n);int main(){int n = 10000;//10^4, 10^5, 10^6, ...clock_t start= clock();sum(n);clock_t end = clock(); //Đo thời gian không đqcout