Anda bisa mencapai 90% perjalanan ke sana dengan menggunakan prinsip-prinsip berikut:
Jika jumlah pembohong dalam suatu himpunan sama dengan nol, bagilah himpunan tersebut menjadi himpunan berukuran 1, yang masing-masing mempunyai jumlah pembohong sama dengan nol. Jadi 1 3 0 menjadi 1 1 0 dan 2 2 0 dan 3 3 0.
Jika banyaknya pembohong dalam suatu himpunan sama dengan besarnya himpunan tersebut, bagilah himpunan tersebut menjadi himpunan berukuran 1 yang masing-masing mempunyai jumlah pembohong sama dengan satu. Jadi 2 5 4 menjadi 2 2 1 dan 3 3 1 dan 4 4 1 dan 5 5 1.
Untuk dua himpunan A dan B yang kita punya, jika A adalah himpunan bagian dari B, hilangkan semua elemen A dari B, dan kurangi jumlah pembohong di A dari jumlah pembohong di B.
Kami akan menggunakan prinsip-prinsip ini untuk menyelesaikan dua contoh soal yang lebih panjang. Mulailah dengan mengambil masukan yang diberikan, dan mengubahnya menjadi kumpulan indeks.
3 4 5 6 7 8 [4]
1 2 3 4 5 6 7 8 9 [6]
1 2 3 4 5 6 7 8 9 10 11 12 13 [9]
5 6 7 8 9 10 11 [5]
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 [12]
8 9 10 11 12 13 [5]
4 5 6 7 8 [4]
7 8 9 [2]
10 11 12 13 [3]
7 8 9 10 11 12 13 14 15 16 [7]
14 15 16 17 18 19 [4]
4 5 6 7 8 adalah bagian dari 3 4 5 6 7 8, jadi kurangi satu dari yang lain.
3 [1]
1 2 3 4 5 6 7 8 9 [6]
1 2 3 4 5 6 7 8 9 10 11 12 13 [9]
5 6 7 8 9 10 11 [5]
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 [12]
8 9 10 11 12 13 [5]
4 5 6 7 8 [4]
7 8 9 [2]
10 11 12 13 [3]
7 8 9 10 11 12 13 14 15 16 [7]
14 15 16 17 18 19 [4]
7 8 9, 10 11 12 13, dan 14 15 16 17 18 19 semuanya merupakan himpunan bagian dari 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19, jadi kurangi keduanya.
3 [1]
1 2 3 4 5 6 7 8 9 [6]
1 2 3 4 5 6 7 8 9 10 11 12 13 [9]
5 6 7 8 9 10 11 [5]
4 5 6 [3]
8 9 10 11 12 13 [5]
4 5 6 7 8 [4]
7 8 9 [2]
10 11 12 13 [3]
7 8 9 10 11 12 13 14 15 16 [7]
14 15 16 17 18 19 [4]
4 5 6 memiliki tiga pembohong, jadi bagilah mereka menjadi beberapa set.
3 [1]
4 [1]
5 [1]
6 [1]
1 2 3 4 5 6 7 8 9 [6]
1 2 3 4 5 6 7 8 9 10 11 12 13 [9]
5 6 7 8 9 10 11 [5]
8 9 10 11 12 13 [5]
4 5 6 7 8 [4]
7 8 9 [2]
10 11 12 13 [3]
7 8 9 10 11 12 13 14 15 16 [7]
14 15 16 17 18 19 [4]
kurangi 3,4,5 dan 6 dari semua himpunan yang memuatnya.
3 [1]
4 [1]
5 [1]
6 [1]
1 2 7 8 9 [2]
1 2 7 8 9 10 11 12 13 [5]
7 8 9 10 11 [3]
8 9 10 11 12 13 [5]
7 8 [1]
7 8 9 [2]
10 11 12 13 [3]
7 8 9 10 11 12 13 14 15 16 [7]
14 15 16 17 18 19 [4]
kurangi 7 8 dari 7 8 9
3 [1]
4 [1]
5 [1]
6 [1]
9 [1]
1 2 7 8 9 [2]
1 2 7 8 9 10 11 12 13 [5]
7 8 9 10 11 [3]
8 9 10 11 12 13 [5]
7 8 [1]
10 11 12 13 [3]
7 8 9 10 11 12 13 14 15 16 [7]
14 15 16 17 18 19 [4]
kurangi 9 dari semua himpunan yang memuatnya.
3 [1]
4 [1]
5 [1]
6 [1]
9 [1]
1 2 7 8 [1]
1 2 7 8 10 11 12 13 [4]
7 8 10 11 [2]
8 10 11 12 13 [4]
7 8 [1]
10 11 12 13 [3]
7 8 10 11 12 13 14 15 16 [6]
14 15 16 17 18 19 [4]
kurangi 7 8 dari himpunan mana pun yang berisi keduanya.
3 [1]
4 [1]
5 [1]
6 [1]
9 [1]
1 2 [0]
1 2 10 11 12 13 [3]
10 11 [1]
8 10 11 12 13 [4]
7 8 [1]
10 11 12 13 [3]
10 11 12 13 14 15 16 [5]
14 15 16 17 18 19 [4]
1 2 memiliki 0 pembohong, jadi bagilah menjadi beberapa set.
1 [0]
2 [0]
3 [1]
4 [1]
5 [1]
6 [1]
9 [1]
1 2 10 11 12 13 [3]
10 11 [1]
8 10 11 12 13 [4]
7 8 [1]
10 11 12 13 [3]
10 11 12 13 14 15 16 [5]
14 15 16 17 18 19 [4]
kurangi 1 dan 2 dari semua himpunan lain yang memuatnya.
1 [0]
2 [0]
3 [1]
4 [1]
5 [1]
6 [1]
9 [1]
10 11 [1]
8 10 11 12 13 [4]
7 8 [1]
10 11 12 13 [3]
10 11 12 13 14 15 16 [5]
14 15 16 17 18 19 [4]
kurangi 10 11 dari himpunan mana pun yang berisi keduanya.
1 [0]
2 [0]
3 [1]
4 [1]
5 [1]
6 [1]
9 [1]
10 11 [1]
8 12 13 [3]
7 8 [1]
12 13 [2]
12 13 14 15 16 [4]
14 15 16 17 18 19 [4]
8 12 13 memiliki tiga pembohong, jadi bagilah mereka menjadi himpunan tersendiri, dan kurangi dari himpunan lain yang memuatnya.
1 [0]
2 [0]
3 [1]
4 [1]
5 [1]
6 [1]
7 [0]
8 [1]
9 [1]
10 11 [1]
12 [1]
13 [1]
14 15 16 [2]
14 15 16 17 18 19 [4]
kurangi 14 15 16 dari 14 15 16 17 18 19.
1 [0]
2 [0]
3 [1]
4 [1]
5 [1]
6 [1]
7 [0]
8 [1]
9 [1]
10 11 [1]
12 [1]
13 [1]
14 15 16 [2]
17 18 19 [2]
Kumpulan hasil kami semuanya terputus-putus satu sama lain. Jika kita menyatukannya, seperti ini:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 [13]
kita lihat banyaknya pembohong dari 1 sampai 19 adalah 13.
Teknik ini tidak sepenuhnya menyelesaikan masalah di semua kasus. Misalnya, dalam dua contoh masukan yang lebih pendek, teknik ini benar-benar tidak menghasilkan apa-apa. Namun, untuk masalah yang lebih besar, hal ini akan menguraikan set Anda menjadi bentuk yang lebih modular, yang menurut saya akan membuat brute force lebih mudah/lebih cepat. Misalnya, dalam sampel yang lebih besar, kami telah menguraikan ruang masalah menjadi dua kemungkinan:
1. there are 13 liars among soldiers 1-19, and Soldier 20 is not a liar.
2. there are 13 liars among soldiers 1-19, Soldier 20 is a liar.
Kita dapat dengan mudah mengevaluasi kedua kasus ini untuk menentukan bahwa jumlah pembohong minimum adalah 13, dan maksimum adalah 14. Ini jauh lebih cepat daripada mencoba semua 2^20 kombinasi pembohong dan tidak pembohong.
person
Kevin
schedule
07.06.2012
