趣味题

〇〇

c语言版。貌似比plsql简单很多，cl -O2 pc4.c 17秒

1. 
   
2. #include <stdio.h>
   
3. #include <time.h>
   
4. int main()
   
5. {
   
6. int i,j,k,r,t;
   
7. char buf[13];
   
8. char f[13];
   
9. r=0;
   
10. t=clock();
    
11. for(i=0x1234;i<=0xcba9/2;i++)
    
12. {
    
13. if ((i%0x10==0)||(i/0x10%0x10==0)||(i/0x100%0x10==0)||(i%0x10==0xd)||(i/0x10%0x10==0xd)||(i/0x100%0x10==0xd)||(i%0x10==0xf)||(i/0x10%0x10==0xf)||(i/0x100%0x10==0xf)||(i%0x10==0xe)||(i/0x10%0x10==0xe)||(i/0x100%0x10==0xe))continue;
    
14. for(j=i+1;j<=(0xcba9-i);j++)
    
15. {
    
16. if ((j%0x10==0)||(j/0x10%0x10==0)||(j/0x100%0x10==0)||(j%0x10==0xd)||(j/0x10%0x10==0xd)||(j/0x100%0x10==0xd)||(j%0x10==0xf)||(j/0x10%0x10==0xf)||(j/0x100%0x10==0xf)||(j%0x10==0xe)||(j/0x10%0x10==0xe)||(j/0x100%0x10==0xe))continue;
    
17. k=i+j;
    
18. if ((k%0x10==0)||(k/0x10%0x10==0)||(k/0x100%0x10==0)||(k%0x10==0xd)||(k/0x10%0x10==0xd)||(k/0x100%0x10==0xd)||(k%0x10==0xf)||(k/0x10%0x10==0xf)||(k/0x100%0x10==0xf)||(k%0x10==0xe)||(k/0x10%0x10==0xe)||(k/0x100%0x10==0xe))continue;
    
19. sprintf(buf,"%x%x%x",i,j,i+j);
    
20. for(k=1;k<=12;k++)f[k]=0;
    
21. for(k=1;k<=12;k++)
    
22. if(++f[(buf[k-1]-'0'>0 && buf[k-1]-'0'<=9)?buf[k-1]-'0':buf[k-1]-'a'+10]>1)goto a;
    
23. r++;
    
24. a:
    
25. ;
    
26. }
    
27. }
    
28. t=clock()-t;
    
29. printf("%d,%d",r,t);
    
30. return 1;
    
31. }
    

复制代码

1. 
   
2. #include <stdio.h>
   
3. int main()
   
4. {
   
5. int i,j,k,r;
   
6. char buf[10];
   
7. char f[10];
   
8. r=0;
   
9. for(i=123;i<=987;i++)
   
10. {
    
11. if ((i%10==0) || (i/10%10==0)||(i/100%10==0))continue;
    
12. for(j=i+1;j<=(987-i);j++)
    
13. {
    
14. if ((j%10==0) || (j/10%10==0)||(j/100%10==0))continue;
    
15. k=i+j;
    
16. if ((k%10==0) || (k/10%10==0)||(k/100%10==0))continue;
    
17. sprintf(buf,"%d%d%d",i,j,i+j);
    
18. for(k=1;k<=9;k++)f[k]=0;
    
19. for(k=1;k<=9;k++)
    
20. if(++f[buf[k-1]-'0']>1)goto a;
    
21. r++;
    
22. a:
    
23. ;
    
24. }
    
25. }
    
26. printf("%d",r);
    
27. return 1;
    
28. }
    

复制代码

熊猫儿

oo很厉害。。

newkid

原帖由 〇〇 于 2010-6-14 14:04 发表
怎么才能利用加数交换个十百位减少穷举次数呢

跟求组合的原理一样，先强行按升序或降序，然后对换。

〇〇

