Tìm số lớn nhất trong danh sách
Mục tiêu: Nhập 6 số vào một danh sách, mèo tìm số lớn nhất và vị trí của nó.
Em sẽ học gì
- Nội dung trong bài: danh sách, một biến chứa được nhiều giá trị.
- Duyệt lần lượt các phần tử của danh sách bằng vòng lặp.
- Và thuật toán tìm số lớn nhất: giữ số lớn nhất đã gặp, gặp số lớn hơn thì thay.
Bài làm như sau. Đặt mèo sang bên phải để chừa chỗ cho danh sách: x bằng 120, y bằng âm 40. Chọn nhóm Biến số, bấm Tạo một Danh sách, đặt tên là ds. Danh sách hiện ngay trên sân khấu, lúc này còn trống. Bấm Tạo một biến, đặt tên là lonnhat: số lớn nhất tìm được. Tạo biến vt: vị trí của số lớn nhất. Và biến i: vị trí đang xét.
Thuật toán. 1. Nhập: xoá danh sách cũ, lặp 6 lần: hỏi một số, thêm vào cuối danh sách. 2. Tìm: lonnhat = phần tử thứ 1, vt = 1; cho i chạy từ 2 đến hết: nếu phần tử thứ i lớn hơn lonnhat thì lonnhat = phần tử đó, vt = i.
Sơ đồ khối ở khung bên phải. Phần một: xoá hết ds, rồi nhập 6 số vào ds. Phần hai: lấy phần tử thứ nhất làm lonnhat, vt bằng 1, i bắt đầu từ 2. Khi i chưa vượt kích thước ds: nếu phần tử thứ i lớn hơn lonnhat thì cập nhật lonnhat và vt. Rồi i tăng 1. Duyệt hết danh sách thì nói kết quả.
Chọn nhóm Sự kiện, kéo khối: Khi bấm vào cờ xanh,
Chọn nhóm Biến số, kéo xuống phần danh sách, gắn khối xoá hết tất cả trong ds: mỗi lần chạy, danh sách bắt đầu trống.
Chọn nhóm Điều khiển, gắn khối lặp lại, đổi thành 6 lần.
Bên trong, khối hỏi và đợi, trong nhóm Cảm biến, gõ: Nhập một số,
rồi khối thêm phần tử vào trong ds, trong nhóm Biến số,
thả khối câu trả lời, trong nhóm Cảm biến, vào ô phần tử. Ta vừa làm phần nhập: lặp 6 lần, mỗi lần hỏi một số rồi thêm vào danh sách.
Giải thích: Mỗi lần thêm, phần tử mới nằm ở cuối danh sách. Các phần tử được đánh số thứ tự 1, 2, 3, từ trên xuống.
Chạy thử: bấm cờ xanh, nhập 3, 8, 5, 12, 7, 1. Sáu số lần lượt xuất hiện trong danh sách, kèm số thứ tự ở bên trái.
Phần hai, tìm số lớn nhất. Thuật toán: coi phần tử thứ nhất là lớn nhất, vt bằng 1. Rồi cho i chạy từ 2 đến hết danh sách: nếu phần tử thứ i lớn hơn lonnhat, thì ghi lại lonnhat mới và vị trí mới.
Chọn nhóm Biến số, gắn khối đặt biến thành xuống dưới vòng lặp, chọn lonnhat,
thả khối phần tử thứ 1 của ds vào ô giá trị: lúc đầu, coi số thứ nhất là lớn nhất.
Khối đặt biến thành, chọn vt, gõ 1: vị trí của nó là 1.
Thêm khối đặt biến thành, chọn i, gõ 2: bắt đầu xét từ phần tử thứ hai.
Chọn nhóm Điều khiển, gắn khối lặp lại.
Còn phải xét bao nhiêu phần tử? Tất cả, trừ phần tử thứ nhất. Lấy khối phép trừ, trong nhóm Các phép toán, đặt ra chỗ trống, ô bên phải gõ 1,
ô bên trái thả khối kích thước của ds, trong nhóm Biến số: số phần tử của danh sách. Kéo cả biểu thức vào ô số lần lặp.
Bên trong vòng lặp, khối điều kiện nếu, trong nhóm Điều khiển,
Lấy khối phần tử thứ của ds, trong nhóm Biến số, đặt ra chỗ trống,
thả biến i vào ô số thứ tự: phần tử thứ i.
Lấy khối so sánh lớn hơn, trong nhóm Các phép toán,
bên phải thả biến lonnhat, kéo khối phần tử thứ i vào bên trái, rồi kéo điều kiện vào khối nếu: phần tử thứ i lớn hơn lonnhat.
Khi đó, khối đặt biến thành, trong nhóm Biến số, chọn lonnhat,
lại lấy khối phần tử thứ của ds,
thả biến i vào, rồi kéo vào ô giá trị: lonnhat nhận giá trị mới.
Thêm khối đặt biến thành, chọn vt,
thả biến i vào: ghi lại vị trí mới.
Sau khối nếu, vẫn trong vòng lặp: khối thay đổi biến một lượng, chọn i, giữ số 1: sang phần tử kế tiếp.
Giải thích: Chỉ khi gặp số lớn hơn lonnhat thì mới thay. Gặp số bằng lonnhat thì giữ nguyên, nên vt luôn là vị trí đầu tiên của số lớn nhất.
Cuối cùng, xuất kết quả. Chọn nhóm Hiển thị, gắn khối nói trong 2 giây xuống dưới vòng lặp,
lấy khối kết hợp, trong nhóm Các phép toán, đặt ra chỗ trống, Kết hợp là để nối lời nói ô thứ nhất gõ: Số lớn nhất, hai chấm,
ô thứ hai thả biến lonnhat, vậy khối kết hợp sẽ ra chuỗi: Số lớn nhất là bao nhiêu rồi kéo khối kết hợp vào ô lời nói.
Thêm khối nói, loại không có số giây,
khối kết hợp, gõ: Ở vị trí thứ,
và thả biến vt, rồi kéo khối kết hợp vào ô lời nói. Ta vừa làm phần tìm kiếm: bắt đầu với phần tử thứ nhất, duyệt các phần tử còn lại, gặp số lớn hơn thì cập nhật lonnhat và vt, rồi nói kết quả.
Kiểm thử: nhập 3, 8, 5, 12, 7, 1. Số lớn nhất là 12, ở vị trí thứ 4. Đúng. Thử toàn số âm: âm 5, âm 2, âm 9, âm 1, âm 7, âm 3. Số lớn nhất là âm 1, ở vị trí thứ 4. Thử sáu số bằng nhau: số lớn nhất là 4, ở vị trí thứ 1, vì các số sau không lớn hơn nó. Và một dãy giảm dần: số lớn nhất là 9, nằm ngay vị trí thứ 1. Vòng lặp vẫn duyệt hết, nhưng không lần nào phải thay lonnhat.
Các khối mới trong bài
- Khối thêm phần tử vào trong danh sách: đặt một giá trị mới vào cuối danh sách.
- Khối phần tử thứ … của danh sách: lấy giá trị nằm ở số thứ tự đã cho.
- Khối kích thước của danh sách: cho biết danh sách đang có bao nhiêu phần tử.
Kỹ thuật lập trình đã học
- Về kỹ thuật lập trình, bài này ta học: danh sách: một biến chứa nhiều giá trị, đánh số từ 1.
- Duyệt danh sách: biến i chạy qua từng số thứ tự.
- Tìm kiếm tuần tự: xét lần lượt từng phần tử, giữ lại kết quả tốt nhất.
- Và kiểm thử với nhiều dạng dữ liệu: số âm, số bằng nhau, dãy giảm dần.
Bài tập
Bài tập: sửa chương trình để tìm số nhỏ nhất. Rồi tính trung bình cộng của các phần tử trong danh sách.