|
|
在这里再SHOW一下我死掉了的一个PLSQL解法。。。（结果已经不重要了）
--下面的这些脚本是程序实现的基础对象
--在包编译之前先运行
--1.该表存放用于构造数据的基本数据
--共计16行: C(0,5) + C(1,5) + C(2,5)
create table t1(c1 number(1),
c2 number(1),
c3 number(1),
c4 number(1),
c5 number(1));
--2.存放构造的所有可能的结果集
--这个结果集中，5*5方格中的每行最多不超过两个球
--每列不超过两个，以及第一三象限，第二四象限的斜线最多不超过两个球
--这三个条件在程序中判断;每行最多不超过两个球已经在构造中成立。
create table t2(cid number, --标记行的序号关键字
csum number, --存25个单元格中球的总数
c11 number(1), --单元格: 0表示没有球，1表示放了一个球
c12 number(1),
c13 number(1),
c14 number(1),
c15 number(1),
c21 number(1),
c22 number(1),
c23 number(1),
c24 number(1),
c25 number(1),
c31 number(1),
c32 number(1),
c33 number(1),
c34 number(1),
c35 number(1),
c41 number(1),
c42 number(1),
c43 number(1),
c44 number(1),
c45 number(1),
c51 number(1),
c52 number(1),
c53 number(1),
c54 number(1),
c55 number(1));
create unique index pk_t2 on t2(cid);
--3.存储5*5方格中元素的坐标
create type typ_xy as object(x number(1),
y number(1));
/
--4.函数返回引用的对象
create or replace type t_record is table of typ_xy;
/
--5.记录最终的满足所有条件的表T2中的行关键字ID
create table T3
(
A NUMBER
);
create or replace package pkg_ball
is
procedure sp_single_row;
procedure sp_all_combination;
function fn_return_x(p_row pls_integer,p_column pls_integer)
return t_record pipelined;
function fn_return_y(p_row pls_integer,p_column pls_integer)
return t_record pipelined;
function fn_return_13(p_row pls_integer,p_column pls_integer)
return t_record pipelined;
function fn_return_24(p_row pls_integer,p_column pls_integer)
return t_record pipelined;
function fn_location_ball(p_cid number)
return t_record pipelined;
procedure sp_process;
procedure sp_output;
procedure sp_main;
end;
/
create or replace package body pkg_ball
is
--该过程将5*5图形中的单行中不能超过两个球的组合插入表T1
--共计16行: C(0,5) + C(1,5) + C(2,5)
procedure sp_single_row
is
type t_num is array(5) of number;
l_array t_num := t_num();
l_start_time number := 0;
l_end_time number := 0;
begin
l_start_time := dbms_utility.get_time;
--1.初始化一维数组
for i in 1..5 loop
l_array.extend;
l_array(i) := 0;
end loop;
--2.初始化临时结果表
execute immediate 'truncate table t1';
--3.一个球也不选的行记录结果插入表T1
insert into t1 values(l_array(1),l_array(2),l_array(3),l_array(4),l_array(5));
commit;
--4. 五选一即只选取一个球的行记录结果插入表T1
for j in 1..5 loop
for i in 1..5 loop
if i=j then
l_array(j) := 1;
else
l_array(i) := 0;
end if;
end loop;
insert into t1 values(l_array(1),l_array(2),l_array(3),l_array(4),l_array(5));
end loop;
commit;
--5.五选二的所行组合
for k in 1..5 loop
for j in k+1..5 loop
for i in 1..5 loop
if i=k then
l_array(k) := 1;
elsif i=j then
l_array(j) := 1;
else
l_array(i) := 0;
end if;
end loop;
insert into t1 values(l_array(1),l_array(2),l_array(3),l_array(4),l_array(5));
end loop;
end loop;
commit;
l_end_time := dbms_utility.get_time;
dbms_output.put_line('Elipse time :'||(l_end_time - l_start_time)/100);
exception when others then
raise;
end;
--因原始图形是5*5方格,在先不考虑列与斜线都不超过2个球的的情况下,
--那么5个行的所以组合可以采用join T1表的方法得到,结果T2表就有
--power(16,5)= 1048576行
procedure sp_all_combination
is
c_commit_rec constant smallint := 10000;
l_ins_counter number := 0;
l_start_time number := 0;
l_end_time number := 0;
type target_typ is table of t2%rowtype;
l_target target_typ;
l_limit number := 5000;
cursor cur is
select rownum cid,
a.c1+a.c2+a.c3+a.c4+a.c5+b.c1+b.c2+b.c3+b.c4+b.c5+c.c1+c.c2+c.c3+c.c4
+c.c5+d.c1+d.c2+d.c3+d.c4+d.c5+e.c1+e.c2+e.c3+e.c4+e.c5 csum,
a.c1 c11,
a.c2 c12,
a.c3 c13,
a.c4 c14,
a.c5 c15,
b.c1 c21,
b.c2 c22,
b.c3 c23,
b.c4 c24,
b.c5 c25,
c.c1 c31,
c.c2 c32,
c.c3 c33,
c.c4 c34,
c.c5 c35,
d.c1 c41,
d.c2 c42,
d.c3 c43,
d.c4 c44,
d.c5 c45,
e.c1 c51,
e.c2 c52,
e.c3 c53,
e.c4 c54,
e.c5 c55
from t1 a,
t1 b,
t1 c,
t1 d,
t1 e;
begin
execute immediate 'truncate table t2';
l_start_time := dbms_utility.get_time;
open cur;
loop
fetch cur bulk collect into l_target limit l_limit;
exit when l_target.count = 0;
forall i in l_target.first .. l_target.last
insert into t2 values l_target(i);
l_ins_counter := l_ins_counter + l_target.count;
if l_ins_counter >= c_commit_rec then
commit;
l_ins_counter :=0;
end if;
end loop;
commit work;
close cur;
l_end_time := dbms_utility.get_time;
dbms_output.put_line('Elipse time :'||(l_end_time - l_start_time)/100);
exception when others then
raise;
end sp_all_combination;
--这里只是为了完整性引入,后面程序没有引用
--因为每行最多不超过两个球已经在构造中成立,行数据不需要检测
--返回元素A[i][j]相同的行的元素坐标
function fn_return_x(p_row pls_integer,p_column pls_integer)
return t_record pipelined
is
l_xy typ_xy;
l_exception exception;
begin
if p_column > 0 and p_column < 6 and p_row > 0 and p_row < 6 then
for i in 1..5 loop
l_xy := typ_xy(p_row,i);
pipe row(l_xy);
end loop;
else
raise l_exception;
end if;
return;
exception when l_exception then
raise;
end;
--返回元素A[i][j]相同的列的元素坐标,包括自已
function fn_return_y(p_row pls_integer,p_column pls_integer)
return t_record pipelined
is
l_xy typ_xy;
l_exception exception;
begin
if p_column > 0 and p_column < 6 and p_row > 0 and p_row < 6 then
for i in 1..5 loop
l_xy := typ_xy(i,p_column);
pipe row(l_xy);
end loop;
else
raise l_exception;
end if;
return;
exception when l_exception then
raise;
end;
--返回元素A[i][j]第一第三象限的对角线元素的元素坐标,包括自已
function fn_return_13(p_row pls_integer,p_column pls_integer)
return t_record pipelined
is
l_xy typ_xy;
l_exception exception;
i pls_integer := 0;
j pls_integer := 0;
begin
if p_column > 0 and p_column < 6 and p_row > 0 and p_row < 6 then
--第一象限对角线元素
i := p_row;
j := p_column;
--把自已加进去先
l_xy := typ_xy(i,j);
pipe row(l_xy);
loop
exit when i-1<=0 or j+1 >=6;
i:=i-1;
j:=j+1;
l_xy := typ_xy(i,j);
pipe row(l_xy);
end loop;
--第三象限对角线元素
i := p_row;
j := p_column;
loop
exit when i+1>=6 or j-1 <=0;
i:=i+1;
j:=j-1;
l_xy := typ_xy(i,j);
pipe row(l_xy);
end loop;
else
raise l_exception;
end if;
return;
exception when l_exception then
raise;
end;
--返回元素A[i][j]第二第四象限的对角线元素的元素坐标,包括自已
function fn_return_24(p_row pls_integer,p_column pls_integer)
return t_record pipelined
is
l_xy typ_xy;
l_exception exception;
i pls_integer := 0;
j pls_integer := 0;
begin
if p_column > 0 and p_column < 6 and p_row > 0 and p_row < 6 then
--第二象限对角线元素
i := p_row;
j := p_column;
--把自已加进去先
l_xy := typ_xy(i,j);
pipe row(l_xy);
loop
exit when i-1<=0 or j-1 <=0;
i:=i-1;
j:=j-1;
l_xy := typ_xy(i,j);
pipe row(l_xy);
end loop;
--第四象限对角线元素
i := p_row;
j := p_column;
loop
exit when i+1>=6 or j+1 >=6;
i:=i+1;
j:=j+1;
l_xy := typ_xy(i,j);
pipe row(l_xy);
end loop;
else
raise l_exception;
end if;
return;
exception when l_exception then
raise;
end;
--判断T2中的行数据中值为1的元素在5*5方阵中的坐标位置
--也就是判断结果集中哪些位置上放了球
function fn_location_ball(p_cid number)
return t_record pipelined
is
l_xy typ_xy;
l_stmt varchar2(200) := null;
l_value number(1) := 0;
begin
for i in 1..5 loop
for j in 1..5 loop
l_stmt := 'select '||'c'||i||j||' from t2 where cid ='||p_cid;
execute immediate l_stmt into l_value;
if l_value = 1 then
l_xy := typ_xy(i,j);
pipe row(l_xy);
end if;
end loop;
end loop;
return;
exception when others then
raise;
end;
--按球放的多少,由大到小扫描,直到有一条满足条件
--将该组扫描完即可,总球数较小的分组就不用再扫描
procedure sp_process
is
l_max number := 0;
l_min number := 0;
l_col_string1 varchar2(200) := null;
l_col_string2 varchar2(200) := null;
l_col_string3 varchar2(200) := null;
l_stmt1 varchar2(200) := null;
l_stmt2 varchar2(200) := null;
l_stmt3 varchar2(200) := null;
l_value1 number(1) := 0;
l_value2 number(1) := 0;
l_value3 number(1) := 0;
l_counter number := 0;
l_total number := 0;
type t_cell is table of number;
l_cell_x t_cell;
l_cell_y t_cell;
l_cell_x1 t_cell;
l_cell_y1 t_cell;
l_cell_x2 t_cell;
l_cell_y2 t_cell;
l_cell_x3 t_cell;
l_cell_y3 t_cell;
l_start_time number := 0;
l_end_time number := 0;
begin
l_start_time := dbms_utility.get_time;
execute immediate 'truncate table t3';
select max(csum),min(csum) into l_max,l_min from t2;
<<set_loop>>
--按总球数由大到小进行分组扫描
for i in reverse l_min..l_max loop
exit when l_total >=1;
<<row_loop>>
for j in (select cid from t2 where csum = i) loop
--记录合格的cell元素个数
l_counter := 0;
select x,y bulk collect into l_cell_x,l_cell_y
from table(pkg_ball.fn_location_ball(j.cid));
if l_cell_x.count > 1 then
<<cell_loop>>
for k in l_cell_x.first..l_cell_x.last loop
l_value1 := 0;
l_value2 := 0;
l_value3 := 0;
--同列元素和不能大于2
begin
select x,y bulk collect into l_cell_x1,l_cell_y1
from table(pkg_ball.fn_return_y(l_cell_x(k),l_cell_y(k)));
if l_cell_x1.count > 1 then
for rec1 in l_cell_x1.first..l_cell_x1.last loop
l_col_string1 := l_col_string1||'c'||l_cell_x1(rec1)||l_cell_y1(rec1)||'+';
end loop;
l_col_string1 := substr(l_col_string1,1,length(l_col_string1)-1);
l_stmt1 := 'select '||l_col_string1||' from t2 where cid ='||j.cid;
execute immediate l_stmt1 into l_value1;
end if;
l_col_string1 := null;
l_stmt1 := null;
exit when l_value1 >2;
end;
--第一三象限斜线元素和不能大于2
begin
select x,y bulk collect into l_cell_x2,l_cell_y2
from table(pkg_ball.fn_return_13(l_cell_x(k),l_cell_y(k)));
if l_cell_x2.count > 1 then
for rec2 in l_cell_x2.first..l_cell_x2.last loop
l_col_string2 := l_col_string2||'c'||l_cell_x2(rec2)||l_cell_y2(rec2)||'+';
end loop;
l_col_string2 := substr(l_col_string2,1,length(l_col_string2)-1);
l_stmt2 := 'select '||l_col_string2||' from t2 where cid ='||j.cid;
execute immediate l_stmt2 into l_value2;
end if;
l_col_string2 := null;
l_stmt2 := null;
exit when l_value2 >2;
end;
--第二四象限斜线元素和不能大于2
begin
select x,y bulk collect into l_cell_x3,l_cell_y3
from table(pkg_ball.fn_return_24(l_cell_x(k),l_cell_y(k)));
if l_cell_x3.count > 1 then
for rec3 in l_cell_x3.first..l_cell_x3.last loop
l_col_string3 := l_col_string3||'c'||l_cell_x3(rec3)||l_cell_y3(rec3)||'+';
end loop;
l_col_string3 := substr(l_col_string3,1,length(l_col_string3)-1);
l_stmt3 := 'select '||l_col_string3||' from t2 where cid ='||j.cid;
execute immediate l_stmt3 into l_value3;
end if;
l_col_string3 := null;
l_stmt3 := null;
exit when l_value3 >2;
end;
--三个条件都OK,则合格单元数加1
l_counter :=l_counter + 1;
end loop cell_loop;
end if;
if l_counter = i then
insert into t3 values (j.cid);
commit;
end if;
end loop row_loop;
select count(*) into l_total from t3;
end loop set_loop;
l_end_time := dbms_utility.get_time;
dbms_output.put_line('Elipse time :'||(l_end_time - l_start_time)/100);
exception when others then
raise;
end;
--格式化输出结果
procedure sp_output
is
cursor cur_output is
select rownum output_id,
output
from (
select
c11||c12||c13||c14||c15||
c21||c22||c23||c24||c25||
c31||c32||c33||c34||c35||
c41||c42||c43||c44||c45||
c51||c52||c53||c54||c55 as output
from t2
where cid in (select * from t3)
order by 1 desc
);
begin
for rec in cur_output loop
dbms_output.put_line(lpad(rec.output_id,2,' ')||' '||rec.output);
end loop;
end;
--主执行程序
procedure sp_main
is
begin
--初始化表T1
sp_single_row;
--利用T1构造T2表,得到所有可能的组合
sp_all_combination;
--对T2中的行进行分组,并逐行判断,符合的结果行ID插入T3表
sp_process;
--按要求格式化输出结果
sp_output;
end;
end pkg_ball;
/
三：执行步骤
根据提交的脚本依次执行
SQL> create_objects.sql;
SQL> start create_package.sql;
SQL> set serveroutput on size 1000000;
SQL> set timing on;
SQL> exec pkg_ball.sp_main;
SQL> start drop_all.sql;
最后一步清理垃圾
四：参赛测试结果(答案共计92组)
dev)/backup>sqlplus /nolog
SQL*Plus: Release 9.2.0.4.0 - Production on Thu Mar 3 16:10:48 2011
Copyright (c) 1982, 2002, Oracle Corporation. All rights reserved.
SQL> conn hr/hr
Connected.
SQL> start create_objects.sql;
Table created.
Table created.
Index created.
Type created.
Type created.
Table created.
SQL> start create_package.sql;
Package created.
Package body created.
SQL> set serveroutput on size 1000000;
SQL> set timing on;
SQL> exec pkg_ball.sp_main;
Elipse time :.09
Elipse time :232.86
Elipse time :2351.83
1 1100010010000110110000101
2 1100001010100010010100110
3 1100000110100010110000011
4 1100000011011001000100110
5 1010011000000110100100110
6 1010010010010100100100101
7 1010001001010101000100110
8 1010001001000111100000110
9 1010000110110000100100011
10 1010000101110000001101010
11 1010000101100010101001010
12 1010000101010010101010010
13 1010000011110000001101100
14 1010000011011001000101010
15 1010000011010101100000101
16 1001010100001010100101010
17 1001001100100010010101010
18 1001001010100010010101100
19 1001001010010010010110100
20 1001000110100010110001001
21 1001000101101000100101010
22 1000101100000111100000110
23 1000100110110000001101100
24 0110010100100010101000011
25 0110010010110000001100101
26 0110010001101000001101010
27 0110010001010101001000101
28 0110010001001101100000011
29 0110010001001011001001010
30 0110010001000111100000110
31 0110000101100011001001010
32 0110000101100010101010010
33 0110000011110001001000101
34 0110000011110001000100110
35 0110000011110000011010001
36 0110000011110000001110100
37 0110000011101001000101010
38 0101011000001011000100110
39 0101011000000111010000101
40 0101010100100010011001001
41 0101010010101000010101001
42 0101010010100010010101100
43 0101010010001011010001001
44 0101010010001011000101100
45 0101010001101000001101100
46 0101010001011000001110100
47 0101010001001101100000101
48 0101010001001011100000110
49 0101001010100011010000101
50 0101001010100010010110100
51 0101001001101001000100110
52 0101001001101000010110010
53 0101001001100011010000110
54 0101001001001011010010010
55 0101000101100010110010010
56 0101000011110000010110100
57 0101000011101001000101100
58 0100110100001011001001010
59 0100101100100010011010010
60 0100101010100101010000101
61 0100101010100011010000110
62 0100100110100011010001010
63 0100100101101001001001010
64 0011011000001011000101010
65 0011011000000111100000101
66 0011011000000111000101100
67 0011011000000110110010001
68 0011011000000110100110100
69 0011010100100010101001001
70 0011010100100010100101010
71 0011010001110000001101100
72 0011010001101000100101010
73 0011010001011000001111000
74 0011010001010100100110100
75 0011010001001011100001010
76 0011001001000111100010100
77 0011000101100010101011000
78 0010111000010100001110100
79 0010111000001101000101010
80 0010111000000111100000110
81 0010110100100100101001001
82 0010110100100010101001010
83 0010110100000111100001010
84 0010110010110000001101100
85 0010110010010101000101100
86 0010101100000111001011000
87 0010101001010101001010100
88 0010100011110001001001100
89 0001111000001101000101100
90 0001101100100010011011000
91 0001101010100011010001100
92 0001101001110000011010100
PL/SQL procedure successfully completed.
drop table t1;
drop table t2;
drop table t3;
drop type t_record;
drop type typ_xy;
drop package pkg_ball;
[[i] 本帖最后由 〇〇 于 2011-3-16 10:38 编辑 [/i]] |
|
楼主: ~贝贝~
IP卡
狗仔卡
发表于 2011-3-16 10:09
显身卡
发表于 2011-3-16 10:13
