猜数字游戏, 为保证所有条件下能猜出，求最少猜多少次

〇〇 · 发表于 2009-10-4 19:19

puzzleup 9.30

Number Game

You are playing a game with your friend. Your friend chooses three distinct numbers from the set (1, 2, 3, 4, 5, 6, 7, 8, 9). You will call four distinct numbers from the same set in each turn, and he will tell you how many of them are among the chosen numbers.

In order to guarantee to find these numbers in all cases, how many turns are needed?

Note: Naming these three numbers after your 4-number calls are finished does not count as a turn

【数字游戏】
你和朋友玩一个游戏。朋友从1-9中选3个不同的数字(你来猜)。你每轮猜4个不同数字，你的朋友将告诉你猜中了几个他选择的数字。
为了确定他到底是选择的哪3个数字，你需要多少轮？
注：你最后指出他的三个数字时，不算一轮。

http://bbs.emath.ac.cn/thread-1808-1-1.html
http://www.puzzleup.com/2009/

〇〇 · 发表于 2009-10-5 06:16

最多猜C(3,9)=9!/3!/6!次

newkid · 发表于 2009-10-5 08:46

这是正确答案吗？比想象的要多。有点像那个用天平找出不同小球的题目，只是更复杂。

〇〇 · 发表于 2009-10-5 09:22

正确答案还不知道，2楼只是不同组合的总数
感觉运气好 2次,
1.4中有3
2.换掉1中的1个，仍然4中有3

〇〇 · 发表于 2009-10-5 09:28

运气不好
1.4中有2
2.换掉1中的1个，仍然4中有2,不知道换掉的是不是..
3.用1中没有的数取4...

newkid · 发表于 2009-10-5 09:34

用已知的代替未知的，如果数目发生变化、不发生变化都可以知道被替换的是什么。
以#5为例，
1. 4中有2 则另外5中有1
2. 从另5个取四，则可知道剩下的一个是不是，得到一个已知的。
3. 利用这个已知的去替代，求出其他的。

可能的分支太多了，不知道怎么优化。

zhangweicai74 · 发表于 2009-10-5 10:00

问一下魔术师.

〇〇 · 发表于 2009-10-5 17:30

发表于昨天 22:49 | 只看该作者踩窝窝送礼物问候Ta
本帖最后由 056254628 于 2009-10-4 23:02 编辑

下面是我的最多6轮的方案：             →  { }    大括号里的是答案（即朋友选中的三个数）：
$f_1(1234)$ $f_2(1256)$
----------------------------------------------------------------------------------------------
=0             =0                                                                            →  {789}
----------------------------------------------------------------------------------------------
=1             =3             $f_3(1789)$
                                             =0                                                    →  {256}
                                             =1                                                 →  {156}
----------------------------------------------------------------------------------------------
   =3          =1                $f_3(1567)$
                                             =1                                                 →  {134}
                                             =0                                                 →  {234}
----------------------------------------------------------------------------------------------
=3          =2             $f_3(3567)$
                                             =1                                                    →  {123}
                                             =0                                                    →  {124}
----------------------------------------------------------------------------------------------
=2          =3             $f_3(5789)$
                                          =1                                                    →  {125}
                                          =0                                                    →  {126}
----------------------------------------------------------------------------------------------
   =0       =2                $f_3(7123)$
                                       =1                                                       →  {567}
                                       =0                   $f_4(8123)$
                                                                     =1                         →  {568}
                                                                     =0                         →  {569}
----------------------------------------------------------------------------------------------
=2             =0          $f_3(7125)$
                                       =1                                                       →  {347}
                                       =0                   $f_4(8125)$
                                                                     =1                         →  {348}
                                                                     =0                         →  {349}
----------------------------------------------------------------------------------------------
=0          =1             $f_3(5123)$          $f_4(7123)$
                                          =0                      =0                         →  {689}
                                          =1                      =0                         →  {589}
                                          =1                      =1       $f_5(8123)$
                                                                                       =1          →  {578}
                                                                                    =0          →  {579}

                                          =0                      =1       $f_5(8123)$
                                                                                       =1       →  {678}
                                                                                       =0          →  {679}
