Font size
Worksheetsđề 1_ bé Tâm Cute
Total questions: 30
Worksheet time: 15mins
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
1. Cách 1.
Chỉ dẫn 1: Phân tích m và n thành các thừa số nguyên tố như sau
Chỉ dẫn 2: Tính tích của các uớc số chung với số mũ nhỏ nhất
2. 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
3. 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ách 3
Cách 1
Cách 2
Không cách nào tốt hơn cách nào vì còn phụ thuộc vào trường hợp cụ thể
Một người viết chương trình chơi cờ vua. Bài toán chơi cờ có output là:
Nước đi của máy
Nước đi của máy và thời gian đi tương ứng với mỗi nước của máy
Nước đi của máy và của người chơi kèm theo thời gian của mỗi nước đi
Nước đi của máy và của người chơi
Độ phức tạp của thuật toán không phụ thuộc vào?
Kích thước của dữ liệu đầu vào.
Tốc độ tính toán của máy tính thực hiện thuật toán.
Bản chất của thuật toán.
Bản chất của bài toán
Giả sử một thuật toán được xác định bằng một số các chỉ dẫn. Tính xác định của thuật toán là
Sau mỗi bước thực hiện một chỉ dẫn, với những input xác định, luôn xác định được duy nhất chỉ dẫn cần thực hiện tiếp theo
Các chỉ dẫn của thuật toán phải hoàn toàn rõ ràng, dễ hiểu
Không có các chỉ dẫn nào không thể thực hiện được
Một thuật toán phải được thể hiện bằng một dãy các chỉ dẫn và quá trình phải kết thúc ở chỉ dẫn cuối cùng
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 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
Quá trình trên đúng là một giải thuật nhưng chưa đầy đủ vì cần thêm các buớc xử lý những trường hợp M, N chưa thích hợp
Quá trình mô tả trên là một giải thuật
Quá trình trên không phải là một giải thuật vì mặc dù xác định và dừng nhưng thử hết mọi khả năng thì không đáng gọi là giải thuật.
Không xác định được tính xác định và tính dừng vì còn phụ thuộc vào M và N mà ta chưa biết.
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
Số cho trước
Điều kiện là Nguyên tố
Không có input
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.x2/((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ì
Tính sin x theo khai triển Taylor đến số hạng thứ 50
Tính sin x theo khai triển Taylor đến số hạng thứ 49
Tính ex theo khai triển Taylor đến số hạng thứ 49
Tính ex theo khai triển Taylor đến số hạng thứ 50
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
Quá trình mô tả trên là một giải thuật
Quá trình trên không phải là một giải thuật vì mặc dù xác định và dừng nhưng thử hết mọi khả năng thì không đáng gọi là giải thuật.
Quá trình trên không phải là một giải thuật vì vi phạm tính dừng
Quá trình trên không phải là một giải thuật vì vi phạm tính xác định và tính dừng
Quá trình trên không phải là một giải thuật vì vi phạm tính xác định
Cho một dãy số tăng dần x1, x2, ... xn và một số a nào đó. Xác định có chỉ
số i nào để a= xi. Sau đây là một số thuật toán tìm kiếm nhị phân với 5
bước từ 1 đến 5. Cho trước 3 bước đầu. Có tới 3 phương án cho bước 4
và 5 như sau:
Bước 1. Cho p=1 q=n
Bước 2 . Cho r = [(p+q)/2] [x] là hàm phần nguyên của x
Bước 3. Kiểm tra nếu a= xr thì thông báo r là chỉ số mà xr bằng a. Sau đó
kết thúc xử lý
PA1. Bước 4. Nếu a<xr thì thay q=r-1 ngược lại thay p=r+1
Bước 5. Nếu p≤ q thì quay về bước 2, nếu không thì dừng và tuyên
bố không có r nào để xr=a
PA2. Bước 4. Nếu a<xr thì thay q=r ngược lại thay p=r
Bước 5. Nếu p<q thì quay về bước 2, nếu không thì dừng và tuyên bố
không có r nào để xr=a
PA3. Bước 4. Nếu a<xr thì thay q=r-1 ngược lại thay p=r+1
Bước 5. Nếu p<q thì quay về bước 2, nếu không thì dừng và tuyên bố
không có r nào để xr=a
Khẳng định nào trong 4 khẳng định sau đây là đúng
Chỉ có phương án 2 đúng
Chỉ có phương án 1 đúng
Chỉ có phương án 3 đúng
Cả 3 phương án trên đều đúng
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ì.
Không có "Danh sách học sinh của cả trường" và "Tên của lớp X"
Tên của lớp X
Danh sách học sinh của cả trường
Có cả "Danh sách học sinh của cả trường" và "Tên của lớp X"
Tính phổ dụng của thuật toán là
Một thuật toán có thể cho nhiều output tương ứng với nhiều input
Một thuật toán có thể thực hiện bởi bất kỳ ai
Một thuật toán có thể ứng dụng cho nhiều input cùng loại
Một thuật toán có thể thực hiện trong bất kỳ điều kiện gì
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ì
Tính ex theo khai triển Taylor đến số hạng thứ 99
Tính sin x theo khai triển Taylor đến số hạng thứ 100
Tính ex theo khai triển Taylor đến số hạng thứ 100
Tính sin x theo khai triển Taylor đến số hạng thứ 99
Tính xác định của thuật toán có nghĩa là:
Không thể thực hiện thuật toán 2 lần mà nhận được hai output khác nhau
Sau khi hoàn thành một bước (một chỉ dẫn), bước thực hiện tiếp theo hoàn toàn xác định
Mục đích của thuật toán được xác định
Cho một dãy số tăng dần x1, x2, ... xn và một số a nào đó. Xác định có chỉ số i nào để a= xi. Sau đây là một số thuật toán tìm kiếm nhị phân à bước 3 và 4 có tới 3 phương án cho bới các nhóm phương án 1, 2,3 Bước 1. Cho p=1 q=n Bước 2 . Cho r = [(p+q)/2] [x] là hàm phần nguyên của x Bước 3. Kiểm tra nếu a= xr thì thông báo r là chỉ số mà xr bằng a. Sau đó kết thúc xử lý
Phương án 1.
- Bước 4. Nếu a<xr thì thay q=r-1 ngược lại thay p=r+1
- Bước 5. Nếu p≤ q thì quay về bước 2, nếu không thì dừng và tuyên bố
không có r nào để xr=a
Phương án 2.
- Bước 4. Nếu a<xr thì thay q=r ngược lại thay p=r
- Bước 5. Nếu p<q thì quay về bước 2, nếu không thì dừng và tuyên bố
không có r nào để xr=a
Phương án 3.
- Bước 4. Nếu a<xr thì thay q=r-1 ngược lại thay p=r+1
- Bước 5. Nếu p<q thì quay về bước 2, nếu không thì dừng và tuyên bố
không có r nào để xr=a
Khẳng định nào trong 4 khẳng định sau đây là đúng
Chỉ có phương án 1 đúng
Cả 3 phương án đều đúng.
Chỉ có phương án 3 đúng
Chỉ có phương án 2 đúng
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.
Giải thuật này sai và cần sửa bước 2 như sau: "Chia số hàng trong rổ thành 3 đống 1,2,3 có số lượng gói là m, m và n sao cho n chỉ hơn kém m tối đa là 1 điều này luôn luôn làm được"
Giải thuật sai, cần sửa như sau: Bỏ bước 1 và thay trong bước 3 câu "quay về bước 1" bằng "quay về bước 2"
Giải thuật này sai và cần sửa bước 3 như sau: Chọn gói nhẹ hơn bỏ vào rổ rối quay lại bước 2
Giải thuật này đúng. Không cần phải sửa
Bỏ đi bước 0 vì không cần thiết
Tính khả thi của thuật toán được hiểu là
Có thể thực hiện được
Có thể thực hiện được trong điều kiện có máy tính rất mạnh
Có thể thực hiện được nếu không khó
Tính dừng của thuật toán được hiểu là
Sau một số hữu hạn bước tính toán thì phải gặp yêu câu dừng đối với mọi dữ liệu nằm trong phạm vi được quy định của thuật toán
Thuật toán phải quy định những điều kiện để đảm bảo tính toán phải dừng sau một số hữu hạn bước
Không thể kéo dài mãi tiến trình tính toán
Đâu không phải là đặc trưng của thuật toán?
Tính dừng: thuật toán phải dừng sau một số bước hữu hạn.
Thông tin vào và ra xác định
Thuật toán phải giải được mọi bài toán
Tính khả thi: Các chỉ dẫn trong thuật toán phải có khả năng thực hiện được trong một thời gian hữu hạn.
Một người mê tín. Trước khi đi chơi bao giờ anh ta cũng lấy quyển Kiều và làm theo các bước như sau
Bước 1. Hãy mở một trang bất kỳ
Bước 2. Xem câu thơ thứ 5
Bước 3. Nếu câu này có chữ a thì đi, nếu không thì ở nhà
Khẳng định nào đúng
Quá trình mô tả trên là một giải thuật
Quá trình trên không phải là một giải thuật vì vi phạm tính xác định và tính dừng
Quá trình trên không phải là một giải thuật vì vi phạm tính xác định
Quá trình trên không phải là một giải thuật vì vi phạm tính dừng
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ó
không
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 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
Quá trình mô tả trên là một giải thuật
Quá trình trên đúng là một giải thuật nhưng chưa đầy đủ vì cần thêm các buớc xử lý những trường hợp M, N chưa thích hợp
Không xác định được tính xác định và tính dừng vì còn phụ thuộc vào M và N mà ta chưa biết.
Quá trình trên không phải là một giải thuật vì mặc dù xác định và dừng nhưng thử hết mọi khả năng thì không đáng gọi là giải thuật.
Độ phức tạp của thuật toán không phụ thuộc vào?
Bản chất của bài toán.
Tốc độ tính toán của máy tính thực hiện thuật toán
Kích thước của dữ liệu đầu vào
Bản chất của thuật toán
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
Quá trình mô tả trên là một giải thuật
Quá trình trên không phải là một giải thuật vì vi phạm tính dừng
Quá trình trên không phải là một giải thuật vì vi phạm tính xác định và tính dừng
Quá trình trên không phải là một giải thuật vì mặc dù xác định và dừng nhưng thử hết mọi khả năng thì không đáng gọi là giải thuật.
Quá trình trên không phải là một giải thuật vì vi phạm tính xác định
Tính khả thi của thuật toán được hiểu là
Có thể thực hiện được
Có thể thực hiện được trong điều kiện có máy tính rất mạnh
Có thể thực hiện được nếu không khó
Một người viết chương trình chơi cờ vua. Bài toán chơi cờ có output là:
Nước đi của máy và của người chơi
Nước đi của máy
Nước đi của máy và của người chơi kèm theo thời gian của mỗi nước đi
Nước đi của máy và thời gian đi tương ứng với mỗi nước của máy
Giả sử một thuật toán được xác định bằng một số các chỉ dẫn. Tính xác định của thuật toán là
Một thuật toán phải được thể hiện bằng một dãy các chỉ dẫn và quá trình phải kết thúc ở chỉ dẫn cuối cùng
Các chỉ dẫn của thuật toán phải hoàn toàn rõ ràng, dễ hiểu
Sau mỗi bước thực hiện một chỉ dẫn, với những input xác định, luôn xác định được duy nhất chỉ dẫn cần thực hiện tiếp theo
Không có các chỉ dẫn nào không thể thực hiện được
Câu nào sau đây mô tả không chính xác về chương trình dịch :
Lỗi cú pháp của chương trình nguồn sẽ được kiểm tra trong quá trình dịch.
Có thể dịch ở chế độ thông dịch hoặc biên dịch.
Trong quá trình dịch sẽ phát hiện lỗi ngữ nghĩa của chương trình nguồn.
Là một phần mềm có chức năng dịch các chương trình khác sang ngôn ngữ máy
Có các khẳng định sau đây về chương trình dịch (comliler), khẳng định nào sai:
Với cùng một ngôn ngữ lập trình, trên mỗi loại máy tính hoặc hệ điều hành khác nhau, cần một chương trình dịch khác nhau
Chương trình dịch giúp có thể lập trình trên một ngôn ngữ tự nhiên hơn, do đó giảm nhẹ được công sức làm phần mềm
Chương trình dịch giúp tìm ra tất cả các lỗi của chương trình
Chương trình dịch cho phép chuyển chương trình về ngôn ngữ máy để máy tính có thể thực hiện được mà vẫn bảo toàn được ngữ nghĩa
Chọn phương án tốt nhất trong định nghĩa về hợp ngữ (assembly). Hợp ngữ là loại ngôn ngữ
Là ngôn ngữ có các lệnh được viết trong mã chữ nhưng về cơ bản mỗi lệnh tương đương với một một lệnh máy. Để chạy được cần dịch ra ngôn ngữ máy
Là ngôn ngữ lập trình mà các lệnh không viết trực tiếp bằng mã nhị phân
Là loại ngôn ngữ không viết bằng mã nhị phân được thiết kế cho một số loại máy có thể chạy trực tiếp dưới dạng chữ
Máy tính có thể thực hiện được trực tiếp không cần dịch
Đánh dấu vào câu sai
Hợp ngữ (assembly) là ngôn ngữ về cơ bản có cấu trúc của ngôn ngữ máy nhưng địa chỉ và toán hạng có thể viết bằng mã chữ.
Để máy tính có thể chạy được các chương trình trên các ngôn ngữ nói trong A, B, C đều phải cần một chương trình dịch dịch ra dưới dạng máy tính có thể thực hiện được
Ngôn ngữ máy là ngôn ngữ mà các chương trình trên đó chính là dãy lệnh máy duới dạng nhị phân.
Ngôn ngữ thuật toán là ngôn ngữ chỉ nhằm vào diễn đạt giải thuật và không phụ thuộc vào các hệ máy tính cụ thể
