Chủ đề này có 12 trả lời

[namdung]

Các bạn thân mến,

Trong nghiên cứu khoa học và thực tế cuộc sống, thuật tóan đóng một vai trò quan trọng. Nó giúp chúng ta một quy trình thống nhất giải quyết những bài tóan vốn thường được lặp đi lặp lại.

Trong chuỗi bài của tôi, tôi sẽ không đi sâu về vấn đề lý thuyết cũng như triết học, chỉ đưa ra một số bài tập vui, giúp các bạn vừa thư giãn, vừa học được những tư duy thuật tóan một cách thật tự nhiên thông qua lời giải, ý kiến, nhận xét của tất cả chúng ta. Rất mong sự hưởng ứng của các bạn.

Bài số 1 (Trích từ tạp chí Komal, tháng 9/2002)

Alice chọn ra 1 trong các số 1, 2, ..., 16. Bob có quyền hỏi 7 câu hỏi dạng Có/Không để tìm ra số Alice nghĩ. Alice được phép trả lời sai nhiều nhất 1 lần, hãy giúp Bob tìm được số đó trong tất cả các trường hợp.

[pascal]

Bài này cũ rồi , cứ hỏi xem số đó có lớn hơn số ở giữa của tập các phương án không là ok rồi ( Chắc chắn số câu hỏi sẽ ko vượt wá quy định ). Câu này còn có thể tổng quát hoá lên n số .
Bạn còn thuật toán nào lạ ko???

[emon]

Cần gì đến 7 câu ha, 4 câu đủ xài rồi.

[Trytolive]

Cần gì đến 7 câu ha, 4 câu đủ xài rồi.

Nên nhớ đề bài này còn một chỗ lắc léo là Alice được trả lời sai ít nhất 1 lần. 4 câu không đủ đâu

to namdung: Hình như là Alice được trả lời sai nhiều nhất là 1 lần chứ. Nếu cô ta toàn trả lời sai không thì...

[namdung]

Đúng rồi, có khi các bạn đọc đề chưa kỹ. Chú ý là Alice có quyền trả lời sai nhiều nhất 1 lần! Do đó 4 câu chắc chắn là không đủ.

[pascal]

sao lại kết thúc ở số 1 nhỉ ??? vậy 2 , 3, 4, .... đâu rồi ? namdung post tiếp mấy cái thuật tóan hay lên đi bạn .

[Trytolive]

sao lại kết thúc ở số 1 nhỉ ??? vậy 2 , 3, 4, .... đâu rồi ? namdung post tiếp mấy cái thuật tóan hay lên đi bạn .

Bình tĩnh làm :cafe đã.

Bài toán namdung đưa ra rất là hay. Hãy để các bạn cùng suy ngẫm. Có nhiều phương án trả lời nhưng chung quy về vẫn là phân hoạch đoạn [1,16]. Các phương án khác nhau sẽ do giả thuyết Alice có thể trả lời sai nhiều nhất 1 câu.

Bạn có đọc truyện Sơ lốc hôm không? Nếu nói ra cách giải quyết thì ai cũng cảm thấy dễ dàng và nhàm chán.

[truonglequan]