----------------------------------------------------------------------------------------------
=1          =0             $f_3(3125)$          $f_4(7125)$
                                          =0                      =0                               →  {489}
                                          =1                      =0                               →  {389}
                                          =1                      =1       $f_5(8125)$
                                                                                       =1             →  {378}
                                                                                       =0             →  {379}

                                          =0                      =1       $f_5(8125)$
                                                                                       =1             →  {478}
                                                                                       =0             →  {479}
----------------------------------------------------------------------------------------------
=1          =1       $f_3(1278)$
                                 =0          $f_4(3127)$       $f_5(5127)$
                                                            =0                   =1                            →  {459}
                                                            =0                =0                               →  {469}
                                                            =1                =1                               →  {359}
                                                            =0                =0                            →  {369}
                                 =1          $f_4(3129)$    $f_5(5129)$       $f_6(7129)$
                                                            =0                =0                =0          →  {468}
                                                            =0                =0                =1          →  {467}
                                                            =0                =1                =0          →  {458}
                                                            =0                =1                =1          →  {457}
                                                            =1                =0                =0          →  {368}
                                                            =1                =0                =1          →  {367}
                                                            =1                =1                =0          →  {358}
                                                            =1                =1                =1          →  {357}
                                 =2             $f_4(1345)$    $f_5(7345)$
                                                         =0                =0                               →  {289}
                                                         =0                =1                               →  {279}
                                                         =1                =0                               →  {189}
                                                         =1                =1                               →  {179}
                                 =3             $f_4(1345)$
                                                         =0                                                    →  {278}
                                                         =1                                                    →  {178}
----------------------------------------------------------------------------------------------
=1          =2    $f_3(1278)$
                                 =0             $f_4(3789)$
                                                         =0                                                 →  {456}
                                                         =1                                                 →  {356}
                              =1             $f_4(1347)$       $f_5(5347)$
                                                         =0                =0                               →  {269}
                                                         =0                =1                               →  {259}
                                                         =1                =0                               →  {169}
                                                         =1                =1                               →  {159}
                              =2                $f_4(1349)$       $f_5(5349)$    $f_6(7349)$
                                                         =0                =0                =0          →  {268}
                                                         =0                =0                =1          →  {267}
                                                         =0                =1                =0          →  {258}
                                                         =0                =1                =1          →  {257}
                                                         =1                =0                =0          →  {168}
                                                         =1                =0                =1          →  {167}
                                                         =1                =1                =0          →  {158}
                                                         =1                =1                =1          →  {157}
----------------------------------------------------------------------------------------------
  =2       =1    $f_3(1278)$
                              =0                   $f_4(5789)$
                                                         =1                                                    → {345}
                                                         =0                                                    → {346}
                              =1                $f_4(1567)$       $f_5(3567)$
                                                         =0                =0                            →  {249}
                                                         =0                =1                            →  {239}
                                                         =1                =0                            →  {149}
                                                         =1                =1                            →  {139}
                              =2                $f_4(1569)$    $f_5(3569)$ $f_6(7569)$
                                                         =0                =0                =0          →  {248}
                                                         =0                =0                =1          →  {247}
                                                         =0                =1                =0          →  {238}
                                                         =0                =1                =1          →  {237}
                                                         =1             =0                =0          →  {148}
                                                         =1                =0                =1          →  {147}
                                                         =1                =1                =0          →  {138}
                                                         =1                =1                =1          →  {137}
----------------------------------------------------------------------------------------------
=2          =2    $f_3(1278)$
                           =1                $f_4(1789)$       $f_5(3789)$       $f_6(5789)$
                                                         =0                =0                =0          →  {246}
                                                         =0                =0                =1          →  {245}
                                                         =0                =1                =0          →  {236}
                                                         =0                =1                =1          →  {235}
                                                         =1                =0                =0          →  {146}
                                                         =1                =0                =1          →  {145}
                                                         =1                =1                =0          →  {136}
                                                         =1                =1                =1          →  {135}
                           =2                                                                                  → {129}
                           =3                $f_4(7345)$
                                                         =1                                                    → {127}
                                                         =0                                                       → {128}

