趣味题

〇〇 · 发表于 2010-6-18 08:38

加上输出时间，
D:\app>tp7
当前时间: 8:35:29.12
输入新时间:
当前时间: 8:35:29.18
输入新时间:

#include <stdio.h>
#include <time.h>
int main()
{
int i=0;
int j=0;
int k=0;
int l=0;
char a[60000][15];
int b[15];
int c=0;
for(i=1;i<=7;i++)//level 1 第一个数第一位最大7
{
a[i][1]=i;
a[i][2]=a[i][3]=a[i][4]=a[i][5]=a[i][6]=a[i][7]=a[i][8]=a[i][9]=a[i][10]=a[i][11]=a[i][12]=0;
a[i][13]=1;
a[i][14]=0;
}
b[0]=1;
b[1]=8;
i=b[1]-1;
for(j=2;j<=12;j++)//level 2-12
{
//printf("j=%d,%d-%d,count=%d\n",j,b[j-2],b[j-1]-1,b[j-1]-b[j-2]);
for(k=1;k<=12;k++)//digit 1-12
{
for(l=b[j-2];l<b[j-1];l++) //l -> last level
{
if(
(k!=a[l][1]&&k!=a[l][2]&&k!=a[l][3]&&k!=a[l][4]&&k!=a[l][5]&&k!=a[l][6]&&k!=a[l][7]&&k!=a[l][8]&&k!=a[l][9]&&k!=a[l][10]&&k!=a[l][11])
&&((a[l][13]==3||a[l][13]==6||a[l][13]==9)
||(a[l][13]==11&&k==(a[l][10]+a[l][11]+a[l][14])%16&&a[l][3]==a[l][1]+a[l][2]+(a[l][10]+a[l][11])/16)
||(a[l][13]==10&&k>a[l][10])
||(a[l][13]==8&&k==(a[l][7]+a[l][8]+a[l][14])%16)
||(a[l][13]==7&&k>a[l][7])
||(a[l][13]==5&&k==(a[l][4]+a[l][5])%16)
||(a[l][13]==4&&k>a[l][4])
||(a[l][13]==2&&(k==a[l][1]+a[l][2]||k==a[l][1]+a[l][2]+1))
||(a[l][13]==1&&k>a[l][1]&&k+a[l][1]<=15)//12)
)
)
{
i++;
a[i][1]=a[l][1];
a[i][2]=(a[l][13]==1)?k:a[l][2];
a[i][3]=(a[l][13]==2)?k:a[l][3];
a[i][4]=(a[l][13]==3)?k:a[l][4];
a[i][5]=(a[l][13]==4)?k:a[l][5];
a[i][6]=(a[l][13]==5)?k:a[l][6];
a[i][7]=(a[l][13]==6)?k:a[l][7];
a[i][8]=(a[l][13]==7)?k:a[l][8];
a[i][9]=(a[l][13]==8)?k:a[l][9];
a[i][10]=(a[l][13]==9)?k:a[l][10];
a[i][11]=(a[l][13]==10)?k:a[l][11];
a[i][12]=(a[l][13]==11)?k:a[l][12];
a[i][13]=a[l][13]+1;
a[i][14]=
(a[l][13]==5)?(a[l][4]+a[l][5])/16:(
(a[l][13]==8?(a[l][7]+a[l][8]+a[l][14])/16:(
(a[l][13]==11)?(a[l][10]+a[l][11]+a[l][14])/16:a[l][14])));
if(a[i][13]==12)
{
c++;
printf("%x%x%x%x+%x%x%x%x=%x%x%x%x\n",/*1 10 7 4 2 11 8 5 3 12 9 6*/a[i][1],a[i][10],a[i][7],a[i][4],a[i][2],a[i][11],a[i][8],a[i][5],a[i][3],a[i][12],a[i][9],a[i][6]);
printf("%x%x%x%x+%x%x%x%x=%x%x%x%x\n",/*1 10 7 5 2 11 8 4 3 12 9 6*/a[i][1],a[i][10],a[i][7],a[i][5],a[i][2],a[i][11],a[i][8],a[i][4],a[i][3],a[i][12],a[i][9],a[i][6]);
printf("%x%x%x%x+%x%x%x%x=%x%x%x%x\n",/*1 10 8 4 2 11 7 5 3 12 9 6*/a[i][1],a[i][10],a[i][8],a[i][4],a[i][2],a[i][11],a[i][7],a[i][5],a[i][3],a[i][12],a[i][9],a[i][6]);
printf("%x%x%x%x+%x%x%x%x=%x%x%x%x\n",/*1 11 7 4 2 10 8 5 3 12 9 6*/a[i][1],a[i][11],a[i][7],a[i][4],a[i][2],a[i][10],a[i][8],a[i][5],a[i][3],a[i][12],a[i][9],a[i][6]);
printf("%x%x%x%x+%x%x%x%x=%x%x%x%x\n",/*1 11 8 4 2 10 7 5 3 12 9 6*/a[i][1],a[i][11],a[i][8],a[i][4],a[i][2],a[i][10],a[i][7],a[i][5],a[i][3],a[i][12],a[i][9],a[i][6]);
printf("%x%x%x%x+%x%x%x%x=%x%x%x%x\n",/*1 11 7 5 2 10 8 4 3 12 9 6*/a[i][1],a[i][11],a[i][7],a[i][5],a[i][2],a[i][10],a[i][8],a[i][4],a[i][3],a[i][12],a[i][9],a[i][6]);
printf("%x%x%x%x+%x%x%x%x=%x%x%x%x\n",/*1 11 8 5 2 10 7 4 3 12 9 6*/a[i][1],a[i][11],a[i][8],a[i][5],a[i][2],a[i][10],a[i][7],a[i][4],a[i][3],a[i][12],a[i][9],a[i][6]);
printf("%x%x%x%x+%x%x%x%x=%x%x%x%x\n",/*1 10 8 5 2 11 7 4 3 12 9 6*/a[i][1],a[i][10],a[i][8],a[i][5],a[i][2],a[i][11],a[i][7],a[i][4],a[i][3],a[i][12],a[i][9],a[i][6]);
}
} //if
} //l
} //k
b[j]=i+1;
} //j
printf("c=%d\n",c*8);
return 1;
}

