Giáo án Tin học 10 Bài 3: Bài toán và thuật toán

3.- Một số ví dụ về thuật toán (Học sinh tự dọc trong SGK)

Tuy nhiên ta hãy phân tích thêm ví dụ 1. (trang 36):

Kiểm tra tính nguyên tố của một số tự nhiên.

Ở đây, ta chỉ xét trường hợp gay cấn: số n lẻ > 10.

Kinh nghiệm mới đầu lấy số bé để thử đã, sau nâng lên thành tổng quát.

Chẳng hạn n= 97.

Thuật toán 1.

Thử các phép chia 97 cho 2,3,4,5 ,96. Nếu không khi nào chia hết thì 97 là số nguyên tố, trái lại 97

không là số nguyên tố. Cách này cần 95 phép thử chia. Tổng quát hết n-2 phép thử.

Thuật toán 2.

Thử các phép chia 97 cho 3,5,7, ,95 thôi, vì 97 lẻ không cần thử chia cho số chẵn! Cách này mất

[(n-2)/2] phép thử và ít hơn Thuật toán 1

TÀI LIỆU LUẬN VĂN CÙNG DANH MỤC

TIN KHUYẾN MÃI

  • Thư viện tài liệu Phong Phú

    Hỗ trợ download nhiều Website

  • Nạp thẻ & Download nhanh

    Hỗ trợ nạp thẻ qua Momo & Zalo Pay

  • Nhận nhiều khuyến mãi

    Khi đăng ký & nạp thẻ ngay Hôm Nay

NẠP THẺ NGAY