Bài thực hành số 2: Hàm và tối ưu mã nguồn

 Bài thực hành số 2: Hàm và tối ưu mã nguồn
 Created by SangDV
 Ngày 4 tháng 4 năm 2020
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(){
 floatx=3;
 floaty=4;
 // gán x bằng4 chữ số đầu của mã số sinh viên
 // gán y bằng4 chứ số cuối của mã số sinh viên
 /*****************
 # YOUR CODE HERE #
 *****************/
 floatz= get_hypotenuse(x, y);
 printf("z = %.2f\n", z);
 return0;
 }
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() {
 1
 intx=3;
 inty=4;
 intz=5;
 // gán x bằng chữ số hàng đơn vị của mã số sinh viên
 // gán y bằng chữ số hàng chục của mã số sinh viên
 // gán z bằng chữ số hàng trăm của mã số sinh viê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);
 return0;
 }
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 get_value(int x, inta=2, intb=1, intc=0){
 returna*x*x+b*x+ c;
 }
 int main()
 {
 int x;
 scanf("%d",&x);
 inta=3;
 intb=4;
 intc=5;
 // gán a bằng4 chữ số đầu của mã số sinh viên
 // gán b bằng4 chứ số cuối của mã số sinh viên
 // gán c bằng mã số sinh viên
 /*****************
 # 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));
 return0;
 }
 2
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 
 using namespace std;
 int cube(int x) {
 // trả về lập phương của x
 /*****************
 # YOUR CODE HERE #
 *****************/
 }
 // viết hàm tính lập phương của một số kiểu double
 /*****************
 # YOUR CODE HERE #
 *****************/
 int main() {
 intn= 17;
 cout <<"Int:" << cube(n) << endl;
 cout <<"Double:" << cube(17.1) << endl;
 return0;
 }
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 
 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 #
 *****************/
 }
 3
 Complex operator/ (Complex a, Complex b) {
 /*****************
 # YOUR CODE HERE #
 *****************/
 }
 ostream& operator << (ostream& out, const Complex&a) {
 out =0 ? '+' : '-') << abs(a.imag) << 'i' << ')';
 return out;
 }
 int main() {
 Complex a{-6,-3};
 Complex b{4,6};
 cout <<a <<"+" <<b <<"=" <<a+b << endl;
 cout <<a <<"-" <<b <<"=" <<a-b << endl;
 cout <<a <<"*" <<b <<"=" <<a*b << endl;
 cout <<a <<"/" <<b <<"=" <<a/b << endl;
 return0;
 }
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 một vài giá trị của
n.
In []: #include 
 void print(int n) {
 printf("n=%d\n", n);
 }
 int div2(int n) {
 returnn*3+1;
 }
 int mul3plus1(int n) {
 returnn/2;
 }
 // khai báo các tham số cho các con trỏ 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;
 4
 int(*even)(int)= NULL;
 /*****************
 # YOUR CODE HERE #
 *****************/
 simulate(19, odd, even, print);
 return0;
 }
Bài tập 7: Khái quát hóa hàm
Viết hàm tính tích của 2 đa thức. Trong đó đa thức bậc N được biểu diễn bằng mảng các hệ số, phần tử
thứ i là giá trị của hệ số của xi.
In []: #include 
 #include 
 using namespace std;
 // viết hàm multiply, nhận vào2 mảng mảng biểu diễn đa thức và độ dài của chúng
 // trả về con trỏ tới mảng kết quả
 /*****************
 # YOUR CODE HERE #
 *****************/
 int main() {
 {
 int a[]={3,2,0,5};
 int b[]={5,6,1,2,7};
 int*c= multiply(a,4, b,5);
 for(inti=0; i<8;++i) printf("%d", c[i]);
 printf("\n");
 }
 {
 double a[]={3.0,2,0,5};
 double b[]={5, 6.1,1, 2.3,7};
 double*c= multiply(a,4, b,5);
 for(inti=0; i<8;++i) printf("%.2f", c[i]);
 printf("\n");
 }
 return0;
 }
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 
 5
 using namespace std;
 int main() {
 vector>a={
 {1,3,7},
 {2,3,4,5},
 {9,8, 15},
 {10, 10},
 };
 // sắp xếp các vector trong a theo tổng các phần tử giảm dần
 /*****************
 # YOUR CODE HERE #
 *****************/
 for (const auto&v : a) {
 for(int it : v) {
 cout << it << '' ;
 }
 cout << endl;
 }
 return0;
 }
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(inti=0; i< NUM_INPUTS;++i) {
 6
 x[i]= RANGE* (rand()% PRECISION- rand()% PRECISION)/ PRECISION;
 }
}
// BEGIN fast code
// khai báo các biến phụ trợ cần 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)
/*****************
# YOUR CODE HERE #
*****************/
// END fast code
double benchmark(double (*calc)(double), vector&result) {
 const int NUM_TEST= 1000;
 double taken=0;
 result= vector();
 result.reserve(NUM_ITER);
 int input_id=0;
 clock_t start= clock();
 for(intt=0; t< NUM_TEST;++t) {
 double sum=0;
 for(inti=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(inti=0; i<a.size();++i) {
 if (fabs(a[i]- b[i])> EPS) {
 return false;
 }
 }
 7
 return true;
 }
 int main() {
 prepare_input();
 precalc();
 vector a, b;
 printf("Slow version\n");
 double slow= benchmark(sigmoid_slow, a);
 printf("Fast version\n");
 double fast= benchmark(sigmoid_fast, b);
 if (is_correct(a, b)) {
 printf("Correct answer! Your code is %.2f%% faster\n", slow/ fast* 100.0);
 } else{
 printf("Wrong answer!\n");
 }
 return0;
 }
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 intN= 128;
 struct Matrix {
 unsigned int mat[N][N];
 Matrix() {
 memset(mat,0, sizeof mat);
 }
 };
 bool operator == (const Matrix&a, const Matrix&b) {
 for(inti=0; i<N;++i) {
 for(intj=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(inti=0; i<N;++i) {
 for(intj=0; j<N;++j) {
 for(intk=0; k<N;++k) {
 c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
 }
 8
 }
 }
 return c;
}
Matrix multiply_fast(const Matrix&a, const Matrix&b) {
 /*****************
 # YOUR CODE HERE #
 *****************/
}
Matrix gen_random_matrix() {
 Matrix a;
 for(inti=0; i<N;++i) {
 for(intj=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(intt=0; t< NUM_TEST;++t) {
 clock_t start= clock();
 for(inti=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{
 9
 printf("Wrong answer!\n");
 }
 return0;
 }
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 đa thức tích C(x) = A(x) * B(x) có bậc
N+M-1.
Dữ liệu vào: Gồm 2 dòng biểu diễn các đa thức A(x) và B(x), mỗi dòng gồm:
 • 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.
Kết quả: Ghi ra 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ụ:
Dữ liệu vào:
3 -3 62 58 -6 4 28 35 31 37 14
Kết quả:
20731
Giải thích: Các hệ số của đa thức kết quả là 7719 10903 17309 19122 19126 12588 5153 735.
Do đó kết quả in ra bằng:
7719 xor 10903 xor 17309 xor 19122 xor 19126 xor 12588 xor 5153 xor 735 = 20731
Lưu ý: Để tính xor hai số nguyên a và b trong C/C++, các bạn có thể dùng câu lệnh a ∧ b.
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.
 10