复制代码

killkill_shadow · 发表于 2010-7-19 09:52

用一个比较暴力的方法：

WITH n AS (
SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM<=9
),
tmp as (
select n1.n n1 , n2.n n2, n3.n n3 ,
      n4.n n4 , n5.n n5, n6.n n6 ,
      n7.n n7 , n8.n n8, n9.n n9
from n n1,n n2,n n3,n n4,n n5,n n6,n n7,n n8,n n9
where n1.n between 1 and 4
   and n1.n + n4.n <= 9 /*
   and n7.n - n1.n - n4.n = trunc(( ( n2.n + n5.n )  + (n3.n + n6.n - n9.n)/10 )/10)*/
   and n8.n - n2.n - n5.n = (n3.n + n6.n - n9.n)/10
   and mod( n3.n + n6.n ,10 ) = n9.n
   and n1.n < n4.n
   and n1.n*100+n2.n*10+n3.n + n4.n*100+n5.n*10+n6.n = n7.n*100+n8.n*10+n9.n
   and n1.n not in (    n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n, n9.n)
   and n2.n not in ( n1.n,    n3.n, n4.n, n5.n, n6.n, n7.n, n8.n, n9.n)
   and n3.n not in ( n1.n, n2.n,    n4.n, n5.n, n6.n, n7.n, n8.n, n9.n)
   and n4.n not in ( n1.n, n2.n, n3.n,    n5.n, n6.n, n7.n, n8.n, n9.n)
   and n5.n not in ( n1.n, n2.n, n3.n, n4.n,    n6.n, n7.n, n8.n, n9.n)
   and n6.n not in ( n1.n, n2.n, n3.n, n4.n, n5.n,    n7.n, n8.n, n9.n)
   and n7.n not in ( n1.n, n2.n, n3.n, n4.n, n5.n, n6.n,    n8.n, n9.n)
   and n8.n not in ( n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n,    n9.n)
   and n9.n not in ( n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n    )
)
select * from tmp;

