Puzzleup 2010 比赛快开始了，大家用SQL解答啊

nlrte13 · 发表于 2010-9-24 18:10

需要这么麻烦吗？
简单的推理就可以算出来^^
何必整这么乱七八糟的程序呢

newkid · 发表于 2010-9-24 21:40

原帖由 nlrte13 于 2010-9-24 18:10 发表
需要这么麻烦吗？
简单的推理就可以算出来^^
何必整这么乱七八糟的程序呢

你有更简单的方法就贴出来嘛？
我那个方法用纸笔也可以完成，之所以用SQL是为了锻炼自己。
最后凑出d10~d1的过程，数值从大到小排列是个充分非必要条件，这也是可以推理的，因此可以把19～1从左边开始逐个去掉，很快就能试出来。

lastwinner · 发表于 2010-9-24 21:51

原帖由 nlrte13 于 10-9-24 18:10 发表
需要这么麻烦吗？
简单的推理就可以算出来^^
何必整这么乱七八糟的程序呢

一个乐子而已嘛

说说看你是怎么推理的？

btw：欢迎来到Oracle开发版，一个潜水4年的老会员^_^

lastwinner · 发表于 2010-9-25 00:25

with t10 as (select 0-rownum a10 from dual connect by rownum<=23),
t9 as (select rownum-1 a9 from dual connect by rownum<=28),t8 as (select rownum-1 a8 from dual connect by rownum<=15),
t7 as (select rownum-1 a7 from dual connect by rownum<=11),t6 as (select rownum-1 a6 from dual connect by rownum<=9),
t5 as (select rownum-1 a5 from dual connect by rownum<=8),t4 as (select rownum-1 a4 from dual connect by rownum<=7)
select  a10, a9, a8, a7, a6, a5, a4, a10+a9+a8+a7+a6+a5+a4 Q,
      rank()over(order by a10+a9+a8+a7+a6+a5+a4 asc, a10 desc, a9 desc, a8 desc, a7 desc) rk from t10, t9, t8, t7, t6, t5, t4
where 19*a10+17*a9+15*a8+13*a7+11*a6+9*a5+7*a4=22
and a9>=a8 and a8>=a7 and a7>=a6 and a6>=a5 and a5>=a4
/

A10    A9    A8    A7    A6    A5    A4    Q    RK
------ ------ ------ ------ ------ ------ ------ ------ ------
-3    3    1    1    0    0    0    2    1
-4    4    2    0    0    0    0    2    2
-5    6    1    0    0    0    0    2    3
-6    8    0    0    0    0    0    2    4
-5    2    2    2    1    1    1    4    5
-6    3    3    1    1    1    1    4    6
-7    5    2    1    1    1    1    4    7
-7    4    2    2    2    1    0    4    8
-7    3    3    3    1    1    0    4    9
-8    7    1    1    1    1    1    4    10
-8    4    4    2    1    1    0    4    11

A10    A9    A8    A7    A6    A5    A4    Q    RK
------ ------ ------ ------ ------ ------ ------ ------ ------
-8    4    3    3    2    0    0    4    12
-9    6    3    2    1    1    0    4    13
-9    5    5    1    1    1    0    4    14
-9    5    4    2    2    0    0    4    15
-10    8    2    2    1    1    0    4    16
-10    7    4    1    1    1    0    4    17
-10    7    3    2    2    0    0    4    18
-10    6    4    3    1    0    0    4    19
-10    5    5    4    0    0    0    4    20
-11    9    3    1    1    1    0    4    21
-11    9    2    2    2    0    0    4    22

A10    A9    A8    A7    A6    A5    A4    Q    RK
------ ------ ------ ------ ------ ------ ------ ------ ------
-11    8    3    3    1    0    0    4    23
-11    7    5    2    1    0    0    4    24
-11    7    4    4    0    0    0    4    25
-11    6    6    3    0    0    0    4    26
-12    11    2    1    1    1    0    4    27
-12    9    4    2    1    0    0    4    28
-12    8    6    1    1    0    0    4    29
-12    8    5    3    0    0    0    4    30
-12    7    7    2    0    0    0    4    31
-13    13    1    1    1    1    0    4    32
-13    11    3    2    1    0    0    4    33
..............
-23    8    7    7    6    6    1    12 566
-23    8    6    6    6    6    5    14 568

已选择568行。

已用时间:  00: 00: 07.78

可知最小的Q为2，共有4种方案可选
任选其中一种，代入到
{x20,x19,x18,...x1}={212,19,18,...1}
然后除去x8～x13中任意五个数，再计算即可得到3540。

newkid给出了三种，我给出了一种，正好将这四种情况都覆盖到了
注意，newkid列出的那三种情况是按d给出的，即差值
我这里求的是a，是与最初设定的xn的偏移量，对xn作修正用的

nlrte13 · 发表于 2010-9-25 09:40

原帖由 lastwinner 于 2010-9-24 21:51 发表

一个乐子而已嘛
说说看你是怎么推理的？

btw：欢迎来到Oracle开发版，一个潜水4年的老会员^_^

哈哈，不知不觉的，都4年过去了，怀念曾经年少轻狂的日子呀。
话说，前辈都已经在此霸版8年之久了啊。。。

简单说说我的“策略”吧
对于20数的情况，
19A + 17B + 15C + 13D + 11E + 9F + 7G +5H + 3I + J -
K - 3L - 5M - 7N - 9O - 11P - 13Q - 15R - 17S -19T = 5000                   ---------1
对于15数，有
14A + 12B + 10C + 8D + 6E + 4F + 2G - 2N - 4O - 6P - 8Q - 10R - 12S - 14T = ?                ------------2
两算式之差为
5A + 5B + 5C + 5D + 5E + 5F + 5G + ( 5H + 3I + J - K - 3L - 5M ) -
5N - 5O - 5P - 5Q - 5R - 5S - 5T = ?    -------------3

欲使3式最小，可令 5A 到 5G 部分尽可能小，亦可令 -5N 到 -5T 部分尽可能大，亦或二者皆为之。
另由1式知，3式的 5A 到 5G 部分与 -5N 到 -5T 部分变换对等，且 5H 到 -5M 部分的内变换对结果值无影响。
所以可简化为求
A + B + C + D + E + F + G       -----------4
的最小值。

尝试
20（A），19（B），18，17，16，15，14，13，12，11，10，9，8，7，6，5，4，3，2，1
A增量193的情况，1式 = 4997，
要使 A = 20 + 193 减小，而令 B + C + D + E + F + G 增大，使1式 = 5000，
由于A的系数19，大于 BCDEFG 的系数，
那么总增量必然大于 193，
容易得到
20+193-7（A），19+8（B），18，17，16，15，14，13，12，11，10，9，8，7，6，5，4，3，2，1
这个结果，
总增量194（大于193的最小数），即为所求。
由此，得到2式结果为3540，即为最大值。

nlrte13 · 发表于 2010-9-25 09:57

前一题就更简单啦
26 + 26 * 25 / 2 * 4 + 26 * 25 * 24 / 2 / 3 * 5 * 3 + 26 * 25 * 24 * 23 / 2 / 3 / 4 * 8 =
26 + 1300 + 39000 + 119600 =
159926

始终觉得，思想，方法，才是最重要的，编程，只是个实现手段啦~ ^^