Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 15 kết quả

Đề tài: Bài tập lập trình san cột (Giống bài tháp Hà Nội)

  1. #1
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Bài tập lập trình san cột (Giống bài tháp Hà Nội)

    Đây là 2 bài khá hay và cũng có nhiều điểm tương đồng, tuy nhiên không phải giống hoàn toàn đâu nhé hì hì !

    Bài 1
    Một bộ bài được cho bởi N đống, mỗi đống chứa một số quân bài. Xem hình 1. Các đống được ký hiệu từ 1 đến N. Ta định nghĩa một nước đi khi nói p và chỉ ra số m. Khi đó m quân bài sẽ được chuyển từ đống p sang tất cả các đống hàng xóm. Đống p có hai hàng xóm là p-1 và p+1 nếu 1 < p < N, và có một hàng xóm là 2 nếu p=1, một hàng xóm là N-1 nếu p=N. Để ý rằng nước đi như­ vậy chỉ tồn tại nếu đống p có ít nhất 2m quân bài nếu p có hai hàng xóm và m quân bài nếu p có một hàng xóm.

    Bài toán đặt ra là "làm phẳng" tất cả các đống sao cho các đống có số quân bài như­ nhau sau khi sử dụng ít nước đi nhất. Trong trường hợp có nhiều nghiệm chỉ cần chỉ ra 1 trong chúng.



    · Dữ liệu đã cho bảo đảm rằng để giải quyết bài toán trên phải sử dụng tối đa là 10000 nước đi.

    · 2 <= N <= 200

    · 0 <= Ci <= 2000 với Ci là số quân bài ban đầu của đống i với 1<= i <= N

    Input

    Input là file text flat.inp có hai dòng

    - Dòng đầu tiên: N
    - Dòng thứ hai có N số nguyên là các giá trị Ci

    Output

    Output là tệp văn bản flat.out

    - Dòng đầu tiên: số các nước đi (gọi số này là M)
    - Mỗi dòng tiếp theo trong M dòng: các số tương ứng p, m

    Số thứ tự các bước đi đúng theo thứ tự các dòng được mô tả ở trên.
    Ví dụ
    Flat.inp

    Code:
    5
    0 7 8 1 4
    Flat.out
    Code:
    5
    5 2
    3 4
    2 4
    3 1
    4 2
    Bài 2
    Cho N số tự nhiên. Phép biến đổi P(i,j,d) giảm đồng lọat các phần tử từ phần tử thứ i đến phần tử thứ j của dãy xuống d đơn vị, d>0.
    Hãy thực hiện một số ít nhất phép biến đổi dạn P để đưa dãy đã cho về dãy số tòan số 0.

    Input

    - Dòng đầu tiên ghi số N (1<=N<=30000)
    - Các dòng tiếp theo ghi N của dãy, các số cách nhau ít nhất 1 khỏang trắng hoặc 1 dấu xuống dòng.

    Output

    - Dòng đầu hứa một số nguyên duy nhất K là số lần thực hiện các phép biến đổi dạng P để đưa dãy đã cho về dãy toàn số 0.
    - K dòng tiếp theo ghi ra các phép biến đổi tương ứng.

    Ví dụ :
    Flat.inp
    Code:
    7
    1 3 5 7 5 3 1
    Flat.out
    Code:
    4
    4 4 2 
    3 5 2  
    2 6 2 
    1 7 1
    Đã được chỉnh sửa lần cuối bởi rox_rook : 18-11-2007 lúc 12:40 AM.

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Mới đọc bài 1 thôi là thấy mệt rồi, có ý tưởng nhưng chưa code (Bận quá hix)

    - Tính tổng số quân bài có trong N đống
    - Nếu A%N != 0 -> Bài toán vô nghiệm.
    - Ngược lại số quân bài ở mỗi đống cần có là A/N
    - Tình cột có số quân bài lớn nhất.
    - Tính số quân bài cần để đạt đến tổng số bài trung bình cần có ở các cột bên trái và bên phải Sau đó chuyển số bài cần thiết qua.

    VD:
    5
    0 7 8 1 4

    Tổng Số Sum = 7+8+1+4 = 20
    Sum % n = 20%5 =0 . Vậy bài toán có kết quả.
    Arg= Sum/n =4. // Số phần tử có trong cột là 4.

    Cột có Số Phần tử lớn nhất là cột 3 với 8 phần tử. Do đó sẽ phải xuất đi 4 phần tử.

    Tổng Số phần tử đang có ở các cột bên trái là :
    LSum = 0+7 = 7.
    Số phần tử cần thiết để về trạng thái cần bằng là 4*số cột = 4*2 = 8.
    Vậy số phần tử cần truyền là: 8-7 =1.
    Do đó spt cần truyền cho cột bên phải là 4-1 = 3.

    Như thế sẽ truyền 1 qua cột bên trái của cột 3 và truyền 3 cho cột bên phải của cột 3 . Có nghĩa là:
    Cột 2 sẽ nhận 1, và cột 4 sẽ nhận 3. Đệ qui sẽ có lời giải chính xác. Tớ tin tưởng vào giải thuật này.

    Tớ còn cách nữa bằng cây. Nhưng ko thể nêu lên đây được. Hết tiền online rồi bb

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Hì hì, lần này để Kid trổ tài đây ^^ ! Cố lên !

  4. #4
    Ngày gia nhập
    08 2006
    Bài viết
    59

    Thân gửi kidkid,

    Đệ qui sẽ có lời giải chính xác. Tớ tin tưởng vào giải thuật này
    => nếu mình có 3 cột như sau:

    o
    o o
    o o o
    ------
    3 2 1

    => thì bạn sẽ làm ra sao ?

    -thân

  5. #5
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Cậu cứ coi lại thử thuật toán đi:

    Theo đề có n=3 với n1=3,n2=2,n3=1.
    Sum = n1+n2+3 = 6
    Sum%n = 0 . Vậy bài có lời giải.
    Số lá bài cần có ở mỗi cột là . arg =NumberOfPile = sum/n = 6/3 = 2.

    Tìm cột lớn nhất -> maxN=n1=3.
    Số lá bài thừa ( hay được quyền chuyển). 3 - arg = 3-2=1
    Tổng số phần tử cột bên trái 0.
    Tổng số cột bên trái : 0
    => Số Piles cần chuyển cho cột bên trái 0*0=0
    Do đó số lá bài cần chuyển cho cột bền phải là 1-0=0.
    Vậy chuyển cho cột thứ nhất 1 phần tử xong bước này ta sẽ có:
    -0
    00
    000
    ---
    231

    Đệ qui sẽ có lời giải chính xác.

    Tớ ko định trả lời. Cậu nên đọc kĩ và cùng tham khảo nhé.

  6. #6
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Mặc định Bài tập lập trình san cột (Giống bài tháp Hà Nội)

    Bài số 2 kì kì quá, nhất là phần input cậu coi lại cái ex rox nhé . Chờ cậu

  7. #7
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    ờ ! hì hì ! mình thiếu N cho dãy số ke ke ! Thanks kidkid nhé !

  8. #8
    Ngày gia nhập
    08 2006
    Bài viết
    59

    Thân gửi bạn kidkid,

    o
    o o
    o o o
    -----
    3 2 1

    => nếu tui giải bằng tay thì tui nghĩ tốn chỉ có 2 bước thôi (chưa biết là tối ưu hay không)

    Còn như cách của bạn:

    o
    o o
    o o o
    -----
    3 2 1

    => bước 1:

    - o
    o o
    o o o
    -----
    2 3 1

    => không biết bạn làm tiếp ra sao ? nhưng tui nghĩ bạn KHÔNG THỂ XONG TRONG VÒNG 2 BƯỚC (ĐỀ BÀI YÊU CẦU: ÍT BƯỚC NHỨT) ? (có thể tui hiểu sai cách làm của bạn chăng ?)

    (hiểu biết nông cạn; có gì sai sót mong được góp ý, xin cám ơn)

    -thân
    Đã được chỉnh sửa lần cuối bởi bete : 18-11-2007 lúc 02:51 AM.

  9. #9
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Éc thế nếu tớ có 5000 cột thì liệu cậu có thể làm bằng tay ko ?
    Với lại cậu đọc kĩ đi, chỉ có thể san cột cho cột liền kề nó thôi. Mình chưa đọc kĩ chỉ lướt sơ qua nhớ là có câu đó.

  10. #10
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Bai` 2 to' nghi~ ra roi` . Ok nhé.

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