这里没什么算法可言，首先是9个1~9的序列表进行连接，联接的条件包括，其中直接就把题意的写到联接条件中，当然还有9个数字不重复出现的条件
执行用时月0.23秒，执行计划和统计信息如下：

------------------------------------------------------------------------------------------------------------
| Id  | Operation                      | Name                   | Rows  | Bytes | Cost (%CPU)| Time    |
------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT             |                         |    1 | 117 | 20 (0)| 00:00:01 |
| 1 |  TEMP TABLE TRANSFORMATION    |                         |    |    |          |       |
| 2 | LOAD AS SELECT             | SYS_TEMP_0FD9D6999_55670 |    |    |          |       |
| 3 | COUNT                      |                         |    |    |          |       |
|*  4 |    CONNECT BY WITHOUT FILTERING|                         |    |    |          |       |
| 5 |    FAST DUAL                |                         |    1 |    |    2 (0)| 00:00:01 |
| 6 | NESTED LOOPS                |                         |    1 | 117 | 18 (0)| 00:00:01 |
| 7 | NESTED LOOPS                |                         |    1 | 104 | 16 (0)| 00:00:01 |
| 8 |    NESTED LOOPS             |                         |    1 | 91 | 14 (0)| 00:00:01 |
| 9 |    NESTED LOOPS             |                         |    1 | 78 | 12 (0)| 00:00:01 |
|  10 |    NESTED LOOPS             |                         |    1 | 65 | 10 (0)| 00:00:01 |
|  11 |       NESTED LOOPS          |                         |    1 | 52 |    8 (0)| 00:00:01 |
|  12 |       NESTED LOOPS          |                         |    1 | 39 |    6 (0)| 00:00:01 |
|  13 |       NESTED LOOPS          |                         |    1 | 26 |    4 (0)| 00:00:01 |
|  14 |          VIEW                |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  15 |          TABLE ACCESS FULL | SYS_TEMP_0FD9D6999_55670 |    1 | 13 |    2 (0)| 00:00:01 |
|* 16 |          VIEW                |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  17 |          TABLE ACCESS FULL | SYS_TEMP_0FD9D6999_55670 |    1 | 13 |    2 (0)| 00:00:01 |
|* 18 |       VIEW                |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  19 |          TABLE ACCESS FULL    | SYS_TEMP_0FD9D6999_55670 |    1 | 13 |    2 (0)| 00:00:01 |
|* 20 |       VIEW                   |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  21 |       TABLE ACCESS FULL    | SYS_TEMP_0FD9D6999_55670 |    1 | 13 |    2 (0)| 00:00:01 |
|* 22 |       VIEW                   |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  23 |       TABLE ACCESS FULL    | SYS_TEMP_0FD9D6999_55670 |    1 | 13 |    2 (0)| 00:00:01 |
|* 24 |    VIEW                   |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  25 |       TABLE ACCESS FULL       | SYS_TEMP_0FD9D6999_55670 |    1 | 13 |    2 (0)| 00:00:01 |
|* 26 |    VIEW                      |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  27 |    TABLE ACCESS FULL       | SYS_TEMP_0FD9D6999_55670 |    1 | 13 |    2 (0)| 00:00:01 |
|* 28 |    VIEW                      |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  29 |    TABLE ACCESS FULL       | SYS_TEMP_0FD9D6999_55670 |    1 | 13 |    2 (0)| 00:00:01 |
|* 30 | VIEW                      |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  31 |    TABLE ACCESS FULL          | SYS_TEMP_0FD9D6999_55670 |    1 | 13 |    2 (0)| 00:00:01 |
------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

