Báo cáo thực hành Kỹ thuật lập trình – IT3040 _Bài 15
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (867.95 KB, 119 trang )
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
Contents
Danh mục hình ảnh.................................................................................................................................3
Bài thực hành số 1: Con trỏ và cấp phát......................................................................................................5
Phần 1. Thực hành về con trỏ..................................................................................................................5
1.
Bài tập 1:......................................................................................................................................5
2.
Bài tập 2:......................................................................................................................................6
3.
Bài tập 3:......................................................................................................................................7
4.
Bài tập 4:......................................................................................................................................8
5.
Bài tập 5:....................................................................................................................................10
6.
Bài tập 6:....................................................................................................................................11
7.
Bài tập 7:....................................................................................................................................13
8.
Bài tập 8.....................................................................................................................................15
Phần 2. Bài tập về nhà...........................................................................................................................18
Bài tập 9.............................................................................................................................................18
Bài tập 10...........................................................................................................................................20
Bài thực hành số 2: Hàm và tối ưu mã nguồn............................................................................................24
Phần 1. Thực hành về hàm....................................................................................................................24
1.1 Truyền tham trị, tham chiếu và tham số ngầm định....................................................................24
1.2 Đa năng hóa hàm.........................................................................................................................28
1.3 Con trỏ hàm và tham số hóa hàm................................................................................................32
1.4 Biểu thức lamda và hàm nặc danh...............................................................................................35
Phần 2. Thực hành về tối ưu mã nguồn.................................................................................................36
Bài tập 9 :Tính hàm sigmoid..............................................................................................................36
Bài tập 10 (bonus): Tính tích hai ma trận vng................................................................................40
Phần 3. Bài tập về nhà...........................................................................................................................45
Bài tập 11: Tính tích hai đa thức........................................................................................................45
Bài thực hành số 3: Đệ quy và khử đệ quy để giải quyết một số bài toán.................................................48
Phần 1. Thực hành về đệ quy................................................................................................................48
1.1 Đệ quy - quay lui..........................................................................................................................48
1.2 Kỹ thuật nhánh cận......................................................................................................................51
1. Đệ quy có nhớ................................................................................................................................54
Phần 2. Khử đệ quy...............................................................................................................................56
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
Bài tập 5: Tính tổ hợp........................................................................................................................56
Bài tập 6: Tìm ước chung lớn nhất.....................................................................................................58
Bài tập 7: Liệt kê xâu nhị phân...........................................................................................................60
Bài tập 8: Cân đĩa...............................................................................................................................62
Phần 3. Bài tập về nhà...........................................................................................................................64
Bài tập 9 : Lập lịch cho y tá................................................................................................................64
Bài tập 10 Khoảng cách Hamming.....................................................................................................67
Bài tập 11: Lịch trình chụp ảnh..........................................................................................................70
Bài tập 12 : Đếm đường đi.................................................................................................................74
Bài thực hành số 4: Thực hành sử dụng các cấu trúc dữ liệu cơ bản để giải quyết các bài toán cụ thể....76
Phần 1. Bài tập thực hành.....................................................................................................................76
Bài tập 1: Đảo ngược một danh sách liên kết đơn.............................................................................76
Bài tập 2: Tính diện tích tam giác.......................................................................................................78
Bài tập 3: Tính tích có hướng của 2 vector........................................................................................79
Bài tập 4: Thao tác với vector............................................................................................................81
Bài tập 5: Thực hiện thuật tốn DFS khơng sử dụng đệ quy trên đồ thị biểu diễn bằng danh sách kề.
...........................................................................................................................................................83
Bài tập 6: Thực hiện thuật toán BFS trên đồ thị biểu diễn bằng danh sách kề..................................86
Bài tập 7: Thực hiện các phép giao và hợp của hai tập hợp được biểu diễn bằng set.......................88
Bài tập 8: Thực hiện các phép giao và hợp của hai tập hợp mờ được biểu diễn bằng map...............90
Bài tập 9 : Cài đặt thuật toán Dijkstra trên đồ thị vô hướng được biểu diễn bằng danh sách kề sử
dụng priority_queue..........................................................................................................................93
Phần 2. Bài tập về nhà...........................................................................................................................96
Bài tập 10: Search Engine..................................................................................................................96
Bài thực hành số 5: Thực hành gỡ rối, kiểm thử và tinh chỉnh mã nguồn...............................................101
Phần 1. Thực hành gỡ rối.....................................................................................................................101
1.1 Hướng dẫn tìm một số lỗi cú pháp (Syntax Error) thường gặp..................................................101
1.2 Thực hành sửa lỗi cú pháp.........................................................................................................101
Bài tập 1: Tìm và sửa các lỗi cú pháp...............................................................................................101
Bài tập 2: Tìm và sửa các lỗi cú pháp...............................................................................................102
1.3 Hướng dẫn tìm một số lỗi thực thi (Runtime Error)...................................................................104
1.4 Hướng dẫn tìm một số lỗi logic..................................................................................................104
1.5 Tìm vị trí lỗi bằng trình debug....................................................................................................104
1.6 Tìm vị trí lỗi bằng cách in ra màn hình / file log.........................................................................104
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
1.7 Thực hành sửa lỗi thực thi và lỗi logic.......................................................................................104
Bài tập 3 : Dãy Ngoặc Đúng..............................................................................................................104
Phần 2. Kiểm thử.................................................................................................................................107
2.1 Hướng dẫn.................................................................................................................................107
2.2 Thực hành..................................................................................................................................107
Bài tập 4: Bài toán người du lịch......................................................................................................107
Phần 3. Tinh chỉnh mã nguồn..............................................................................................................113
Bài tập 5: Năm nhuận......................................................................................................................113
Bài tập 6: Tổng kết...........................................................................................................................114
Bài tập 7: Chia tiền...........................................................................................................................116
Danh mục hình ảnhc hình ảnhnh
Hình 1 Bài 1.1 Phép tốn & trả về địa chỉ của biến....................................................................................6
Hình 2 Bài 1.2 Phép toán & trả về địa chỉ của biến....................................................................................7
Hình 3 Bài 1.3 Phép tốn & trả về địa chỉ của biến....................................................................................8
Hình 4 Bài 1.4 Con trỏ và mảng.................................................................................................................9
Hình 5 Bài 1.5 Con trỏ và mảng...............................................................................................................11
Hình 6 Bài 1.6 Con trỏ và mảng...............................................................................................................13
Hình 7 Bài 1.7 Cấp phát động..................................................................................................................15
Hình 8 Bài 1.8 Cấp phát động...................................................................................................................18
Hình 9 Bài 1.9...........................................................................................................................................20
Hình 10 Bài 1.10.......................................................................................................................................23
Hình 1 Bài 2.1 Truyền tham trị.................................................................................................................24
Hình 2 Bài 2.2 Truyền tham chiếu............................................................................................................26
Hình 3 Bài 2.3 Tham số ngầm định..........................................................................................................28
Hình 4 Bài 2.4 Đa năng hóa hàm.............................................................................................................29
Hình 5 Bài 2.5 Đa năng hóa tốn tử........................................................................................................31
Hình 6 Bài 2.6 Con trỏ hàm.....................................................................................................................33
Hình 7 Bài 2.7 Khái qt hóa hàm...........................................................................................................35
Hình 8 Bài 2.8 Sắp xếp.............................................................................................................................36
Hình 9 Bài 2.9 Tính hàm sigmoid..............................................................................................................40
Hình 10 Bài 2.10 Tích hai ma trận vng.................................................................................................44
Hình 11 Bài 2.11 Tích hai đa thức............................................................................................................48
Hình 1 Bài 3.1 Dãy Lucas..........................................................................................................................49
Hình 2 Bài 3.2 Quân mã đi tuần...............................................................................................................51
Hình 3 Bài 3.3 Bài tốn người du lịch.......................................................................................................53
Hình 4 Bài 3.4 LIS....................................................................................................................................56
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
Hình 5 Bài 3.5 Tính tổ hợp......................................................................................................................58
Hình 6 Bài 3.6 Tính ước chung lớn nhất..................................................................................................60
Hình 7 Bài 3.7 Liệt kê xâu nhị phân.........................................................................................................62
Hình 8 Bài 2.8 Sắp xếp.............................................................................................................................64
Hình 9 Bài 3.9 Lập lịch cho y tá................................................................................................................67
Hình 10 Bài 3.10 Khoảng cách Hamming.................................................................................................70
Hình 11 Bài 3.11 Lịch trình chụp ảnh ......................................................................................................74
Hình 12 Bài 3.12 Đếm đường đi...............................................................................................................76
Hình 1 Bài 4.1 Danh sách liên kết đơn.....................................................................................................78
Hình 2 Bài 4.2 Tính diện tích tam giác......................................................................................................79
Hình 3 Bài 4.3 Tích có hướng của 2 vector...............................................................................................81
Hình 4 Bài 4.4 Thao tác với vector..........................................................................................................83
Hình 5 Bài 4.5 DFS...................................................................................................................................86
Hình 6 Bài 4.6 BFS...................................................................................................................................88
Hình 7 Bài 4.7 Set....................................................................................................................................90
Hình 8 Bài 4.8 Map..................................................................................................................................93
Hình 9 Bài 4.9 Dijkstra..............................................................................................................................96
Hình 10 Bài 4.10 Search engine.............................................................................................................100
Hình 1 Bài 5.1 Tìm và sửa các lỗi cú pháp..............................................................................................102
Hình 2 Bài 5.2 Tìm và sửa lỗi cú pháp....................................................................................................103
Hình 3 Bài 5.3 Tìm dãy ngoặc đúng........................................................................................................107
Hình 4 Bài 5.4 Bài tốn người du lịch....................................................................................................113
Hình 5 Bài 5.5 Năm nhuận....................................................................................................................114
Hình 6 Bài 5.6 Điểm tổng kết................................................................................................................116
Hình 7 Bài 5.7 Chia tiền.........................................................................................................................117
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
Bài thực hành số 1: Con trỏ và cấp phátc hành số 1: Con trỏ và cấp phát 1: Con trỏ và cấp phát và cấp phátp phát
Phần 1. Thực hành về con trỏn 1. Thực hành số 1: Con trỏ và cấp phátc hành về con trỏ con trỏ và cấp phát
1. Bài tập 1: p 1:
Viết một chương trình C nhập vào 3 số nguyên. Thiết lập một con trỏ để lần lượt trỏ tới từng số
nguyên và hiển thị kết quả giá trị tham chiếu ngược của con trỏ. Lưu ý: Phép toán & trả về địa
chỉ của biến.
Tên file: 20183555-NguyenXuanHuy_Bai 1_1.cpp
# include <stdio.h>
int main(){
printf("Ho va Ten: Nguyen Xuan Huy\n");
printf("MSSV:20183555 \n");
int x, y, z;
int* ptr;
printf("Enter three integers: ");
scanf("%d %d %d", &x, &y, &z);
printf("\nThe three integers are:\n");
ptr = &x;
printf("x = %d\n", *ptr);
ptr = &y;
printf("y = %d\n", *ptr);
ptr = &z;
printf("z = %d\n", *ptr);
return 0;
}
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
Hình 1 Bài 1.1 Phép toán & trả về địa chỉ của biến
2. Bài tập 1: p 2:
Viết chương trình in ra địa chỉ của 5 phần tử đầu tiên trong mảng được định nghĩa sau đây: int
a[7]= {13, -355, 235, 47, 67, 943, 1222}; Lưu ý: Để in địa chỉ con trỏ các bạn sử dụng ký tự định
dạng %p
Tên file: 20183555-NguyenXuanHuy_Bai 1_2.cpp
#include <stdio.h>
int main(){
int i;
printf("Ho va Ten: Nguyen Xuan Huy\n");
printf("MSSV:20183555 \n");
int a[7]= {13, -355, 235, 47, 67, 943, 1222};
printf("address of first five elements in memory.\n");
for (i=0; i<5;i++)
{
printf("\ta[%d]",i);
printf("\n");
printf("address: %p \n",a+i);
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
}
return 0;
}
Hình 2 Bài 1.2 Phép toán & trả về địa chỉ của biến
3. Bài tập 1: p 3:
Viết chương trình yêu cầu nhập giá trị cho 3 biến số nguyên a, b, c kiểu int. Sau đó sử dụng duy nhất
một con trỏ để cộng giá trị của mỗi biến thêm 100.
Tên file: 20183555-NguyenXuanHuy_Bai 1_3.cpp
#include <stdio.h>
void main(void)
{
printf("Ho va Ten: Nguyen Xuan Huy\n");
printf("MSSV:20183555 \n");
int x = 25, y = 50, z = 75;
int *ptr;
printf("Here are the values of x, y, and z:\n");
printf("%d %d %d\n", x, y, z);
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
ptr=&x;
(*ptr)+=100; //x+=100
ptr=&y;
(*ptr)+=100; //y+=100
ptr=&z;
(*ptr)+=100; //z+100
printf("Once again, here are the values of x, y, and z:\n");
printf("%d %d %d\n", x,y, z);
}
Hình 3 Bài 1.3 Phép tốn & trả về địa chỉ của biến
4. Bài tập 1: p 4:
Viết hàm countEven(int*, int) nhận một mảng số nguyên và kích thước của mảng, trả về số lượng số
chẵn trong mảng.
Tên file: 20183555-NguyenXuanHuy_Bai 1_4.cpp
#include <stdio.h>
int counteven(int* arr, int size){
int i;
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
int count =0;
for(i=0;i
}
return count;
}
int main(){
int i;
printf("Ho va Ten: Nguyen Xuan Huy\n");
printf("MSSV:20183555 \n");
int a[7]= {13, -352, 235, 42, 67, 943, 122};
printf("So luong so chan: %d",counteven(a,sizeof(a)/sizeof(int)));
return 0;
}
Hình 4 Bài 1.4 Con trỏ và mảng
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
5. Bài tập 1: p 5:
Viết hàm trả về con trỏ trỏ tới giá trị lớn nhất của một mảng các số double. Nếu mảng rỗng hãy trả về
NULL.
Tên file: 20183555-NguyenXuanHuy_Bai 1_5.cpp
#include <stdio.h>
double* maximum(double* a, int size){
double *max;
int i;
max=a;
if (a==NULL) return NULL;
for(i=0;i
}
return max;
}
int main(){
int i;
printf("Ho va Ten: Nguyen Xuan Huy\n");
printf("MSSV:20183555 \n");
double a[7]= {13.5, -352.5, 235.56, 42.550, 67.7, 943.7, 122.4};
printf("Max la: %0.1f",*maximum(a,sizeof(a)/sizeof(double)));
return 0;
}
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
Hình 5 Bài 1.5 Con trỏ và mảng
6. Bài tập 1: p 6:
Viết hàm đảo ngược một mảng các số nguyên theo hai cách: dùng chỉ số và dùng con trỏ. Ví dụ mảng
đầu vào là [9, -1, 4, 5, 7] thì kết quả là [7, 5, 4, -1, 9].
Tên file: 20183555-NguyenXuanHuy_Bai 1_6.cpp
#include <stdio.h>
void reversearray1(int arr[], int size){
int i, j, tmp;
i=0; j= size -1;
for(i=0;i
arr[j-i]=arr[i];
arr[i]=tmp;
}
}
void reversearray2(int *arr, int size){
int i, j, tmp;
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
i=0; j= size -1;
for(i=0;i
*(arr+i)=*(arr+j-i);
*(arr+j-i)=tmp;
}
}
int main(){
printf("Ho va Ten: Nguyen Xuan Huy\n");
printf("MSSV:20183555 \n");
int i;
int a[5]={9, -1, 4, 5, 7};
reversearray1(a,sizeof(a)/sizeof(int));
printf("After reverse1: ");
for(i=0;i<5;i++){
printf("%d ",a[i]);
}
reversearray2(a,sizeof(a)/sizeof(int));
printf("\nAfter reverse2: ");
for(i=0;i<5;i++) {
printf("%d ",a[i]);
}
return 0;
}
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
Hình 6 Bài 1.6 Con trỏ và mảng
7. Bài tập 1: p 7:
Viết chương trình nhập vào một mảng các số nguyên với số lượng các phần tử nhập từ bàn phím. Sau đó
sắp xếp mảng theo thứ tự tăng dần. Hiển thị danh sách mảng trước và sau khi sắp xếp. Yêu cầu chỉ sử
dụng con trỏ để truy cập mảng, không truy cập theo index mảng.
Tên file: 20183555-NguyenXuanHuy_Bai 1_7.cpp
#include <stdio.h>
int *a;
int n, tmp;
int main(){
printf("Ho va Ten: Nguyen Xuan Huy\n");
printf("MSSV:20183555 \n");
int i,j,tmp;
printf("Enter the number of elements: ");
scanf("%d", &n);
a = (int *) calloc( n, sizeof( int ));
for( i = 0; i < n; i++)
{
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
scanf("%d", a + i);
}
printf("The input array is: \n");
for( i = 0; i < n; i++)
{
printf("%d ", *(a + i));
printf("\n");
}
for(i=0;i
for(j=i+1;j
if(*(a+j)<*(a+i))
{
tmp=*(a+j);
*(a+j)=*(a+i);
*(a+i)=tmp;
}
}
}
printf("The sorted array is: \n");
for( i = 0; i < n; i++)
{
printf("%d ", *(a + i));
printf("\n");
}
free(a);
return 0;
}
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
Hình 7 Bài 1.7 Cấp phát động
8. Bài tập 1: p 8
Viết chương trình nhập vào một ma trận 2 chiều kích thước m*n với m và n nhập từ bàn phím. Sau đó
đưa ra tổng các phần tử chẵn của ma trận đó.
Tên file: 20183555-NguyenXuanHuy_Bai 1_8.cpp
#include <stdio.h>
void input(int **mt, int m, int n){
int i,j;
for(i=0;i
for(j=0;j
scanf("%d",(*(mt+i)+j));
}
}
}
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
void output(int **mt, int m, int n){
int i,j;
for(i=0;i
for(j=0;j
printf("%d ",*(*(mt+i)+j));
}
printf("\n");
}
}
int process(int **mt, int m, int n){
int tong = 0;
int i,j;
for(i=0;i
for(j=0;j
tong+=*(*(mt+i)+j);
}
}
return tong;
}
void free_mem(int **mt, int m, int n){
int i;
for (i = 0; i < m; i++)
{
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
free(mt[i]);
}
free(mt);
}
int main(){
printf("Ho va Ten: Nguyen Xuan Huy\n");
printf("MSSV:20183555 \n");
int i;
int m, n, **mt;
printf("Enter m, n = ");
scanf("%d %d", &m, &n);
mt = (int **)malloc(m * sizeof(int *));
for (i = 0; i < m; i++)
{
mt[i] = (int *)malloc(n * sizeof(int));
}
input(mt, m, n);
output(mt, m, n);
printf("The sum of all even elements is %d", process(mt, m, n));
free_mem(mt, m, n);
return 0;
}
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
Hình 8 Bài 1.8 Cấp phát động
Phần 1. Thực hành về con trỏn 2. Bài tập 1: p về con trỏ nhà
Bài tập 1: p 9
Viết chương trình in ra tất cả các dãy con của một dãy cho trước. Ví dụ dãy 1 3 4 2 có các dãy con sau:
1
13
134
1342
3
34
342
4
42
Tên file: 20183555-NguyenXuanHuy_Bai 1_9.cpp
# include <stdio.h>
int main(){
printf("Ho va Ten: Nguyen Xuan Huy\n");
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
printf("MSSV:20183555 \n");
int n,i,j,k;
scanf("%d",&n);
int *arr= (int*)calloc(n,sizeof(int));
for(i=0;i
scanf("%d",arr+i);
}
for(i=0;i
for(j=i;j
k=i;
while(k<=j)
{
printf("%d ",*(arr+k));
k++;
}
printf("\n");
}
}
free(arr);
return 0;
}
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
24-20183555-NguyenXuanHuy - IT3040- 697698 – BTH01-05
Hình 9 Bài 1.9
Bài tập 1: p 10
Viết chương trình nhập vào 2 ma trận vng cùng kích thước n*n, trong đó n nhập từ bàn phím. Sau đó
tính tổng và tích của hai ma trận đó và đưa kết quả ra màn hình. u cầu sử dụng cấp phát động để cấp
phát bộ nhớ cho các ma trận.
Tên file: 20183555-NguyenXuanHuy_Bai 1_10.cpp
#include <stdio.h>
int n;
void input(int **mt, int n){
int i,j;
for(i=0;i
for(j=0;j
scanf("%d",(*(mt+i)+j));
}
Báo cáo thực hành Kỹ thuật lập trình – IT3040 - 20193
