Số Bạn Bè Và Số Hoàn Hảo - Lập Trình Pascal - NGUYỄN THÀNH SƠN

Đăng nhập / Đăng ký

• Trang chủ
• Thành viên
• Liên kết Website
• Trợ giúp
• Liên hệ

• Trường THPT Quang Trung
• Báo bóng đá
• Tin nhanh
• Tìm kiếm
• Thầy Nguyễn Tất Thu

Đăng nhập

Tên truy nhập Mật khẩu Ghi nhớ   Quên mật khẩu ĐK thành viên

Thông tin

• Giới thiệu bản thân
• Chia sẻ kinh nghiệm
• Lưu giữ kỉ niệm
• Hình ảnh hoạt động
• Công Nghệ Thông Tin
• Tin tức đó đây

• Tin IT
• Phần cứng
• Thủ thuật
• Lập trình Pascal
• Access
• Visual Basic

• Tin giáo dục
• Tin 24h

Tài nguyên dạy học

Các ý kiến mới nhất

cho mình hỏi nếu đề cho file inp như này...

Thăm trang, hân hạnh được giao lưu cùng các Thầy...

Hi http://tinhbotnghe.violet.vn/...

hay quá cô ơi...

thầy ơi cho em hỏi nếu em muốn tìm đường...

thầy ơi cho em hỏi về giải thuật này ....

TVM gia nhập trang. Rất hân hạnh được giao lưu...

Mời các thầy cô tham gia và xây dựng diễn...

TVM THANH NGHỊ GIA NHẬP TRANG, RẤT HÂN HẠNH ĐƯỢC...

Chúc quý thầy cô dồi dào sức khỏe chuẩn bị...

lâu oyf e hok gặp thầy ha? dạo này thầy...

Nhật Trường chúc thầy Nguyễn Thành Sơn nhiều niềm vui...

TVN MONG ĐƯỢC GIAO LƯU VỚI CHỦ NHÀ. ...

TH ghé thăm chúc thầy kỳ nghỉ hè thật vui...

Hỗ trợ trực tuyến

• (Nguyễn Thành Sơn)
• (Nước Mắt Thần Linh)

Điều tra ý kiến

Học chứng chỉ tin học A ? Bạn sẽ học trong thời gian tới. Chưa biết có nên học không. Không học.

Thống kê

465028 truy cập (chi tiết) 76 trong hôm nay

1035518 lượt xem 112 trong hôm nay

295 thành viên

Ảnh ngẫu nhiên

Thành viên trực tuyến

2 khách và 0 thành viên

Sắp xếp dữ liệu

Mới nhất

Tải nhiều nhất

Đưa giáo án lên Gốc > Lập Trình Pascal >

• Số bạn bè và số hoàn hảo
• Cùng tác giả
• Lịch sử tải về

Số bạn bè và số hoàn hảo

• 
• 
• 
• 
• 
• 
• 0 / 0
• 

