kết quả từ 1 tới 5 trên 5

Ai rành về lập trình Pascal cho em hỏi tý.

  1. #1
    Ðến Từ
    Hải Dương
    Thành Viên Thứ: 394120
    Giới tính: Nam
    Bài gửi
    18

    Question Ai rành về lập trình Pascal cho em hỏi tý.

    Đề bài: Cho số nguyên dương N. Hãy đếm số cách phân tích N thành tổng các số nguyên dương liên tiếp. Ví dụ, nếu N=9 thì có 3 cách phân tích:
    9=9.
    9=4+5.
    9=2+3+4.
    Input: Nhập từ bàn phím số nguyên dương N ≤ 109
    Output: Ghi ra màn hình số cách phân tích N thành tổng các số nguyên dương liên tiếp.
    ____________
    Em làm như sau:
    For i:=1 to n div 2 do
    If (2n-i*(i-1)) mod 2*i = 0 then d:=d+1;
    Nhưng khi chạy, chương trình của em không thể chạy được những số quá lớn, ví dụ như 9.105. Và em lên mạng xem lời giải thì như thế này:
    max:=Trunc((1+sqrt(1+8.0*n))/2);
    For i:=1 to max do
    If (i*(i-1)<2*n) and ((2*n-i*(i-1) mod 2*i = 0) then d:=d+1;
    ___________
    Cho em hỏi cái chỗ (i*(i-1)<2*n) để làm gì? Và vì sao có thể biết chỉ cần chạy đến Trunc((1+sqrt(1+8.0*n))/2) là đã đủ trường hợp rồi. Em đã nháp, cố chứng minh đủ kiểu nhưng vẫn ko hiểu 2 chỗ đó.<Cần lắm 1 cao nhân giải thích cặn kẽ.> .
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Ai rành về lập trình Pascal cho em hỏi tý.

    Mình nghĩ chắc bạn đã biết đc kết quả chính là số lượng các giá trị i sao cho biểu thức
    Mã:
    ( 2n - i (i - 1) ) / (2i)
    là nguyên. Thật ra phải là nguyên dương vì là tổng các số nguyên dương liên tiếp.

    Như vậy, ta có thể thấy:
    Mã:
    a) 2n - i(i - 1) chia hết cho 2i.
    Phần này bạn đã thực hiện xong.

    Mã:
    b) i(i - 1) < 2n để có đc nguyên dương.
    Đây là trả lời cho câu hỏi thứ 1 của bạn.

    Mã:
    c) Giải bất phương trình i(i - 1) < 2n sẽ ra đc upper limit cho i theo n.
    Đây là trả lời cho câu hỏi thứ 2 của bạn.

    Hope it helps!
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. Đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 358027
    Bài gửi
    1.678

    Reply: Ai rành về lập trình Pascal cho em hỏi tý.

    Đây là cách giải của mình. Phân tích đề bài

    Số nguyên dương N là tổng của n số nguyên dương liên tiếp. Ta có thể biểu diễn như sau:

    N = m + (m + 1) + ... = m*n + (0 + 1 + ....) = m*n + S(n)

    với S(n) chính là cấp số cộng với a[0] = 0, d = 1 => S(n) = n*[2*0 + (n-1)*1]/2 = n*(n-1)/2

    +) Xét m = 0 khi đó N = S(n) bài toán trở thành tìm n nguyên thỏa mãn: N = n*(n-1)/2 hay giải nghiệm nguyên phương trình bậc 2: n^2 - n - 2N = 0

    +) Xét m > 0

    Thay S(n) = n*(n-1)/2 vào N ta có:

    N = m*n + n*(n-1)/2 = n*(2m + n -1)/2 hay N = n*(2m + n -1)/2 hoặc m = (2N/n - n + 1)/2

    Do m, n nguyên, m > 0 suy ra 2m + n - 1 >= n <=> N >= n^2/2 <=> 2N >= n^2 <=> sqrt(2N) >= n hay 1 < n =< sqrt(2N)

    Bây giờ bài toán sẽ trở thành tìm m nguyên sao cho thỏa mãn

    +) n nguyên chạy trong khoảng 1 < n =< sqrt(2N)

    +) giá trị m được xác định theo công thức m = (2N/n - n + 1)/2

    P/S: phân tích N thành tổng các số nguyên dương liên tiếp. Ví dụ, nếu N=9 thì có 3 cách phân tích:
    9=9. <= sai, tổng tối thiểu là 2 và 0 + 9 = 9 không phải số nguyên dương liên tiếp nên chỉ có 2 cách phân tích
    9=4+5.
    9=2+3+4
    www.thuthuatdoday.tk - Chia sẻ thủ thuật, tiện ích máy tính

  5. Đã cảm ơn gunshot9x:


  6. #4
    Ðến Từ
    Hải Dương
    Thành Viên Thứ: 394120
    Giới tính: Nam
    Bài gửi
    18

    Reply: Ai rành về lập trình Pascal cho em hỏi tý.

    Không phải sai đâu bạn, đề bài mình táng nguyên vào rồi đấy. Cái này là đề học sinh giỏi tỉnh Hải Dương năm 2014-2015 mà.

  7. #5
    Ðến Từ
    Hải Dương
    Thành Viên Thứ: 394120
    Giới tính: Nam
    Bài gửi
    18

    Lightbulb Reply: Ai rành về lập trình Pascal cho em hỏi tý.

    Trích Nguyên văn bởi tengiday Xem bài viết
    Mình nghĩ chắc bạn đã biết đc kết quả chính là số lượng các giá trị i sao cho biểu thức
    Mã:
    ( 2n - i (i - 1) ) / (2i)
    là nguyên. Thật ra phải là nguyên dương vì là tổng các số nguyên dương liên tiếp.

    Như vậy, ta có thể thấy:
    Mã:
    a) 2n - i(i - 1) chia hết cho 2i.
    Phần này bạn đã thực hiện xong.

    Mã:
    b) i(i - 1) < 2n để có đc nguyên dương.
    Đây là trả lời cho câu hỏi thứ 1 của bạn.

    Mã:
    c) Giải bất phương trình i(i - 1) < 2n sẽ ra đc upper limit cho i theo n.
    Đây là trả lời cho câu hỏi thứ 2 của bạn.

    Hope it helps!
    À ra vậy.
    i2-i-2n<0.
    → ∆=1+8n.
    →i1=(1-sqrt(1+8n))/2, i2=(1+sqrt(1+8n))/2.
    Xét dấu p.trình
    →i1< i <i2.
    Thanks bác nha.