Câu hỏi và bài tập

1. Thuật toán là gì? Cho ví dụ.

3. Cho tam giác ABC có góc vuông A và cho biết cạnh a và góc B. Hãy viết thuật toán để tính góc C, cạnh b và cạnh c.

4. Trình bày tính chất xác định của thuật toán và nêu rõ nghĩa của tính chất này.

5*.Hãy phát biểu thuật toán để giải bài toán sau: "Có một số quả táo. Dùng cân hai đĩa (không có quả cân) để xác định quả táo nặng nhất"

6. Xác định input và output cho các thuật toán sau đây:

a) Rút gọn một phân số.

b) Kiểm tra xem ba số cho trước a, b và c có thể là độ dài ba cạnh của một tam giác hay không?

c) Tính trung bình cộng của hai số.

d) Dùng một cốc phụ để tráo nước ở hai cốc cho trước.

e) Tìm chu vi và diện tích của hình tròn có bán kính cho trước.

7. Chỉ dùng phép cộng, viết thuật toán để từ số tự nhiên n, tính số n²

Câu hỏi trắc nghiệm

Thời gian: Không giới hạn

Có người đề xuất cách giải bài toán sau "Vừa gà vừa chó; bó lại cho tròn;  Có N con; M chân. Hỏi có mấy gà mấy chó?" như sau:

Bước 1. Lấy số chó giả định là 1

Bước 2. Nhân số chó với 4 để tìm số chân chó

Bước 3. Lấy M trừ đi chân chó để tìm số chân gà

Bước 4. Chia số chân gà cho 2 để tìm số gà

Bước 5. Kiểm tra tổng số gà + số chó nếu bằng N thì dừng và đó là kết quả. Nếu không thực hiện bước 6

Bước 6. Tăng số chó lên 1 và chuyển tới bước 2

Khẳng định nào đúng

Có người đề xuất cách giải bài toán cổ "Trăm trâu trăm bó cỏ. Trâu đứng ăn 5; trâu nằm ăn 3; trâu gia 3 con ăn 1. Hỏi mỗi loại trâu có bao nhiêu con ?" như sau:

Lần lượt thử số trâu đứng từ 0 đến 20 (vì không thể có quá 20 trâu đứng); với mỗi số đã chọn nhân với 5 tìm số cỏ đã bị ăn.

Với mỗi số trâu đứng đã chọn thử với số trâu nằm từ 0 đến 33 . Với mỗi số trâu nằm tính tổng số cỏ mà cả trâu đứng và trâu nằm đã ăn.

Với mỗi số trâu đứng và trâu nằm đã chọn, lấy 100 trừ đi số trâu đứng và trâu nằm để tìm số trâu già. Lấy 100 trừ đi số cỏ mà trâu đứng và trâu nằm đã ăn để tìm số cỏ còn lại sau đó kiểm tra số trâu già có gấp 3 số cỏ còn lại. Nếu đúng tuyên bố nghiệm

Nếu không tìm được bộ 3 số trâu đứng, trâu nằm, trâu già thoả mãn thì tuyên bố vô nghiệm

Xét các cách tìm USCLN của hai số tự nhiên m và n qua các giải thuật sau đây

Cách 1.

 Chỉ dẫn 1: Phân tích m và n thành các thừa số nguyên tố

 Chỉ dẫn 2: Tính tích của các uớc số chung với số mũ nhỏ nhất

B. Cách 2

 Chỉ dẫn 1: Nếu m = n thì USCLN(m,n) lấy là m. Nếu không thực hiện chỉ dẫn 2

 Chỉ dẫn 2: Nếu m > n thì bớt m một lượng n và quay lại thực hiện chỉ dẫn 1. Nếu không thực hiện chỉ dẫn 3

 Chỉ dẫn 3:  Bớt n một lượng m và quay lại thực hiện chỉ dẫn 1

C. Cách 3

 Chỉ dẫn 1: Nếu m = n thì USCLN(m,n) lấy là m. Nếu không thực hiện chỉ dẫn 2

 Chỉ dẫn 2: Nếu n > m thì tráo đổi giá trị m và n và thực hiện chỉ dẫn 3

 Chỉ dẫn 3:  Thay m bởi số dư của phép chia m cho n sau đó quay lại thực hiện chỉ dẫn 1

Nếu tính độ phức tạp tính toán của giải thuật là số phép tính số học phải thực hiện thì giải thuật nào tốt nhất

Có một giải thuật được mô tả như sau

Cho 2 số tự nhiên m và n, ta tính số x theo quy trình sau

Bước 1. Cho x = 0