怎么强行，
1.如果1234不行，只能1342才能拼出？
2.怎么记录已经成功的，下次跳过？

完全翻译plsql的c,6秒

1. 
   
2. #include <stdio.h>
   
3. #include <time.h>
   
4. int main()
   
5. {
   
6. int i,j,k,r,t;
   
7. char buf[13];
   
8. char f[13];
   
9. unsigned short I[12*11*90];
   
10. unsigned short J[0xcbaa];
    
11. r=0;
    
12. t=clock();
    
13. for(i=0x1234;i<=0xcba9;i++)
    
14. {
    
15. if ((i%0x10==0)||(i/0x10%0x10==0)||(i/0x100%0x10==0)||(i%0x10==0xd)||(i/0x10%0x10==0xd)||(i/0x100%0x10==0xd)||(i%0x10==0xf)||(i/0x10%0x10==0xf)||(i/0x100%0x10==0xf)||(i%0x10==0xe)||(i/0x10%0x10==0xe)||(i/0x100%0x10==0xe))
    
16. J[i]=r;
    
17. else
    
18. {
    
19. sprintf(buf,"%x",i);
    
20. if (buf[0]!=buf[1] && buf[0]!=buf[2] && buf[0]!=buf[3] && buf[1]!=buf[2] && buf[1]!=buf[3] && buf[2]!=buf[3] )
    
21. {
    
22. I[r]=i;
    
23. J[i]=r;
    
24. r++;
    
25. }
    
26. else
    
27. J[i]=r;
    
28. }
    
29. }
    
30. r=0;
    
31. for(i=0;i<J[0xcba9/2+1];i++)
    
32. {
    
33. for(j=J[I[i]+1];j<=J[0xcba9-I[i]];j++)
    
34. {
    
35. k=I[i]+I[j];
    
36. if ((k%0x10==0)||(k/0x10%0x10==0)||(k/0x100%0x10==0)||(k%0x10==0xd)||(k/0x10%0x10==0xd)||(k/0x100%0x10==0xd)||(k%0x10==0xf)||(k/0x10%0x10==0xf)||(k/0x100%0x10==0xf)||(k%0x10==0xe)||(k/0x10%0x10==0xe)||(k/0x100%0x10==0xe))continue;
    
37. sprintf(buf,"%x%x%x",I[i],I[j],k);
    
38. for(k=1;k<=12;k++)f[k]=0;
    
39. for(k=1;k<=12;k++)
    
40. if(++f[(buf[k-1]-'0'>0 && buf[k-1]-'0'<=9)?buf[k-1]-'0':buf[k-1]-'a'+10]>1)goto a;
    
41. r++;
    
42. a:
    
43. ;
    
44. }
    
45. }
    
46. t=clock()-t;
    
47. printf("%d,%d",r,t);
    
48. return 1;
    
49. }
    

复制代码

newkid

比如我自己的写法，我在递归时强行指定顺序，输出时再对换:
WITH n AS (
   SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM<=9
   )
,t (n1,n2,n3,n4,n5,n6,n7,n8,n9,lvl) AS (
   SELECT n,0,0,0,0,0,0,0,0,1
     FROM n
    WHERE n<=4
   UNION ALL
   SELECT t.n1
         ,DECODE(t.lvl,1,n.n,t.n2)
         ,DECODE(t.lvl,2,n.n,t.n3)
         ,DECODE(t.lvl,3,n.n,t.n4)
         ,DECODE(t.lvl,4,n.n,t.n5)
         ,DECODE(t.lvl,5,n.n,t.n6)
         ,DECODE(t.lvl,6,n.n,t.n7)
         ,DECODE(t.lvl,7,n.n,t.n8)
         ,DECODE(t.lvl,8,n.n,t.n9)
         ,t.lvl+1
     FROM t,n
    WHERE n.n NOT IN (n1,n2,n3,n4,n5,n6,n7,n8)
          AND (t.lvl=1 AND n.n>t.n1 AND n.n+t.n1<=9
               OR (t.lvl=2 AND n.n - t.n1- t.n2 IN (0,1))
               OR (t.lvl=4 AND n.n > t.n4)
               OR (t.lvl=5 AND n.n = MOD(t.n4+ t.n5,10))
               OR (t.lvl=7 AND n.n > t.n7)
               OR t.lvl=8 AND n1*100+n7*10+n4 + n2*100+n8*10+n5 = n3*100+n.n*10+n6
               OR t.lvl IN (3,6)
              )
   )