4 - filter(ROWNUM<=9)
  16 - filter("N8"."N"<>"N9"."N")
  18 - filter("N7"."N"<>"N8"."N" AND "N7"."N"<>"N9"."N")
  20 - filter("N6"."N"<>"N7"."N" AND "N6"."N"<>"N8"."N" AND "N6"."N"<>"N9"."N")
  22 - filter("N9"."N"=MOD("N3"."N"+"N6"."N",10) AND "N3"."N"<>"N6"."N" AND "N3"."N"<>"N7"."N" AND
            "N3"."N"<>"N8"."N" AND "N3"."N"<>"N9"."N")
  24 - filter("N3"."N"<>"N5"."N" AND "N5"."N"<>"N6"."N" AND "N5"."N"<>"N7"."N" AND
            "N5"."N"<>"N8"."N" AND "N5"."N"<>"N9"."N")
  26 - filter("N2"."N"<>"N3"."N" AND "N2"."N"<>"N5"."N" AND "N2"."N"<>"N6"."N" AND
            "N2"."N"<>"N7"."N" AND "N2"."N"<>"N8"."N" AND "N2"."N"<>"N9"."N" AND
            "N8"."N"-"N2"."N"-"N5"."N"=("N3"."N"+"N6"."N"-"N9"."N")/10)
  28 - filter("N2"."N"<>"N4"."N" AND "N3"."N"<>"N4"."N" AND "N4"."N"<>"N5"."N" AND
            "N4"."N"<>"N6"."N" AND "N4"."N"<>"N7"."N" AND "N4"."N"<>"N8"."N" AND "N4"."N"<>"N9"."N" AND
            "N4"."N">1)
  30 - filter("N1"."N">=1 AND "N1"."N"<=4 AND "N1"."N"+"N4"."N"<=9 AND "N1"."N"<"N4"."N" AND
            "N1"."N"*100+"N2"."N"*10+"N3"."N"+"N4"."N"*100+"N5"."N"*10+"N6"."N"="N7"."N"*100+"N8"."N"*10+"N9"."N
            " AND "N1"."N"<>"N2"."N" AND "N1"."N"<>"N3"."N" AND "N1"."N"<>"N4"."N" AND "N1"."N"<>"N5"."N" AND
            "N1"."N"<>"N6"."N" AND "N1"."N"<>"N7"."N" AND "N1"."N"<>"N8"."N" AND "N1"."N"<>"N9"."N")

Statistics
----------------------------------------------------------
      2  recursive calls
      8  db block gets
   49879  consistent gets
      1  physical reads
      600  redo size
   3501  bytes sent via SQL*Net to client
      578  bytes received via SQL*Net from client
      7  SQL*Net roundtrips to/from client
      1  sorts (memory)
      0  sorts (disk)
      84  rows processed

没有想象中的差。

mdcpaulliu · 发表于 2010-7-19 14:39

佩服啊！

cj402444206 · 发表于 2010-7-30 17:08

我是这样写的：
不过是136条。
SELECT N1,N2,N3 FROM
(WITH DATA AS
  (SELECT REPLACE(SYS_CONNECT_BY_PATH(NUM, ','), ',') STR_NUM
FROM (SELECT LEVEL NUM FROM DUAL CONNECT BY LEVEL <10)
WHERE LEVEL = 9
START WITH NUM = 1
CONNECT BY NOCYCLE PRIOR NUM != NUM
AND LEVEL <= 9
  )

  SELECT TO_NUMBER(SUBSTR(STR_NUM,1,3)) N1, TO_NUMBER(SUBSTR(STR_NUM,4,3)) N2, TO_NUMBER(SUBSTR(STR_NUM,7)) N3
  FROM DATA)
  WHERE N1+N2=N3
  OR N1+N3=N2
/*OR N2+N3=N1*/--R1 最小
------------------------------------------------
136 rows selected
Executed in 2.734 seconds

cj402444206 · 发表于 2010-7-30 17:17

求解，怎么试136条：
SELECT N1,N2,N3 FROM
(WITH DATA AS
  (SELECT REPLACE(SYS_CONNECT_BY_PATH(NUM, ','), ',') STR_NUM
FROM (SELECT LEVEL NUM FROM DUAL CONNECT BY LEVEL <10)
WHERE LEVEL = 9
START WITH NUM = 1
CONNECT BY NOCYCLE PRIOR NUM != NUM
AND LEVEL <= 9
  )

  SELECT TO_NUMBER(SUBSTR(STR_NUM,1,3)) N1, TO_NUMBER(SUBSTR(STR_NUM,4,3)) N2, TO_NUMBER(SUBSTR(STR_NUM,7)) N3
  FROM DATA)
  WHERE N1+N2=N3
  OR N1+N3=N2
