Câu 1.
a) Vẽ cây tưng ứng với định nghĩa đệ quy khi n = 5. (0.5đ)
b) Tính giá trị F(5). (0.5đ)
Code:
F(5) = F(4) + 2F(3) = F(3) + 2F(2) + 2(F(2) + 2F(1)) = F(2) + 2F(1) + 8 = 11c) Viết chương trình tính giá trị của F(n). (1.đ)
Code:
#include <conio.h>
#include <stdio.h>
/*Ham tra ve so nguyen tinh gia tri Fibonacci thu n*/
int F(int n) {
if(n==1 || n==2)
return 1;
else
return F(n-1) + F(n-2);
}
/*Chuong trinh chinh*/
void main(){
clrscr();
int n;
printf("Nhap vao gia tri cua n = ");
scanf("%d",&n);
printf("F(%d) = %d",n,F(n));
getch();
}
Câu 2. Sử dụng thuật toán Bubble Sort sắp xếp danh sách theo thứ tự tăng dần. Danh sách gồm các phần tử sau: (2.đ)
Code:
16 11 -1 6 2 -2 1 3 8 7Giải: Thể hiện thuật toán Bubble Sort từng bước theo dạng bảng
Danh sách được sắp xếp là {-2,-1,1,2,3,6,7,8,11,16}
Câu 3. Cho mảng 1 chiều A gồm n số nguyên thực hiện các yêu cầu sau:
a) Viết thủ tục nhập, xuất mảng 1 chiều A với n phần tử, n cho trước. (1.đ)
Code:
//Thủ tục nhập mảng
void NhapMang(int A[], int n){
for(int i = 0; i<n ; i++)
{
printf("Phan tu %d =",i);
scanf("%d", &A[i]);
}
}
// Thủ tục xuất mảng
void XuatMang(int A[], int n){
printf("\n");
for(int i = 0; i<n ; i++)
{
printf("%d\t",A[i]);
}
}
b) Viết hàm trả về số nguyên tính tích n phần tử trong mảng A. (0.5đ)
Code:
long int Tich(int A[], int n){
int temp = 1;
for(int i = 0; i<n ; i++)
temp*=A[i];
return temp;
}c) Viết hàm trả về số nguyên nhỏ nhất trong mảng A gồm n phần tử. (0.5đ)
Code:
int SoNguyenNhoNhat(int A[], int n){
int min = A[0];
for(int i = 1; i<n ; i++)
if(min>A[i])
min = A[i];
return min;
}d) Viết thủ tục sắp xếp mảng A theo thứ tự giảm dần sử dụng thuật toán Insertion Sort. (1.đ)
Code:
void HoanVi(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
void InsertionSort(int A[], int n)
{
for(int i = 0; i<n-1; i++)
{
for(int j = i+1; j>0; j--)
if(A[j] > A[j-1])
HoanVi(A[j],A[j-1]);
}
}
e) Viết hàm tìm kiếm phần tử x trong mảng A gồm n phần tử. Nếu tìm thấy trả về giá trị 1 ngược lại trả về giá trị 0. (1.đ)
Code:
char TimKiem(int A[], int n, int x){
for(int i = 0; i<n ; i++)
if(x==A[i])
return 1;
return 0;
}Câu 4. Viết chương trình tính tổng và tích hai ma trận vuông A, B cùng cấp n. (2.đ)
Code:
#include <conio.h>
#include <stdio.h>
#define max 100
//Nhap ma tran vuong A cap n
void NhapMaTran(int A[max][max], int n)
{
for(int i = 0; i<n ; i++)
for(int j = 0; j<n ; j++)
{
printf("[%d][%d] =",i,j);
scanf("%d", &A[i][j]);
}
}
//Xuat ma tran vuong A cap n
void XuatMaTran(int A[max][max], int n)
{
for(int i = 0; i<n ; i++)
{
printf("\n");
for(int j = 0; j<n ; j++)
printf("%d\t",A[i][j]);
}
}
//Tong hai ma tran A va B luu vao trong ma tran C
void Tong(int A[max][max], int B[max][max], int C[max][max], int n){
for(int i = 0; i<n ; i++)
for(int j = 0; j<n ; j++)
C[i][j] = A[i][j]+B[i][j];
}
//Tich hai ma tran A va B luu vao trong ma tran C
void Tich(int A[max][max], int B[max][max], int C[max][max], int n)
{
for(int i = 0; i<n ; i++)
for(int k = 0; k<n ; k++)
{
C[i][k] = 0;
for(int j = 0; j<n ; j++)
C[i][k] = C[i][k] + A[i][j]*B[j][k];
}
}
void main()
{
clrscr();
int A[max][max],B[max][max], C[max][max], n;
//nhap cap n
printf("Nhap cap n= ");
scanf("%d",&n);
//nhap ma tran A
printf("Nhap vao ma tran A\n");
NhapMaTran(A,n);
//nhap ma tran B
printf("Nhap vao ma tran B\n");
NhapMaTran(B,n);
//In hai ma tran A va B vua nhap
printf("Ma tran A vua nhap\n");
XuatMaTran(A,n);
printf("\nMa tran B vua nhap\n");
XuatMaTran(B,n);
//C=A+B
Tong(A,B,C,n);
printf("\nMa tran C=A+B\n");
XuatMaTran(C,n);
//C=A*B
printf("\nMa tran C=A*B\n");
Tich(A,B,C,n);
XuatMaTran(C,n);
getch();
}