newkid · 发表于 2009-10-6 07:30

我的程序弄出来的5轮结果。有没有错？

SEQ PATH NUM
3 1234:0->1568:1->1569:1 {789}
4 1234:0->1568:1->1569:2->1579:2 {679}
4 1234:0->1568:1->1569:2->1579:3 {579}
4 1234:0->1568:2->1589:1->1678:2 {567}
4 1234:0->1568:2->1589:1->1678:3 {678}
4 1234:0->1568:2->1589:2->1689:1 {578}
4 1234:0->1568:2->1589:2->1689:2 {569}
4 1234:0->1568:2->1589:2->1689:3 {689}
3 1234:0->1568:2->1589:3 {589}
2 1234:0->1568:3 {568}
3 1234:1->1256:0->1359:0 {478}
4 1234:1->1256:0->1359:1->1367:0 {489}
4 1234:1->1256:0->1359:1->1367:1 {479}
4 1234:1->1256:0->1359:1->1367:2 {378}
4 1234:1->1256:0->1359:2->1268:0 {379}
4 1234:1->1256:0->1359:2->1268:1 {389}
5 1234:1->1256:1->1237:0->1238:0->1257:0 {469}
5 1234:1->1256:1->1237:0->1238:0->1257:1 {459}
5 1234:1->1256:1->1237:0->1238:1->1246:1 {458}
5 1234:1->1256:1->1237:0->1238:1->1246:2 {468}
5 1234:1->1256:1->1237:1->1258:0->1235:0 {467}
5 1234:1->1256:1->1237:1->1258:0->1235:1 {369}
5 1234:1->1256:1->1237:1->1258:1->1236:0 {457}
5 1234:1->1256:1->1237:1->1258:1->1236:1 {359}
5 1234:1->1256:1->1237:1->1258:1->1236:2 {368}
5 1234:1->1256:1->1237:1->1258:2->1345:0 {289}
5 1234:1->1256:1->1237:1->1258:2->1345:1 {189}
5 1234:1->1256:1->1237:1->1258:2->1345:2 {358}
5 1234:1->1256:1->1237:2->1248:0->1245:0 {367}
5 1234:1->1256:1->1237:2->1248:0->1245:1 {357}
5 1234:1->1256:1->1237:2->1248:1->1346:0 {279}
5 1234:1->1256:1->1237:2->1248:1->1346:1 {179}
5 1234:1->1256:1->1237:2->1248:2->1347:1 {278}
5 1234:1->1256:1->1237:2->1248:2->1347:2 {178}
5 1234:1->1256:2->1259:1->1267:1->1239:0 {456}
5 1234:1->1256:2->1259:1->1267:1->1239:1 {356}
5 1234:1->1256:2->1259:1->1267:2->1348:1 {268}
5 1234:1->1256:2->1259:1->1267:2->1348:2 {168}
5 1234:1->1256:2->1259:1->1267:3->1349:0 {267}
5 1234:1->1256:2->1259:1->1267:3->1349:1 {167}
4 1234:1->1256:2->1259:2->1357:0 {269}
5 1234:1->1256:2->1259:2->1357:1->1249:1 {258}
5 1234:1->1256:2->1259:2->1357:1->1249:2 {169}
5 1234:1->1256:2->1259:2->1357:2->1247:1 {158}
5 1234:1->1256:2->1259:2->1357:2->1247:2 {257}
4 1234:1->1256:2->1259:2->1357:3 {157}
4 1234:1->1256:2->1259:3->1356:1 {259}
4 1234:1->1256:2->1259:3->1356:2 {159}
3 1234:1->1256:3->1358:1 {256}
3 1234:1->1256:3->1358:2 {156}
3 1234:2->1269:0->1478:1 {345}
4 1234:2->1269:0->1478:2->1489:1 {347}
4 1234:2->1269:0->1478:2->1489:2 {348}
4 1234:2->1269:1->1368:0->1379:0 {245}
4 1234:2->1269:1->1368:0->1379:1 {247}
4 1234:2->1269:1->1368:1->1458:0 {237}
5 1234:2->1269:1->1368:1->1458:1->1278:0 {349}
5 1234:2->1269:1->1368:1->1458:1->1278:1 {235}
5 1234:2->1269:1->1368:1->1458:2->1279:1 {248}
5 1234:2->1269:1->1368:1->1458:2->1279:2 {147}
4 1234:2->1269:1->1368:1->1458:3 {145}
4 1234:2->1269:1->1368:2->1289:0 {346}
5 1234:2->1269:1->1368:2->1289:1->1378:2 {135}
5 1234:2->1269:1->1368:2->1289:1->1378:3 {137}
5 1234:2->1269:1->1368:2->1289:2->1456:0 {238}
5 1234:2->1269:1->1368:2->1289:2->1456:2 {148}
3 1234:2->1269:1->1368:3 {138}
4 1234:2->1269:2->1578:0->1468:0 {239}
5 1234:2->1269:2->1578:0->1468:1->1469:1 {236}
5 1234:2->1269:2->1578:0->1468:1->1469:2 {249}
4 1234:2->1269:2->1578:0->1468:2 {246}
5 1234:2->1269:2->1578:1->1369:2->1389:1 {146}
5 1234:2->1269:2->1578:1->1369:2->1389:2 {149}
5 1234:2->1269:2->1578:1->1369:3->1459:1 {136}
5 1234:2->1269:2->1578:1->1369:3->1459:2 {139}
4 1234:2->1269:2->1578:2->1457:1 {128}
5 1234:2->1269:2->1578:2->1457:2->1467:1 {125}
5 1234:2->1269:2->1578:2->1457:2->1467:2 {127}
3 1234:2->1269:3->1479:1 {126}
3 1234:2->1269:3->1479:2 {129}
3 1234:3->2356:1->2456:1 {134}
3 1234:3->2356:1->2456:2 {124}
3 1234:3->2356:2->1567:0 {234}
3 1234:3->2356:2->1567:1 {123}