,t2 AS (SELECT * FROM t WHERE lvl=9)
SELECT n1||n7||n4||' + '||n2||n8||n5||' = '||n3||n9||n6 FROM t2
UNION ALL
SELECT n1||n7||n5||' + '||n2||n8||n4||' = '||n3||n9||n6 FROM t2
UNION ALL
SELECT n1||n8||n4||' + '||n2||n7||n5||' = '||n3||n9||n6 FROM t2
UNION ALL
SELECT n1||n8||n5||' + '||n2||n7||n4||' = '||n3||n9||n6 FROM t2
;

newkid

原来你是自己实现了SORT MERGE JOIN, 这个交换位数恐怕用不上了，因为没有什么可以快速跳过的办法。

[ 本帖最后由 newkid 于 2010-6-15 05:09 编辑 ]

〇〇

来晚了，没有看到你的精彩解释
请教merge join的原理，我自己实现了都不知道...

4.8秒

1. 
   
2. #include <stdio.h>
   
3. #include <time.h>
   
4. unsigned short m1(unsigned short i)
   
5. {
   
6.         unsigned short a=i/0x1000%0x10+1;
   
7.         unsigned short b=i/0x100%0x10;
   
8.         unsigned short c=i/0x10%0x10;
   
9.         unsigned short d=i%0x10;
   
10.         unsigned short t=a;
    
11.         if(b==t)t=b+1;
    
12.         if(c==t)t=c+1;
    
13.         if(d==t)t=d+1;
    
14.         return t*0x1000;
    
15. }
    
16. unsigned short m(unsigned short in)
    
17. {
    
18.         int i,j;
    
19.         unsigned short t;
    
20.         char buf[13]={0};
    
21.         buf[in/0x1000%0x10]=1;
    
22.         buf[in/0x100%0x10]=1;
    
23.         buf[in/0x10%0x10]=1;
    
24.         buf[in%0x10]=1;
    
25.         t=0;//find highest digit
    
26.         for(i=in/0x1000%0x10;i<=0xc;i++)
    
27.         {
    
28.                 if(buf[i]==0)
    
29.                 {
    
30.                         t=i;
    
31.                         buf[i]=1;
    
32.                         break;
    
33.                 }
    
34.         }
    
35.         if(t==0)
    
36.         return 0xcba9;
    
37.         for(i=1,j=0;i<=0xc&&j<3;i++)//find other digit
    
38.         if(buf[i]==0)
    
39.         {t=(t<<4)+i;
    
40.         j++;
    
41.         }
    
42.         return t;
    
43. }
    
44. int main()
    
