Câu 80: [1đ] Cho thuật toán được mô tả bởi các bước như sau:
Bước 1: Nhập số nguyên dương N và N số nguyên A1, A2, …, AN;
Bước 2: i ¬1; sum ¬ 0;
Bước 3: Nếu i >N thì đưa ra giá trị sum rồi kết thúc;
Bước 4: Nếu Ai >0 và Ai 2 thì sum ¬ sum +Ai ;
Bước 5: Gán i ¬ i+1, quay lại Bước 3.
Hãy cho biết thuật toán trên dùng để giải bài toán nào dưới đây:
A. Tính tổng các số dương chia hết cho 2 trong dãy số A1, A2, …, AN .
B. Tính tổng các số dương trong dãy số A1, A2, …, AN .
C. Tính tổng N số nguyên cho trước A1, A2, …, AN .
D. Tính tổng các số chia hết cho 2 trong dãy số A1, A2, …, AN .
Việc giải bài toán trên máy tính thường được tiến hành qua các bước sau:
• Giải bài toán trên máy tính thường được tiến hành qua 5 bước
- B1: xác định bài toán;
- B2: lựa chọn hoặc thiết kế thuật toán;
- B3: viết chương trình;
- B4: hiệu chỉnh;
- B5: viết tài liệu;
1. Xác định bài toán
- Là quá trình xác định 2 thành phần: Input và Output và mối quan hệ giữa chúng.
- Ví dụ: Tìm bội chung lớn nhất [BCNN] của hai số nguyên dương A và B
+ Input: A, B
+ Output: BCNN[A,B]
2. Lựa chọn hoặc thiết kế thuật toán
a] Lựa chọn thuật toán
- Một bài toán có nhiều cách giải, do đó người ta lựa chọn thuật toán phù hợp nhất dựa trên các tiêu chí:
+ Thời gian thực hiện ngắn;
+ Sử dụng ít ô nhớ;
+ Thuật toán dễ hiểu, ít phức tạp;
+ Tốn ít tài nguyên nhất có thể.
b] Diễn tả thuật toán
Ví dụ: Tìm ước chung lớn nhất [ƯCLN] của hai số nguyên dương M và N.
• Xác định bài toán:
- Input: Nhập M, N;
- Output: ƯCLN[M, N].
• Ý tưởng: Sử dụng những điều đã biết sau:
- Nếu M = N thì giá trị chung đó là ƯCLN của M và N;
- Nếu M > N thì ƯCLN[M, N] = ƯCLN[M – N,N];
- Nếu M < N thì ƯCLN[M, N] = ƯCLN[M,N- M].
• Thuật toán
- Thuật toán diễn tả bằng cách liệt kê
+ Bước 1: Nhập M, N;
+ Bước 2: Nếu M = N đưa ra ƯCLN[M,N]=M; Kết thúc;
+ Bước 3: Nếu M > N thì M ←M - N rồi quay lại bước 2;
+ Bước 4: N ←N - M rồi quay lại bước 2.
- Thuật toán diễn tả bằng sơ đồ khối
Sau đây là hai ví dụ mô phỏng các bước thực hiện thuật toán trên:
3. Viết chương trình
- Viết chương trình là việc tổng hợp giữa việc lựa chọn cách tổ chức dữ liệu và sử dụng ngôn ngữ lập trình để diễn đạt đúng thuật toán.
Ngôn ngữ lập trình + Thuật toán = Chương trình
- Khi viết chương trình ta nên chọn một ngôn ngữ lập trình hoặc một phần mềm chuyên dụng thích hợp với thuật toán.
- Viết chương trình trong ngôn ngữ nào thì phải tuân theo ngôn ngữ đó.
- Chương trình dịch chỉ có thể phát hiện và thông báo về mặt ngữ pháp.
4. Hiệu chỉnh
- Khái niệm: là việc thử chương trình với 1 số bộ Input tương ứng với Output đã biết trước, từ đó ta xác định được các lỗi của chương trình.
- Mỗi bộ Input – Output được gọi là các Test.
5. Viết tài liệu
- Tài liệu dùng để:
+ mô tả bài toán, thuật toán;
+ thiết kế chương trình;
+ kết quả thử nghiệm;
+ hướng dẫn sử dụng.
- Tài liệu này rất có ích cho người sử dụng chương trình và cho việc đề xuất những khả năng hoàn thiện thêm.
- Các bước có thể lặp đi lặp lại nhiều lần cho đến khi ta cho rằng chương trình đã làm việc đúng đắn và hiệu quả.
Loigiaihay.com
Cho N và dãy số a1... aN, hãy sắp xếp dãy số đó thành dãy số không tăng [số hạng trước lớn hơn hay bằng số hạng sau].
Đề bài
Cho N và dãy số a1... aN, hãy sắp xếp dãy số đó thành dãy số không tăng [số hạng trước lớn hơn hay bằng số hạng sau].
Lời giải chi tiết
• Xác định bài toán
- Input: Dãy A gồm N số nguyên a1, a2..., aN.
- Output: Dãy A được sắp xếp lại thành dãy không tăng:
• Ý tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước nhỏ hơn số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.
• Thuật toán theo cách liệt kê:
Bước 1. Nhập N, các số hạng a, a2, .., aN;
Bước 2: M
Bước 3: Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
Bước 4: M
Bước 5: i
Bước 6: Nếu i > M thì quay lại bước 3
Bước 7: Nếu ai < ai+1 thì tráo đổi ai và ai+1 cho nhau
Bước 8: Quay lại bước 5
• Sơ đồ khối:
Loigiaihay.com
TRƯỜNG THPT IASAO ĐỀ KIỂM TRA 1 TIẾT LẦN 1 – MÔN TIN HỌC KHỐI 10TỔ TOÁN – TIN NĂM HỌC 2007 - 2008Họ và tên:…………….................... Lớp:10A... Mã đề: 354 Điểm:………..PHẦN A: TRẮC NGHIỆM ĐƠN TUYỂN [3,0 ĐIỂM]Hãy khoanh tròn đáp án đúng nhất trong mỗi câu sau:Câu 1: Khi biểu diễn thuật toán bằng sơ đồ khối, hình thoi có ý nghĩa gì?A. thể hiện các phép tính toán; B. thể hiện các thao tác nhập, xuất dữ liệu;C. quy định trình tự thực hiện các thao tác; D. thể hiện thao tác so sánh;Câu 2: Thuật toán có những tính chất nào?A. tính xác định, tính liệt kê, tính đúng đắn; B. tính dừng, tính liệt kê, tính đúng đắn;C. tính xác định, tính liệt kê, tính dừng; D. tính dừng, tính xác định, tính đúng đắn;Câu 3: Tính xác định của thuật toán có nghĩa là:A. Sau khi thực hiện một thao tác thì có đúng một thao tác xác định để được thực hiện tiếp theo;B. Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác;C. Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc, hoặc là có đúng một thao tác xác định đểđược thực hiện tiếp theo;D. Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm;Câu 4: Input của bài toán giải hệ phương trình bậc nhất tổng quát =+=+pnymxcbyax là:A. a, b, c, m, n, p; B. a, b, c, m, n, p, x, y;C. m, n, p, x, y; D. a, b, c, x, y;Câu 5: Khi dùng máy tính để giải bài toán, ta cần quan tâm đến hai yếu tố nào?A. đưa vào máy thông tin gì [Output] và cần lấy ra thông tin gì [Input];B. đưa vào máy thông tin gì [Inbut] và cần lấy ra thông tin gì [Outbut];C. đưa vào máy thông tin gì [Input] và cần lấy ra thông tin gì [Output];D. đưa vào máy thông tin gì [Outbut] và cần lấy ra thông tin gì [Inbut];Câu 6: Khi phát biểu nội dung của một bài toán, ta cần trình bày rõ:A. Mối quan hệ giữa Input và Output của bài toán đó;B. Thuật toán để giải bài toán đó;C. Input, Output và thuật toán để giải bài toán đó;D. Input, Output và mối quan hệ giữa Input và Output của bài toán đó;PHẦN B: TRẮC NGHIỆM ĐÚNG SAI [2,0 ĐIỂM]Những phát biểu sau đúng hay sai? Cho biết ý kiến của em bằng cách khoanh tròn vào lựa chọn Đúng hay Sai tương ứng.Câu 7: Mọi bài toán đều có thuật toán để giảiA. Sai B. ĐúngCâu 8: Có thể có nhiều thuật toán để giải một bài toánA. Sai B. ĐúngCâu 9: Có thuật toán giải được mọi bài toánA. Đúng B. SaiCâu 10: Ta có thể dùng ngôn ngữ tự nhiên để mô tả thuật toánA. Đúng B. SaiCâu 11: Thiết kế thuật toán là một hoạt động trí óc khó khăn và không có thuật toán cho công việc thiết kết thuật toán.A. Sai B. ĐúngCâu 12: Thông tin ban đầu đưa vào máy tính để giải một bài toán gọi là InputA. Đúng B. SaiCâu 13: Ta chỉ có thể dùng sơ đồ khối để mô tả thuật toánA. Sai B. ĐúngCâu 14: Khi biết thuật toán nào đó, ta chỉ có thể giả được bài toán tương ứng với một bộ dữ liệu InputA. Đúng B. SaiĐĐSSPHẦN C: TỰ LUẬN [5,0 ĐIỂM]Câu 15: Cho thuật toán mô tả bằng sơ đồ khối như sau:a. Với A = 14, B = 23, C = 7, sau khi thực hiện xong thuật toán trên thì giá trị của K là bao nhiêu? [1,0 điểm]b. Với A = 9, B = 7, C = 10, sau khi thực hiện xong thuật toán trên thì có bao nhiêu phép so sánh được thựchiện? [0,5 điểm]Câu 16: Cho thuật toán được mô tả bằng cách liệt kê như sau:Bước 1: Nhập hai số M và N;Bước 2: M ← M + N;Bước 3: N ← M - N;Bước 4: M ← M - N;Bước 5: Đưa ra giá trị của M và N rồi kết thúc.a. Hãy mô tả lại thuật toán trên bằng sơ đồ khối. [1,0 điểm]b. Giả sử ở bước 1, ta nhập M = 27 và N = 10, thì giá trị của M và N sau khi thực hiện xong thuật toán trên làbao nhiêu? [1,0 điểm].c. Giả sử ở bước 1, ta nhập M = 30 và N = 4, sau khi thực hiện xong thuật toán trên thì có bao nhiêu phép sosánh được thực hiện? [0,5 điểm].Câu 17: Hãy phát biểu một bài toán và chỉ rõ Input và Output của bài toán đó [1,0 điểm].Nhập ba số A, B, CK > B?K ← AK ← BK > C?K ← CĐưa ra giá trị K, rồi kết thúcTRƯỜNG THPT IASAO ĐỀ KIỂM TRA 1 TIẾT LẦN 1 – MÔN TIN HỌC KHỐI 10TỔ TOÁN – TIN NĂM HỌC 2007 - 2008Họ và tên:…………….................... Lớp:10A... Mã đề: 368 Điểm:………..PHẦN A: TRẮC NGHIỆM ĐƠN TUYỂN [3,0 ĐIỂM]Hãy khoanh tròn đáp án đúng nhất trong mỗi câu sau:Câu 1: Input của bài toán giải hệ phương trình bậc nhất tổng quát =+=+pnymxcbyax là:A. m, n, p, x, y; B. a, b, c, m, n, p;C. a, b, c, x, y; D. a, b, c, m, n, p, x, y;Câu 2: Khi biểu diễn thuật toán bằng sơ đồ khối, hình thoi có ý nghĩa gì?A. thể hiện thao tác so sánh; B. quy định trình tự thực hiện các thao tác;C. thể hiện các phép tính toán; D. thể hiện các thao tác nhập, xuất dữ liệu;Câu 3: Thuật toán có những tính chất nào?A. tính xác định, tính liệt kê, tính dừng; B. tính dừng, tính xác định, tính đúng đắn;C. tính xác định, tính liệt kê, tính đúng đắn; D. tính dừng, tính liệt kê, tính đúng đắn;Câu 4: Khi phát biểu nội dung của một bài toán, ta cần trình bày rõ:A. Input, Output và mối quan hệ giữa Input và Output của bài toán đó;B. Thuật toán để giải bài toán đó;C. Mối quan hệ giữa Input và Output của bài toán đó;D. Input, Output và thuật toán để giải bài toán đó;Câu 5: Tính xác định của thuật toán có nghĩa là:A. Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác;B. Sau khi thực hiện một thao tác thì có đúng một thao tác xác định để được thực hiện tiếp theo;C. Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc, hoặc là có đúng một thao tác xác định đểđược thực hiện tiếp theo;D. Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm;Câu 6: Khi dùng máy tính để giải bài toán, ta cần quan tâm đến hai yếu tố nào?A. đưa vào máy thông tin gì [Input] và cần lấy ra thông tin gì [Output];B. đưa vào máy thông tin gì [Inbut] và cần lấy ra thông tin gì [Outbut];C. đưa vào máy thông tin gì [Outbut] và cần lấy ra thông tin gì [Inbut];D. đưa vào máy thông tin gì [Output] và cần lấy ra thông tin gì [Input];PHẦN B: TRẮC NGHIỆM ĐÚNG SAI [2,0 ĐIỂM]Những phát biểu sau đúng hay sai? Cho biết ý kiến của em bằng cách khoanh tròn vào lựa chọn Đúng hay Sai tương ứng.Câu 7: Có thuật toán giải được mọi bài toánA. Đúng B. SaiCâu 8: Có thể có nhiều thuật toán để giải một bài toánA. Sai B. ĐúngCâu 9: Mọi bài toán đều có thuật toán để giảiA. Sai B. ĐúngCâu 10: Khi biết thuật toán nào đó, ta chỉ có thể giả được bài toán tương ứng với một bộ dữ liệu InputA. Sai B. ĐúngCâu 11: Ta có thể dùng ngôn ngữ tự nhiên để mô tả thuật toánA. Đúng B. SaiCâu 12: Ta chỉ có thể dùng sơ đồ khối để mô tả thuật toánA. Sai B. ĐúngCâu 13: Thiết kế thuật toán là một hoạt động trí óc khó khăn và không có thuật toán cho công việc thiết kết thuật toán.A. Sai B. ĐúngCâu 14: Thông tin ban đầu đưa vào máy tính để giải một bài toán gọi là InputA. Sai B. ĐúngĐĐSSPHẦN C: TỰ LUẬN [5,0 ĐIỂM]Câu 15: Cho thuật toán mô tả bằng sơ đồ khối như sau:a. Với A = 14, B = 20, C = 65, sau khi thực hiện xong thuật toán trên thì giá trị của K là bao nhiêu? [1,0 điểm]b. Với A = 5, B = 7, C = 3, sau khi thực hiện xong thuật toán trên thì có bao nhiêu phép so sánh được thựchiện? [0,5 điểm]Câu 16: Cho thuật toán được mô tả bằng cách liệt kê như sau:Bước 1: Nhập hai số X và Y;Bước 2: X ← X + Y;Bước 3: Y ← X - Y;Bước 4: X ← X - Y;Bước 5: Đưa ra giá trị của X và Y rồi kết thúc.a. Hãy mô tả lại thuật toán trên bằng sơ đồ khối. [1,0 điểm]b. Giả sử ở bước 1, ta nhập X = 98 và Y = 65, thì giá trị của X và Y sau khi thực hiện xong thuật toán trên làbao nhiêu? [1,0 điểm].c. Giả sử ở bước 1, ta nhập X = 45 và Y = 23, sau khi thực hiện xong thuật toán trên thì có bao nhiêu phép sosánh được thực hiện? [0,5 điểm].Câu 17: Hãy phát biểu một bài toán và chỉ rõ Input và Output của bài toán đó. [1,0 điểm]Nhập ba số A, B, CK < B?K ← AK ← BK < C?K ← CĐưa ra giá trị K, rồi kết thúcTRƯỜNG THPT IASAO ĐỀ KIỂM TRA 1 TIẾT LẦN 1 – MÔN TIN HỌC KHỐI 10TỔ TOÁN – TIN NĂM HỌC 2007 - 2008Họ và tên:…………….................... Lớp:10A... Mã đề: 376 Điểm:………..PHẦN A: TRẮC NGHIỆM ĐƠN TUYỂN [3,0 ĐIỂM]Hãy khoanh tròn đáp án đúng nhất trong mỗi câu sau:Câu 1: Input của bài toán giải hệ phương trình bậc nhất tổng quát =+=+pnymxcbyax là:A. a, b, c, x, y; B. a, b, c, m, n, p;C. a, b, c, m, n, p, x, y; D. m, n, p, x, y;Câu 2: Thuật toán có những tính chất nào?A. tính xác định, tính liệt kê, tính dừng; B. tính dừng, tính liệt kê, tính đúng đắn;C. tính dừng, tính xác định, tính đúng đắn; D. tính xác định, tính liệt kê, tính đúng đắn;Câu 3: Tính xác định của thuật toán có nghĩa là:A. Sau khi thực hiện một thao tác thì có đúng một thao tác xác định để được thực hiện tiếp theo;B. Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc, hoặc là có đúng một thao tác xác định đểđược thực hiện tiếp theo;C. Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác;D. Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm;Câu 4: Khi dùng máy tính để giải bài toán, ta cần quan tâm đến hai yếu tố nào?A. đưa vào máy thông tin gì [Output] và cần lấy ra thông tin gì [Input];B. đưa vào máy thông tin gì [Outbut] và cần lấy ra thông tin gì [Inbut];C. đưa vào máy thông tin gì [Inbut] và cần lấy ra thông tin gì [Outbut];D. đưa vào máy thông tin gì [Input] và cần lấy ra thông tin gì [Output];Câu 5: Khi biểu diễn thuật toán bằng sơ đồ khối, hình thoi có ý nghĩa gì?A. thể hiện các thao tác nhập, xuất dữ liệu; B. quy định trình tự thực hiện các thao tác;C. thể hiện thao tác so sánh; D. thể hiện các phép tính toán;Câu 6: Khi phát biểu nội dung của một bài toán, ta cần trình bày rõ:A. Input, Output và mối quan hệ giữa Input và Output của bài toán đó;B. Mối quan hệ giữa Input và Output của bài toán đó;C. Thuật toán để giải bài toán đó;D. Input, Output và thuật toán để giải bài toán đó;PHẦN B: TRẮC NGHIỆM ĐÚNG SAI [2,0 ĐIỂM]Những phát biểu sau đúng hay sai? Cho biết ý kiến của em bằng cách khoanh tròn vào lựa chọn Đúng hay Sai tương ứng.Câu 7: Thông tin ban đầu đưa vào máy tính để giải một bài toán gọi là InputA. Sai B. ĐúngCâu 8: Có thuật toán giải được mọi bài toánA. Sai B. ĐúngCâu 9: Khi biết thuật toán nào đó, ta chỉ có thể giả được bài toán tương ứng với một bộ dữ liệu InputA. Sai B. ĐúngCâu 10: Có thể có nhiều thuật toán để giải một bài toánA. Sai B. ĐúngCâu 11: Ta có thể dùng ngôn ngữ tự nhiên để mô tả thuật toánA. Đúng B. SaiCâu 12: Mọi bài toán đều có thuật toán để giảiA. Sai B. ĐúngCâu 13: Ta chỉ có thể dùng sơ đồ khối để mô tả thuật toánA. Đúng B. SaiCâu 14: Thiết kế thuật toán là một hoạt động trí óc khó khăn và không có thuật toán cho công việc thiết kết thuật toán.A. Đúng B. Sai