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

Đề tài: Bài toán 13 chiếc nhẫn vàng

  1. #1
    Ngày gia nhập
    07 2016
    Bài viết
    421

    Mặc định Bài toán 13 chiếc nhẫn vàng

    Có 13 cái nhẫn vàng - màu sắc, kích thước, hình dạng giống nhau - gồm 12 cái thật và 1 cái mẫu (khối lượng khác, nhưng không biết nặng hay nhẹ hơn)

    Dùng cân (loại đòn bẩy - cân tiểu ly) cân 3 lần để tìm cái nhẫn mẫu.

    Click vào hình ảnh để lấy hình ảnh lớn

Tên:		CongLy.jpg
Lần xem:	1
Size:		7.1 KB
ID:		48183

    Viết thành chương trình GUI càng tốt
    Bắc thang lên hỏi ông giời
    Tiền vàng giao đoảng có đòi được không ?

  2. #2
    Ngày gia nhập
    07 2016
    Bài viết
    421

    lần 1: 6 - 6(1 cái dư)
    - nếu bằng nhau thì cái còn lại là cái giả
    OK - chỉ 1 lần đã xong

    - nếu khác nhau thì 6 cái lớn hơn + 1 cái(thật, được đánh dấu) cân tiếp
    Lấy bên nào Trái hay Phải ? Cân tiếp có tính thêm 1 lần ?

    - Lấy 6 cái thật còn lại chia ra để biết khối lượng của mỗi chiếc
    Bắc thang lên hỏi ông giời
    Tiền vàng giao đoảng có đòi được không ?

  3. #3
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    https://www.av8n.com/physics/twelve-coins.htm

  4. #4
    Ngày gia nhập
    07 2016
    Bài viết
    421

    12 khác 13


    The Twelve-Coins Puzzle
    Bắc thang lên hỏi ông giời
    Tiền vàng giao đoảng có đòi được không ?

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

    13 thì thêm trường hợp BBB vô nữa thôi.

    người ta dọn sẵn hết rồi, mình chỉ việc code theo thôi
    http://ideone.com/JPUVKy

    C++ Code:
    1. #include <iostream>
    2. #include <set>
    3. #include <vector>
    4. #include <algorithm>
    5. #include <cassert>
    6.  
    7. class ThirteenCoins
    8. {
    9. public:
    10.     ThirteenCoins(int coinWeight, int fakeCoinWeight, int fakeCoinId)
    11.     : coinWeight(coinWeight), coinWeightDiff(fakeCoinWeight-coinWeight),
    12.       fakeCoinId(fakeCoinId) {}
    13.     char compare(const std::set<int>& lhs, const std::set<int>& rhs)const
    14.     {
    15.         std::vector<int> commonCoins;
    16.         std::set_intersection(begin(lhs), end(lhs), begin(rhs), end(rhs),
    17.                               std::back_inserter(commonCoins));
    18.         if (!commonCoins.empty()) throw "Some coins appear on both sides";
    19.        
    20.         int lhsWeight = lhs.size() * coinWeight;
    21.         int rhsWeight = rhs.size() * coinWeight;
    22.         if (lhs.find(fakeCoinId) != end(lhs)) lhsWeight += coinWeightDiff;
    23.         if (rhs.find(fakeCoinId) != end(rhs)) rhsWeight += coinWeightDiff;
    24.         if (lhsWeight == rhsWeight) return 'B';
    25.         return lhsWeight < rhsWeight ? 'R' : 'L';
    26.     }
    27. private:
    28.     int coinWeight;
    29.     int coinWeightDiff;
    30.     int fakeCoinId;
    31. };
    32.  
    33. int fakeCoinId(const ThirteenCoins& p)
    34. {
    35.     static std::vector<std::string> codeWords = {
    36.         "RRR", "LLL", "BBR", "BBL", "BRL", "BLR", "BRB", "BLB", "BRR",
    37.         "BLL", "RLL", "LRR", "RLB", "LRB", "LRL", "RLR", "RBL", "LBR",
    38.         "LBB", "RBB", "RBR", "LBL", "LLR", "RRL", "LLB", "RRB", "BBB"
    39.     };
    40.     std::string comp;
    41.     comp += p.compare({ 7, 9,11,12}, { 5, 6, 8,10});
    42.     comp += p.compare({ 5, 6,11,12}, { 2, 3, 4, 7});
    43.     comp += p.compare({ 2, 5, 7, 8}, { 1, 4,10,11});
    44.     return std::distance(begin(codeWords),
    45.                          std::find(begin(codeWords), end(codeWords), comp)) / 2;
    46. }
    47.  
    48. int main()
    49. {
    50.     for (int i = 1; i <= 13; ++i)
    51.     {
    52.         assert(fakeCoinId(ThirteenCoins(10, 11, i)) == i);
    53.         assert(fakeCoinId(ThirteenCoins(10,  9, i)) == i);
    54.     }
    55. }

    3 lần cân:
    Code:
        comp += p.compare({ 7, 9,11,12}, { 5, 6, 8,10});
        comp += p.compare({ 5, 6,11,12}, { 2, 3, 4, 7});
        comp += p.compare({ 2, 5, 7, 8}, { 1, 4,10,11});
    rồi biện luận kết quả comp thu được là 1 trong 27 trường hợp thôi. Ở đây ta sắp xếp sẵn trường hợp nào tương ứng với index của fake coin luôn, vì nặng nhẹ ko biết nên chia 2 nữa, ví dụ comp có index 2k hay 2k+1 trong codeWords thì tương ứng với coin thứ k.

    đáng lẽ biết fake coin là nặng hay nhẹ luôn, nhưng do có 13 thay vì 12 coins nên có thêm trường hợp nó ra BBB nên ko biết nặng nhẹ của xu giả

  6. #6
    Ngày gia nhập
    01 2013
    Nơi ở
    Học viện Kỹ thuật Quân Sự
    Bài viết
    247

    Mặc định Bài toán 13 chiếc nhẫn vàng

    Trích dẫn Nguyên bản được gửi bởi hvcuongit Xem bài viết
    lần 1: 6 - 6(1 cái dư)
    - nếu bằng nhau thì cái còn lại là cái giả
    - nếu khác nhau thì 6 cái lớn hơn + 1 cái(thật, được đánh dấu) cân tiếp
    - Lấy 6 cái thật còn lại chia ra để biết khối lượng của mỗi chiếc
    lần 2: 3 - 3(1 cái dư, không phải là cái ở lần 1)
    - nếu bằng nhau thì cái còn lại là giả
    - nếu khác nhau thì lấy 3 cái lớn hơn + 1 cái(thật, được đánh dấu) nữa cân tiếp
    lần 3: 1-1(Còn lại 4 cái, chỉ cần 2 cái vì 2 cái đã biết được là thật do 2 lần cần phía trên)
    (Lấy 1 cái trong 2 cái chưa phân biệt ,cân với một trong 2 cái thật)
    - Nếu bằng nhau thì cái chưa phân biệt kia là giả, khác nhau thì cai chưa phân biệt đang cân là thật
    Bạn thử đếm lại xem mấy lần rồi, hình như 4 lần rồi thì phải
    Nếu cần giúp đỡ, hỗ trợ:
    Bài Tập. Đồ Án. Tools. Phần mềm. Liên hệ:
    Facebook: http://www.facebook.com/thuecodedoan
    Website: https://thuecodedoan.wordpress.com
    Email: thuecodedoan@gmail.com
    Sđt: 094.76.76.854

  7. #7
    Ngày gia nhập
    07 2016
    Bài viết
    421

    IdeOne thật là khó tánh, lúc có - lúc không output
    http://ideone.com/JPUVKy

    13 đương nhiên khác 12

    Tổ hợp, chỉnh hợp, tập hợp chúng đều thuộc toán rời rạc. Suy biến trong tập lớn về tập nhỏ, nó là định lý trong tập cha - chứng minh trong tập con không dễ hơn.
    Bắc thang lên hỏi ông giời
    Tiền vàng giao đoảng có đòi được không ?

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

    bạn có hiểu mình đang làm gì ko mà đòi có output @_@

    ko có in ra gì tức là đúng hết 13x2 trường hợp đó.

    có cách cân khác dễ nhớ hơn :p
    4 5 6 7 và 8 9 10 11
    6 7 8 9 và 1 2 11 12
    2 4 6 8 và 1 3 5 7

    BLL/BRR 1
    BLR/BRL 2
    BBL/BBR 3
    RBR/LBL 4
    RBL/LBR 5
    RRR/LLL 6
    RRL/LLR 7
    LRR/RLL 8
    LRB/RLB 9
    LBB/RBB 10
    LLB/RRB 11
    BLB/BRB 12
    BBB 13

    ví dụ 3 lần cân đều bằng nhau thì xu giả là xu thứ 13. 3 lần cân đều là trái trái trái hoặc phải phải phải thì là xu thứ 6. Nếu là trái trái bằng hoặc phải phải bằng thì là xu thứ 11, v.v...
    Đã được chỉnh sửa lần cuối bởi INTP : 05-07-2016 lúc 12:23 PM.

  9. #9
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Trích dẫn Nguyên bản được gửi bởi INTP Xem bài viết
    bạn có hiểu mình đang làm gì ko mà đòi có output @_@

    ko có in ra gì tức là đúng hết 13 trường hợp đó.
    Vậy là code này pass được test

    Dòng 7 - 31: đặc tả bài toán
    Dòng 33 - 46: parallel algorithm
    Dòng 48 - 55: test cases.

    Dòng 44 hơi khó hiểu nhưng thực sự nó chỉ là tìm kiếm tuần tự thôi. Phần cấu hình 27 words x 3 chữ mới khó.
    Đã được chỉnh sửa lần cuối bởi prog10 : 05-07-2016 lúc 01:06 PM.

  10. #10
    Ngày gia nhập
    07 2016
    Bài viết
    421

    bác @INTP không nên hiểu lầm, tôi hỏi bác vài lần về IdeOne về output mà

    Bài toán là tập hợp thì

    4 5 6 7 và 8 9 10 11
    6 7 8 9 và 1 2 11 12
    2 4 6 8 và 1 3 5 7

    không khác nhau gì

    Tần suất phân bố là như nhau
    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

    Cần xác định nó là phần tử nào sau 3 lần nhận kết quả so sánh
    {A, B, C, D, E, F, G, H, I, J, K, L, M}
    Bắc thang lên hỏi ông giời
    Tiền vàng giao đoảng có đòi được không ?

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