Nhấn vào đây để tải về Báo tài liệu có sai sót Nhắn tin cho tác giả (Tài liệu chưa được thẩm định) Nguồn: Người gửi: Trần Trung (trang riêng) Ngày gửi: 13h:21' 21-03-2009 Dung lượng: 97.5 KB Số lượt tải: 484 Số lượt thích: 0 người Số bè bạn và số hoàn hảoTrong quá trình học lập trình và thuật toán, đa số trong chúng ta đã từng nghe tới và làm các bài tập về các số bè bạn (friend numbers) và số hoàn hảo (perfect numbers). Các số bè bạn n, m là hai số nguyên mà tổng ước số của n bằng m và tổng các ước của m bằng n, ví dụ như cặp số bè bạn nhỏ nhất là 220 và 284. Các số hoàn hảo là các số mà tổng các ước thực sự của nó bằng chính nó, ví dụ như các số hoàn thiện đầu tiên là 6, 28 ...Bài toán thường liên quan tới các số bè bạn và số hoàn hảo là in ra tất cả các cặp số bè bạn và các số hoàn hảo không vượt quá một số nguyên N nào đó. Đây là hai bài toán khác nhau song lại có liên quan mật thiết với nhau vì trong quá trình xây dựng giải thuật cho bài toán chúng ta đều cần đến khái niệm gọi là tổng các ước của một số nguyên. Trong trường hợp N là một số nguyên nhỏ (N < 10000) thì một thuật toán đơn giản và hết sức trực quan cũng tạm chấp nhận được là:• Xây dựng một hàm tính tổng ước của một số nguyên• Duyệt các số từ 2 tới N, nếu tồn tại hai số i, j khác nhau mà tổng ước của i bằng j và tổng ước của j bằng i thì in ra i, j. Khi đó i, j chính là một cặp số bè bạn.• Duyệt các số từ 2 tới N, nếu tổng ước của số đó bằng chính nó thì in ra màn hình, đó chính là một số hoàn thiện cần tìm.Trước hết ta đi xây dựng hàm tính tổng các ước số của một số nguyên m: ta đã biết các ước số của m, nếu có sẽ không vượt quá căn bậc 2 của m (tức là sqrt(m)), và khi a là một ước của m thì m/a (m chia a) cũng là một ước của m (phần này xin đọc thêm bài báo “Số nguyên tố” để biết thêm chi tiết) nên một thuật toán hiệu quả sẽ xét các ứng cử viên có thể là ước của m nằm trong khoảng 1 tới sqrt(m) (gọi ước này là a), sau đó cộng a và m/a vào tổng ước của số m. Cài đặt cụ thể bằng ngôn ngữ C của thuật toán như sau:
Sau khi đã có hàm tính tổng ước số của một số nguyên, việc in ra các số hoàn thiện trở nên dễ dàng với 1 vòng lặp, nên ta chỉ xét đoạn chương trình in ra các cặp số hoàn thiện phân biệt (không kể thứ tự của các số):
Hầu hết các lập trình viên mới học lập trình và thuật toán sẽ dừng lại ở đây. Thuật toán in ra các cặp số bè bạn có hai vòng lặp lồng nhau, thuật toán sẽ chạy cỡ khoảng O(N) = N*(N+1)/2 bước, mỗi bước gọi tới hàm tong_uocso() hai lần để thực hiện so sánh nên độ phức tạp của thuật toán sẽ là O(N) = N2 * O(hàm tong_uocso()). Nếu N = 1000000 thì chắc chắn thuật toán không thể chạy trong thời gian 3 giây (thời gian test tối đa của các bài toán trong các cuộc thi lập trình).Tuy nhiên quan sát kỹ thuật toán, ta thấy rằng mỗi lần xét i trong vòng lặp thứ nhất, ta không cần thiết phải chạy một vòng lặp để xét các ứng cử viên có thể làm thành một cặp số bè bạn với i, mà chỉ cần xét số z = tong_uocso(i). Vì vậy một thuật toán hiệu quả hơn nhiều sẽ là như sau:
Ta cần thêm điều kiện z > i để in ra các cặp số khác nhau (vì z bây giờ đóng vai trò thay j trong thuật toán trước).Rõ ràng thuật toán thứ hai này có độ phức tạp nhỏ hơn nhiều so với thuật toán thứ nhất, thay vì chạy hai vòng lặp, ta chỉ cần một vòng lặp là đủ. Tất nhiên cải tiến này không thể áp dụng cho bài toán số hoàn hảo vì ta cũng chỉ cần một vòng lặp để in ra tất cả các số hoàn hảo không vượt quá N.Rõ ràng bây giờ các cải tiến của chúng ta, nếu có, sẽ không thể tập trung vào các vòng lặp, mà chỉ có thể nằm ở việc tính tổng ước số của mỗi số nguyên. Chúng ta đã biết thuật toán sàng Erastosthene để đánh dấu các số nguyên không phải là số nguyên tố (các số còn lại không được đánh dấu sẽ là số nguyên tố - có thể tham khảo trong bài báo số nguyên tố). Thuật toán sàng Erastosthene dựa trên một chi tiết hết sức tinh tế sau: nếu z là một số nguyên tố (hay hợp số) thì các bội số của z sẽ là các hợp số. Chúng ta hoàn toàn Thành viên mới chào thầy! Nguyễn Quang Loan @ 22h:41p 16/11/10 Các trang của quý thầy cô đẹp quá Nguyễn Ngọc Khuê @ 22h:57p 16/11/10 Phùng Văn Định @ 21h:59p 20/03/11

thầy sơn oj sao tài liệu về pascal mà ko viết bằng pascal khó coi wá

Phùng Văn Định @ 22h:05p 20/03/11

Tài liệu này sưu tầm thôi ah

Code C và pascal chuyển qua chuyển lại nhanh mà. Với lại giúp hiểu được cách làm là được rồi.

Nguyễn Thành Sơn @ 11h:08p 17/04/11   ↓ ↓ Gửi ý kiến Website được thừa kế từ Violet.vn, người quản trị: Nguyễn Thành Sơn