newkid · 发表于 2009-10-6 09:05

程序如下，以下算法仅仅是猜测，无法证明是最优解。

CREATE TABLE guess AS
WITH tmp AS (SELECT LEVEL l FROM DUAL CONNECT BY LEVEL<=9)
,num AS (  ---- 所有可能的答案，共有C(3,9)=84 种
SELECT REPLACE(SYS_CONNECT_BY_PATH(l,','),',') AS num
FROM tmp
WHERE LEVEL=3
CONNECT BY l>PRIOR L AND LEVEL<=3
)
,attempt AS (  ---- 所有可能的猜测，共有C(4,9)=126 种
  SELECT REPLACE(SYS_CONNECT_BY_PATH(l,','),',') AS attempt
FROM tmp
WHERE LEVEL=4
  CONNECT BY l>PRIOR l AND LEVEL<=4
  )
SELECT attempt.attempt ---- 所有猜测和答案的组合
   ,num.num
   ,4-LENGTH(REPLACE(TRANSLATE(attempt.attempt,num.num,'***'),'*')) AS hit ---- 猜对的个数
  FROM num,attempt;

CREATE TABLE result (seq number,attempt varchar2(4), num varchar2(3), hit number);

解法说明：
把每种猜测看作一个树节点，猜对个数的不同形成树枝，答案是树叶。目标就是构造一棵树使得高度尽可能的低。
每当提出一种猜测，根据不同的猜对个数形成几个树枝，每个树枝都会筛选出一部分答案，只剩下一个答案就猜对了。
如果答案多于一个则需要根据某种策略选择下一次猜测。
同样的策略使用于其他树枝，这个过程是递归的。

