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ố 12 kết quả

Đề tài: 3 Bài tập ôn thi môn C

  1. #1
    Ngày gia nhập
    10 2007
    Bài viết
    2

    Mặc định 3 Bài tập ôn thi môn C

    Mình có một số bài tập C sau:
    B1:
    Liệt kê tất cả các cách viết n thành tổng các số nhỏ hơn n (Sinh kế tiếp).

    B2:
    Một người muốn đi từ thành phố số 1 qua đủ n thành phố và trở về vị trí ban đầu. Chi phí đi từ TP(i) đến TP(j) là C[i] [j]. Tìm cách đi với tổng chi phí là nhỏ nhất.
    DATA IN: chiphi.inp
    Dòng 1 ghi số n,
    n dòng kế tiếp mỗi dòng ghi n số của dòng trong ma trận C
    DATA OUT: ketqua.out
    Dòng 1 ghi đường đi tối ưu
    Dòng 2 ghi chi phí nhỏ nhất

    B3:
    Có n đồ vật, mỗi đồ vật có giá trị C[i], thể tích V[i]. túi có thể tích B. Tìm cách xếp các đồ vật vào túi sao cho tổng thể tích không vượt quá B và giá trị túi đồ vật là lớn nhât.
    DATA IN: giatri.inp
    Dòng 1 ghi 2 số n và B
    Dòng 2 ghi 1 số của mảng C
    Dòng 3 ghi 1 số của mảng V
    DATA OUT: ketqua.out Ghi thứ tự các đò vật được chọn.
    Mình không hiểu cách giải các bài tập này. Các bạn có thể giúp mình nhé!
    Cảm ơn mọi người.
    Đã được chỉnh sửa lần cuối bởi thanhhoacanhac : 17-01-2009 lúc 12:18 PM.

  2. #2
    Ngày gia nhập
    02 2008
    Bài viết
    15

    Trích dẫn Nguyên bản được gửi bởi thanhhoacanhac Xem bài viết
    Mình có một số bài tập C sau:
    B1:
    Liệt kê tất cả các cách viết n thành tổng các số nhỏ hơn n (Sinh kế tiếp).
    .
    cho mình hỏi nếu liệt kê như thế các số nhỏ hơn n có được trùng nhau ko ???
    ví dụ n =5 chẳng hạn
    có được 1 + 1 + 1 +1 + 1 không ???
    nếu không được trùng nhau thì bài toán đơn giản hơn nhiều !!!
    bạn dùng 1 while và 2 vòng lặp for làm như sau
    tìm tất cả các tổng của 2 số bằng n,
    rồi tồng của 3 số bằng n
    ......

    còn nếu lặp thì bạn có thể làm như sau :
    coi như từ 1 đến n ;
    1 có n số 1
    2 có n /2 số 2
    3 có n/3 số 3
    4 có n/4 số 4
    ....
    tiếp tục như thế vậy cuối cùng các số nhỏ hơn n không còn là n-1 nữa mà là
    n+n/2 +n/3 +.....
    và tìm như cách 1 (coi như các số là khác nhau) nhưng thực ra như thế nó sẽ lặp
    a = N!*(n/2)!*(n/3)!....
    vậy sau khi tìm được tổng cách viết bạn chia cho số a ở trên sẽ được số cách phân tích
    I dlatego lubię mówić z tobą !!!

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

    Cảm ơn ý kiến của ledinhtung61. Mình cũng chỉ xét trường hợp n không được trùng nhau, mình cũng đã tính như ý kiến của cậu: n+n/2 +n/3 +.....
    Nhưng không chắc chắn lắm về cách này. Giờ thấy có người suy nghĩ như mình, chắc là chính xác rồi. Cảm ơn cậu

  4. #4
    Ngày gia nhập
    11 2008
    Nơi ở
    Bình Dương
    Bài viết
    37

    Theo tui nên dùng đệ quy , đệ quy là cách ngắn nhất và đơn giản nhất với loại bài này

  5. #5
    Ngày gia nhập
    02 2008
    Bài viết
    15

    Trích dẫn Nguyên bản được gửi bởi thanhhoacanhac Xem bài viết
    Cảm ơn ý kiến của ledinhtung61. Mình cũng chỉ xét trường hợp n không được trùng nhau, mình cũng đã tính như ý kiến của cậu: n+n/2 +n/3 +.....
    Nhưng không chắc chắn lắm về cách này. Giờ thấy có người suy nghĩ như mình, chắc là chính xác rồi. Cảm ơn cậu

    ừ nhưng nói thật mình cũng ngại code nhũng bài thế này !!! cái này thực ra chỉ là 1 bài toán tổ hợp bình thường thôi !!! (nếu bạn học tổ hợp rổi có suy nghĩ giống mình ko có gì là lạ ) !!! nhưng nói thật là nó chỉ giúp bạn biết được có bao nhiêu cách phân tích thôi !!! còn để viết tất cả các cách phân tích là cả 1 vấn đề ( mình cũng gặp mấy bài dạng này ) nói chung code lần nào cũng ko vừa ý
    I dlatego lubię mówić z tobą !!!

  6. #6
    Ngày gia nhập
    11 2008
    Bài viết
    7

    Mặc định 3 Bài tập ôn thi môn C

    bài 2 là bài toán người du lịch. thuật toán : kĩ thuật nhánh cận
    bài 3 là bài toán cái túi ( cái balo or tên trộm ). thuật toán : quy hoạch động

    code thì bạn cứ search trên google là có.

    topic : 3 Bài tập ôn thi môn C (Cho hỏi bạn học trường gì sao ôn thi khó thế . Bài 2+3 là 2 bài nặng về thuật toán.)

  7. #7
    Ngày gia nhập
    02 2008
    Bài viết
    15

    Trích dẫn Nguyên bản được gửi bởi itachisasuke Xem bài viết
    bài 2 là bài toán người du lịch. thuật toán : kĩ thuật nhánh cận
    bài 3 là bài toán cái túi ( cái balo or tên trộm ). thuật toán : quy hoạch động

    code thì bạn cứ search trên google là có.

    topic : 3 Bài tập ôn thi môn C (Cho hỏi bạn học trường gì sao ôn thi khó thế . Bài 2+3 là 2 bài nặng về thuật toán.)

    ủa nghe lạ nhỉ mấy kĩ thuật này chưa nghe bao giờ đó
    I dlatego lubię mówić z tobą !!!

  8. #8
    Ngày gia nhập
    11 2008
    Bài viết
    7

    Trích dẫn Nguyên bản được gửi bởi ledinhtung61 Xem bài viết
    ủa nghe lạ nhỉ mấy kĩ thuật này chưa nghe bao giờ đó
    ^^. Bài 1 bạn làm là dùng thuật toán quay lui đấy ( đừng comment
    mấy kĩ thuật này chưa nghe bao giờ đó )

  9. #9
    Ngày gia nhập
    02 2008
    Bài viết
    15

    Trích dẫn Nguyên bản được gửi bởi itachisasuke Xem bài viết
    ^^. Bài 1 bạn làm là dùng thuật toán quay lui đấy ( đừng comment
    mấy kĩ thuật này chưa nghe bao giờ đó )
    Ủa cái đó cũng có tên hả ??? nghe hay nhỉ !!! mình chỉ nghĩ nó đơn giản là 1 bài toán tổ hợp lớp 12 hay làm thôi !!!
    các thuật toán bạn nói tên nghe hay nhỉ !!! thực sự là mình ko biết đó (mà cũng có thể dùng nhiều mà ko biết)
    phiền bạn tí chút share mình mấy quyển ebook thuật toán đó được ko !!! thanks trước nha
    I dlatego lubię mówić z tobą !!!

  10. #10
    Ngày gia nhập
    11 2008
    Bài viết
    7

    bạn down 3 ebook :
    - Bài giảng chuyên đề :Giải thuật và lập trình -thầy lê hoàng
    - 150 + bài toán tin - thầy lê minh hoàng
    - Introduction to alogrithms (2nd edition ) ( quyển này là giáo trình của MIT)

    http://vnoi.info/index.php?option=co...d=20&Itemid=27

    Ps : 2 quyển của thầy lê minh hoàng toàn thi quốc gia + quốc tế nên hơi khó nhằn T_T .

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