Bước 2. Kiểm tra m chẵn hay lẻ, nếu m chẵn thì thực hiện chỉ dẫn 3 nguợc lại thực hiện chỉ dẫn 5

Bước 3. Nếu m > 0 thì thực hiện chỉ dẫn 4 ngược lại dừng quá trình tính toán.

Bước 4. Gấp đôi x và giảm m đi 2 lần  sau đó quay về bước 2

Bước 5. Tăng x lên một lượng là n, giảm m đi 1 và quay lại bước 2

Thực hiện giải thuật sau và cho biết kết quả là gì

Cho số tự nhiên m, tính n theo quá trình sau

Bước 1. Cho n = 1, cho i = 1

Bước 2  Nếu m > 1 thì thực hiện bước 3. Nếu m = 1 thì dừng tính toán

Bước 3 giảm m đi 1 và tăng i thêm 2 đơn vị sau đó tăng n thêm i đơn vị. Quay  trở lại bước 2.

Quá trình này tính:

Có n gói hàng đáng lẽ phải nặng như nhau nhưng có một gói sai quy cách nhẹ hơn các gói khác. Một sinh viên đã viết giải thuật sau để tìm gói hàng này bằng cách dùng cân đĩa theo nguyên lý thăng bằng.

Bước 0. Lấy một cái rổ bỏ tất cả hàng vào

Bước 1. Nếu rổ chỉ có 1 gói thì đó chính là gói hàng khuyết. Dừng quá trình tìm. Nếu  không thực hiện bước 2

Bước 2. Chia số hàng trong rổ thành 3 đống 1,2,3 trong đó đống 1 và đóng 2 có số lượng bằng nhau rồi làm tiếp bước 3.

Bước 3. Đặt lên cân đĩa hai nhóm 1 và 2. Nếu cân thăng bằng thì bỏ nhóm này đi và để vào rổ đống hàng thứ 3. Nếu cân không thăng bằng thì bỏ đống nhẹ hơn vào rổ rồi quay về bước 1.

Tính dừng của thuật toán được hiểu là

Tính phổ dụng của thuật toán là:

Câu 10:   

Xác đinh Input của bài toán tìm tất cả các số nguyên tố nhỏ hơn một số cho trước

Câu 11:  

Trong một trường học đã có cơ sở dữ liệu (hồ sơ trên máy tính) của tất cả học sinh trong trường. Bài toán in ra danh sách học sinh của lớp x nào đó có input là gì

Câu 12:   

 Một người viết chương trình chơi cờ vua. Bài toán chơi cờ có input là

Câu 13:  

 Một người viết chương trình chơi cờ vua. Bài toán chơi cờ có output là

Câu 14:   

Tính khả thi của thuật toán được hiểu là

Câu 15:   

Có một phương pháp tính gọi là Monter-Carlo để tính dựa vào các đặc trưng xác xuất, người ta phải chế ra các số ngẫu nhiên. Mỗi khi yêu cầu, máy tính lại đưa ra một con số không dự đoán được trước. Có thể nói rằng bài toán đưa ra một số ngẫu nhiên có thuật toán vi phạm tính xác định không?

Câu 16:   

Cho một số x và một dãy l các số a₁, a₂…a_i… a_k được xếp theo chiều tăng dần. Ta thi hành thụât toán xác định x có ở trong dãy không và nếu có thì ở vị trí nào

Bước 1: cho  m=1, i= 1 và n=k

Bước 2: Lấy  i =  [(m+n)/2]   (hàm phần nguyên) sau đó kiểm tra x= a_i, nếu đúng chuyển tới bước 5,  nếu sai thực hiện  bước 3

Bước 3: Nếu x < a_i, thay m bằng i và quay lại bước 2, nếu không thực hiện bước 4

Bước 4: Thay n bằng  i và quay lại bước 2

Bước 5: Tuyên bố x là phần tử thứ i

Khẳng định nào sai

Câu 17:   

Cho thuật toán sau

Bước 1. Cho S = 1, i = 1, u = 1, x

Bước 2. Tính  U:= U.x/i;   S := S + U; i:=i+1  (các phép tính thực hiện đúng theo thứ tự)

Bước 3. Nếu i <100 quay lại bước 2, nếu không chuyển xuống bước 4

Bước 4. Lấy output S

Thuật toán này tính gì

Câu 18:   

Cho thuật toán sau

Bước 1. Cho S = 0, i = 1, u = 1, x

Bước 2. Tính   S := S + U; U:= -U.x²/((i+1)(i+2));  i:=i+2

Bước 3. Nếu i <100 quay lại bước 2, nếu không chuyển xuống bước 4

Bước 4. Lấy output S

Thuật toán này tính gì