Bài ôn tập nhập môn 2 - Công nghệ thông tin | Trường Đại học Quy Nhơn

BÀI 2 Bài 1: Function C(n,k) If (k=0 or k=n) Return 1 Else Return C(n-1, k)+C(n-1,k-1) End if End function *Thực thi vd C(5,3): C(5,3)=C(4,3)+ C(4,2)
= C(3,3)+ C(3,2)+ C(3,2)+ C(3,1)
=1+ C(2,2)+ C(2,1)+ C(2,2)+ C(2,1)+ C(2,1)+ C(2,0)
=1+1+ C(1,1)+ C(1,0)+1+ C(1,1)+ C(1,0)+ C(1,1)+ C(1,0)+1 =1+1+1+1+1+1+1+1+1+1 =10 Bài 2: Function dem(n) If n<10 Return 1 Else Return 1+ dem(n/10) End if End function *Thực thi vd dem(9872): Dem(9872)=1+dem(987) =1+1+dem(98) =1+1+1+dem(9) =1+1+1+1 =4 Bài 5: Function GTK(n) If n==1 or n==0 Return 1 Else return n*GTK(n-2) End if End function *Thực thi vd GKT(7): GTK(7)=7* GKT(5) =7*5* GKT(3) =7*5*3*GTK(1) =7*5*3*1=105 *Thực thi vd GTK(10): GTK(10)=10*GTK(8) =10*8*GTK(6) =10*8*6*GTK(4) =10*8*6*4*GTK(2) =10*8*6*4*2*GTK(0) =10*8*6*4*2*1 =3480 Bài 6: *Thực thi vd nguyento(17,2):
 17<=2 sai không thực thi lệnh, end if 1 à if 2
 2>sqrt(17) sai không thực thi lệnh, end if 3
 17%2==0 sai khong thực thi lệnh, end if 4
 Tiếp tục gọi hàm nguyento(17,3)
 17<=2 sai không thực thi lệnh, end if 1 à if 2
 3>sqrt(17) sai không thực thi lệnh, end if 3
 17%3==0 sai khong thực thi lệnh, end if 4
 Tiếp tục gọi hàm nguyento(17,4)
 17<=2 sai không thực thi lệnh, end if 1 à if 2
 4>sqrt(17) sai không thực thi lệnh, end if 3
 17%4==0 sai khong thực thi lệnh, end if 4
 Tiếp tục gọi hàm nguyento(17,5)
 17<=2 sai không thực thi lệnh, end if 1 à if 2
 5>sqrt(17) đúng nên trả kết quả true Vậy nguyento(17,2) = true *Thực thi vd nguyento(8,2)
 8<=2 sai không thực thi lệnh, end if 1 à if 2
 2>sqrt(8) sai không thực thi lệnh, end if 3
 8%2==0 đúng, trả kết quả false Vậy nguyento(8,2)= false. Bài 8:
Thực thi vd daytang(a,n) với n=7, a[]={1 3 5 10 30 33 100}:  n<= 1 sai bỏ qua if 1
 kiểm tra a[6] tiếp tục gọi daytang(a,6)  n<= 1 sai bỏ qua if 1
 kiểm tra a[5] tiếp tục gọi daytang(a,5)  n<= 1 sai bỏ qua if 1
 kiểm tra a[4] tiếp tục gọi daytang(a,4)  n<= 1 sai bỏ qua if 1
 kiểm tra a[3] tiếp tục gọi daytang(a,3)  n<= 1 sai bỏ qua if 1
 kiểm tra a[2] tiếp tục gọi daytang(a,2)  n<= 1 sai bỏ qua if 1
 kiểm tra a[1] tiếp tục gọi daytang(a,1)
 n<=1 đúng trả kết quả true
Vậy daytang(a,n) ra kết quả true. Bài 7:
Thực thi vd xaucon(s1,s2,3,7) với s1=”123” và s2=”1012534”:  m==0 sai, bỏ qua if 1  n==0 sai, bỏ qua if 2
 s1[2]==s2[6] sai, gọi xaucon(s1,s2,3,6)  m==0 sai, bỏ qua if 1  n==0 sai, bỏ qua if 2
 s1[2]==s2[5] đúng, gọi xaucon(s1,s2,2,5)  m==0 sai, bỏ qua if 1  n==0 sai, bỏ qua if 2
 s1[1]==s2[5] sai, gọi xaucon(s1,s2,2,4)  m==0 sai, bỏ qua if 1  n==0 sai, bỏ qua if 2
 s1[1]==s2[3] đúng, gọi xaucon(s1,s2,1,3)  m==0 sai, bỏ qua if 1  n==0 sai, bỏ qua if 2
 s1[0]==s2[2] đúng, gọi xaucon(s1,s2,0,2)
 m==0 đúng, đưa ra kết quả true
Vậy xaucon(s1,s2,3,7) ra kết quả đúng. Bài 3:
Thực thi vd ktdoixung(a,0,5) với a[]={5 3 2 2 3 5}:  0>5 sai, bỏ qua if 1
 a[0]!=a[5] sai, bỏ qua if 2
 gọi đệ quy ktdoixung(a,1,4)  1>4 sai, bỏ qua if 1
 a[1]!=a[4] sai, bỏ qua if 2
 gọi đệ quy ktdoixung(a,2,3)  2>3 sai, bỏ qua if 1
 a[2]!=a[3] sai, bỏ qua if 2
 gọi đệ quy ktdoixung(a,3,2)
 3>2 đúng, ra kết quả true
Vậy ktdoixung(a,0,5) trả kết quả true
Thực thi vd ktdoixung(a,0,4) với a[]={4 5 6 3 4}:  0>4 sai, bỏ qua if 1
 a[0]!=a[4] sai, bỏ qua if 2
 gọi đệ quy ktdoixung(a,1,3)  1>4 sai, bỏ qua if 1
 a[1]!=a[3] đúng, trả kết quả false
Vậy ktdoixung(a,0,4) ra false Bài 4:
Thực thi vd max(a,7) với a[]={15 3 2 12 30 5 10)  7==1 sai, bỏ qua if 1  So sánh a[6] >max(a,6)
 Đệ quy max(a,6): so sánh a[5]>max(a,5)
 Đệ quy max(a,5): so sánh a[4]>max(a,4)
 Đệ quy max(a,4): so sánh a[3]>max(a,3)
 Đệ quy max(a,3): so sánh a[2]>max(a,2)
 Đệ quy max(a,2): so sánh a[1]>max(a,1)  Đệ quy max(a,1): a[0] Kết quả là 30.