Thuật toán kiểm tra số mạnh mẽ minh họa bằng Pascal và Scratch

Like và share giúp mình phát triển website nhé.
  •  
  •  

Có rất nhiều những con số thú vị trong toán học, hôm bữa mình đã tìm hiểu về cặp số thân thiết rồi hôm nay mình tình cờ phát hiện ra một con số mới đó là số mạnh mẽ, nghe cái tên thôi mình đã thấy hứng thú rồi, ngay lập tức mình bắt tay vào tìm hiểu con số này ngay, tìm trên mạng thì chưa thấy nơi nào có thuật toán kiểm tra số mạnh mẽ cả vậy là mình quyết định dùng Pascal và Scratch để code bài toán tìm các số mạnh mẽ ngay.

Số mạnh mẽ là số như thế nào?

Số mạnh mẽ là số khi nó chia hết cho số nguyên tố thì cũng chia hết cho cả bình phương của số nguyên tố đó.

Ví dụ: 25 là số mạnh mẽ, vì nó chia hết cho số nguyên tố 5 và chia hết cho cả bình phương của 5 là 25.

Đây là danh sách tất cả các con số mạnh mẽ từ 1 đến 1000, mình đưa ra để khi code các bạn kiểm tra cho dễ

1, 4, 8, 9, 16, 25, 27, 32, 36, 49,

64, 72, 81, 100, 108, 121, 125, 128, 144, 169,

196, 200, 216, 225, 243, 256, 288, 289, 324, 343,

361, 392, 400, 432, 441, 484, 500, 512, 529, 576,

625, 648, 675, 676, 729, 784, 800, 841, 864, 900,

961, 968, 972, 1000.

Ta sẽ đưa ra bài toán cụ thể để dễ phân tích hơn bài toán như sau: Liệt kê các số mạnh mẽ không vượt quá 1000

Ý tưởng về thuật toán tìm số mạnh mẽ

Trong định nghĩa số mạnh mẽ có liên quan đến số nguyên tố vì vậy phải có một chương trình con kiểm tra số nguyên tố. Nếu chưa biết thuật toán này bạn vui lòng đọc lại bài viết Thuật toán kiểm tra số nguyên tố trước khi đọc tiếp nhé.

Mình sẽ duyệt từ 1 đến 1000, với mỗi số mình sẽ làm như sau;

  • Giả sử số cần kiểm tra (a) là số mạnh mẽ
  • Tìm các số nguyên tố nhỏ hơn hoặc bằng a (giả sử là i) và kiểm tra nếu a chia hết cho i nhưng a không chia hết cho i2  thì a không phải mạnh mẽ, thoát vòng lặp.
  • Xuất ra màn hình số đó nếu nó là mạnh mẽ.

Chương trình tìm số mạnh mẽ từ 1 đến 1000 trong pascal


Giải thích một chút về chương trình:

  • Biến a duyệt từ 1 đến 1000: Kiểm tra xem từ 1 đến 1000 số nào là số mạnh mẽ.
  • Mở đầu vòng lặp gài KT:= true (giả sử nó là mạnh mẽ)
  • Cho i chạy từ 2 đến a nếu i nguyên tố và a chia hết cho i và a chia hết cho ithì số này không mạnh mẽ (Kt:False)
  • Như vậy sau vòng lặp trên (i:2 ->a) nếu KT vẫn là true thì có nghĩa là số a là mạnh mẽ ta ghi kết quả ra.

Chương trình kiểm tra số mạnh mẽ trong Scratch

Xem video hướng dẫn kiểm tra số mạnh mẽ trong Scratch

Các bạn hãy đọc thật kĩ cho hiểu được thuật toán tìm số mạnh mẽ trên và hiểu được code Pascal, rồi sau đó mình tin rằng chỉ hai phút là bạn có thể kéo thả và hoàn thiện code bằng Scratch.

À mà cách viết chương trình trong Scratch để kiểm tra số nguyên tố hơi khác một chút trong Pascal vì vậy bạn hãy đọc lại bài viết thật kĩ thành thạo rồi mới làm bài này nhé.

Bạn nào có code Scratch tìm số mạnh mẽ thành công vui lòng chia sẻ để các bạn cùng học tập. Bạn nào khó khăn cứ comment mình sẽ cùng thảo luận.

Chúc các bạn thành công

 

 

2 Trả lời “Thuật toán kiểm tra số mạnh mẽ minh họa bằng Pascal và Scratch

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *