Tài liệu thực hành môn Kỹ thuật lập trình| Trường Đại học Bách Khoa Hà Nội

Bài thực hành 1: Con trỏ và cấp phát động
Trong bài này các bạn sẽ làm quen với việc sử dụng con trỏ và cấp phát động.
Phần 1. Thực hành về con trỏ Bài tậ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. In [ ]: # include int main(){ 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); /***************** # YOUR CODE HERE # *****************/ return 0; } Bài tậ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
Để lấy địa chỉ của một biến ta có thể dùng phép toán & In [ ]: #include int main(){
int a[7]= {13, -355, 235, 47, 67, 943, 1222};
printf("address of first five elements in memory.\n");
for (int i=0; i<5;i++) printf("\ta[%d] ",i); printf("\n"); /***************** # YOUR CODE HERE # *****************/ return 0; } Bài tập 3
Viết chương trình yêu cầu nhập giá trị cho 3 biến số nguyên x, y, z 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. In [ ]: #include int main() { int x, y, z; int *ptr;
scanf("%d %d %d", &x, &y, &z);
printf("Here are the values of x, y, and z:\n");
printf("%d %d %d\n", x, y, z); /***************** # YOUR CODE HERE # *****************/
printf("Once again, here are the values of x, y, and z:\n");
printf("%d %d %d\n", x, y, z); return 0; }
Phần 2. Con trỏ và mảng Bài tậ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. In [ ]:
int counteven(int* arr, int size){ int count = 0; /***************** # YOUR CODE HERE # *****************/ return count; } Bài tậ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. In [ ]:
double* maximum(double* a, int size){ double *max; max = a;
if (a==NULL) return NULL; /***************** # YOUR CODE HERE # *****************/ return max; } Bài tậ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]. In [ ]:
void reversearray(int arr[], int size){ int l = 0, r = size - 1, tmp; /***************** # YOUR CODE HERE # *****************/ }
void ptr_reversearray(int *arr, int size){ int l = 0, r = size - 1, tmp; /***************** # YOUR CODE HERE # *****************/ }
Phần 3. Cấp phát động Bài tậ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. In [ ]: #include int *a; int n, tmp; int main(){
printf("Enter the number of elements: "); scanf("%d", &n); //#Allocate memory /***************** # YOUR CODE HERE # *****************/
for(int i = 0; i < n; i++) scanf("%d", a + i);
printf("The input array is: \n");
for(int i = 0; i < n; i++)
printf("%d ", *(a + i)); printf("\n"); //#Sort array /***************** # YOUR CODE HERE # *****************/
printf("The sorted array is: \n");
for(int i = 0; i < n; i++)
printf("%d ", *(a + i)); printf("\n"); delete [] a; return 0; } Bài tậ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 đó.
Lưu ý: Khi viết hàm cấp phát bộ nhớ cho một ma trận hai chiều biểu diễn bởi con trỏ int **mt,
nếu ta truyền con trỏ theo kiểu địa chỉ void allocate(int **mt, int m, int n) sẽ dẫn tới
việc cấp phát bộ nhớ cho một bản sao của con trỏ **mt. Do đó, sau khi gọi hàm thì con
trỏ **mt gốc vẫn không được cấp phát bộ nhớ. Để cấp phát thành công cần truyền con trỏ theo dạng
địa chỉ, ví dụ sử dụng con trỏ cấp 3 dạng int ***mt. In [ ]: #include
void allocate_mem(int ***mt, int m, int n){
//#Allocate memory for the matrix /***************** # YOUR CODE HERE # *****************/ }
void input(int **mt, int m, int n){
//#Input elements of the matrix /***************** # YOUR CODE HERE # *****************/ }
void output(int **mt, int m, int n){
//# Print all elements of the matrix /***************** # YOUR CODE HERE # *****************/ }
int process(int **mt, int m, int n){ int tong = 0;
//# Calculate the sum of all even elements in the matrix /***************** # YOUR CODE HERE # *****************/ return tong; }
void free_mem(int **mt, int m, int n){ //# Free memory /***************** # YOUR CODE HERE # *****************/ } int main(){ int m, n, **mt; printf("Enter m, n = ");
scanf("%d%d", &m, &n); allocate_mem(&mt, m, n); 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; }
Phần 4. Bài tập về nhà Bài tậ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 1 3 1 3 4 1 3 4 2 3 3 4 3 4 2 4 4 2 2 Bài tập 10
Viết chương trình nhập vào 2 ma trận vuông 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.
Yêu cầu sử dụng cấp phát động để cấp phát bộ nhớ cho các ma trận.
Bài thực hành 2: Hàm và tối ưu mã nguồn
Phần 1. Thực hành về hàm
1.1 Truyền tham trị, tham chiếu và tham số ngầm định
Bài tập 1: Truyền tham trị
Viết hàm tính độ dài cạnh huyền của tam giác theo độ hai cạnh góc vuông. In [ ]: #include #include
float get_hypotenuse(float x, float y) { /***************** # YOUR CODE HERE # *****************/ } int main(){ float x, y;
scanf("%f%f", &x, &y);
float z = get_hypotenuse(x, y);
printf("z = %.2f\n", z); return 0; }
Bài tập 2: Truyền tham chiếu
Viết hàm hoán vị vòng tròn 3 biến a, b, c. Sau khi thực hiện hàm, các biến a, b, c tương ứng nhận các giá trị mới b, c, a. In [ ]: #include
void rotate(int &x, int &y, int &z) { /***************** # YOUR CODE HERE # *****************/ } int main() { int x, y, z; //# Nhập 3 số nguyên /***************** # YOUR CODE HERE # *****************/
printf("Before: %d, %d, %d\n", x, y, z); rotate(x, y, z);
printf("After: %d, %d, %d\n", x, y, z); return 0; }
Bài tập 3: Tham số ngầm định
Viết chương trình yêu cầu nhập giá trị cho số nguyên x nhỏ hơn 100. In ra giá trị ax2+bx+c với a, b, c định sẵn. In [ ]: #include
//# Viê t hàm get_value /***************** # YOUR CODE HERE # *****************/ int main(){ int x; scanf("%d", &x);
int a = 2; //# giá trị mặc định cu-a a
int b = 1; //# giá trị mặc định cu-a b
int c = 0; //# giá trị mặc định cu-a c
//# Nhập 3 số nguyên a, b, c từ bàn phím /***************** # YOUR CODE HERE # *****************/
printf("a=2, b=1, c=0: %d\n", get_value(x));
printf("a=%d, b=1, c=0: %d\n", a, get_value(x, a));
printf("a=%d, b=%d, c=0: %d\n", a, b, get_value(x, a, b));
printf("a=%d, b=%d, c=%d: %d\n", a, b, c, get_value(x, a, b, c)); return 0; } 1.2 Đa năng hóa hàm
Bài tập 4: Đa năng hóa hàm
Viết các hàm tính lập phương của số nguyên và số thực. In [ ]: #include int cube(int x) {
//# tra- vê2 lập phương cu-a x /***************** # YOUR CODE HERE # *****************/ }
//# viê t hàm tính lập phương cu-a một số kiê-u double /***************** # YOUR CODE HERE # *****************/ int main() { int n; double f;
scanf("%d %lf", &n, &f);
printf("Int: %d\n", cube(n));
printf("Double: %.2lf\n", cube(f)); return 0; }
Bài tập 5: Đa năng hóa toán tử
Viết các toán tử tính tổng, hiệu, tích và thương của hai số phức. In [ ]: #include #include #include #include using namespace std; struct Complex { double real; double imag; };
Complex operator + (Complex a, Complex b) { /***************** # YOUR CODE HERE # *****************/ }
Complex operator - (Complex a, Complex b) { /***************** # YOUR CODE HERE # *****************/ }
Complex operator * (Complex a, Complex b) { /***************** # YOUR CODE HERE # *****************/ }
Complex operator / (Complex a, Complex b) { /***************** # YOUR CODE HERE # *****************/ }
ostream& operator << (ostream& out, const Complex &a) {
out << '(' << std::setprecision(2) << a.real << (a.imag >= 0 ? '+' : '-')
<< std::setprecision(2) << fabs(a.imag) << 'i' << ')'; return out; } int main() {
double real_a, real_b, img_a, img_b;
cin >> real_a >> img_a;
cin >> real_b >> img_b; Complex a{real_a, img_a}; Complex b{real_b, img_b};
cout << a << " + " << b << " = " << a + b << endl;
cout << a << " - " << b << " = " << a - b << endl;
cout << a << " * " << b << " = " << a * b << endl;
cout << a << " / " << b << " = " << a / b << endl; return 0; }
1.3 Con trỏ hàm và tham số hóa hàm Bài tập 6: Con trỏ hàm
Giả thuyết Collatz: bắt đầu từ số dương n bất kỳ, nếu n chẵn thì chia 2, nếu lẻ thì nhân 3 cộng 1,
giả thuyết cho rằng ta luôn đi đến n=1.
Hãy viết chương trình mô phỏng lại quá trình biến đổi để kiếm chứng giả thuyết với giá trị
của n nhập từ bàn phím. In [ ]: #include void print(int n) { printf("n=%d\n", n); } int mul3plus1(int n) { return n * 3 + 1; } int div2(int n) { return n / 2; } // khai báo các tham số; cho các con tro < hàm odd, even và output
void simulate(int n, /*****************# YOUR CODE HERE #*****************/) { (*output)(n);
if (n == 1) return; if (n % 2 == 0) { n = (*even)(n); } else { n = (*odd)(n); }
simulate(n, odd, even, output); } int main() { int (*odd)(int) = NULL; int (*even)(int) = NULL; /***************** # YOUR CODE HERE # *****************/ int n; scanf("%d", &n);
simulate(n, odd, even, print); return 0; }
Bài tập 7: Khái quát hóa hàm
Viết hàm tính tổng các phần tử trong hai mảng.
Yêu cầu sử dụng function template để cho phép hàm làm việc với các mảng số nguyên lẫn số thực. In [ ]: #include using namespace std; //# viê t hàm arr_sum /***************** # YOUR CODE HERE # *****************/ int main() { int val; cin >> val; { int a[] = {3, 2, 0, val}; int b[] = {5, 6, 1, 2, 7};
cout << arr_sum(a, 4, b, 5) << endl; } {
double a[] = {3.0, 2, 0, val * 1.0};
double b[] = {5, 6.1, 1, 2.3, 7};
cout << arr_sum(a, 4, b, 5) << endl; } return 0; }
1.4 Biểu thức lamda và hàm nặc danh Bài tập 8: Sắp xếp
Viết hàm so sánh cho thuật toán sắp xếp. In [ ]: #include #include #include #include using namespace std; int main() { int val1, val2;
cin >> val1 >> val2; vector< vector > a = { {1, 3, 7}, {2, 3, 4, val1}, {9, 8, 15}, {10, val2}, };
//# sắ p xê p các vector trong a theo tố-ng các phầ2n tư- gia-m dầ2n /***************** # YOUR CODE HERE # *****************/
for (const auto &v : a) { for (int it : v) {
cout << it << ' '; } cout << endl; } return 0; }
Phần 2. Thực hành về tối ưu mã nguồn
Hãy giải các bài toán sau đây một cách tối ưu nhất có thể, cố gắng sử dụng các kỹ thuật đã được học như inline, static, ...
Bài tập 9: Tính hàm sigmoid
Dưới đây cung cấp đoạn code đơn giản để tính hàm sigmoid theo công thức trực tiếp.
Hãy viết hàm tính xấp xỉ sigmoid(x) đến độ chính xác 10−6 và có tốc độ nhanh hơn ít nhất 30% so với code đơn giản.
Gợi ý: sử dụng kỹ thuật "chuẩn bị trước" như trong slide. In [ ]: #include #include #include #include #include #include using namespace std; const int LIMIT = 100; const int NUM_ITER = 100000;
const int NUM_INPUTS = NUM_ITER * 100;
double sigmoid_slow(double x) {
return 1.0 / (1.0 + exp(-x)); } double x[NUM_INPUTS]; void prepare_input() {
const int PRECISION = 1000000;
const double RANGE = LIMIT / 20.0;
for (int i = 0; i < NUM_INPUTS; ++i) {
x[i] = RANGE * (rand() % PRECISION - rand() % PRECISION) / PRECISION; } } //# BEGIN fast code
//# khai báo các biê n phụ trợ cầ2n thiê t /***************** # YOUR CODE HERE # *****************/
//# hàm chuầ-n bị dữ liệu void precalc() { /***************** # YOUR CODE HERE # *****************/ }
//# hàm tính sigmoid(x) nhanh sigmoid_fast(x)
inline double sigmoid_fast(double x) { /***************** # YOUR CODE HERE # *****************/ } //# END fast code
double benchmark(double (*calc)(double), vector &result) { const int NUM_TEST = 20; double taken = 0; result = vector(); result.reserve(NUM_ITER); int input_id = 0; clock_t start = clock();
for (int t = 0; t < NUM_TEST; ++t) { double sum = 0;
for (int i = 0; i < NUM_ITER; ++i) {
double v = fabs(calc(x[input_id])); sum += v;
if (t == 0) result.push_back(v);
if ((++input_id) == NUM_INPUTS) input_id = 0; } } clock_t finish = clock();
taken = (double)(finish - start);
//# printf("Time: %.9f\n", taken / CLOCKS_PER_SEC); return taken; }
bool is_correct(const vector &a, const vector &b) { const double EPS = 1e-6;
if (a.size() != b.size()) return false;
for (int i = 0; i < a.size(); ++i) {
if (fabs(a[i] - b[i]) > EPS) { return false; } } return true; } int main() { prepare_input(); precalc(); vector a, b;
double slow = benchmark(sigmoid_slow, a);
double fast = benchmark(sigmoid_fast, b); double xval;
scanf("%lf", &xval);
printf("%.2f \n", sigmoid_fast(xval));
if (is_correct(a, b) && (slow/fast > 1.3)) {
printf("Correct answer! Your code is faster\n"); } else {
printf("Wrong answer or your code is not fast enough!\n"); } return 0; }
Bài tập 10 (bonus): Tính tích hai ma trận vuông
Dưới đây cung cấp đoạn code đơn giản để tính tích của hai ma trận cỡ NxN theo công thức trực tiếp.
Hãy viết hàm tính tích hai ma trận nhưng có tốc độ nhanh hơn ít nhất 10% so với code đơn giản.
Gợi ý: hãy để ý đến thứ tự truy cập các phần tử trong ma trận, tối ưu cache hoặc sử dụng thuật toán tốt hơn O(N3). In [ ]: #include #include using namespace std; const int N = 128; struct Matrix { unsigned int mat[N][N]; Matrix() { memset(mat, 0, sizeof mat); } };
bool operator == (const Matrix &a, const Matrix &b) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (a.mat[i][j] != b.mat[i][j]) return false; } } return true; }
Matrix multiply_naive(const Matrix &a, const Matrix &b) { Matrix c;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
c.mat[i][j] += a.mat[i][k] * b.mat[k][j]; } } } return c; }
Matrix multiply_fast(const Matrix &a, const Matrix &b) { /***************** # YOUR CODE HERE # *****************/ } Matrix gen_random_matrix() { Matrix a;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) { a.mat[i][j] = rand(); } } return a; } Matrix base;
double benchmark(Matrix (*multiply) (const Matrix&, const Matrix&), Matrix &result) { const int NUM_TEST = 10; const int NUM_ITER = 64; Matrix a = base; result = a; double taken = 0;
for (int t = 0; t < NUM_TEST; ++t) { clock_t start = clock();
for (int i = 0; i < NUM_ITER; ++i) { a = multiply(a, result); result = multiply(result, a); } clock_t finish = clock();
taken += (double)(finish - start); } taken /= NUM_TEST;
printf("Time: %.9f\n", taken / CLOCKS_PER_SEC); return taken; } int main() { base = gen_random_matrix(); Matrix a, b;
printf("Slow version\n");
double slow = benchmark(multiply_naive, a);
printf("Fast version\n");
double fast = benchmark(multiply_fast, b); if (a == b) {
printf("Correct answer! Your code is %.2f%% faster\n", slow / fast * 100.0); } else {
printf("Wrong answer!\n"); } return 0; }
Phần 3. Bài tập về nhà
Bài tập 11: Tính tích hai đa thức
Cho 2 đa thức A(x) và B(x) tương ứng có bậc N và M. Hãy tính ma trận tích C(x) = A(x) * B(x) có bậc N+M−1.
Input: Gồm 2 dòng biểu diễn các đa thức A(x) và B(x), mỗi dòng
 Số đầu tiên N là bậc của đa thức;
 N+1 số nguyên tiếp theo, số thứ i là hệ số của xi−1.
