Bài tập và thực hành 4

Bài 1
Câu a: Hãy tìm hiểu và chạy thử chương trình thực hiện sắp xếp dãy số nguyên bằng thuật toán tráo đổi với các giá trị khác nhau của n.

Các bước để sắp xếp các phần tử của một mảng theo thứ tự không giảm?
Lần lượt lấy từng phần tử từ trái qua phải.
Cứ mỗi phần tử đem so sánh lần lượt với các phần tử đứng bên phải của nó. Nếu phần tử bên phải của nó nhỏ hơn nó thì đổi chỗ.
Bài 1
Khai báo như thế nào?
Bổ sung câu lệnh gì, vào vị trí nào?
Câu b: Khai báo biến Dem và bổ sung vào
chương trình những câu lệnh cần thiết để
biến Dem tính số lần thực hiện tráo đổi trong
thuật toán. Đưa kết quả tìm được ra màn hình.
BÀI 2
Hãy đọc và tìm hiểu những phân tích để
viết chương trình giải bài toán:
Cho mảng A gồm n phần tử. Hãy viết
chương trình tạo mảng B[1..n], trong đó
B[i] là tổng của i phần tử đầu tiên của A.
B[1] = ?
B[2] = ?
…………
B[n] = ?
B[i] = ?

(với i = 1,2,…,n)
A[1]
A[1] + A[2]
………….
A[1] + A[2] + … + A[n]
B[i] = A[1] + …+ A[i]

(với i = 1,2,…,n)
Input: Mảng A gồm n phần tử.
Output: Mảng B gồm n phần tử.
Ví dụ:
A
B
1 2 3 4
1
-4
2
4
Với:
B[1] = A[1]
B[2] = A[1] + A[2]
B[3] = A[1] + A[2] + A[3]
B[4] = A[1] + A[2] + A[3] + A[4]
Tạo mảng B
For j:=1 to i do
B[i] := B[i] + A[j];
B[i] := 0;
For i:=1 to n do
begin




end;
n(n+1)/2 phép +
Bao nhiêu phép + ?
B[1] = A[1]
B[2] = A[1] + A[2]
…………….
B[n] = A[1] + A[2] + … + A[n]
B[1] = A[1]
B[i] = B[i-1] + A[i] , 1n -1 phép +
Chú ý
Cùng một bài toán, có nhiều cách giải quyết khác nhau. Người lập trình cần chọn cách sao cho máy thực hiện nhanh nhất.