/*OR N2+N3=N1*/--R1 最小

newkid · 发表于 2010-7-30 21:38

原帖由 cj402444206 于 2010-7-30 17:17 发表
求解，怎么试136条：
SELECT N1,N2,N3 FROM
(WITH DATA AS
(SELECT REPLACE(SYS_CONNECT_BY_PATH(NUM, ','), ',') STR_NUM
FROM (SELECT LEVEL NUM FROM DUAL CONNECT BY LEVEL

这个有错：
START WITH NUM = 1

这就注定其中有一个数是 1XX, 题目没有这种限制。

cj402444206 · 发表于 2010-8-5 13:30

呵呵，明白，谢谢newkid！
我改了下，就可以：
SELECT N1,N2,N3 FROM
(WITH DATA AS
  (SELECT REPLACE(SYS_CONNECT_BY_PATH(NUM, ','), ',') STR_NUM
FROM (SELECT LEVEL NUM FROM DUAL CONNECT BY LEVEL <10)
WHERE LEVEL = 9
CONNECT BY NOCYCLE PRIOR NUM != NUM
  )
  SELECT TO_NUMBER(SUBSTR(STR_NUM,1,3)) N1, TO_NUMBER(SUBSTR(STR_NUM,4,3)) N2, TO_NUMBER(SUBSTR(STR_NUM,7)) N3
  FROM DATA)
  WHERE N1+N2=N3
  AND  N1<N2
  AND N2<N3;

〇〇 · 发表于 2010-8-28 18:44

oracle 9i

SQL> with t as(
  2 select x from (select level+122 x from dual connect by level<=(987-122))
  3 where substr(x,1,1)<>substr(x,2,1)
  4    and substr(x,1,1)<>substr(x,3,1)
  5    and instr(x,0)=0
  6  )
  7  select count(*) from (
  8 select a.x||'+'||b.x||'='||c.x
  9 from t a,t b,t c
10 where a.x+b.x=c.x
11    and a.x<494
12    and a.x<b.x
13    and b.x<c.x
14    and translate('123456789','$'||a.x||b.x||c.x,'$') is null
15  )
16  ;

  COUNT(*)
----------
   168

已用时间:  00: 00: 01.09
SQL> /

  COUNT(*)
----------
   168

已用时间:  00: 00: 00.05

tree_new_bee · 发表于 2010-12-4 17:01

原帖由〇〇于 2010-8-28 18:44 发表
oracle 9i

SQL> with t as(
2 select x from (select level+122 x from dual connect by level

翻老贴来了。

想到的思路，看了看，前面似乎都有了。

发现还是你这个最朴实的办法最好用。

[ 本帖最后由 tree_new_bee 于 2010-12-4 17:13 编辑 ]

tree_new_bee · 发表于 2010-12-4 17:12

原帖由〇〇于 2010-8-28 18:44 发表
oracle 9i

SQL> with t as(
  2 select x from (select level+122 x from dual connect by level<=(987-122))
  3 where substr(x,1,1)<>substr(x,2,1)
  4    and substr(x,1,1)<>substr(x,3,1)
  5    and instr(x,0)=0
  6  )
  7  select count(*) from (
  8 select a.x||'+'||b.x||'='||c.x
  9 from t a,t b,t c
10 where a.x+b.x=c.x
11    and a.x<494
12    and a.x<b.x
13    and b.x<c.x
14    and translate('123456789','$'||a.x||b.x||c.x,'$') is null
15  )
16  ;

不过，这里为什么不在前面加入substr(x,2,1)<>substr(x,3,1)? 另外两条件并不能覆盖这个条件
加上这个条件，能进一步减小t表的数量，性能会略有改善

[转载] 趣味题

回复 #1 〇〇的帖子

求解，怎么试136条

回复 #106 newkid 的帖子

浏览过的版块

[转载] 趣味题

回复 #1 〇〇 的帖子

求解，怎么试136条

回复 #106 newkid 的帖子

浏览过的版块

回复 #1 〇〇的帖子