Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Mời Các bạn vào đóng góp ý kiến nha

  1. #1
    Ngày gia nhập
    10 2007
    Nơi ở
    Trái Đất
    Bài viết
    0

    Cool Mời Các bạn vào đóng góp ý kiến nha

    Đây là bài ôn tâp thi Olympic sắp tới tại Đà Nẵng,cùng với gợi ý của mình mong các bạn xem và đóng góp ý kiến cho mình,nếu ai có cách hay hơn thì nêu ra cho mình biết luôn nha ok?
    bài 1:Cho trước 1 số R.hãy liệt kê tất cả các cách phân tích R thành tổng các số tự nhiên khác nhau từng đôi một.Dữ liệu ghi ở file b1.inp.Kết quả là file b1.out.Sao cho kết quả là số m,và là số cách phân tích.Và n dòng là các số tìm được

    Theo mình thì ta nên chọn R là 1 số bất kì,rồi cho R trừ lấn lượt các số tự nhiên đến khi nào kết quả cho ra trùng với 1 số trừ thì minh dừng lại.Vậy thì lúc đó số m sẽ là đếm số của các số bị trừ,còn n sẽ là đếm số của các kết quả tìm được.ban nao co ý kiến hay hơn thì up lên cho minh nha.

  2. #2
    Ngày gia nhập
    09 2006
    Nơi ở
    /usr/share/.hack@
    Bài viết
    1,433

    Từng đôi một chắc là phân tích dạng : R = a + b

    1. Nếu không tính hoán vị tổng tức là : a + b <=> b + a . chỉ lấy 1 cái
    thì ta đếm các số tự nhiên từ 0 tăng lần lượt 1 đơn vị lấy R trừ đi là ra số tương ứng. a tăng lên - b tính bằng hiệu (R - a). a tăng đến giá trị floor(R/2) là được.
    + Nếu R là số chẵn thì : R/2 = floor(R/2)
    + Nếu R là số lẻ thì : R/2 > floor(R/2)
    ta có : ( a + b ) / 2 = R / 2
    theo điều kiện ở trên đưa ra thì a <= b => a = b - 1
    Do đó sẽ có a + 1 = b -> trùng lặp hoán vị.

    Kết luận : a chỉ tăng đến floor(R/2)

    2. Nếu tính cả hoán vị thì cứ trừ đến R thì thoai

    Từ đó tính ra m và n .
    None!

  3. #3
    Ngày gia nhập
    05 2007
    Bài viết
    64

    Nhân việc bạn nói về mấy bài toán "luyện Olympic" mình có bài này, các bạn xem thử giải bằng cách nào là hiệu quả nhất nha.
    Xét tập N số tự nhiên đầu tiên {1..N}
    - Nếu N=3, ta có 1 cách chia tập này thành 2 tập con sao cho tổng các số trong 2 tập con này bằng nhau : {1,2} và {3}.
    - Nếu N=4, ta có 1 cách chia : {1,4} và {2,3}
    - Nếu N=5, hoặc N=6, ta k có cách chia vì tổng 1+2+...+N là 1 số lẻ (15 và 21).
    - Nếu N=7 ta có 4 cách chia: {2,3,4,5} và {1,6,7} ; {1,3,4,6} và {2,5,7}; {1,2,5,6} và {3,4,7}; {3,5,6} và {1,2,4,7}

    Yêu cầu : cho N, hãy tính số cách chia, ko cần liệt kê các trường hợp (tất nhiên, nếu có thì quá tốt -- câu này của mình )
    I know... nothing

  4. #4
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    - Theo yêu cầu bài toán: với 1 số nguyên n thì với một tổ hợp từ 2 đến l phần tử (l<n) sẽ có nhiều nhất 1 tổ hợp đạt yêu cầu với tổng bằng n. Ví dụ:
    + Với n=15, ta có:
    tổ hợp với nhiều nhất là 5 phần tử đạt yêu cầu bài toán (1+2+3+4+5)
    Vậy với tổ hợp 4 phần tử ta không có tổ hợp nào vì: 3+4+5+6>15
    Tổ hợp 3 phần tử cũng không có tổ hợp nào vì: 4+5+6>15
    Tổ hợp 2 phần tử thì có: 7+8
    - Cài đặt thuật toán:
    Bước 1: Xác định có bao nhiêu phần tử (gọi là k) để tổng các phần tử >=n (tính từ 1+2+…+ phần tử thứ k)
    Bước 2: Với trường hợp =n: ta có ngay trường hợp ban đầu thoả mãn.
    Bước 3: sử dụng vòng lặp giảm dần số phần tử k-1 đến k=2 và xét với mỗi số phần tử có đạt ngay từ lúc đầu (1+2+…+ phần tử k-1) đã có tổng =n chưa?
    Nếu bằng thì in ra màn hình và tiếp tục vòng lặp
    Nếu lớn hơn n trở lại vòng lặp
    Nếu nhỏ hơn n tiếp tục bước 4
    Bước 4: Áp dụng thuật toán sinh liệt kê các tập con k phần tử của n để sinh tiếp các tập con. Xét tập con mà tổng số phần tử có bằng n hay không?
    Nếu bằng thì in ra màn hình và trở lại bước 3
    Nếu lớn hơn trở lại bước 3
    Nếu nhỏ hơn trở lại bước 4 sinh tiếp tập con và xét tiếp
    Thuật toán dừng khi vòng lặp ở bước 3 xét xong với k=2
    - Đó là ý kiến của mình, mọi người góp ý thêm nha!!!!
    Không biết ghi gì luôn ...

Các đề tài tương tự

  1. Tìm nghiệm phức của PT bậc n - mọi người cùng đóng góp ý tưởng nhé!
    Gửi bởi trubavuong trong diễn đàn Ý tưởng sản phẩm CNTT của bạn
    Trả lời: 8
    Bài viết cuối: 25-09-2012, 05:57 PM
  2. Lớp tính toán với số nguyên lớn bằng C++. Mong mọi người đóng góp ý kiến nhé
    Gửi bởi thangit trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 14
    Bài viết cuối: 20-09-2008, 08:36 PM
  3. hỏi về multithread..Rất mong có sự đóng góp ý kiến (P2)
    Gửi bởi cakiempc trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 31-10-2007, 11:55 AM
  4. hỏi về multithread..Rất mong có sự đóng góp ý kiến
    Gửi bởi cakiempc trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 27-10-2007, 11:55 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn