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

Bài tập và thực hành 4
Mục đích yêu cầu:
 Biết nhận xét, phân tích, đề xuất thuật toán giải bài toán sao cho chương trình chạy nhanh hơn;
 Làm quen với kiểu dữ liệu có cấu trúc và bài toán sắp xếp.
2. Nội dung
- Bài 1 (trang 65 SGK);
- Bài 2 (trang 66 SGK ).
Bài 1.
Chú ý:
 Đây là bài toán áp dụng kiểu dữ liệu có cấu trúc mảng một chiều, và thuật toán sắp xếp tráo đổi tăng dần các phần tử trong dãy số (mảng);
 Ý nghĩa hàm chuẩn random(n); tương tự như bài tập và thực hành 3.
1a) Tìm hiểu và chạy thử chương trình – nhận xét về thời gian chạy của chương trình.
uses crt;
var A: array[1..250] of integer;
n,i,j,tg: integer;
begin
clrscr; randomize;
write(‘Nhap n =‘); readln(n);
{tạo ngẫu nhiên mảng gồm n số nguyên}
for i:=1 to n do A[i]:= random(300)-random(300);
for i:=1 to n do write(A[i]:5); writeln; {in mảng vừa tạo}
for j:=n downto 2 do
for i:=1 to j-1 do
if A[i] > A[i+1] then
begin {trao đổi A[i] và A[i+1]}
tg:= A[i]; A[i]:= A[i+1]; A[i+1]:= tg;
end;
writeln(‘Day so sau khi sap xep:’) ;
for i:=1 to n do write(A[i]:7); writeln;
readln
end.



Khai báo
Tạo và in mảng
Sắp xếp và tráo đổi
In mảng sau khi sắp
1b) Khai báo thêm biến nguyên dem, bổ sung vào chương trình các câu lệnh cần thiết để biến đếm tính số lần thực hiện tráo đổi và đưa kết quả ra màn hình.

uses crt;
const Nmax= 250;
type ArrInt= array[1..250] of integer;
var n,i,j,y,t,dem: integer;
A: ArrInt;
begin
clrscr; randomize; dem:=0;
write(‘Nhap n =‘); readln(n);
{tạo ngẫu nhiên mảng gồm n số nguyên}
for i:=1 to n do A[i]:= random(300)-random(300);
for i:=1 to n do write(A[i]:5); writeln; {in mảng vừa tạo}
for j:=n downto 2 do
for i:=1 to j-1 do
if A[i] > A[i+1] then
begin {trao đổi A[i] và A[i+1]}
t:= A[i]; A[i]:= A[i+1]; A[i+1]:= t; inc(dem);
end;
writeln(‘Day so sau khi sap xep:’);
for i:=1 to n do write(A[i]:7); writeln;
write(‘So lan thuc hien trao doi la:’, dem);
readln
end.

Khai báo thêm biến dem
Tạo và in mảng
Sắp xếp, tráo đổi và dem
In mảng sau khi sắp và in số lần tráo đổi dem.
khởi tạo biến dem = 0;
Bài 2.
- 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.
- Đọc kĩ đề bài, phân tích và tìm hiểu chương trình giải bài toán trên (trang 66, 67 SGK).
Thay đoạn lệnh tạo mảng B[1..n], bởi hai lệnh như sau:
program subsum1;
const nmax=100;
type MyArr= array[1..nmax] of integer;
var a, b : Myarr;
n,i,j: integer;
begin
randomize; write(`Nhap n =`); readln(n);
{Tao ngau nhien mang gom n so nguyen}
for i:=1 to n do a[i]:= random(300) - random(300);
for i:=1 to n do write(a[i]:5); writeln;
{Bat dau tao b}
for i:=1 to n do
begin
b[i]:=0; for j:=1 to i do b[i]:= b[i]+a[j];
end;
{Ket thuc tao b}
for i:=1 to n do write(b[i]:6);
readln
end.
Ta th?y r?ng:
b[1] = a[1], t? dó suy ra
b[i] = b[i-1] + a[i], (1program subsum1;
const nmax=100;
type MyArr= array[1..nmax] of integer;
var a, b : Myarr;
n,i,j: integer;
begin
randomize; write(`Nhap n =`); readln(n);
{Tao ngau nhien mang gom n so nguyen}
for i:=1 to n do a[i]:= random(300) - random(300);
for i:=1 to n do write(a[i]:5); writeln;
{Bat dau tao b}
for i:=1 to n do
begin
b[i]:=0; for j:=1 to i do b[i]:= b[i]+a[j];
end;
{Ket thuc tao b}
for i:=1 to n do write(b[i]:6);
readln
end.
b[1]:= a[1];
for i:=2 to n do b[i]:= b[i-1] + a[i];
{ta sẽ tiết kiệm được một lượng tính toán đáng kể}
Củng cố:
Cần phân tích bài toán trước khi tiến hành viết chương trình, để tiết kiệm được dung lượng bộ nhớ của máy tính.
Cần khai báo kiểu dữ liệu trước khi khai báo biến kiểu mảng một chiều.
Dặn dò:
Về nhà học bài và xem trước bài 12 “Kiểu xâu”.