<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

Đại học Bách Khoa Hà Nội

Trường Công Nghệ Thông Tin và Truyền Thông

Báo cáo Bài thực hành số 2

Giảng viên hướng dẫn: Lê Thị HoaSinh viên thực hiện: Lương Hoài Nam

MSSV: 20210623

Hà Nội, ngày 6 tháng 11 năm 2023

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

Mục lục

Bài thực hành số 2...5Bài tập 2.1. Viết hàm tính độ dài cạnh huyền của tam giác theo độ hai cạnh góc vng.... 5Bài tập 2.2. Viết hàm hố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.iết hàm tính độ dài cạnh huyền của tam giác theo độ hai cạnh góc vng...7Bài tập 2.3. 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...9Bài tập 2.4. Viết các hàm tính lập phương của số nguyên và số thực...12Bài tập 2.5. Viết các tốn tử tính tổng, hiệu, tích và thương của hai số phức...14Bài tập 2.6. Giả thuyết Collatz: bắt đầu từ số dương n bất kỳ, nếu n chẵn thì chia 2, nếulẻ 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 q 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...18Bài tập 2.7. 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...18Bài tập 2.8. Viết hàm so sánh cho thuật toán sắp xếp...19Bài tập 2.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...22Bài tập 2.10. Tính tích hai ma trận vng...28Bài tập 2.11. 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...34Bài tập 2.12. 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 <key, value> 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...39Bài 2.13. 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ằngcá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:... 42

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

Bài thực hành số 2

Bài tập 2.1. Viết hàm tính độ dài cạnh huyền của tam giác theo độ hai cạnh góc vng.

<small>Hình 1 Code bài 2.1</small>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

<small>Hình 2 Minh chứng đã pass bài 2.1</small>

#include <stdio.h>#include <math.h>

