›
›

Tài liệu thực hành Kỹ thuật lập trình - Bài thực hành số 2: Hàm và tối ưu mã nguồn

Download
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 <stdio.h>  
#include <math.h>  
float get_hypotenuse(float x, float y) {  
/*****************  
# YOUR CODE HERE #  
*****************/  
}
int main(){  
float x = 3;  
float y = 4;  
// gán x bằng 4 chữ số đầu của mã số sinh viên  
// gán y bằng 4 chứ số cuối của mã số sinh viên  
/*****************  
# YOUR CODE HERE #  
*****************/  
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 <stdio.h>  
void rotate(int &x, int &y, int &z) {  
/*****************  
# YOUR CODE HERE #  
*****************/  
}
int main() {  
1
int x = 3;  
int y = 4;  
int z = 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);  
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 <stdio.h>  
// Viết hàm get_value  
/*****************  
# YOUR CODE HERE #  
*****************/  
int get_value(int x, int a = 2, int b = 1, int c = 0) {  
return a * x * x + b * x + c;  
}
int main()  
{
int x;  
scanf("%d", &x);  
int a = 3;  
int b = 4;  
int c = 5;  
// gán a bằng 4 chữ số đầu của mã số sinh viên  
// gán b bằng 4 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));  
return 0;  
}
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 <iostream>  
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() {  
int n = 17;  
cout << "Int: " << cube(n) << endl;  
cout << "Double: " << cube(17.1) << endl;  
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 <iostream>  
#include <ostream>  
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 << '(' << a.real << (a.imag >= 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;  
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 một vài giá trị của  
n.  
In [ ]: #include <stdio.h>  
void print(int n) {  
printf("n=%d\n", n);  
}
int div2(int n) {  
return n * 3 + 1;  
}
int mul3plus1(int n) {  
return n / 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);  
return 0;  
}
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 <iostream>  
#include <cstring>  
using namespace std;  
// viết hàm multiply, nhận vào 2 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 (int i = 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 (int i = 0; i < 8; ++i) printf("%.2f ", c[i]);  
printf("\n");  
}
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 <iostream>  
#include <vector>  
#include <algorithm>  
#include <numeric>  
5
using namespace std;  
int main() {  
vector< vector<int> > 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;  
}
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 <vector>  
#include <algorithm>  
#include <cmath>  
#include <ctime>  
#include <algorithm>  
#include <cstdio>  
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) {  
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<double> &result) {  
const int NUM_TEST = 1000;  
double taken = 0;  
result = vector<double>();  
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<double> &a, const vector<double> &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;  
}
}
7
return true;  
}
int main() {  
prepare_input();  
precalc();  
vector<double> 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");  
}
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 <iostream>  
#include <cstring>  
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];  
}
8
}
}
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 {  
9
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 đ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  
pdf 10 trang yennguyen 21640 Free
Download
Bạn đang xem tài liệu "Tài liệu thực hành Kỹ thuật lập trình - Bài thực hành số 2: Hàm và tối ưu mã nguồn", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdftai_lieu_thuc_hanh_ky_thuat_lap_trinh_bai_thuc_hanh_so_2_ham.pdf