Euler Project 挨个做- 之二 (Q51-Q78)

〇〇

下题另起一贴吧...

tree_new_bee

原帖由 〇〇 于 2011-1-5 15:35 发表
下题另起一贴吧...

啊？ 才刚100楼就开新贴？
我这里只是刚到第3页而已。


64题我现在没头绪， 一起想思路吧。

〇〇

你是什么浏览器，我是第11页了，我知道了，你修改了个人设置。50帖/页

[ 本帖最后由 〇〇 于 2011-1-5 16:05 编辑 ]

〇〇

64 中文
在根号 1 、 2 、 …… 10000 中 ， 那些无理数可以用
连分数展开表示，会得到一个循环节。问其中
循环节长度为奇数的有几个

newkid

Q62: 用TRANSLATE
with tdigis as (
SELECT n
      ,cb
      ,TRANSLATE(cb,'0123456789','0')||
       TRANSLATE(cb,'1023456789','1')||
       TRANSLATE(cb,'2013456789','2')||
       TRANSLATE(cb,'3012456789','3')||
       TRANSLATE(cb,'4012356789','4')||
       TRANSLATE(cb,'5012346789','5')||
       TRANSLATE(cb,'6012345789','6')||
       TRANSLATE(cb,'7012345689','7')||
       TRANSLATE(cb,'8012345679','8')||
       TRANSLATE(cb,'9012345678','9') AS digis
  FROM (select level n, TO_CHAR(level*level*level) cb from dual connect by level <=10000)
)
SELECT * FROM (SELECT  tdigis.*,COUNT(*) OVER(PARTITION BY digis) cnt FROM tdigis)
WHERE cnt=5;




         N CB
---------- --------------
DIGIS
-------------------------
       CNT
----------
      8288 569310543872
012334556789
         5

      7061 352045367981
012334556789
         5

      5027 127035954683
012334556789
         5

      7202 373559126408
012334556789
         5

      8384 589323567104
012334556789
         5

      9783 936302451687
012334566789
         5

      8124 536178930624
012334566789
         5

      8496 613258407936
012334566789
         5

      9702 913237656408
012334566789
         5

      5196 140283769536
012334566789
         5


10 rows selected.

Elapsed: 00:00:00.28

tree_new_bee

原帖由 newkid 于 2011-1-5 22:43 发表
Q62: 用TRANSLATE

这样简明多了。




快帮着一起想想Q64.  这个我被难倒了。

newkid

每个步骤都可以用整数来表示的嘛？写段代码把根号23里面那些1,3,1,8找出来就行了，PLSQL肯定没问题。

newkid

按照例子写成PLSQL函数，一点也不难：

---- 每个步骤表示为 A+(B*SQRT(N)-C)/D

CREATE OR REPLACE FUNCTION F_SQRT (N NUMBER) RETURN NUMBER
AS
  A NUMBER;
  B NUMBER;
  C NUMBER;
  D NUMBER;
  A2 NUMBER;
  B2 NUMBER;
  C2 NUMBER;
  D2 NUMBER;
  GCD NUMBER;
  STR VARCHAR2(4000);
  STR2 VARCHAR2(1000);
  
BEGIN
  A:=TRUNC(SQRT(N));
  B:=1;
  C:=A;
  D:=1;
  STR :='~'|| A||','||B||','||C||','||D||'~';
  
  LOOP
    --- 分子=D*(B*SQRT(N)+C) = D*B*SQRT(N)+D*C
    --- 分母=(B*SQRT(N)-C)*(B*SQRT(N)+C) = B*B*N - C*C
   
    A2 := TRUNC((D*B*SQRT(N)+D*B*C)/(B*B*N - C*C));
    B2 := D*B;
    C2 := A2*(B*B*N - C*C) - D*C;
    D2 := (B*B*N - C*C);

    A := A2;
    B := B2;
    C := C2;
    D := D2;   
   
    GCD := 2;
   
    WHILE GCD <= LEAST(B,C,D) LOOP
        IF MOD(B,GCD)=0 AND MOD(C,GCD)=0 AND MOD(D,GCD)=0 THEN
           B := B/GCD;
           C := C/GCD;
           D := D/GCD;
           GCD := 2;
        ELSE
           GCD := GCD+1;
        END IF;
    END LOOP;
   
    STR2 := A||','||B||','||C||','||D||'~';
    IF INSTR(STR,'~'||STR2)>0 THEN
       -- DBMS_OUTPUT.PUT_LINE(STR);
       STR := SUBSTR(STR,INSTR(STR,'~'||STR2)+1);
       RETURN LENGTH(STR)-LENGTH(REPLACE(STR,'~'));
    END IF;
    STR := STR||STR2;
  END LOOP;
  DBMS_OUTPUT.PUT_LINE('ERROR: N='||N);