45. {
    
46.        
    
47. int i,j,k,r,t;
    
48. char buf[13];
    
49. char f[13];
    
50. unsigned short I[12*11*90];
    
51. unsigned short J[0xcbaa];
    
52. r=0;
    
53. /*
    
54. printf("%x:%x\n",0x7234,m(0x7234));
    
55. printf("%x:%x\n",0x7235,m(0x7235));
    
56. printf("%x:%x\n",0x7238,m(0x7238));
    
57. printf("%x:%x\n",0x523a,m(0x523a));
    
58. printf("%x:%x\n",0x523b,m(0x523b));
    
59. printf("%x:%x\n",0x523c,m(0x523c));
    
60. return 1;
    
61. */
    
62. t=clock();
    
63. for(i=0x1234;i<=0xcba9;i++)
    
64. {
    
65. if ((i%0x10==0)||(i/0x10%0x10==0)||(i/0x100%0x10==0)||(i%0x10==0xd)||(i/0x10%0x10==0xd)||(i/0x100%0x10==0xd)||(i%0x10==0xf)||(i/0x10%0x10==0xf)||(i/0x100%0x10==0xf)||(i%0x10==0xe)||(i/0x10%0x10==0xe)||(i/0x100%0x10==0xe))
    
66. J[i]=r;
    
67. else
    
68. {
    
69. sprintf(buf,"%x",i);
    
70. if (buf[0]!=buf[1] && buf[0]!=buf[2] && buf[0]!=buf[3] && buf[1]!=buf[2] && buf[1]!=buf[3] && buf[2]!=buf[3] )
    
71. {
    
72. I[r]=i;
    
73. J[i]=r;
    
74. r++;
    
75. }
    
76. else
    
77. J[i]=r;
    
78. }
    
79. }
    
80. r=0;
    
81. for(i=0;i<J[0xcba9/2+1];i++)
    
82. {
    
83. for(j=J[m(I[i])];j<=J[0xcba9-I[i]];j++)
    
84. {
    
85. k=I[i]+I[j];
    
86. if ((k%0x10==0)||(k/0x10%0x10==0)||(k/0x100%0x10==0)||(k%0x10==0xd)||(k/0x10%0x10==0xd)||(k/0x100%0x10==0xd)||(k%0x10==0xf)||(k/0x10%0x10==0xf)||(k/0x100%0x10==0xf)||(k%0x10==0xe)||(k/0x10%0x10==0xe)||(k/0x100%0x10==0xe))continue;
    
87. sprintf(buf,"%x%x%x",I[i],I[j],k);
    
88. for(k=1;k<=12;k++)f[k]=0;
    
89. for(k=1;k<=12;k++)
    
90. if(++f[(buf[k-1]-'0'>0 && buf[k-1]-'0'<=9)?buf[k-1]-'0':buf[k-1]-'a'+10]>1)goto a;
    
91. r++;
    
92. a:
    
93. ;
    
94. }
    
95. }
    
96. t=clock()-t;
    
97. printf("%d,%d",r,t);
    
98. return 1;
    
99. }
    

复制代码

〇〇

1. 
   
2. SQL> set serverout on
   
3. SQL> create or replace procedure pc7
   
4.   2  as
   
5.   3     time_before BINARY_INTEGER;
   
6.   4     time_after BINARY_INTEGER;
   
7.   5     TYPE t_num IS TABLE OF PLS_INTEGER INDEX BY  PLS_INTEGER ;
   
8.   6     x t_num;
   
9.   7     --a t_num;
   
10.   8     b t_num;
    
11.   9     c PLS_INTEGER;
    
12. 10     c1 PLS_INTEGER;
    
13. 11     r PLS_INTEGER;
    
14. 12     t PLS_INTEGER;
    
15. 13     t1 PLS_INTEGER;
    
16. 14     l varchar(4);
    
17. 15  begin
    
18. 16  c:=0;
    
19. 17  time_before := DBMS_UTILITY.GET_TIME;
    
20. 18  for i in to_number('1234','fm0xxx')..to_number('cba9','fm0xxx') loop
    
21. 19  l:=to_char(i,'fm0xxx');
    
22. 20  if substr(l,1,1)<>substr(l,2,1)and
    
23. 21  substr(l,2,1)<>substr(l,3,1)and
    
24. 22  substr(l,3,1)<>substr(l,4,1)and
    
25. 23  substr(l,1,1)<>substr(l,3,1)and
    
26. 24  substr(l,2,1)<>substr(l,4,1)and
    
27. 25  substr(l,1,1)<>substr(l,4,1)and
    