xin lỗi nha cho mình hỏi các bạn có thể đưa ra cho mình vài trường hợp ví dụ được không.Mình vẫn chưa hiểu lắm về thuật toán này lắm
mình thử đặt ra cách giải này nha:
câu hỏi đầu tiên là số đó là số có 2 chữ số
>alice trả lời có(đúng) thì xác định dược 10,11,12,13,14,15,16
*sau đó sẽ hỏi là số chẵn
alice trả lời có(đúng)thì xác định được 10,12,14,16(chuyện còn lại qua' dễ)
alice trả lời không(đúng)thì xác định được 11,13,15(còn lại thì càng dễ)
còn trường hơp sai thì ko vấn đè gi`
>alice trả lời có(sai)đồng nghĩa với không(đúng)thì xác định được 1,2,3,4,5,6,7,8,9
*sau đó là câu hỏi số chẵn (hoặc chia hết cho 2 ,3đèu được)
alice trả lời có(đúng)thì co2,4,6,8(còn lại ok)
alice trả lời có (sai) đồng nghĩa vốikhông(đúng)thì 1,3,5,7,9(ok chưa)
cách nay` có phải là nhanh hơn cách phân hoạch đoạn (1,16) không
có gì sai sót xin các bạn chỉ dạy

[Trytolive]

xin lỗi nha cho mình hỏi các bạn có thể đưa ra cho mình vài trường hợp ví dụ được không.Mình vẫn chưa hiểu lắm về thuật toán này lắm
mình thử đặt ra cách giải này nha:
câu hỏi đầu tiên là số đó là số có 2 chữ số
>alice trả lời có(đúng) thì xác định dược 10,11,12,13,14,15,16
*sau đó sẽ hỏi là số chẵn
alice trả lời có(đúng)thì xác định được 10,12,14,16(chuyện còn lại qua' dễ)
alice trả lời không(đúng)thì xác định được 11,13,15(còn lại thì càng dễ)
còn trường hơp sai thì ko vấn đè gi`
>alice trả lời có(sai)đồng nghĩa với không(đúng)thì xác định được 1,2,3,4,5,6,7,8,9
*sau đó là câu hỏi số chẵn (hoặc chia hết cho 2 ,3đèu được)
alice trả lời có(đúng)thì co2,4,6,8(còn lại ok)
alice trả lời có (sai) đồng nghĩa vốikhông(đúng)thì 1,3,5,7,9(ok chưa)
cách nay` có phải là nhanh hơn cách phân hoạch đoạn (1,16) không
có gì sai sót xin các bạn chỉ dạy

1. Cách phân hoạch của bạn chưa hay lắm. (Phân hoạch nhị phân là tốt nhất)
2. Chẳng hạn trong cách của hỏi của bạn, nếu Alice trả lời sai ở câu hỏi số 1( tức là số Alice chọn là số có 1 chữ số mà Alice trả lời là có 2 chữ số - Alice được quyền) thì sao???

[Trytolive]

Gọi X là số Alice chọn
Cho hình vuông được chia làm 4 phần và đặt tên mỗi phần tư là 1,2,3,4 như sau:

1 2

3 4

Đặt 16 số vào ô vuông, mối phần tư có 4 số.
Câu hỏi 1:Hỏi X có ở trong 1,2 không? Câu trả lời có thì bôi đen 1,2. Không thì bôi đen 3,4
Câu hỏi 2:Hỏi X có ở trong 2,4 không? Câu trả lời có thì bôi đen 2,4. Không thì bôi đen 1,3
Không mất tính tổng quát ta có thể giả sử 2,3,4 bị bôi đen. Có 2 trường hợp xảy ra:
1. Một trong hai câu 1,2 có câu Alice trả lời sai thì X {2,4} hoặc X {3,4}
2. Cả hai câu trên đều được trả lời đúng thì X {4}
Câu hỏi 3:Hỏi X có ở trong 4 không?
Trường hợp 1: Câu trả lời là có thì cả hai câu 1,2 không sai (vì sao????) =>X {4} và Alice chưa trả lời câu nào sai. Tiếp tuc lặp lại bằng cách đặt vào mỗi phần tư 1 số và cần 4 câu hỏi nữa(chắc không cần trình bày )
Trường hợp 2: Câu trả lời là không thì ít nhất trong hai câu 1,2 có câu trả lời sai và câu trả lời 3 đúng (vì sao???) => X {2,3} và Alice không được quyền trả lời sai nữa. {2,3} có 8 số và Alice không trả lời sai thì chỉ cần 3 câu hỏi nữa là đủ.

Không biết thuật toán trên có sai sót gì không?
Mong tiên sinh namdung và các bạn chỉ giáo thêm.

[Trytolive]

namdung post lời giải gốc trong tạp chí Kornal để mọi người tham khảo. Cám ơn.

[nemo]

Những bài toán đoán số kiểu này vẫn thường được giải bởi một thuật toán gọi là "nguyên lý chia đôi" cách rõ ràng nhất là chuyển số cần tìm về hệ cơ số 2.

Trong bài toán đoán tuổi hoặc số điện thoại như sau: Giả sử bạn cần biết số điện thoại của tôi bạn sẽ hỏi tôi một số câu hỏi, mỗi câu hỏi tôi sẽ chỉ trả lời đúng hoặc sai, vậy bạn sẽ hỏi ít nhất bao nhiêu câu để chắc chắn tìm ra được số điện thoại của tôi !? Và nếu trong các câu trả lời tôi có thể trả lời sai một câu thì số câu hỏi ít nhất lúc này sẽ là bao nhiêu !? Biết số điện thoại của tôi có n chữ số.

[namdung]

namdung post lời giải gốc trong tạp chí Kornal để mọi người tham khảo. Cám ơn.

Chúng ta mã hóa 16 số nguyên này sang hệ cơ số 2. Mỗi số được mã hóa thành một dãy số có 4 chữ số gồm các số 0 và 1. Giả sử số mà Alỉc chọn được mã hóa thành http://dientuvietnam...cgi?x_1 x_2 x_3 lẻ thì http://dientuvietnam...cgi?V_{1,2,3}=1)

Nếu http://dientuvietnam...2 V_3 V_{1,2,3} là số chẵn thì các câu trả lời này là đúng và chúng ta biết được http://dientuvietnam...mimetex.cgi?x_4, do có thể cho phép 1 câu trả lời sai, nên giá trị http://dientuvietnam...mimetex.cgi?x_4 mà ta thu được giống nhau từ hai câu trả lời khác nhau chính là giá trị http://dientuvietnam...mimetex.cgi?x_4 cần tìm.

Thực hiện tương tự nếu một trong các giá trị sau là số chẵn:
http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_1+V_2+V_4+V_{1,2,4}
http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_1+V_3+V_4+V_{1,3,4}.

Nếu
http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_1+V_3+V_4+V_{1,3,4}
đều là các số lẻ. Khi đó phải có một câu trả lời sai trong mỗi nhóm câu trả lời trên. Do chỉ cho phép một câu trả lời sai và chỉ có http://dientuvietnam...mimetex.cgi?V_1 là cùng thuộc cả 3 nhóm câu trả lời nên: http://dientuvietnam.net/cgi-bin/mimetex.cgi?V_1 là câu trả lời sai và tất cả các câu trả lời còn lại là đúng. Từ đó ta xác định được các giá trị http://dientuvietnam.net/cgi-bin/mimetex.cgi?k là một số nguyên dương, http://dientuvietnam.net/cgi-bin/mimetex.cgi?h=2^k-1 và http://dientuvietnam.net/cgi-bin/mimetex.cgi?m=h-k. "Mã Hamming http://dientuvietnam.net/cgi-bin/mimetex.cgi?\(m,h\) là tập các dãy http://dientuvietnam.net/cgi-bin/mimetex.cgi?h phần tử gồm 0 và 1, sô các phần tử của tập này là http://dientuvietnam.net/cgi-bin/mimetex.cgi?2^m, và với mọi dãy đọ dài h gồm 0 và 1 tồn tại duy nhất một dãy trong mã sao cho 2 dãy khác nhau trong nhiều nhất một phần tử.

Ví dụ "mã Hamming (4,7)" chứa các dãy sau:
0000000 0100101 1000011 1100110
0001111 0101010 1001100 1101001
0010110 0110011 1010101 1110000
0011001 0111100 1011010 1111111

Bài toán tương đương với việc xây dựng một tương ứn tới Mã Hamming (4,7)