ĐỀ SỐ 2

Câu 1:

Cho hàm số f(x,y) với x,y là các đối số kiểu nguyên như sau:

y nếu x <=0

F(x,y)= x + f(x -1 ,y) nếu y<=0

f( x-1 ,y)+ f(x,y-1) trong các trường hợp còn lại

a) Tính f(3,2) ,giải thích cách tính ?

b) Viết giải thuật đệ qui và thủ tục đệ qui để tính giá trị hàm f. Để tính f( 3,2) phải gọi thủ tục tính hàm giá trị bao nhiêu lần ?

Hướng dẫn

a, Tớnh F(3,2).

, Tớnh F(3,2).

• F(3,2) = F(2,2) + F(3,1)

• F(3,2) = F(1,2) + F(2,1) + F(2,1) + F(3,0)

• F(3,2) = F(0,2) + F(1,1) + F(1,1) + F(1,0) + F(1,1) + F(2,0) + F(2,0) + F(3,-1)

• F(3,2) = F(-1,2) + F(0,1) + F(0,1) + F(1,0) + F(0,1) + F(1,0) + 1+ + F(0,1) + F(0,1) + F(1,0) + F(1,0) + F(2,-1) + F(1,0) + F(2,-1) + 3 + F(2,1)

• F(3,2) = 2 + 1 + 1 +1+F(0,1)+ 1 + 1+F(0,1) +1 + 1 + 1 +1+F(0,1) + 1+F(0,1)+F(1,-2) + 1+F(0,1)+F(1,-2) + 1 +3 +F(1,1)+F (2,0)

Trong đó:F(1,-2)=F(0,-2)+F(1,-3)

=-2 + 1 + F(0,1)=2=1=1=4

F(1,1)=F(0,1)+F(1,0)

=1+1+F(0,1)=3

F(2,0)=0+ F(1,1)=3

vậy F(3,2)=32

b,viết hàm đệ quy tính giá trị hàm F

Function F(x:byte,y:byte):longint;

begin

if(x<=0)then F(x,y)=y

else if(y<=0) then F(x,y) = x + F(x-1,1)

else F(x,y)= F(x-1,y) + F(x,y-1) ;

end;

Câu 2:

Cho danh sách thí sinh dự thi, mỗi thí sinh có các thông tin: Số báo danh, họ và tên, năm sinh, điểm toán, điểm lý, điểm hoá, tổng điểm (TĐ = ĐT + ĐL + ĐH).

a) Hãy biểu diễn CTDL của danh sách nói trên dưới dạng một danh sách liên kết đơn.

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

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

+ Tìm và in ra những thí sinh có tổng điểm >= 20.

+ Loại bỏ những thí sinh có tổng điểm bằng 0.

Hướng dẫn;

program de_8;

uses crt;

const max=1000;

type ts=record

ten:string[25];

d,m,y:byte;

td: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;

begin

for i:=1 to n do

begin

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

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

write('ngay sinh: ');readln(x.d);

write('thang sinh: ');readln(x.m);

write('nam sinh: ');readln(x.y);

write('tong diem: ');readln(x.td);

l.a[i]:=x;

end;

end;

Function tim_kiem(var l:list):boolean;

var i:byte;

begin

if (n=0) then tim_kiem:= false

else

begin

for i:=1 to n do

if(l.A[i].td >= 20)then

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

tim_kiem:=true;

end;

end;

procedure delete(var l:list );

var i,j:byte;

begin

for i:=1 to n do

if (l.A[i].td=0) then

begin

for j:=i to n-1 do

l.A[j]:=l.A[j+1];

n:=n-1;

end;

end;

var k,i:byte;x:ts;

begin

clrscr;

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

nhap_ds(l,n);

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

tim_kiem(l);

writeln('danh sach sau khi loai bo nhung thi sinh co dtk=0 ' );

for i:=1 to n do

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

readln;

end.

Câu 2 : Làm kiểu danh sách móc nối

program De_2;

{uses crt;}

type Ts=record

ten:string[25];

gtinh:string[3];

ns:integer;

dtb:real;

end;

tro=^node;

node=record

infor:Ts;

next:tro;

end;

var l:tro; d:byte;

procedure input(var l:tro);

var x:ts ; i,d:byte ; p,q:tro;

begin

l:=nil;i:=1;d:=0;

while(x.ten<>'') do

begin

writeln('nhap thong tin thi sinh thu',i,':');

write('Ten Thi sinh :') ; readln(x.ten);

write('gioi tinh:') ; readln(x.gtinh);

write('dtb') ; readln(x.dtb);

new(p);

p^.infor:=x;

p^.next:=nil;

if l=nil then

begin

l:=p;

i:=i+1;

end

else

begin

q:=l;

while q^.next<>nil do q:=q^.next;

q^.next:=p;

i:=i+1;

d:=d+1;

end;

end;

end;

procedure timkiem(var l:tro);

var x:ts ; q:tro;i:byte;

begin

i:=1;q:=l;

while (q^.next<>nil) do

begin

x:=q^.infor;

if (x.dtb>=8) then

begin

writeln('thi sinh thu ',i,x.ten:10, x.dtb:5:1 );

q:=q^.next;

end;

end;

end;

Function empty(l:tro):boolean;

begin

empty:=(l=nil);

end;

procedure insert_fist(var l:tro; x:ts);

var p:tro;

begin

new(p);

p^.infor:=x;

p^.next:=nil;

if empty(l)then l:=p

else begin

p^.next:=l;

l:=p;

end;

end;

procedure insert_mid(var l:tro;m:tro;x:ts);

var p:tro;

begin

new(p);m:=l;

p^.next:=m^.next;

m^.next:=p;

end;

procedure insert(var l:tro; x:ts; k:byte );

var d:byte ; q,m:tro;

begin

d:=0; q:=l;

while(q^.next<>nil) do

begin

d:=d+1;

q:=q^.next;

end;

if (k<1) or (k>d)then write('khong bo sung dc')

else

if (k=1) then

insert_fist(l,x)

else

begin

d:=1;m:=l;

while (d<k-1)do

begin

m:=m^.next;

d:=d+1;

end;

insert_mid(l,m,x);

end;

end;

procedure output(l:tro;q:tro);

var x:Ts ;

begin

q:=l;

while(q<>nil) do

begin

x:=q^.infor;

writeln('ten thi sinh:',x.ten:10 ,'g tinh:',x.gtinh:10 ,' diem trung binh:',x.dtb:3:1);

q:=q^.next;

end;

end;

var q:tro;k:byte;x:ts;

begin

writeln('nhap thong tin thi sinh ');

input(l);

writeln('nhung thi sinh co dtb>8 : ');

timkiem(l);

write('nhap vao vi tri can bo sung k:') ;readln(k);

writeln('nhap nhung thong tin cua ts can chen');

write('ten,gtinh,dtb');readln(x.ten,x.gtinh,x.dtb);

Writeln('danh sach sau khi bo sung:');

insert(l,x,k);

output(l,q);

readln;

end.