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

Đề tài: Cần giúp đỡ một bài tập C khá hay

  1. #1
    Ngày gia nhập
    09 2011
    Bài viết
    0

    Mặc định Cần giúp đỡ một bài tập C khá hay

    Bài 4 (bonus): Rút gọn dãy số. Tên chương trình: sequence.c
    Cho một dãy số a1, …, an. Chúng ta cần thao tác dãy này sử dụng các phép toán reduce(i), thay
    phần tử ai và ai+1 bằng max(ai, ai+1). Chi phí của thao tác đó bằng max(ai, ai+1). Kết quả sẽ được
    một dãy có độ dài nhỏ hơn. Thực hiện n-1 thao tác này sẽ được dãy có độ dài bằng 1.
    Nhiệm vụ của bạn là thực hiện n-1 thao tác để rút gọn dãy số về 1 phần tử với tổng chi phí nhỏ
    nhất.
    Dữ liệu vào từ màn hình:
    Dòng đầu chứa số n là số phần tử của dãy số ( 1 ≤ n ≤ 1000)
    n dòng tiếp theo dòng thứ i+1 ghi số ai (0 ≤ ai ≤ 1,000,000,000)
    Kết quả ra màn hình:
    Ghi một số duy nhất là tổng chi phí thấp nhất.
    * Dữ liệu vào
    3
    1
    2
    3
    * Kết quả tương ứng 5
    Chú ý:
    • Không dùng mảng để nhớ.
    • Khi làm nhớ chứng minh cách làm là đúng!

    Anh chị nào giúp em với. Em cảm ơn nhiều. Nhớ chứng minh thuật toán đúng cho em nhé !!!

  2. #2
    Ngày gia nhập
    03 2009
    Bài viết
    45

    Bài này dùng toán rời rạc thôi, bạn tìm quyển toán rời rạc của Nguyễn Đức Nghĩa về tự đọc nhé, mình nghĩ là pthueeatsaj toán nhánh cận hoặc Dijiktra j đó, có cả lời giả lẫn chứng minh lun.

  3. #3
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Trích dẫn Nguyên bản được gửi bởi kiemsi.yaiba Xem bài viết
    Bài 4 (bonus): Rút gọn dãy số. Tên chương trình: sequence.c
    Cho một dãy số a1, …, an. Chúng ta cần thao tác dãy này sử dụng các phép toán reduce(i), thay
    phần tử ai và ai+1 bằng max(ai, ai+1). Chi phí của thao tác đó bằng max(ai, ai+1). Kết quả sẽ được
    một dãy có độ dài nhỏ hơn. Thực hiện n-1 thao tác này sẽ được dãy có độ dài bằng 1.
    Nhiệm vụ của bạn là thực hiện n-1 thao tác để rút gọn dãy số về 1 phần tử với tổng chi phí nhỏ
    nhất.
    Dữ liệu vào từ màn hình:
    Dòng đầu chứa số n là số phần tử của dãy số ( 1 ≤ n ≤ 1000)
    n dòng tiếp theo dòng thứ i+1 ghi số ai (0 ≤ ai ≤ 1,000,000,000)
    Kết quả ra màn hình:
    Ghi một số duy nhất là tổng chi phí thấp nhất.
    * Dữ liệu vào
    3
    1
    2
    3
    * Kết quả tương ứng 5
    Chú ý:
    • Không dùng mảng để nhớ.
    • Khi làm nhớ chứng minh cách làm là đúng!

    Anh chị nào giúp em với. Em cảm ơn nhiều. Nhớ chứng minh thuật toán đúng cho em nhé !!!
    Hihi, đây là bài toán thì đúng hơn là bài lập trình. Mà chứng minh bài toán luôn phức tạp và dài dòng.

    OK cách mình đưa ra là: Thuật toán ăn tham. Tức là luôn chọn cặp số có chi phí rút gọn nhỏ nhất tiến hành trước.
    Nếu có nhiều cặp số có chi phí rút gọn bằng nhau và cùng là nhỏ nhất thì chọn cặp nào cũng được (Khi implement thì chọn cặp đầu tiên từ bên trái dãy sang).

    Chứng minh: Có thể chứng minh bằng quy nạp, mình chỉ nói sơ lược còn bạn phải tự diễn giải cụ thể thôi Mình tin rằng sẽ có cách chứng minh hay hơn, ngắn gọn hơn nhưng mình chưa nghĩ ra
    Quy ước:
    Gọi F(dãy) là tổng chi phí rút gọn - cái cần tối ưu để nhỏ nhất
    Fmin(dãy) là tổng chi phí rút gọn nhỏ nhất có thể được đối với dãy. Nghĩa là Fmin(S) <= Fx(S) với mọi thuật toán X và mọi dãy S.
    Gọi CPRG(i) là chi phí của phép toán reduce(i) như định nghĩa trong đề bài; 1 <= i < n
    Gọi CP(dãy) = chi phí thao tác reduce nhỏ nhất của dãy, tức CP(S) = min{CPRG(i): 1 <= i < n}

    Gọi thuật toán ta đang chứng minh là thuật toán A. Fa(dãy) là tổng chi phí rút gọn khi thực hiện theo thuật toán A. Thuật toán A sẽ chọn 1 cặp số a[k], a[k+1] bất kỳ thỏa mãn CPRG(k) = CP(dãy) để tiến hành rút gọn. Ta cần chứng minh không tồn tại thuật toán X với 1 dãy S nào mà Fx(S) < Fa(S)

    Trường hợp dãy có 2 phần tử, chỉ có duy nhất 1 cách rút gọn, vậy thuật toán là đúng
    Với n > 2: giả sử ta đã chứng minh được thuật toán là đúng cho mọi dãy có <= n-1 phần tử (giả thuyết quy nạp). Tức là Fa(S) = Fmin(S) với mọi dãy S có <= n-1 phần tử. Ta cần chứng minh thuật toán cũng đúng cho dãy có n phần tử, tức là Fa(S) = Fmin(S) với mọi dãy S có n phần tử (quy nạp mà)

    Gọi cặp số mà thuật toán A chọn trong thao tác đầu tiên là S[k] và S[k+1]. Theo thuật toán, ta có CPRG(k) = CP(S) và CPRG(k) <= CPRG(i) với mọi 1 <= i < n

    Giả sử tồn tại thuật toán X có tổng chi phí Fx(dãy) nhỏ hơn chi phí Fa(dãy) của thuật toán A đang chứng minh. Thao tác rút gọn đầu tiên của thuật toán X là reduce(x) và dãy S sau khi thực hiện thao tác đó trở thành dãy Sx, Sx sẽ có n-1 phần tử. Có 4 trường hợp xảy ra:
    x = k - 1, x = k, x = k+1 và {x < k-1 hoặc x > k+1}
    [1] x = k. Bước đầu nó làm giống như ta mà sau bước đầu thì đưa về dãy n-1 phần tử, thuật toán A của ta là tối ưu (theo giả thuyết quy nạp). Vậy nó không thể tốt hơn ta được ==> giả thuyết Fx(dãy) < Fa(dãy) là sai

    [2] x < k-1 hoặc x > k+1, tức là thao tác đầu của thuật toán X không động chạm gì đến 2 phần tử k và k+1. Vậy sau thao tác này vẫn còn nguyên 2 phần tử k và k+1 và chúng vẫn ở cạnh nhau. Sau thao tác đầu thì còn lại dãy Sx có n - 1 phần tử, theo giả thuyết quy nạp thuật toán A sẽ đúng với dãy Sx, mà bước tiếp theo thuật toán A sẽ chọn 2 phần tử đó để rút gọn ==> Đằng nào cũng có thao tác rút gọn 2 phần tử S[k], S[k+1] ==> thuật toán đúng (Cái này khi diễn giải phải dùng 1 loạt công thức dài dòng đó)

    [3][4] x = k-1 (chỉ với k > 1) và x = k+1 (chỉ với k+1 < n)
    2 dãy Sx và Sk sau khi thực hiện tương ứng 2 thao tác reduce(x) và reduce(k) sẽ chỉ khác nhau duy nhất 2 phần tử. Tính toán lý luận 1 hồi => chứng minh được sự chênh lệch giữa Fmin(Sx) và Fmin(Sk) không đủ bù đắp cho sự chênh lệch giữa CPRG(k) và CPRG(x), tức là Fmin(Sx) + CPRG(x) >= Fmin(Sk) + CPRG(k).
    Mà Fmin(Sk) + CPRG(k) = Fa(Sk) + CPRG(k) = Fa(S), suy ra nó vẫn không tốt hơn ta được

    Diễn giải cho các trường hợp [2] và [3][4] phải dùng 1 loạt công thức khá dài dòng, phải chứng minh 1 vài bổ đề phụ nữa (mà có lẽ bổ đề phụ cũng phải chứng minh bằng quy nạp tiếp =)) ). Bài này làm ra giấy chắc phải kín ít nhất 2 mặt tờ A4
    Đã được chỉnh sửa lần cuối bởi fbchicken : 02-10-2011 lúc 02:55 AM.

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

  1. Sự cố Nhờ mod chuyển giúp bài "Sắp xếp số thứ tự ngay trong bảng của 1 database?" từ MySQL sang MSSQL giúp!
    Gửi bởi hu-xeko trong diễn đàn Ý kiến, đề xuất và khiếu nại
    Trả lời: 1
    Bài viết cuối: 12-03-2012, 07:48 PM
  2. Mới nhập môn khó quá , cần trợ giúp [Vấn đề của bạn cần muốn giúp là gì ?]
    Gửi bởi cuingo212 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 5
    Bài viết cuối: 22-10-2011, 08:43 AM
  3. Chương trình giúp một học sinh cấp 1 học phép nhân, xử lý hàm rand, giúp mình với?
    Gửi bởi chankx trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 12-05-2009, 08:52 PM
  4. Code giúp add một key vào registry, ai giúp em?
    Gửi bởi olavien trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 12-12-2007, 08:45 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