Project Euler Problem 276, 268, 347

newkid · 发表于 2012-1-11 02:38

#366挺有意思：
两个人轮流从一堆N个石子中取石子，规则：
第一个人可以取任意数量但不可以全取（至少留下一个）;
下一个人取得的数量不能超过上一人所取数量的两倍;
谁取到最后一个石子则获胜。

N=2: 先取者败
N=3: 先取者败
N=4: 先取者胜。先取一个，把对手置于N=3
N=5: 先取者败。如果先取一个，则对手获得N=4的胜位；如果取两个以上，对手可以取走所有。

求所有N的胜败算法：
假设 M 为败位，则从 M1=M+1 至 M2=M+FLOOR((M-1)/2) 为胜位，因为先手者可以取走第M1至M2个，把败位M留给对方(比如M=5为败位，则6至7为胜位)。不可再多取，否则对手可以一下子取走剩余的石子。
从M2+1开始，问题转换为谁能取到第M+1个石子（把败位M留给对手）
找到第一个 >FLOOR((M-1)/2)的败位 L, 则M2+1至M2+L-1为胜位
M2+L为败位。
重复以上步骤。

例子：M=5, 下一个败位就是 5+3=8
当M=8, 则第9/10/11为胜位；超过11时问题转换为竞争第9个石子，12=8+4仍为胜位(因为4为胜位)，13=8+5为败位。

题目要求找出在胜位的第一次取最多可拿多少个。在M1至M2很简单，就是拿到剩下M个（M为败位）。超过M2时问题转换，变成竞争第M+1个石子，前面的M个可不考虑，首次取的最大值等于 N-M 位的最大值。

CREATE OR REPLACE PROCEDURE sp_stone_game (p_num IN NUMBER)
AS
  TYPE t_stone IS TABLE OF NUMBER;
  lv_stones t_stone := t_stone();
  lv_lose NUMBER;
  lv_sum NUMBER :=0;
BEGIN
  lv_stones.EXTEND(p_num);

  FOR i IN 1..p_num LOOP
   lv_stones(i):=0;
  END LOOP;

  lv_stones(1):=1;
  lv_stones(4):=1;

  lv_lose :=5;

  WHILE lv_lose+1<=p_num LOOP
      FOR i IN  lv_lose+1 .. LEAST(lv_lose+FLOOR((lv_lose-1)/2),p_num) LOOP
         lv_stones(i) := i-lv_lose; ---- 每次取掉lv_lose之上的那部分，把lv_lose留给对手
                                    ---- 不可取多于FLOOR((lv_lose-1)/2)，否则对手可以一下子取走剩余的石子
      END LOOP;
      IF lv_lose+FLOOR((lv_lose-1)/2) < p_num THEN
         FOR i IN lv_lose+FLOOR((lv_lose-1)/2)+1 .. p_num LOOP
               lv_stones(i) := lv_stones(i-lv_lose);  --- 变成竞争第lv_lose+1个石子
               IF lv_stones(i)=0 THEN  ----- 到达败位，本轮结束继续下一轮
                  lv_lose := i;
                  EXIT;
               END IF;
         END LOOP;
      ELSE
         EXIT;
      END IF;
  END LOOP;

  FOR i IN 2..p_num LOOP    ---- N=1 不算，肯定先拿的赢
   DBMS_OUTPUT.PUT_LINE('i='||i||'  '||CASE WHEN lv_stones(i)=0 THEN 'Lose' ELSE 'First fetch='||lv_stones(i) END);
   lv_sum := lv_sum+lv_stones(i);
  END LOOP;
  DBMS_OUTPUT.PUT_LINE('sum='||lv_sum);
END;
/

EXEC sp_stone_game(100);

