Tin học đại cương - Nguyễn Duy Hiệp

Sắp xếp nổi bọt

Có thể bạn quan tâm!

Xem toàn bộ 250 trang tài liệu này.

Lần lặp 3

kết thúc lần lặp 3

Sắp xếp nổi bọt

Lần lặp 4

kết thúc lần lặp 4

Dãy đã được sắp xếp !

Sắp xếp nổi bọt

 B1: Nhập số N và dãy số a1,a2,…,aN

 B2: i  N

 B3: Nếu i < 2 thì chuyển tới bước 9.

 B4: j  2

 B5: Kiểm tra j ≤ i

Nếu đúng chuyển sang bước 6 Nếu sai chuyển sang bước 8

 B6: so sánh aj-1 và aj

Nếu aj-1>aj thì hoán đổi vị trí 2 phần tử

 B7: Tăng j và quay lại bước 5

 B8: giảm i và quay lại bước 3

 B9: Kết thúc

Sắp xếp nổi bọt

Bắt đầu

 Nhập N

 Nhập a1,..,aN

i  N

Đúng

i > 1

Sai

Kết thúc

Sai

j=2

j≤ i

i=i-1

j=j+1 Sai

aj-1 > aj

Đúng Đúng

Đổi chỗ aj và aj-1

Một số thuật toán thông dụng

 Thuật toán kiểm tra số nguyên tố

 Đầu vào: số nguyên dương n

 Đầu ra: trả lời n có phải số nguyên tố hay không

 VD. 19, 57 là số nguyên tố

 Ý tưởng:

 Số nguyên tố là số chỉ chia hết cho 1 và chính nó.

 Để kiểm tra số nguyên tố ta sẽ thử chia số đó với các số từ 2 đến 𝑛. Nếu chia hết cho bất kỳ 1 số nào thì không phải số nguyên tố.

Một số thuật toán thông dụng

 Bước 1: Nhập n

 Bước 2: i=2

 Bước 3: so sánh 𝑖 ≤ 𝑛.

Nếu sai thì chuyển sang Bước 6

Nếu đúng thì chuyển sang Bước 4

 Bước 4: Kiểm tra n có chia hết cho i

Nếu đúng thì chuyển sang Bước 5

Nếu sai thì tăng i lên 1 và quay lại Bước 3

 Bước 5: In thông báo n không phải số nguyên tố và kết thúc

 Bước 6: In thông báo n là số nguyên tố và kết thúc

Một số thuật toán thông dụng

Bắt đầu

Nhập N

i=2

i ≤ căn bậc hai của n

Sai

N là số nguyên tố

Đúng N chia hết cho i Sai

Đúng

N không phải là số nguyên tố

i=i+1

Kết thúc

1.11. Ngôn ngữ lập trình

Review

1. Nêu các bước giải quyết vấn đề

2. Giải quyết vấn đề bằng máy tính có đặc điểm gì

3. Các bước để giải quyết vấn đề bằng máy tính

4. Thuật toán là gì

5. Trình bày phương pháp thiết kế top-down