Output: Một số nguyên duy nhất là XOR của các hệ số của đa thức C(x). Ví dụ: Input: 3 83 86 77 15 4 93 35 86 92 49 Output: 20731
Giải thích: các hệ số của đa thức kết quả lần lượt là 7719, 10903, 17309, 19122, 19126, 12588, 5153, 735. Giới hạn:
 Các hệ số của các đa thức đầu vào có trị tuyệt đối nhỏ hơn 100.
 Có 5 tests, test thứ i có bậc của các đa thức đầu vào không quá 10i. Bài tập 12: Map Sort
Hôm nay, cô giáo giao cho An một câu hỏi hóc búa. Cô cho một danh sách với mỗi phần tử có dạng
và yêu cầu An sắp xếp danh sách đó giảm dần theo giá trị value. Nếu 2 phần tử có
value giống nhau thì sắp xếp giảm dần theo key.
Hãy viết một chương trình sử dụng hàm nặc danh để giúp An làm bài tập.
Input: Danh sách đầu vào. Mỗi dòng ghi một cặp giá trị key, value cách nhau bởi dấu cách (| key| ≤109, |value| ≤109).
Output: In danh sách đã được sắp xếp theo yêu cầu. Mỗi dòng ghi một cặp giá trị key, value cách nhau bởi dấu cách. Ví dụ: Input: 2 3 4 8 9 1 1 8 Output: 4 8 1 8 2 3 9 1 Bài tập 13: Big Integer
Số nguyên lớn là các số nguyên có giá trị rất lớn và không thể biểu diễn bằng các kiểu dữ liệu
nguyên cơ bản. Để biểu diễn số nguyên lớn, ta có thể dùng kiểu struct như sau: struct bigNum{ char sign; char num[101]; };
Nhiệm vụ các bạn là đa năng hóa các toán tử để thực hiện các phép toán số học với kiểu dữ liệu số
nguyên lớn vừa định nghĩa ở trên.
Input: Dữ liệu vào gồm hai dòng mô tả hai số nguyên lớn a và b, mỗi dòng chứa 1 chuỗi ký tự mô
tả 1 số nguyên lớn không vượt quá 10100. Chữ số đầu của mỗi chuỗi ký tự sẽ thể hiện dấu của số
đó: 0 là âm, 1 là dương. Các chữ số sau thể hiện giá trị của số đó.
Output: In ra giá trị của biểu thức ab−3a+4b. Kết quả in ra một số nguyên lớn dưới dạng chuỗi
ký tự có định dạng như mô tả trong dữ liệu vào. Ví dụ: Input: 0121807015 1347227347 Output: 042294724910108772 In [ ]:
Bài thực hành 3: Đệ quy và khử đệ quy để
giải quyết một số bài toán
Phần 1. Thực hành về đệ quy 1.1 Đệ quy - quay lui Bài tập 1: Tính dãy Lucas
Dãy Lucas được định nghĩa bởi Ln=Ln−1+Ln−2 và bắt đầu bởi L0=2, L1=1. Viết hàm tính số Lucas thứ n. In [ ]: int lucas(int n) { /***************** # YOUR CODE HERE # *****************/ }
Bài tập 2: Quân mã đi tuần
Trên bàn cờ vua kích thước n×n có một quân mã đang ở ô (1, 1). Hãy đưa ra một dãy các di
chuyển của mã sao cho mỗi ô trên bàn cờ đều được đi qua đúng 1 lần (ô (1, 1) được xem là đã đi qua) In [ ]: #include using namespace std; int n;
int X[100], Y[100]; //# Lưu tọa độ các bước di chuyể%n cu%a quân mã
int mark[100][100]; //# Đánh dâ*u vị trí các ô mà quân mã đã di chuyể%n qua
//# Ma%ng hx, hy mô ta% 8 vị trí quân mã có thể% di chuyể%n kể% từ vị trí hiện tại
const int hx[] = {1, 1, 2, 2, -1, -1, -2, -2};
const int hy[] = {2, -2, 1, -1, 2, -2, 1, -1};
//# In ra dãy các di chuyể%n tìm được void print_sol(){
for (int j = 1; j <= n * n; ++j)
printf("(%d %d)\n", X[j], Y[j]); exit(0); }
//# Thuật toán quay lui void TRY(int k){
for(int i = 0; i < 8; i++){ int xx = X[k-1] + hx[i]; int yy = Y[k-1] + hy[i]; /***************** # YOUR CODE HERE # *****************/ } } int main(){ cin >> n; mark[1][1] = 1; X[1] = Y[1] = 1; TRY(2); return 0; }
1.2 Kỹ thuật nhánh cận
Bài tập 3: Bài toán người du lịch
Một người xuất phát tại thành phố 1, muốn đi thăm tất cả các thành phố khác, mỗi thành phố đúng 1
lần và quay về 1. Chi phí để đi từ thành phố i sang thành phố j là ci,j. Hãy tìm tổng chi phí nhỏ nhất có thể Dữ liệu vào:
Dòng 1: Chứa số nguyên n (1≤n≤16)
n dòng tiếp theo: Chứa ma trận c (0≤ci,j≤1000000) Kết quả:
Ghi tổng chi phí nhỏ nhất có thể Ví dụ: Dữ liệu mẫu: 4 0 2 1 3 4 0 1 2 2 1 0 3 3 4 2 0 Kết quả mẫu: 7 In [ ]: #include using namespace std; #define MAX 100
int n, c[MAX][MAX]; //# sô* thành phô* và ma trận chi phí
int cmin = INT_MAX; //# chi phí đi lại nho% nhâ*t giữa hai thành phô* khác nhau
int best = INT_MAX; //# tô%ng chi phí nho% nhâ*t câIn tìm, ban đâIu đặt bằng
giá trị vô cùng lớn INT_MAX = 2^31-1
int curr; //# tô%ng chi phí tới thời điể%m hiện tại
int mark[MAX]; //# đánh dâ*u những thành phô* đã đi
int x[MAX]; //# lưu giữ các thành phô* đã đi
//# Đọc dữ liệu vào void input(){ cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j){ cin >> c[i][j];
if (c[i][j] > 0) cmin = min(cmin, c[i][j]); } }
//# Thuật toán quay lui void TRY(int k){
for(int i = 2; i <= n; i++){ /***************** # YOUR CODE HERE # *****************/ } } int main() { input(); x[1] = 1; TRY(2); cout << best; return 0; } 1.3 Đệ quy có nhớ Bài tập 4: LIS
Cho dãy a có n phần tử. Một dãy con của a là dãy thu được bằng cách xóa đi một số phần tử
của a và giữ nguyên thứ tự các phần tử còn lại (có thể không xóa phần tử nào). Hãy tìm dãy con tăng dài nhất của a Dữ liệu vào:
Dòng 1: Chứa số nguyên n (1≤n≤1000)
Dòng 2: Chứa n số nguyên a1 a2 … an (|ai|≤109) Kết quả:
Dòng đầu tiên chứa độ dài dãy con tăng dài nhất
Dòng thứ 2 chứa chỉ số các phần tử được chọn vào dãy con đó
Nếu có nhiều dãy con tăng dài nhất, in ra dãy bất kỳ trong số đó Ví dụ: Dữ liệu mẫu: 6 2 1 5 4 3 6 Kết quả mẫu: 3 2 5 6 Hướng dẫn:
Bài toán này được giải bằng phương pháp quy hoạch động.
Giả sử lis(i) là độ dài dãy con tăng dài nhất kết thúc tại ai. Khi đó ta có công thức truy hồi sau:
lis(i)=max1≤j≤i−1:ajIn [ ]: #include using namespace std; int a[1000], n;
int mem[1000]; //# ma%ng ghi nhớ lời gia%i các bài toán con đã được gia%i void init(){ memset(mem, -1, sizeof(mem)); } //# Quy hoạch động,
//# Hàm lis(i) tra% vểI độ dài dãy con tăng dài nhâ*t kể*t thúc bở%i a[i] int lis(int i) { /***************** # YOUR CODE HERE # *****************/ } //# Truy vet loi giai void trace(int i){
for(int j = 0; j < i; j++){
if (a[j] < a[i] && mem[i] == 1 + mem[j]){ trace(j); break; } }
cout << a[i] << " "; } int main(){ init(); cin >> n;
for(int i = 0; i < n; i++) cin >> a[i]; int res = 1, pos = 0;
for(int i = 1; i < n; i++){ if (res < lis(i)){ res = lis(i); pos = i; } }
cout << res << endl; trace(pos); return 0; } Phần 2. Khử đệ quy
Hãy giải các bài toán sau đây bằng phương pháp khử đệ quy
Bài tập 5: Tính tổ hợp Tính Ckn In [ ]: #include using namespace std; int binom(int n, int k) {
if (k > n) return 0;
if (k == 0) return 1;
return binom(n-1, k) + binom(n-1, k-1); } int binom2(int n, int k){ //# Khư% đệ quy /***************** # YOUR CODE HERE # *****************/ } int main() { int m; cin >> m;
for (int n = 1; n <= m; ++n){
for (int k = 0; k <= n; ++k)
printf("%d ", binom(n, k)); printf("\n"); }
for (int n = 1; n <= m; ++n){
for (int k = 0; k <= n; ++k)
printf("%d ", binom2(n, k)); printf("\n"); } return 0;