END;
/

SELECT COUNT(*)
   FROM (SELECT F_SQRT(LEVEL) f
           FROM DUAL
          WHERE MOD(SQRT(LEVEL),1)<>0
          CONNECT BY LEVEL<=10000
        )
WHERE MOD(f,2)=1;

  COUNT(*)
----------
      1322

Elapsed: 00:00:06.15


在此基础上写递归SQL也不难，就是中间有个消除公约数比较罗嗦。

[ 本帖最后由 newkid 于 2011-1-6 08:17 编辑 ]

newkid

SQL虽然写出来了，但是效率不高，1000以上就很慢了，因为消除公因子的算法太差。

WITH n AS (SELECT LEVEL N FROM DUAL WHERE MOD(SQRT(LEVEL),1)>0 CONNECT BY LEVEL<=50)
,t(A,B,C,D,STR,GCD,N) AS (
SELECT TRUNC(SQRT(N)),1,TRUNC(SQRT(N)),1,CAST('~' AS VARCHAR2(4000)),100000,N FROM n
UNION ALL
SELECT CASE WHEN GCD>LEAST(B,C,D) THEN TRUNC((D*B*SQRT(N)+D*B*C)/(B*B*N - C*C)) ELSE A END
      ,CASE WHEN GCD>LEAST(B,C,D) THEN D*B
            WHEN MOD(B,GCD)=0 AND MOD(C,GCD)=0 AND MOD(D,GCD)=0 THEN B/GCD
            ELSE B
       END
      ,CASE WHEN GCD>LEAST(B,C,D) THEN TRUNC((D*B*SQRT(N)+D*B*C)/(B*B*N - C*C))*(B*B*N - C*C) - D*C
            WHEN MOD(B,GCD)=0 AND MOD(C,GCD)=0 AND MOD(D,GCD)=0 THEN C/GCD
            ELSE C
       END
      ,CASE WHEN GCD>LEAST(B,C,D) THEN B*B*N - C*C
            WHEN MOD(B,GCD)=0 AND MOD(C,GCD)=0 AND MOD(D,GCD)=0 THEN D/GCD
            ELSE D
       END
      ,CASE WHEN GCD>LEAST(B,C,D) THEN STR||A||','||B||','||C||','||D||'~' ELSE STR END
      ,CASE WHEN GCD>LEAST(B,C,D) OR MOD(B,GCD)=0 AND MOD(C,GCD)=0 AND MOD(D,GCD)=0 THEN 2 ELSE GCD+1 END
      ,N
  FROM t
WHERE INSTR(STR,'~'||A||','||B||','||C||','||D||'~')=0   
) CYCLE A,B,C,D,GCD,N SET cycle_flag TO 'Y' DEFAULT 'N'
SELECT n,LENGTH(STR)-LENGTH(REPLACE(STR,'~')) p
  FROM (SELECT N,SUBSTR(STR, INSTR(STR,'~'||A||','||B||','||C||','||D||'~')+1) AS STR
          FROM T
         WHERE INSTR(STR,'~'||A||','||B||','||C||','||D||'~')>0
       )
ORDER BY 1
;

tree_new_bee

没看明白你的：
--- 分子=D*(B*SQRT(N)+C) = D*B*SQRT(N)+D*C
--- 分母=(B*SQRT(N)-C)*(B*SQRT(N)+C) = B*B*N - C*C

是怎么得来的。


并且，在excel中按你的算法用几个数模拟了一下， 似乎用不到gcd, 只要每次都让b/c/d都除以b就行了。


23        4        1        4        1        ~4,1,4,1~
        1        1        3        7        ~1,1,3,7~
        3        7        21        14       
        3        1        3        2        ~3,1,3,2~
        1        2        8        14       
        1        1        4        7        ~1,1,4,7~
        8        7        28        7       
        8        1        4        1        ~8,1,4,1~
        1        1        3        7       
        1        1        3        7        ~1,1,3,7~
        3        7        21        14       
        3        1        3        2        ~3,1,3,2~
  
str为空的行， bcd除以b, 得到下一行。
分别用7/13/234验证了一下， 这样除没出现过无法整除的问题。

[ 本帖最后由 tree_new_bee 于 2011-1-6 10:28 编辑 ]