Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 29 kết quả

Đề tài: Bài tập 12 viên bi, tìm viên bi khác loại

  1. #1
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Mặc định Bài tập 12 viên bi, tìm viên bi khác loại

    12 viên bi

    Có 12 hòn bi giống hệt nhau về kích thước, hình dáng và khối lượng. Tuy nhiên trong chúng lại có đúng một hòn bi kém chất lượng: hoặc nhẹ hơn hoặc nặng hơn bình thường. Dùng một cân bàn hai bên, bạn hãy dùng 3 lần cân để tìm ra được viên bi đó. Cần chỉ rõ rằng viên bi đó là nặng hơn hay nhẹ hơn.

  2. #2
    Ngày gia nhập
    01 2007
    Nơi ở
    Somewhere I belong
    Bài viết
    168

    Hừm bài này anh làm từ hồi mới học C nhưng chỉ là 8 viên bi.
    Nếu 12 viên thì theo thuật giải của anh thì phải ít nhất 5 lần cân.
    Nếu 3 lần cân thì quả thuật là khó.
    Attached Files Attached Files
    Đã được chỉnh sửa lần cuối bởi iamvtn : 28-09-2007 lúc 03:25 PM.

  3. #3
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Chắc chắn là 3 lần cân anh ạ

  4. #4
    Ngày gia nhập
    07 2007
    Nơi ở
    Lang thang không nơi nương tựa
    Bài viết
    18

    Chia 12 quả ra làm 3 cân kiểu gì mà chả ra .

  5. #5
    Ngày gia nhập
    09 2007
    Bài viết
    17

    Trích dẫn Nguyên bản được gửi bởi ABC_HT Xem bài viết
    Chia 12 quả ra làm 3 cân kiểu gì mà chả ra .
    Chính xác! You're Number 1
    AI NÂNG MÌNH LÊN SẼ BỊ HẠ XUỐNG VÀ AI HẠ MÌNH XUỐNG SẼ ĐƯỢC NÂNG LÊN


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

    Mặc định Bài tập 12 viên bi, tìm viên bi khác loại

    Thực ra bài này giải thế này là tối ưu nè ( theo suy nghĩ của pete ) ^^!
    Với điều kiện phải biết chắc chắn viên bi đó nặng hơn hoặc nhẹ hơn.
    Ví dụ nếu nó nhẹ hơn, nặng hơn tương tự, thì đáp án sẽ là :

    -- Tối thiểu là 2 lần cân ra luôn
    -- Không quá 3 lần cân là ra.

    Xác định : lấy 12 viên bi chia làm 3 phần , mỗi phần 4 bi ( A , B , C )
    lấy 2 phần A và B ra cân :
    + Nếu A = B --> thằng cần tìm trong C
    + Nếu A < B --> thằng cần tìm trong A
    + Nếu A > B --> thằng cân tìm trong B
    Giả sử thằng cần tìm trong C , ta xét phần C có 4 bi ( C1,C2,C3,C4 )
    Lấy 2 viên bi trong số 4 bi ra cân ^^
    Giả sử lấy C1,C2
    + Nếu C1 < C2 hoặc C1 > C2 thì thằng cần tìm sẽ là C1 hoặc C2 ->> đúng 2 lần cân. XONG
    + Nếu C1 = C2 thì thằng cần tìm sẽ là C3 hoặc C4, đem cân ra là có kết quả.
    ---> Đúng 3 lần cân ^^. XONG

    Đó là xử lý nếu biết chính xác viên bi đó nặng hay nhẹ.

    Còn nếu không biết chính xác thì :-?...Lúc khác nghĩ chứ đau đầu lắm
    None!

  7. #7
    Ngày gia nhập
    01 2007
    Nơi ở
    Somewhere I belong
    Bài viết
    168

    Trích dẫn Nguyên bản được gửi bởi ABC_HT Xem bài viết
    Chia 12 quả ra làm 3 cân kiểu gì mà chả ra .
    Vậy cậu thử trình bầy cách làm của cậu đi. Cứ nói thế mọi người không rõ đâu.

    Trích dẫn Nguyên bản được gửi bởi pete_87 Xem bài viết
    Thực ra bài này giải thế này là tối ưu nè ( theo suy nghĩ của pete ) ^^!
    Với điều kiện phải biết chắc chắn viên bi đó nặng hơn hoặc nhẹ hơn.
    Ví dụ nếu nó nhẹ hơn, nặng hơn tương tự, thì đáp án sẽ là :

    -- Tối thiểu là 2 lần cân ra luôn
    -- Không quá 3 lần cân là ra.

    Xác định : lấy 12 viên bi chia làm 3 phần , mỗi phần 4 bi ( A , B , C )
    lấy 2 phần A và B ra cân :
    + Nếu A = B --> thằng cần tìm trong C
    + Nếu A < B --> thằng cần tìm trong A
    + Nếu A > B --> thằng cân tìm trong B
    Giả sử thằng cần tìm trong C , ta xét phần C có 4 bi ( C1,C2,C3,C4 )
    Lấy 2 viên bi trong số 4 bi ra cân ^^
    Giả sử lấy C1,C2
    + Nếu C1 < C2 hoặc C1 > C2 thì thằng cần tìm sẽ là C1 hoặc C2 ->> đúng 2 lần cân. XONG
    + Nếu C1 = C2 thì thằng cần tìm sẽ là C3 hoặc C4, đem cân ra là có kết quả.
    ---> Đúng 3 lần cân ^^. XONG

    Đó là xử lý nếu biết chính xác viên bi đó nặng hay nhẹ.

    Còn nếu không biết chính xác thì :-?...Lúc khác nghĩ chứ đau đầu lắm
    Vấn đề là ở chỗ không biết rõ nó nặng hơn hay nhẹ hơn. Chứ nếu biết chắc thì không nói làm gì. Đúng là min là 2 lần cân và max là 5 lần cân theo suy nghĩ của tớ.
    Thế này nhá. Có 12 viên chia ra cân thế này:
    - Cân các viên 1 2 3 4 5 với 6 7 8 9 10
    + nếu bằng nhau đem 11 12 ra cân là Ok (Min 2 lần)
    + nếu một trong 2 bên nặng hơn hoặc nhẹ hơn thì đem ra cân thế này
    VD: 1 2 3 4 cân với 5 6 7 8
    + nếu bằng nhau đem 9 10 ra cân là OK (3 lân cân)
    + nếu không bằng nhau thì lại cân thế này tiếp
    *Đem 1 2 3 với 5 6 7 ra cần
    - nếu lại bằng nhau thì lại đem 8 9 ra cần (4 lân cân)
    - nếu cân lại lệch thì lại cân thế này
    + Đem 1 2 với 3 5 ra cân
    + nếu bằng nhau thì lại đem 6 7 ra cân ( 5 Lần)
    + nếu không bằng nhau thì đem 1 2 hoặc 3 5 ra cân cứ thế phải đến 6 lần chứ chả chơi.
    Cái chính là thuật toán để viết ra chương trình ý.

  8. #8
    Ngày gia nhập
    09 2007
    Bài viết
    17

    Thế thì thế này nhé HL.

    12 chia làm 3 phần A,B,C mỗi phần 4 viên.
    Lần Cân 1:

    Cân A,B,C Trong đó sẽ có 1 phần có trọng lượng khác so với 2 phần còn lại.
    Giả sử: A=B != C .
    Nếu C> A thì hòn bi đó có khối lượng nặng hơn.
    Nếu C< A thì hòn bi đó có khối lượng nhỏ hơn.

    Lần Cân 2:

    Chia C ra làm 2 phần. E & F:
    Cân E ,F . Phần nào có khối lượng khác với A/2 thì phần đó chứa viên bi cần tìm.

    Hoặc :

    Do ta biết được khối lượng của viên bi là nặng hay nhẹ hơn các viên bi còn lại nên phần nào nặng hay nhẹ hơn tương ứng sẽ là phần chứ viên bi cần tìm.
    Giả sử ở đây ta tìm được E là phần cần tìm.

    Lần Chia Thứ 3 :

    Chia E ra làm 2 mỗi phần 1 viên và cân. Tương tự như lần chia thứ 2 ta sẽ biết được viên cần tìm và trọng lượng của nó.

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

    @naolmikevol : Logic toán học sai ngay từ đầu , lần cân 1.

    Cân A,B,C Trong đó sẽ có 1 phần có trọng lượng khác so với 2 phần còn lại.
    Giả sử: A=B != C .
    Nếu C> A thì hòn bi đó có khối lượng nặng hơn.
    Nếu C< A thì hòn bi đó có khối lượng nhỏ hơn.
    Khi chưa biết thì không được giả sử. Phải CÂN xác định rồi không mất tính tổng quát mới được giả sử.

    Phân tích lỗi sai nè :

    A, B, C : lúc đầu chưa cân chưa biết thế nào, không biết bi nặng hay nhẹ.
    Ta đem vào cân lấy ra A và B :
    + Nếu A = B -> bi cần tìm sẽ là C
    + Nếu A != B -> Chưa biết là viên bi đó nằm trong A hay B và nặng hơn hay nhẹ hơn. Để xác định nặng hơn hay nhẹ hơn, phải lấy A hoặc B đem cân thử với C. Giả sử ở trên là A < B và lấy ra A so sánh với C :
    __Nếu A = C : --> viên bi đó nặng hơn và trong B.
    __Nếu A < C : --> viên bi đó nhẹ hơn và trong A.
    __Không có trường hợp A > C : vì trong 3 phần có 2 phần chắc chắn bằng nhau và đã so sánh trước đó.

    ---> Không mất tính tổng quát : đáp án của naolmikevol sai ^^!
    Đã được chỉnh sửa lần cuối bởi Xcross87 : 29-09-2007 lúc 11:16 AM.
    None!

  10. #10
    Ngày gia nhập
    06 2007
    Nơi ở
    SN06 - 70 Trương Định - HBT - HN
    Bài viết
    36

    hixx,,, chữ nếu kia của bác thì nói làm gì????
    ai mà biết được nó nặng hơn hay nhẹ hơn,,,,
    cứ giả sử như bác thì tui giả sử viễn cảnh giết người,, tui giết ai đó rùi chốc lát người ta sống lại à????

    Nghĩ cách khác đi bạn nhá.....


    =====================================
    XWAYSTYLE ---------> Brings joy to milions.....
    Intel(R) Pentium 4(R) 2.8GHz Main IntelD845Pemy (Socket 478) RAM 1024Mb VGAFX5200 128Mb 128Bit HDD Maxtor 160Gb PATA Sound Blaster live 5.1 Gamer

    Windows Vista Ultimate Sp1 (activated)
    Rating : 2.5 Mark
    Theme: Windows Aero (very nice!)

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

  1. làm sao để select sinh viên theo mã sinh viên trong 1 chuỗi mã sinh viên
    Gửi bởi thuan trong diễn đàn Thắc mắc Microsoft SQL Server & Microsoft Access
    Trả lời: 11
    Bài viết cuối: 14-12-2012, 08:37 PM
  2. Hà Nội Công ty NEO, 1 thành viên VNPT tuyển Lập trình viên. sinh viên làm thêm
    Gửi bởi Cong ty NEO trong diễn đàn Tuyển dụng - Việc làm CNTT
    Trả lời: 0
    Bài viết cuối: 22-05-2012, 04:11 PM
  3. Bài tập C++ Sắp xếp và phân loại sinh viên. Nhưng sao mình chưa làm được phân loại sinh viên, mong các pro giúp mình.
    Gửi bởi lecongtinh trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 14-09-2011, 04:37 PM
  4. ADO.NET Lấy điểm trên textbox để xếp loại cho sinh viên
    Gửi bởi xuykaa trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 18-07-2011, 08:50 AM
  5. Bài tập C Bài toán xếp loại nhiều sinh viên - help !!
    Gửi bởi herald305 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-2010, 07:04 PM

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