Bài 1:

Giải thuật tính UCLN của hai số nguyên dương p và q(p>q)được mô tả như sau:

Gọi r là số dư trong phép chia p cho q:

• Nếu r=0 thì q là UCLN

• Nếu r≠0 thì gán cho p giá trị của q, gán cho q giá trị của r rồi lặp lại quá trình.

a, Hãy xây dựng một định nghĩa đệ quy cho hàm UCLN(p,q).

b, Viết một giải thuật đệ quy và một giải thuật lặp thể hiện hàm đó.

Lời giải bài 1

a) Định nghĩa ước số chung lớn nhất của hai số là (p>=q)

UCLN(p,q) = q nếu p chia hết cho q

UCLN(q,r) nếu p không chia hết cho q

(r là phần dư của p chia cho q )

b) Chương trình

PROGRAM bai1;

var p,q : integer;

Function ucln(p,q : integer) : integer;

var r : integer;

r := p mod q;

if (r = 0) then ucln := q

else ucln := ucln(q,r)

end;

BEGIN

writeln(' nhap vao 2 so can tim ucln : ') ;

readln(m, n) ;

writeln(' uoc chung lon nhat cua hai so la : ', ucln(m, n));

readln;

END.

Bài 3:

Cho một dãy các số nguyên được xác định như sau:

1 với n=1

an= 3 với n=2

a2n-1 - 2an-2 với n>2

a, viết thủ tục đệ quy xác định giá trị của phần tử thứ n trong dãy.

b, viết thủ tục lặp xác định giá trị của phần tử thứ n trong dãy.

Lời giải bài 3

a,

Function a(n : integer) : integer;

Begin

if (n = 1) then a := 1

else if (n = 2) then a := 3

else a := spr(a(n-1)) - 2*a(n-2)

End;

b, Function (n : integer) : integer;

Var

i : integer;

b : array[1..100] of integer;

Begin

b[1] := 1; b[2] := 3;

for i := 3 to n do

b[i] := sqr(b[i-1])-2*b[i-2];

a := b[n];

End;

Bài 4:

Xét định nghĩa đệ quy:

n + 1 nếu m = 0

Acker (m,n)= Acker(m-1,1) nếu m > 0 và n = 0

Acker(m-1,Acker(m,n-1)) với m > 0 và n > 0

Hàm này gọi là hàm Ackermann. Nó có đặc điểm là giá trị của nó tăng rất nhanh, ứng với giá trị nguyên của m và n.

• Hãy xác định Acker (1,2)

• Viết một thủ tục đệ quy thực hiện tính giá trị của hàm này.

Lời giải bài 4

a(1,2)

= a(0,a(1,1))

= a(0,a(0,a(1,0)))

= a(0,a(0,a(0,1)))

= a(0,a(0,2))

= a(0,3)

= 4

Var

m, n :integer;

Function acker(m, n : integer) : integer;

Begin

if (m = 0) then acker := n+1

else

if (n = 0) then acker := acker(m-1,1)

else acker := acker(m-1,acker(m,n-1))

End;

BEGIN

writeln('nhap m = '); readln(m);

writeln('nhap n = '); readln(n);

writeln('acker(',m,',',n,') = ',acker(m,n));

readln;

END.

Câu hỏi 1: Hãy viết thủ tục đệ quy và không đệ quy biểu diễn số nguyên n thành dãy các chữ số. Ví dụ: số 1989 thành 1 9 8 9

#include"stdio.h"

#include"conio.h"

void ht(int n)

{

if(n<0)

{

printf("-");

n=-n;

}

if (n/10) ht(n/10);

printf(" %d", n%10);

}

void main()

{

clrscr();

printf("Nhap so nguyen:

");a

scanf("%d",&m);

ht(m);

getch();

}

Câu hỏi 2:

Cho biết kết quả trên màn hình khi thực hiện chương trình sau?

Nếu hoán đổi vị trí các câu lệnh 1, 2, 3 thì kết quả sẽ ra sao?

#include"iostream.h"

void Display(int n)

{

if(n<4)

{

1.Display(n+1);

2.Cout<<n;

3.Display(n+1);

}

}

int main()

{

Display(1);

return 0;

}