i=2  Lose
i=3  Lose
i=4  First fetch=1
i=5  Lose
i=6  First fetch=1
i=7  First fetch=2
i=8  Lose
i=9  First fetch=1
i=10  First fetch=2
i=11  First fetch=3
i=12  First fetch=1
i=13  Lose
i=14  First fetch=1
i=15  First fetch=2
i=16  First fetch=3
i=17  First fetch=4
i=18  First fetch=5
i=19  First fetch=6
i=20  First fetch=2
i=21  Lose
i=22  First fetch=1
i=23  First fetch=2
i=24  First fetch=3
i=25  First fetch=4
i=26  First fetch=5
i=27  First fetch=6
i=28  First fetch=7
i=29  First fetch=8
i=30  First fetch=9
i=31  First fetch=10
i=32  First fetch=3
i=33  First fetch=1
i=34  Lose
i=35  First fetch=1
i=36  First fetch=2
i=37  First fetch=3
i=38  First fetch=4
i=39  First fetch=5
i=40  First fetch=6
i=41  First fetch=7
i=42  First fetch=8
i=43  First fetch=9
i=44  First fetch=10
i=45  First fetch=11
i=46  First fetch=12
i=47  First fetch=13
i=48  First fetch=14
i=49  First fetch=15
i=50  First fetch=16
i=51  First fetch=4
i=52  First fetch=5
i=53  First fetch=6
i=54  First fetch=2
i=55  Lose
i=56  First fetch=1
i=57  First fetch=2
i=58  First fetch=3
i=59  First fetch=4
i=60  First fetch=5
i=61  First fetch=6
i=62  First fetch=7
i=63  First fetch=8
i=64  First fetch=9
i=65  First fetch=10
i=66  First fetch=11
i=67  First fetch=12
i=68  First fetch=13
i=69  First fetch=14
i=70  First fetch=15
i=71  First fetch=16
i=72  First fetch=17
i=73  First fetch=18
i=74  First fetch=19
i=75  First fetch=20
i=76  First fetch=21
i=77  First fetch=22
i=78  First fetch=23
i=79  First fetch=24
i=80  First fetch=25
i=81  First fetch=26
i=82  First fetch=27
i=83  First fetch=7
i=84  First fetch=8
i=85  First fetch=9
i=86  First fetch=10
i=87  First fetch=3
i=88  First fetch=1
i=89  Lose
i=90  First fetch=1
i=91  First fetch=2
i=92  First fetch=3
i=93  First fetch=4
i=94  First fetch=5
i=95  First fetch=6
i=96  First fetch=7
i=97  First fetch=8
i=98  First fetch=9
i=99  First fetch=10
i=100  First fetch=11
sum=728

PL/SQL procedure successfully completed.

newkid · 发表于 2012-1-11 04:57

败位是斐波那契数列：2,3,5,8,13,21,34,55,89,....
胜位的取值也有某种规律，如果能把公式总结出来就好办。

newkid · 发表于 2012-1-11 05:05

除去1之外，10^18之内总共只有85个败位。大部分都是先手胜的。

SELECT LEVEL, TO_CHAR(ROUND(SQRT(5)/5*(POWER((1+SQRT(5))/2,LEVEL)-POWER((1-SQRT(5))/2,LEVEL)),4)) LOSE
FROM DUAL
CONNECT BY SQRT(5)/5*(POWER((1+SQRT(5))/2,LEVEL)-POWER((1-SQRT(5))/2,LEVEL))<=1E18;

   LEVEL LOSE
---------- -------------------------------
      1 1
      2 1
      3 2
      4 3
      5 5
      6 8
      7 13
      8 21
      9 34
      10 55
      11 89
      12 144
      13 233
      14 377
      15 610
      16 987
      17 1597
      18 2584
      19 4181
      20 6765
      21 10946
      22 17711
      23 28657
      24 46368
      25 75025
      26 121393
      27 196418
      28 317811
      29 514229
      30 832040
      31 1346269
      32 2178309
      33 3524578
      34 5702887
      35 9227465
      36 14930352
      37 24157817
      38 39088169
      39 63245986
      40 102334155
      41 165580141
      42 267914296
      43 433494437
      44 701408733
      45 1134903170
      46 1836311903
      47 2971215073
      48 4807526976
      49 7778742049
      50 12586269025
      51 20365011074
      52 32951280099
      53 53316291173
      54 86267571272
      55 139583862445
      56 225851433717
      57 365435296162
      58 591286729879
      59 956722026041
      60 1548008755920
      61 2504730781961
      62 4052739537881
      63 6557470319842
      64 10610209857723
      65 17167680177565
      66 27777890035288
      67 44945570212853
      68 72723460248141
      69 117669030460994
      70 190392490709135
      71 308061521170129
      72 498454011879264
      73 806515533049393
      74 1304969544928657
      75 2111485077978050
      76 3416454622906707
      77 5527939700884757
      78 8944394323791464
      79 14472334024676221
      80 23416728348467685
      81 37889062373143906
      82 61305790721611591
      83 99194853094755497
      84 160500643816367088
      85 259695496911122585
      86 420196140727489673
      87 679891637638612258

newkid · 发表于 2012-1-11 06:17

先手取数的规律也找出来了，在两个斐波那契数之间，先从1开始累加到FLOOR((M-1)/2)，剩下的用递归。

〇〇 · 发表于 2012-1-11 07:38

本帖最后由〇〇于 2012-1-11 07:39 编辑

newkid 发表于 2012-1-11 06:17
先手取数的规律也找出来了，在两个斐波那契数之间，先从1开始累加到FLOOR((M-1)/2)，剩下的用递归。

解答很详细很巧妙，慢慢学习

newkid · 发表于 2012-1-11 10:18

本帖最后由 newkid 于 2012-1-13 05:27 编辑