CREATE OR REPLACE PROCEDURE p_guess
AS

  PROCEDURE p_try (p_seq IN NUMBER,p_attempt VARCHAR2,p_hit IN NUMBER)
  AS
   lv_seq NUMBER := p_seq+1;
   lv_attempt NUMBER;
  BEGIN

   BEGIN
      -- 决定下一轮要猜什么数
      -- 策略是使得答案尽可能分散在不同的树枝，如果过于集中于某个分支，则助长了树的高度
      -- 而下一轮问题的树枝则要尽可能的多，这样也有助于降低高度
      -- 以上两点就是排序的依据
      SELECT attempt
      INTO lv_attempt
      FROM (SELECT attempt
               FROM guess
               WHERE attempt NOT IN (SELECT attempt FROM result)
                     AND (p_seq=0
                        OR p_seq>0 AND num in (SELECT num
                                                   FROM result
                                                WHERE hit=p_hit AND attempt=p_attempt and seq=p_seq
                                                )
                        )
               GROUP BY attempt, hit
               ORDER BY MAX(COUNT(*)) OVER(PARTITION BY attempt)
                     ,COUNT(*) OVER(PARTITION BY attempt) DESC
                     ,attempt
            )
      WHERE ROWNUM=1;
   EXCEPTION
      WHEN NO_DATA_FOUND THEN
         RETURN;
   END;

   INSERT INTO result
   SELECT lv_seq
         ,attempt
         ,num
         ,hit
   FROM guess
   WHERE attempt = lv_attempt
         AND (p_seq=0
               OR p_seq>0 AND num in (SELECT num
                                       FROM result
                                       WHERE hit=p_hit AND attempt=p_attempt and seq=p_seq
                                    )
            );

   FOR lv_rec IN (SELECT hit, COUNT(*) CNT
                  FROM result
                  WHERE seq=lv_seq
                        AND attempt = lv_attempt
                  GROUP BY hit
                  HAVING COUNT(*)>1
                  ORDER BY 2
                  )
   LOOP
      p_try (lv_seq,lv_attempt,lv_rec.hit);
   END LOOP;
  END p_try;

BEGIN
DELETE RESULT;
p_try(0,NULL,NULL);
COMMIT;

FOR lv_rec IN (SELECT SEQ
                     ,SUBSTR(SYS_CONNECT_BY_PATH(ATTEMPT||':'||HIT,'->'),3) path
                     ,num
                  FROM result
               WHERE CONNECT_BY_ISLEAF=1
               START WITH seq=1
               CONNECT BY seq=prior seq+1 AND num=prior num
               ORDER BY 2
               )
LOOP
   DBMS_OUTPUT.PUT_LINE(lv_rec.seq||' '||lv_rec.path||' {'||lv_rec.num||'}');
END LOOP;

END p_guess;
/

SQL> EXEC P_GUESS;

