ĐỀ SỐ 3

Câu 1:

Cho hàm số H(n) với n là đối số nguyên không âm như sau:

H(n)=1 nếu n>=10

H(n)=2n+ H(n+2) nếu n<10

A,tớnhH(1) ,giải thớch cỏch tớnh.

B,viết giải thuật đệ quy và hàm đệ quy để tính giá trị hàm H.

a, tớnh H1 va giải thớch cỏch tớnh.

H1=1*2 + H(1+2).

H1=1*2 + 3*2 + H(3+2).

H1=1*2 + 3*2 + 5*2 + H(5+2).

H1=1*2 + 3*2 + 5*2 + 7*2 + H(7+2).

H1=1*2 + 3*2 + 5*2 + 7*2 + 9*2 + H(9+2)(Đây là trường hợp suy biến).

H1=2 + 6 + 10 + 14 + 18 + 1=51

B,giải thuật đệ quy vạ hạm đệ quy.

- Giải thuật đệ quy:

if (t>=10)then H:=1

else H:=2*t +H(2+t) ;

end

-Hàm đệ quy:

procedure H(t:byte);

if (t>=10)then H:=1

else H:=2*t +H(2+t) ;

end;

Câu 2 :

a) Cho dãy số : 3 5 1 9 -2 7 4 . Hãy minh hoạ việc sắp xếp dãy số trên theo chiều giảm dần bằng phương pháp đổi chỗ liên tiếp ( nổi bọt)

b) Viết chương tình nhập một dãy X có n số thực sắp xếp dãy X theo chiều tăng dần bằng phương pháp chọn trực tiếp

Hướng dẫn

A, Minh hoạ việc sắp xếp dóy số theo phương phap nổi bọt.

í tưởng :ta thưc hiện (n-1) lần duyệt dóy, từ trỏi => phải ,trong mỗi lần duyệt so sỏnh : 2 số liờn tiếp nhau . Nếu số trước lớn hơn sô sau , ta tiến hành đổi chỗ hai số này:

Bảng sau đây minh hoạ việc duyệt dóy lần đầu tiên :

X1 X2 X3 X4 X5 X6 X7

3 5 1 9 -2 7 4

3 5 1 9 -2 7 4

3 5 1 9 -2 7 4

3 1 5 9 -2 7 4

3 1 5 -2 9 7 4

3 1 5 -2 7 9 4

3 1 5 -2 7 4 9

Như các bạn thấy sau lần duyệt dóy đầu tiên ta đó được số lớn nhất ở cuối dóy. Như vậy lần duyệt tiếp thao ta không cần xét đến số cuối cùng này nữa.

Bảng sau đây minh hoạ (n-1) lần duyệt dóy :

X1 X2 X3 X4 X5 X6 X7

3 5 1 9 -2 7 4

Lần 1 3 1 5 -2 7 4 9

Lần 2 1 3 -2 5 4 7 9

Lần 3 1 -2 3 4 5 7 9

Lần 4 -2 1 3 4 5 7 9

Lần 5 -2 1 3 4 5 7 9

Lần 6 -2 1 3 4 5 7 9

B, Viêt chương trỡnh nhập một dóy số X cú n số thực sắp dóy theo chiều tăng dần bằng phương pháp chèn trực tiếp rồi in kết quả ra màn hỡnh.

program insertion_sort;

uses crt;

type day_so=array [1..50] of longint;

procedure insertion_sort(var x:day_so; n:byte);

var i,j:byte; t:longint;

for i:=1 to n-1 do

j:=i ; t:=x[i+1];

while (j>0) and (x[j]>t) do

x[j+1]:=x[j]; j:=j-1;

end;

x[j+1]:=t;

end;

end;

var n,i,l,r:byte ; a:day_so;

clrscr;

write('nhap so luong phan tu can sap n=');

readln(n);

writeln('nhap cac phan tu:');

for i:=1 to n do

write('a[',i,']=');

readln(a[i]);

end;

insertion_sort(a,n);

write('day so sau khi sap xep:');

for i:=1 to n do

write (' ',a[i]);

readln;

end.

Câu 3:

Cho danh sách học sinh có các thông tin : Họ và tên, năm sinh, điểm toán, điểm lý, điểm hoá, điểm văn, điểm sử, điểm trung bình

( đtb = 2đt + 2đv + đl + đh + đs )/7

a) Hãy biểu diễn CTDL của danh sách trên bằng một danh sách tuyến tính dạng lưu trữ kế tiếp

b) Dựa vào CTDL đã biểu diễn ở trên viết các thủ tục :

Nhập danh sách n thí sinh ( cho n số nguyên dương )

Tìm và in ra những thí sinh có điểm TB>= 8.0

Thêm một thí sinh mới vào vị trí thứ 4 trong danh sách

Hướng dẫn :

program de_5;

uses crt;

const max=1000;

type ts=record

ten:string[25];

ns:byte;

dt,dl,dh,dv,ds,dtb:real;

end;

list=record

A:array[1..1000] of ts;

end;

var l:list;n:byte;

procedure nhap_ds(var l:list;n:byte);

var i:byte;x:ts;

for i:=1 to n do

writeln('nhap thi sinh thu',i);

write('nhap ten: ');readln(x.ten);

write('nhap diem toan: ');readln(x.dt);

write('nhap diem ly: ');readln(x.dl);

write('nhap diem hoa: ');readln(x.dh);

write('nhap diem van: ');readln(x.dv);

write('nhap diem su: ');readln(x.ds);

x.dtb:=(x.dt*2 + x.dl + x.dh + x.dv*2 + x.ds)/7.0;

l.a[i]:=x;

end;

end;

Function tim_kiem(var l:list):boolean;

var i:byte;

if (n=0) then tim_kiem:= false

else

for i:=1 to n do

if(l.A[i].dtb >= 8)then

writeln('thi sinh thu',i,l.A[i].ten,l.A[i].dtb:3:1);

tim_kiem:=true;

end;

end;

Function insert(var l:list; x:ts; k:byte ):boolean;

var i:byte;

if (k<1) or (k>n) then insert:=false

else

n:=n+1;

for i:=n downto k do

l.A[i]:=l.A[i-1];

end;

writeln('nhap thong tin cua thi sinh can chen ');

write('nhap ten: ');readln(x.ten);

write('nhap diem toan: ');readln(x.dt);

write('nhap diem ly: ');readln(x.dl);

write('nhap diem hoa: ');readln(x.dh);

write('nhap diem van: ');readln(x.dv);

write('nhap diem su: ');readln(x.ds);

x.dtb:=(x.dt*2 + x.dl + x.dh + x.dv*2 + x.ds)/7.0;

l.a[k]:=x;

insert:=true;

end;

end;

var k,i:byte;x:ts;

clrscr;

write('nhap so luong thi sinh n=');readln(n);

nhap_ds(l,n);

writeln('thi sinh co tong diem >=8 la :');

tim_kiem(l);

write('nhap vi tri thi sinh can chen k: ');readln(k);

insert(l,x,k);

writeln('danh sach sau khi bo sung 1 thi sinh vao vi tri thu ',k );

for i:=1 to n do

writeln ('thi sinh thu',i,l.A[i].ten);

readln;

end.