DECLARE
  p_num NUMBER :=1E18;
  TYPE t_lose IS TABLE OF NUMBER;
  lv_lose t_lose := t_lose(2,3);

  lv_sum NUMBER :=0;

  FUNCTION f_sum (
         p_start IN NUMBER
      ,p_cnt IN NUMBER
      ) RETURN NUMBER
  AS
   lv_upper NUMBER;
   lv_start NUMBER;
   lv_limit NUMBER;
  BEGIN
   IF p_cnt<1 THEN
      RETURN 0;
   END IF;

   FOR i IN 2..lv_lose.COUNT LOOP
      IF lv_lose(i)>p_start THEN
         lv_start := p_start-lv_lose(i-1);
         lv_limit := lv_start+p_cnt-1;
         lv_upper := LEAST(FLOOR((lv_lose(i-1)-1)/2),lv_limit);
         RETURN (lv_start +lv_upper)*(lv_upper-lv_start+1)/2 + f_sum(lv_upper+1,lv_limit-lv_upper);
      END IF;
   END LOOP;

  END f_sum;

BEGIN

  WHILE lv_lose(lv_lose.COUNT) < p_num LOOP
      lv_lose.EXTEND;
      lv_lose(lv_lose.COUNT) := lv_lose(lv_lose.COUNT-1) + lv_lose(lv_lose.COUNT-2);
      lv_sum := lv_sum + f_sum(lv_lose(lv_lose.COUNT-1)+1
                              ,LEAST(p_num-lv_lose(lv_lose.COUNT-1)
                                    ,lv_lose(lv_lose.COUNT-2)-1  ---lv_next_lose-lv_last_lose-1
                                    )
                              );
  END LOOP;

  DBMS_OUTPUT.PUT_LINE('------------------');
  DBMS_OUTPUT.PUT_LINE('sum='||lv_sum);
  DBMS_OUTPUT.PUT_LINE('------------------');
END;
/

------------------
sum=90715770608344675900905552588351299
------------------

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.02

〇〇 · 发表于 2012-1-11 11:25

本帖最后由〇〇于 2012-1-11 11:26 编辑

newkid 发表于 2012-1-11 10:18
先写一个看看，明天再来查错：

DECLARE

Sorry, but the answer you gave appears to be incorrect.

Go back to Problem 366..

newkid · 发表于 2012-1-11 11:31

题目要求对10^8取模。

〇〇 · 发表于 2012-1-11 12:14

newkid 发表于 2012-1-11 11:31
题目要求对10^8取模。

对了

Congratulations, the answer you gave to problem 366 is correct.

You are the 105th person to have solved this problem.

You have earned 1 new award:

On The Ball: Solve the most recent problem
Return to Problems page or go to thread 366 in the forum.

newkid · 发表于 2012-1-13 23:37

#268 用递归，花了差不多一小时。没有考虑野花说的临界点的误差情况。顺便把36楼的代码精简了一下。

DECLARE
TYPE t_prime IS RECORD (
      pn NUMBER,lg NUMBER
      );
TYPE t_primes IS TABLE OF t_prime;
lv_primes t_primes := t_primes();
lv_limit NUMBER := 16;
lv_cnt NUMBER;

FUNCTION f_cnt(
         p_level IN NUMBER
         ,p_start IN NUMBER
         ,p_sum IN NUMBER
         ) RETURN NUMBER
AS
   lv_cnt_rest NUMBER:=0;
   lv_sum NUMBER;
BEGIN
   IF p_start>lv_primes.COUNT OR p_sum<=0 THEN
      RETURN 0;
   END IF;
   FOR i IN p_start..lv_primes.COUNT LOOP
      lv_sum := lv_primes(i).lg;
      IF lv_sum>p_sum THEN
         EXIT;
      END IF;
      WHILE lv_sum<=p_sum LOOP
            lv_cnt_rest := lv_cnt_rest+ (CASE WHEN p_level>=4 THEN 1 ELSE 0 END)+f_cnt(p_level+1,i+1,p_sum-lv_sum);
            lv_sum := lv_sum+lv_primes(i).lg;
      END LOOP;
   END LOOP;
   RETURN lv_cnt_rest;
END f_cnt;
BEGIN

WITH
t as(SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY 2*ROWNUM+1 <= 100
   )
SELECT pn,LOG(10,pn)
   BULK COLLECT INTO lv_primes
FROM (
      SELECT rn pn from t
      MINUS
      SELECT t1.rn * t2.rn
         FROM t t1, t t2
      WHERE t1.rn <= t2.rn
            AND t1.rn <=SQRT(100)
            AND t1.rn * t2.rn <100
      UNION ALL SELECT 2 FROM DUAL
      )
ORDER BY pn;

lv_cnt := f_cnt(1,1,lv_limit);

DBMS_OUTPUT.PUT_LINE('count='||lv_cnt);
END;
/

count=2344465914

PL/SQL procedure successfully completed.

Elapsed: 00:58:35.74

Project Euler Problem 276, 268, 347

浏览过的版块