28. 26  instr(l,0)=0 and instr(l,'d')=0 and instr(l,'e')=0 and instr(l,'f')=0 then
    
29. 27  c:=c+1;
    
30. 28  --if i<to_number('cba9','fm0xxx')/2 then
    
31. 29  --a(c):=i;
    
32. 30  --c1:=c;
    
33. 31  --end if;
    
34. 32  b(c):=i;
    
35. 33  x(i):=c;
    
36. 34  else
    
37. 35  x(i):=c;
    
38. 36  end if;
    
39. 37  end loop;
    
40. 38  r:=0;
    
41. 39  --dbms_output.put_line('c='||c||'c1='||c1||a(1)||b(1));
    
42. 40  FOR I IN 1 .. x(to_number('cba9','fm0xxx')/2) LOOP
    
43. 41  t:=mod(trunc(b(i)/4096),16)+1;
    
44. 42  t1:=mod(trunc(b(i)/256),16);
    
45. 43  if t1=t then
    
46. 44   t:=t1+1;
    
47. 45  end if;
    
48. 46  t1:=mod(trunc(b(i)/16),16);
    
49. 47  if t1=t then
    
50. 48   t:=t1+1;
    
51. 49  end if;
    
52. 50  t1:=mod(b(i),16);
    
53. 51  if t1=t then
    
54. 52   t:=t1+1;
    
55. 53  end if;
    
56. 54  t:=t*4096;
    
57. 55  FOR J IN x(t) .. x(to_number('cba9','fm0xxx')-b(i)) LOOP
    
58. 56  --if translate('123456789abc','$'||to_char(b(i),'fm0xxx')||to_char(b(j),'fm0xxx')||to_char(b(i)+b(j),'fm0xxx'),'$')is null then
    
59. 57  --dbms_output.put_line(to_char(b(i),'fm0xxx')||to_char(b(j),'fm0xxx')||to_char(b(i)+b(j),'fm0xxx'));
    
60. 58  --NULL;
    
61. 59  l:=to_char(b(i)+b(j),'fm0xxx');
    
62. 60  if substr(l,1,1)<>substr(l,2,1)and
    
63. 61  substr(l,2,1)<>substr(l,3,1)and
    
64. 62  substr(l,3,1)<>substr(l,4,1)and
    
65. 63  substr(l,1,1)<>substr(l,3,1)and
    
66. 64  substr(l,2,1)<>substr(l,4,1)and
    
67. 65  substr(l,1,1)<>substr(l,4,1)and
    
68. 66  instr(l,0)=0 and instr(l,'d')=0 and instr(l,'e')=0 and instr(l,'f')=0
    
69. 67  --length(translate('0def','$'||l,'$'))=4
    
70. 68  and length(translate(to_char(b(i),'fm0xxx'),'$'||l,'$'))=4
    
71. 69  and length(translate(to_char(b(j),'fm0xxx'),'$'||l,'$'))=4
    
72. 70  and length(translate(to_char(b(i),'fm0xxx'),'$'||to_char(b(j),'fm0xxx'),'$'))=4 then
    
73. 71  r:=r+1;
    
74. 72  --dbms_output.put_line(to_char(b(i),'fm0xxx')||to_char(b(j),'fm0xxx')||to_char(b(i)+b(j),'fm0xxx'));
    
75. 73  end if;
    
76. 74  end loop;
    
77. 75  --if r>=100 then
    
78. 76    --exit;
    
79. 77  --end if;
    
80. 78  end loop;
    
81. 79
    
82. 80  time_after := DBMS_UTILITY.GET_TIME;
    
83. 81  DBMS_OUTPUT.PUT_LINE ('output:'||(time_after - time_before)||'rows:'||r);
    
84. 82  end;
    
85. 83  /
    
86. 
    
87. 过程已创建。
    
88. 
    
89. 已用时间:  00: 00: 00.06
    
90. SQL> exec pc7;
    