float get_hypotenuse(float x, float y) { /*****************

# YOUR CODE HERE # *****************/

return sqrt(x*x+y*y);// Trả về căn bậc 2 của x^2 + y^2}

int main(){ float x, y;

scanf("%f%f", &x, &y);

float z = get_hypotenuse(x, y); // Tính tốn z printf("z = %.2f\n", z);

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

return 0;}

// Lương Hoài Nam - 20210623

Bài tập 2.2. 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.iết hàm tính độ dài cạnh huyền của tam giác theo độ hai cạnh góc vng

<small>Hình 3 Code bài 2.2</small>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

<small>Hình 4 Minh chứng đã pass bài 2.2</small>

int main() { int x, y, z;

scanf("%d",&x);scanf("%d",&y);scanf("%d",&z);IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

//# Nhập 3 số nguyên /***************** # YOUR CODE HERE # *****************/

printf("Before: %d, %d, %d\n", x, y, z); rotate(x, y, z); // Hoán đổi giá trị của x,y,z printf("After: %d, %d, %d\n", x, y, z);

return 0;}

// Lương Hoài Nam – 20210623

Bài tập 2.3. 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.

<small>Hình 5 Code bài 2.3</small>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

<small>Hình 6 Minh chứng đã pass bài 2.3</small>

#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; // Trả về giá trị ax^2 + bx + c}

int main(){ int x;

scanf("%d", &x);

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

int a = 2; //# giá trị mặc định của a int b = 1; //# giá trị mặc định của b int c = 0; //# giá trị mặc định của c scanf("%d",&a);

scanf("%d",&b); scanf("%d",&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;}

// Lương Hoài Nam - 20210623

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

Bài tập 2.4. Viết các hàm tính lập phương của số nguyên và số thực.

<small>Hình 7 Code bài 2.4</small>

<small>Hình 8 Minh chứng đã pass bài 2.4</small>

#include <stdio.h>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

int cube(int x) {

//# trả về lập phương của x /***************** # YOUR CODE HERE # *****************/

return x*x*x; // Trả về lập phương của số nguyên x}

//# viết hàm tính lập phương của một số kiểu double/*****************

# YOUR CODE HERE #*****************/double cube(double x){

return x*x*x; // Trả về lập phương của số thực x}

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;}

// Lương Hoài Nam - 20210623

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

Bài tập 2.5. Viết các toán tử tính tổng, hiệu, tích và thương của hai số phức

<small>Hình 9 Code bài 2.5</small>

<small>Hình 10 Code bài 2.5</small>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 15</span><div class="page_container" data-page="15">

<small>Hình 11 Code bài 2.5</small>

<small>Hình 12 Minh chứng đã pass bài 2.5</small>

#include <iostream>#include <ostream>#include <math.h>#include <iomanip>

using namespace std;

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

struct Complex { double real; double imag;};

Complex operator + (Complex a, Complex b) { /*****************

# YOUR CODE HERE # *****************/ Complex tmp;

tmp.real = a.real + b.real; // Tính phần thực của tổng 2 số phức tmp.imag = a.imag + b.imag; // Tính phần ảo của tổng 2 số phức return tmp;

tmp.real = a.real - b.real; // Tính phần thực của hiệu 2 số phức tmp.imag = a.imag - b.imag; // Tính phần ảo của hiệu 2 số phức return tmp;

Complex operator * (Complex a, Complex b) { /*****************

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 17</span><div class="page_container" data-page="17">

# YOUR CODE HERE # *****************/ Complex tmp;

tmp.real = a.real * b.real - a.imag * b.imag; // Tính phần thực của tích 2 số phức tmp.imag = a.imag * b.real + a.real * b.imag; // Tính phần ảo của tích 2 số phức return tmp;

tmp.real = (a.real * b.real + a.imag * b.imag) / (b.real * b.real + b.imag * b.imag); // Tính phần thực của thương 2 số phức

tmp.imag = (a.imag * b.real - a.real * b.imag) / (b.real * b.real + b.imag * b.imag); // Tính phần ảo của thương 2 số phức

return tmp;}

// Hàm đa năng hóa tốn tử << cho việc in ra số phứcostream& 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;

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 18</span><div class="page_container" data-page="18">

cin >> real_a >> img_a; cin >> real_b >> img_b;

Complex a{real_a, img_a}; // Khởi tạo số phức a Complex b{real_b, img_b}; // Khởi tạo số phức 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;}

// Lương Hoài Nam - 20210623

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 19</span><div class="page_container" data-page="19">

Bài tập 2.6. 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 q 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.

<small>Hình 13 Code bài 2.6</small>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 20</span><div class="page_container" data-page="20">

<small>Hình 14 Code bài 2.6</small>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 21</span><div class="page_container" data-page="21">

<small>Hình 15 Minh chứng pass bài 2.6</small>

#include <stdio.h>void print(int n) {

printf("n=%d\n", n); // Định nghĩa hàm print}

</div><span class="text_page_counter">Trang 22</span><div class="page_container" data-page="22">

void simulate(int n, int (*odd)(int), int (*even)(int), void (*output)(int)) { (*output)(n); // Gọi hàm truyền vào con trỏ hàm output

if (n == 1) return; // Nếu n = 1 thì dừng chương trình if (n % 2 == 0) {

n = (*even)(n); // Nếu n chẵn thì gọi hàm truyền vào con trỏ hàm even } else {

n = (*odd)(n); // Nếu n lẻ thì gọi hàm truyền vào con trỏ hàm odd }

simulate(n, odd, even, output); // Tiếp tục gọi hàm simulate với giá trị n hiện tại}

int main() {

int (*odd)(int) = mul3plus1;// Đưa hàm mul3plus1 vào con trỏ hàm odd int (*even)(int) = div2; // Đưa hàm div2 vào con trỏ hàm even int n;

</div><span class="text_page_counter">Trang 23</span><div class="page_container" data-page="23">

Bài tập 2.7. 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.

<small>Hình 16 Code bài 2.7</small>

<small>Hình 17 Minh chứng pass bài 2.7</small>

#include <iostream>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 24</span><div class="page_container" data-page="24">

using namespace std;

//# viết hàm arr_sum/*****************# YOUR CODE HERE #*****************/template<typename T>

T arr_sum(T* a, int size_a, T* b, int size_b){

T sum = 0; // Khởi tạo tổng = 0 for (int i = 0; i < size_a; i++) {

sum += *(a + i); // Cộng giá trị a[i] vào tổng }

for (int i = 0; i < size_b; i++) {

sum += *(b + i); // Cộng giá trị b[i] vào tổng }

return sum; // Trả về tổng}

int main() { int val; cin >> val; {

int a[] = {3, 2, 0, val}; // Khởi tạo mảng a int b[] = {5, 6, 1, 2, 7}; // Khởi tạo mảng b

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 25</span><div class="page_container" data-page="25">

cout << arr_sum(a, 4, b, 5) << endl; }

{

double a[] = {3.0, 2, 0, val * 1.0}; // Khởi tạo mảng a double b[] = {5, 6.1, 1, 2.3, 7}; // Khởi tạo mảng b cout << arr_sum(a, 4, b, 5) << endl;

} return 0;}

// Lương Hoài Nam - 20210623

Bài tập 2.8. Viết hàm so sánh cho thuật tốn sắp xếp.

<small>Hình 18 Code bài 2.8</small>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 26</span><div class="page_container" data-page="26">

<small>Hình 19 Minh chứng pass bài 2.8</small>

#include <iostream>#include <vector>#include <algorithm>#include <numeric>using namespace std;

int main() { int val1, val2; cin >> val1 >> val2; vector< vector<int> > a = { {1, 3, 7},

{2, 3, 4, val1}, {9, 8, 15}, {10, val2},

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 27</span><div class="page_container" data-page="27">

sort(a.begin(), a.end(), [] (vector<int> p1, vector<int> p2){ int sum1 = 0;int sum2 = 0; // Khởi tạo tổng 2 mảng for(int i = 0; i < (int)p1.size(); i++)

cout << endl; }

return 0;

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 28</span><div class="page_container" data-page="28">

// Lương Hồi Nam – 20210623

Bài tập 2.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.

<small>Hình 20 Code bài 2.9</small>

<small>Hình 21 Code bài 2.9</small>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 29</span><div class="page_container" data-page="29">

<small>Hình 22 Code bài 2.9</small>

<small>Hình 23 Code bài 2.9</small>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 30</span><div class="page_container" data-page="30">

<small>Hình 24 Minh chứng pass bài 2.9</small>

#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;// Đây là hàm sigmoid_slow

double sigmoid_slow(double x) { return 1.0 / (1.0 + exp(-x));}

double x[NUM_INPUTS];

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 31</span><div class="page_container" data-page="31">

// Hàm sinh ra input ngẫu nhiên để test hàm sigmoidvoid 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ần thiết/*****************

# YOUR CODE HERE #*****************/const int N = 100000;double y[N+1];//# hàm chuẩn bị dữ liệuvoid precalc() {

double delta=(LIMIT*2.0)/N; // Tính tốn tham số delta for(int i=0;i<=N;i++)

{

y[i]=sigmoid_slow(-LIMIT+delta*i); // Chuẩn bị trước mảng y[i] là hàm sigmoid của -LIMIT+delta*i

}}

//# hàm tính sigmoid(x) nhanh sigmoid_fast(x)inline double sigmoid_fast(double x) { /*****************

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 32</span><div class="page_container" data-page="32">

# YOUR CODE HERE # *****************/

if(x<-LIMIT) return 0; // Nếu x quá bé thì trả về 0 if(x>=LIMIT) return 1; // Nếu x quá lớn thì trả về 1 static double delta=(LIMIT*2.0)/N; // Tính tốn tham số delta int i=(x+LIMIT)/delta; // Tính tốn tham số i

return (x-(-LIMIT+(delta*i)))/delta*(y[i+1]-y[i])+y[i]; // Tính tốn xấp xỉ sigmoid(x)}

//# END fast code

// Đây là hàm tính thời gian chạy hàm truyền vào con trỏ hàm calcdouble benchmark(double (*calc)(double), vector<double> &result) { const int NUM_TEST = 20;

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;

</div><span class="text_page_counter">Trang 33</span><div class="page_container" data-page="33">

taken = (double)(finish - start); return taken;

// Đây là hàm check xem liệu hàm sigmoid_fast có đúng khơngbool 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 < (int)a.size(); ++i) { if (fabs(a[i] - b[i]) > EPS) { return false;

} } return true;}

int main() { prepare_input(); precalc();

vector<double> a, b;

double slow = benchmark(sigmoid_slow, a); // thời gian chạy hàm sigmoid_slow double fast = benchmark(sigmoid_fast, b); // thời gian chay hàm sigmoid_fast 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 at least 30%%!\n"); } else {

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 34</span><div class="page_container" data-page="34">

printf("Wrong answer or your code is not fast enough!\n"); }

return 0;}

// Lương Hoài Nam – 20210623

Bài tập 2.10. Tính tích hai ma trận vng

<small>Hình 25 Code bài 2.10</small>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 35</span><div class="page_container" data-page="35">

<small>Hình 26 Code bài 2.10</small>

<small>Hình 27 Code bài 2.10</small>

IT3040 – 2023.1 – Mã lớp: 732827

</div><span class="text_page_counter">Trang 36</span><div class="page_container" data-page="36">

<small>Hình 28 Code bài 2.10</small>

<small>Hình 29 Test bài 2.10</small>

#include <iostream>#include <cstring>

using namespace std;

const int N = 128;

// Định nghĩa cấu trúc ma trậnstruct Matrix {

unsigned int mat[N][N]; Matrix() {

memset(mat, 0, sizeof mat); }

// Đa năng hóa tốn tử == cho 2 ma trận

IT3040 – 2023.1 – Mã lớp: 732827

</div>