Trắc nghiệm: Input của bài toán: “Hoán đổi giá trị của hai biến số thực A và C dùng biến trung gian B” là: A. Hai số thực A, C B. Hai số thực A, B C. Hai số thực B, C D. Ba số thực A, B, C Lời giải: Đáp án đúng: A. Hai số thực A,C Input của bài toán là các thông tin đã cho vì vậy Input của bài toán: “Hoán đổi giá trị của hai biến số thực A và C dùng biến trung gian B” là hai số thực A, C. Cùng Top tài liệu tìm hiểu thêm về vấn đề này nhé! – Bài toán là một việc nào đó mà con người muốn máy tính thực hiện – Các yếu tố của một bài toán: + Input: Thông tin đã biết, thông tin đưa vào máy tính + Output: Thông tin cần tìm, thông tin lấy ra từ máy tính – ví dụ: Bài toán tìm ước chung lớn nhất của 2 số nguyên dương, khi đó: + Input: hai số nguyên dương A, B. + Output: ước chung lớn nhất của A và B a. Khái niệm Thuật toán để giải một bài toán là: + Một dãy hữu hạn các thao tác (tính dừng) + Các thao tác được tiến hành theo một trình tự xác định (tính xác định) + Sau khi thực hiện xong dãy các thao tác đó ta nhận được Output của bài toán (tính đúng đắn) b. Cách biểu diễn thuật toán Có 2 cách để biểu diễn thuật toán: – Cách dùng phương pháp liệt kê: Nêu ra tuần tự các thao tác cần tiến hành + Ví dụ: Cho bài toán Tìm nghiệm của phương trình bậc 2: ax2 + bx + c = 0 (a≠0)? + Xác định bài toán Input: Các số thực a, b, c Output: Các số thực x thỏa mãn ax2 + bx + c = 0 (a≠0) + Thuật toán: Bước 1: Nhập a, b, c (a≠0) Bước 2: Tính Δ = b2 – 4ac Bước 3: Nếu Δ>0 thì phương trình có 2 nghiệm là  Bước 4: Nếu Δ = 0 thì phương trình có nghiệm kép rồi kết thúc thuật toán. Nếu không chuyển sang bước tiếp theo Bước 5: Kết luận phương trình vô nghiệm rồi kết thúc c) Các tính chất của thuật toán – Tính dừng: thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện các thao tác. – Tính xác định: sau khi thực hiện 1 thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng 1 thao tác xác định để được thực hiện tiếp theo. – Tính đúng đắn: sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm. 3. Một số ví dụ về thuật toán Kiểm tra tính nguyên tố của 1 số nguyên dương Xác định bài toán – Input: N là một số nguyên dương; – Output: ″N là số nguyên tố″ hoặc ″N không là số nguyên tố″. Ý tưởng: – Định nghĩa: ″Một số nguyên dương N là số nguyên tố nếu nó chỉ có đúng hai ước là 1 và N″ – Nếu N = 1 thì N không là số nguyên tố. – Nếu 1 < N < 4 thì N là số nguyên tố. – N ≥ 4: Tìm ước i đầu tiên > 1 của N. + Nếu i < N thì N không là số nguyên tố (vì N có ít nhất 3 ước 1, i, N). + Nếu i = N thì N là số nguyên tố. Xây dựng thuật toán a) Cách liệt kê – Bước 1: Nhập số nguyên dương N; – Bước 2: Nếu N=1 thì thông báo ″N không là số nguyên tố″, kết thúc; – Bước 3: Nếu N<4 thì thông báo ″N là số nguyên tố″, kết thúc; – Bước 4: i ← 2; – Bước 5: Nếu i là ước của N thì đến bước 7; – Bước 6: i ← i+1 rồi quay lại bước 5; (Tăng i lên 1 đơn vị) – Bước 7: Nếu i = N thì thông báo ″N là số nguyên tố″, ngược lại thì thông báo ″N không là số nguyên tố″, kết thúc; b) Sơ đồ khối Lưu ý: Nếu N >= 4 và không có ước trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tố.
Giả sử x và y là các biến số. Hãy cho biết kết quả của việc thực hiện thuật toán sau:... Đề bài Giả sử x và y là các biến số. Hãy cho biết kết quả của việc thực hiện thuật toán sau: Bước 1. x ← x + y Bước 2. y ← x – y Bước 3. x ← x – y Lời giải chi tiết - Bước 1: Ở bước này giá trị của x sẽ bằng x cộng với y: x = x + y. - Bước 2: Tiếp đến giá trị của y bằng giá trị của x – y: y = x (bước 1) – y = x + y – y = x. - Bước 3: Cuối cùng giá trị của x bằng x – y: x = x (bước 1) - y (bước 2) = x + y – x = y. Vậy kết quả của thuật toán là x = y và y = x. Loigiaihay.com
Trong thực tế, chúng ta phải xây dựng các chương trình, các hàm hoán vị để hoán đổi giá trị của các phần tử, ví dụ chương trình sắp xếp dãy là một điển hình. Để hoán vị 2 số, ta có thể hình dung giống như chúng ta có 2 cốc. Cốc A đựng nước chanh, cốc B đựng thuốc trừ sâu. Làm sao để chúng ta chuyển nước chanh sang cốc B và chuyển thuốc trừ sâu sang cốc a? Đơn giản là dùng thêm 1 cốc phụ là cốc c và bắt đầu chuyển:
2. Code hoán vịLàm tương tự trong lập trình ta sẽ hoán đổi được giá trị của 2 biến. // e.g about swap in C - code by nguyenvanquan7826 #include <stdio.h> int main() { int a, b; printf("Nhap 2 so a, b:\n"); scanf("%d%d", &a, &b); printf("Ban da nhap:\na = %d \nb = %d\n", a, b); int temp = a; a = b; b = temp; printf("Sau khi hoan vi:\na = %d\nb = %d\n", a, b); return 0; }Kết quả:
Ok. Bây giờ thử tách ra thành hàm hoán vị xem sao: 3. Hàm hoán vị trong C// e.g about swap in C - code by nguyenvanquan7826 #include <stdio.h> void hoanvi(int a, int b) { int temp = a; a = b; b = temp; } int main() { int a, b; printf("Nhap 2 so a, b:\n"); scanf("%d%d", &a, &b); printf("Ban da nhap:\na = %d \nb = %d\n", a, b); hoanvi(a, b); printf("Sau khi goi ham hoanvi:\na = %d\nb = %d \n", a, b); return 0; }Kết quả:
Oh, Sao kết quả chúng ta không có sự hoán vị? Với chương trình này chúng ta xây dựng 1 hàm hoán vị để đổi vị trí giữa 2 bến a và b, tuy nhiên chúng ta đã sử dụng tham trị nên các giá trị của a và b không thay đổi hay nói cách khác là chúng không được hoán vị cho nhau. Các bạn hiểu truyền tham trị tức là khi gọi hàm hoanvi(a, b) thì ngay lập tức giá trị của a và b (3 và 6) được đưa vào hàm chứ không phải là các biến a, b nên biến a, b của chúng ta không hề thay đổi khi hàm kết thúc. Code đúng như sau: // e.g about swap in C - code by nguyenvanquan7826 #include <stdio.h> void hoanvi(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } int main() { int a, b; printf("Nhap 2 so a, b:\n"); scanf("%d%d", &a, &b); printf("Ban da nhap:\na = %d \nb = %d\n", a, b); hoanvi(&a, &b); printf("Sau khi goi ham hoanvi:\na = %d\nb = %d \n", a, b); return 0; }Kết quả:
Ở trên chúng ta xây dựng hàm hoanvi với 2 đối số là *a và *b kiểu int. *a và *b nghĩa là con trỏ a và con trỏ b. Trong thân hàm chúng ta có viết *a, *b (VD: int temp = *a) thì dấu * thể hiện là giá trị của con trỏ a. Do hàm dùng con trỏ nên khi gọi hàm chúng ta phải truyền vào địa chỉ của các biến tức là hoanvi(&a, &b) , ở đây dấu & để lấy địa chỉ của biến a và biến b. 4. Hàm hoán vị trong C++Nếu các bạn viết trong C++ (file có đuôi là .cpp) thì có thể viết hàm hoán vị dễ hơn một chút như sau. // e.g about swap in C - code by nguyenvanquan7826 #include <stdio.h> void hoanvi(int &a, int &b) // only in C++, file .cpp { int temp = a; a = b; b = temp; } int main() { int a, b; printf("Nhap 2 so a, b:\n"); scanf("%d%d", &a, &b); printf("Ban da nhap:\na = %d \nb = %d\n", a, b); hoanvi(a, b); printf("Sau khi goi ham hoanvi:\na = %d\nb = %d \n", a, b); return 0; }Hoặc có thể dùng hàm swap có sẵn trong thư viện algorithm #include <stdio.h> #include <algorithm> // swap int main() { int a, b; printf("Nhap 2 so a, b:\n"); scanf("%d%d", &a, &b); printf("Ban da nhap:\na = %d \nb = %d\n", a, b); std::swap(a, b); printf("Sau khi goi ham hoanvi:\na = %d\nb = %d \n", a, b); return 0; } |