2 1234:0->1257:0 {689}
3 1234:0->1257:1->1258:0 {679}
4 1234:0->1257:1->1258:1->1259:0 {678}
4 1234:0->1257:1->1258:1->1259:1 {789}
4 1234:0->1257:1->1258:1->1259:2 {569}
4 1234:0->1257:1->1258:2->1239:0 {568}
4 1234:0->1257:1->1258:2->1239:1 {589}
4 1234:0->1257:2->1236:0->1238:0 {579}
4 1234:0->1257:2->1236:0->1238:1 {578}
3 1234:0->1257:2->1236:1 {567}
3 1234:1->1358:0->1457:0 {269}
4 1234:1->1358:0->1457:1->1459:0 {267}
4 1234:1->1358:0->1457:1->1459:1 {279}
4 1234:1->1358:0->1457:1->1459:2 {469}
4 1234:1->1358:0->1457:2->1359:0 {467}
4 1234:1->1358:0->1457:2->1359:1 {479}
4 1234:1->1358:1->1467:0->1389:1 {259}
4 1234:1->1358:1->1467:0->1389:2 {289}
4 1234:1->1358:1->1467:1->2356:0 {489}
5 1234:1->1358:1->1467:1->2356:1->1569:0 {278}
5 1234:1->1358:1->1467:1->2356:1->1569:1 {379}
5 1234:1->1358:1->1467:1->2356:1->1569:2 {459}
5 1234:1->1358:1->1467:1->2356:2->1578:0 {369}
5 1234:1->1358:1->1467:1->2356:2->1578:1 {268}
5 1234:1->1358:1->1467:1->2356:2->1578:2 {257}
4 1234:1->1358:1->1467:1->2356:3 {256}
4 1234:1->1358:1->1467:2->4568:0 {179}
5 1234:1->1358:1->1467:2->4568:1->1469:1 {367}
5 1234:1->1358:1->1467:2->4568:1->1469:3 {169}
5 1234:1->1358:1->1467:2->4568:2->1489:1 {457}
5 1234:1->1358:1->1467:2->4568:2->1489:2 {478}
5 1234:1->1358:1->1467:2->4568:3->1478:1 {456}
5 1234:1->1358:1->1467:2->4568:3->1478:2 {468}
3 1234:1->1358:1->1467:3 {167}
4 1234:1->1358:2->1468:0->1367:1 {359}
4 1234:1->1358:2->1468:0->1367:2 {357}
4 1234:1->1358:2->1468:1->1567:0 {389}
5 1234:1->1358:2->1468:1->1567:1->1369:0 {258}
5 1234:1->1358:2->1468:1->1567:1->1369:1 {378}
5 1234:1->1358:2->1468:1->1567:2->1379:1 {356}
5 1234:1->1358:2->1468:1->1567:2->1379:2 {159}
4 1234:1->1358:2->1468:1->1567:3 {157}
5 1234:1->1358:2->1468:2->1378:1->1348:1 {156}
5 1234:1->1358:2->1468:2->1378:1->1348:2 {458}
5 1234:1->1358:2->1468:2->1378:2->1368:2 {189}
5 1234:1->1358:2->1468:2->1378:2->1368:3 {368}
4 1234:1->1358:2->1468:2->1378:3 {178}
3 1234:1->1358:2->1468:3 {168}
3 1234:1->1358:3->1456:1 {358}
3 1234:1->1358:3->1456:2 {158}
4 1234:2->1267:0->1245:1->1248:1 {349}
4 1234:2->1267:0->1245:1->1248:2 {348}
3 1234:2->1267:0->1245:2 {345}
4 1234:2->1267:1->1357:0->1278:1 {249}
4 1234:2->1267:1->1357:0->1278:2 {248}
4 1234:2->1267:1->1357:1->1458:0 {239}
5 1234:2->1267:1->1357:1->1458:1->1349:1 {238}
5 1234:2->1267:1->1357:1->1458:1->1349:2 {346}
5 1234:2->1267:1->1357:1->1458:2->1347:1 {245}
5 1234:2->1267:1->1357:1->1458:2->1347:2 {149}
4 1234:2->1267:1->1357:1->1458:3 {148}
4 1234:2->1267:1->1357:2->1289:0 {347}
5 1234:2->1267:1->1357:2->1289:1->1346:1 {235}
5 1234:2->1267:1->1357:2->1289:1->1346:2 {145}
5 1234:2->1267:1->1357:2->1289:2->1279:1 {138}
5 1234:2->1267:1->1357:2->1289:2->1279:2 {139}
3 1234:2->1267:1->1357:3 {135}
4 1234:2->1267:2->1589:0->1246:1 {237}
5 1234:2->1267:2->1589:0->1246:2->1247:1 {236}
5 1234:2->1267:2->1589:0->1246:2->1247:3 {247}
4 1234:2->1267:2->1589:0->1246:3 {246}
4 1234:2->1267:2->1589:1->1356:1 {147}
5 1234:2->1267:2->1589:1->1356:2->1269:1 {137}
5 1234:2->1267:2->1589:1->1356:2->1269:2 {146}
4 1234:2->1267:2->1589:1->1356:3 {136}
5 1234:2->1267:2->1589:2->1249:2->1268:2 {125}
5 1234:2->1267:2->1589:2->1249:2->1268:3 {128}
4 1234:2->1267:2->1589:2->1249:3 {129}
3 1234:2->1267:3->1237:2 {126}
3 1234:2->1267:3->1237:3 {127}
3 1234:3->1256:1->1345:2 {234}
3 1234:3->1256:1->1345:3 {134}
3 1234:3->1256:2->1235:2 {124}
3 1234:3->1256:2->1235:3 {123}

PL/SQL procedure successfully completed.

[ 本帖最后由 newkid 于 2009-10-7 09:08 编辑 ]

[转载] 猜数字游戏, 为保证所有条件下能猜出，求最少猜多少次

有人解出一个

浏览过的版块