91. output:9029rows:3408
    
92. 
    
93. PL/SQL 过程已成功完成。
    
94. 
    
95. 已用时间:  00: 01: 30.30
    

复制代码

〇〇

已用时间:  00: 00: 00.06
SQL> exec pc7;
output:9029rows:3408

PL/SQL 过程已成功完成。

已用时间:  00: 01: 30.30
SQL> alter procedure pc7 compile plsql_code_type=native;

过程已更改。

已用时间:  00: 00: 00.10
SQL> exec pc7;
output:8316rows:3408

PL/SQL 过程已成功完成。

已用时间:  00: 01: 23.16

newkid

sort merge join:
http://asktom.oracle.com/pls/ask ... ON_ID:3109440977616
你的连接条件仅有a.n<b.n，所以和他描述的不太一样。

我稍微改写了一下，奇怪的是答案比你多了很多：
WITH n AS (
   SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM<=15
   )
,t (n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,lvl,roundup) AS (
   SELECT n,0,0,0,0,0,0,0,0,0,0,0,1,0
     FROM n
    WHERE n<8
   UNION ALL
   SELECT t.n1
         ,DECODE(t.lvl,1 ,n.n,t.n2 )
         ,DECODE(t.lvl,2 ,n.n,t.n3 )
         ,DECODE(t.lvl,3 ,n.n,t.n4 )
         ,DECODE(t.lvl,4 ,n.n,t.n5 )
         ,DECODE(t.lvl,5 ,n.n,t.n6 )
         ,DECODE(t.lvl,6 ,n.n,t.n7 )
         ,DECODE(t.lvl,7 ,n.n,t.n8 )
         ,DECODE(t.lvl,8 ,n.n,t.n9 )
         ,DECODE(t.lvl,9 ,n.n,t.n10)
         ,DECODE(t.lvl,10,n.n,t.n11)
         ,DECODE(t.lvl,11,n.n,t.n12)
         ,t.lvl+1
         ,CASE t.lvl
          WHEN 5  THEN FLOOR((t.n4 +t.n5 )/16)
          WHEN 8  THEN FLOOR((t.n7 +t.n8 +t.roundup)/16)
          WHEN 11 THEN FLOOR((t.n10+t.n11+t.roundup)/16)
          ELSE t.roundup
          END
     FROM t,n
    WHERE n.n NOT IN (n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11)
          AND (t.lvl IN (3,6,9)
               OR (t.lvl=11 AND n.n = MOD(t.n10+t.n11+t.roundup,16) AND t.n3=t.n1+t.n2+FLOOR((t.n10+t.n11)/16))
               OR (t.lvl=10 AND n.n>t.n10)
               OR (t.lvl=8 AND n.n = MOD(t.n7+t.n8+t.roundup,16))
               OR (t.lvl=7 AND n.n>t.n7)
               OR (t.lvl=5 AND n.n = MOD(t.n4+ t.n5,16))
               OR (t.lvl=4 AND n.n>t.n4)
               OR (t.lvl=2 AND n.n - t.n1- t.n2 IN (0,1))
               OR (t.lvl=1 AND n.n>t.n1 AND n.n+t.n1<=15)
              )
   )
SELECT TO_CHAR(n1,'X')  ||TO_CHAR(n10,'X')||TO_CHAR(n7,'X')||TO_CHAR(n4,'X')
       ||' + '                          
       ||TO_CHAR(n2,'X')||TO_CHAR(n11,'X')||TO_CHAR(n8,'X')||TO_CHAR(n5,'X')
       ||' = '                          
       ||TO_CHAR(n3,'X')||TO_CHAR(n12,'X')||TO_CHAR(n9,'X')||TO_CHAR(n6,'X')  ------ 位数对调的其他组合略
  FROM t
WHERE lvl=12
      ;

位置的排列组合还可以更彻底，个、十、百还可以对调。