Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

School@net
Bảng giá phần mềm
Educations Software

Đại Lý - Chi Nhánh

Bản tin điện tử
 
Đăng nhập/Đăng ký
Bí danh
Mật khẩu
Mã kiểm traMã kiểm tra
Lặp lại mã kiểm tra
Ghi nhớ
 
Quên mật khẩu | Đăng ký mới

 
Giỏ hàng

Xem giỏ hàng


Giỏ hàng chưa có sản phẩm

 
Xem bài viết theo các chủ đề hiện có
  • Hoạt động của công ty (701 bài viết)
  • Sản phẩm mới (217 bài viết)
  • Dành cho Giáo viên (552 bài viết)
  • Lập trình Scratch (3 bài viết)
  • Mô hình & Giải pháp (155 bài viết)
  • IQB và mô hình Ngân hàng đề kiểm tra (126 bài viết)
  • Hỗ trợ khách hàng (482 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (242 bài viết)
  • Học tiếng Việt (182 bài viết)
  • Thông tin khuyến mại (80 bài viết)
  • Download - Archive- Update (289 bài viết)
  • Các Website hữu ích (71 bài viết)
  • Cùng Học (98 bài viết)
  • Learning Math: Tin học hỗ trợ học Toán trong nhà trường (74 bài viết)
  • Thông tin tuyển dụng (55 bài viết)
  • School@net 15 năm (153 bài viết)
  • Mỗi ngày một phần mềm (7 bài viết)
  • Dành cho cha mẹ học sinh (123 bài viết)
  • Khám phá phần mềm (122 bài viết)
  • GeoMath: Giải pháp hỗ trợ học dạy môn Toán trong trường phổ thông (36 bài viết)
  • Phần mềm cho em (13 bài viết)
  • ĐỐ VUI - THƯ GIÃN (360 bài viết)
  • Các vấn đề giáo dục (1209 bài viết)
  • Bài học trực tuyến (1033 bài viết)
  • Hoàng Sa - Trường Sa (17 bài viết)
  • Vui học đường (276 bài viết)
  • Tin học và Toán học (220 bài viết)
  • Truyện cổ tích - Truyện thiếu nhi (181 bài viết)
  • Việt Nam - 4000 năm lịch sử (97 bài viết)
  • Xem toàn bộ bài viết (8179 bài viết)
  •  
    Thành viên có mặt
    Khách: 3
    Thành viên: 0
    Tổng cộng: 3
     
    Số người truy cập
    Hiện đã có 54908736 lượt người đến thăm trang Web của chúng tôi.

    Ví dụ về bài toán áp dụng thuật giải tin học

    Ngày gửi bài: 22/01/2009
    Số lượt đọc: 1770

    Bài toán: Cho hàm f xác định (N+ , N+ ) được xác định như sau:

    f(n) =1, với n lẻ

    k, nếu n = 2k.t ( với k nguyên dương, t lẻ)

    Tìm số n lớn nhất sao cho:

    f(1) + f(2) + … + f(n) ≤ 123456

    Nếu nhìn vào bài toán trên với cách giải quyết của người lập trình thì vấn đề trở nên rất đơn giản. Từ công thức xác định của hàm f, ta dễ dàng viết được chương trình để tính giá trị hàm f. Hàm f có giá trị được tính theo số mũ lớn nhất của lũy thừa 2 khi ta phân tích số n ra thừa số nguyên tố. (chương trình viết bằng ngôn ngữ C)

    Int somu_2(int n)

    {

    if(n%2==1) return 1

    int k =n, t;

    while(k%2==0)

    t++;

    k /=2;

    return t;

    }

    Đoạn chươngtrình tiếp theo chỉ cần 1 vòng lặp while giới hạn đối với tổng của các hàm f là đủ, vì số đề bài ra 123456 không lớn lắm nên chương trình sẽ nhanh chóng kết thúc.

    Nhưng bạn cùng tôi đều có thể thấy được, như vậy sẽ không có gì để nói về bài toán này cả. Chúng ta hãy cùng nhau phân tích thêm 1 chút để phát hiện thêm 1 số nhận xét hay hơn từ đề bài.

    Bước thứ nhất như ta đã nói, công thức hàm f xác định như trên chính là số mũ lớn nhất của thừa số 2 khi ta phân tích ra thừa số nguyên tố. (Nếu thay đổi đề bài lại 1 chút, nếu giá trị f xác định tại những số lẻ =0 thì ta có thể thấy tổng các hàm f từ 1 đến n chính là tổng các số mũ 2 nhận được khi ta tính n!, và quay về bài toán quen thuộc: Tìm n để n! chia hết cho 2123456).

    Bây giờ ta kí hiệu tổng vế trái là F(n).Từ công thức xác định f, ta có thể dễ dàng tính được giá trị tổng F tại các giá trị đặc biệt dạng 2k.

    Nhận xét 1:

    Kí hiệu Ai là tập hợp các số có số mũ lũy thừa 2 là i. | Ai | là số các phần tử trong nó. Dễ thấy |Ai| = 2k-i

    F(2k) = { tổng các f(Ai), i =1,2,..,k} + { tổng các f tại các số lẻ nhỏ hơn 2k}- { tổng các giá trị f tại các giá trị thuộc giao chung các tập hợp trên).

    Dễ thấy giá trị thừa số thứ nhất =Tổng { i*| Ai | }. Giá trị thứ 2 = { số các số lẻ nhỏ hơn nó }(dễ tính bằng 2 k-1) (1)

    Vấn đề là cần tính giá trị thừa số thứ 3, tức là cần phải đếm số các giá trị đã bị liệt kê khi ta tìm các số thuộc tập Ai. Ta cần thêm 1 nhận xét.

    Cũng như trên, ta thấy ngoài việc loại trừ các số lẻ ra, tổng trên chính là việc đếm số lượt thừa số 2 xuất hiện khi lần lượt xét từ 1đến n = 2k. Mỗi khi gặp 1 số có số mũ 2, thay vì liệt kê số mũ, ta đánh dấu nó và giảm số mũ đi 1. Sau khi đi hết, ta lại quay lại lần nữa để đếm các thừa số mũ 2 còn và lại đánh dấu lại… Vì vậy số lượng số mũ 2 chính bằng tổng số lượng các phần tử | Ai | . Vậy ta có thể tính được giá trị tổng này bằng:

    1 + 21 +…2k-1 = 2k - 1 (2)

    Kết hợp giữa (1) và (2) ta được:

    F(2k) =2k+ 2k-1- 1. Vậy ta có thể tính được giá trị tổng tại các điểm đặc biệt

    Nhận xét 2:

    Với 2 giá trị i

    Từ nhận xét này ta dễ thấy, nếu ta chọn được số i sao cho 2i< n < 2i+1 thì F(2i) < F(n) < F(2i+1).

    Từ nhận xét này ta sẽ có hướng giải quyết bài toán theo hướng đơn giản hơn, tìm các chỉ số mũ i và i+1 như trên rồi so sánh giá trị tại đó ( đã tính được ở bước trên) với giá trị cần xét.

    Nhận xét 3:Quan trọng nhất.

    Khi ta tìm được giá trị i như trên, phần so sánh tổng còn lại từ f(2i +1) đến f(n) với giá trị mới ( = giá trị đề bài – tổng F(2i)) để tìm n cũng có thể giải quyết hoàn toàn như trên với giá trị mới cần tìm = n – 2i.

    Thật vậy, từ cách tính f như trên ta có thể thấy giá trị f cũng như giá trị tổng F không thay đổi (hay không phụ thuộc) tại các giá trị mốc tính 2i ban đầu.

     

    Từ nhận xét 3 trên ta có thể đưa ra 1 cách giải hiệu quả như sau. Đầu tiên ta tìm 1 giá trị i sao cho F(2i) < 123456 < F(2i+1). Tiếp theo ta tính khoảng cách còn thiếu giữa 123456 và F(2i) để tiếp tục áp dụng phương pháp này để tìm giá trị mới. (Các bước thực hiện sẽ có số mũ giảm dần cho đến khi ta tìm được giá trị n lớn nhất thỏa mãn).

     

    Từ 3 nhận xét trên ta có thể đưa ra 1 thuật giải đẹp cho việc giải quyết bài toán. Giá trị đề bài yêu cầu cũng có thể được mở rộng lớn hơn rất nhiêu. Nếu thích, bạn có thể lập trình để đưa ra 1 thuật toán đệ quy chia đôi điển hình để tiếp tục giải quyết.


    NamTB

    School@net



     Bản để in  Lưu dạng file  Gửi tin qua email


    Những bài viết khác:



    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 1407 - Nhà 17T2 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Điện thoại: (024) 62511017 - Fax: (024) 62511081
    Email: school.net@hn.vnn.vn / thukhachhang@yahoo.com


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.