PUZZLEUP 2015

〇〇

solomon_007 发表于 2015-9-17 10:15
#8
暴力解法: 最大 6021
SQL> with t as (select level-1 n from dual connect by level

r表的2 4 3怎么来的

〇〇

〇〇 发表于 2015-9-17 10:59
r表的2 4 3怎么来的

知道了，不可能1 4 5，因为4位数进位必须是999x,进完后一定是1000x,不符合题意

solomon_007

〇〇 发表于 2015-9-17 10:59
r表的2 4 3怎么来的

对于每一个10位的数字串, 分割成A, B, C三个数;
经过分析,A+ B = C   这里面 C 最大只可能是个4位数, 因为假如C是5位及以上的数,那么A和B的总长度就小于等于5, 又因为A或B至少占1位,那么A,B的可能就是2和3位数,或1位和4位数, 最大的4位数(数字不重复)9876,
和一个个位数的和不可能达到5位数;2和3位数的情况就更明显其和也不可能达到5位数, 所以 C的长度<=4,所以对于A, B的长度,也只可能是2,3,4中选择.又 总长度为10, 所以 C要取最大值的可能,那么A, B, C只能是:
2,4,4    4,2,4 和 3 ,3 4

solomon_007

前面有一行 4,2,2 写错了,应该是 4,2,4

SQL> with t as (select level-1 n from dual connect by level <=10),
  2      t1 as (
  3  select str,to_number(substr(str,1,a)) a,to_number(substr(str,a+1,b)) b, to_number(substr(str,a+b+1,c)) c
  4    from (
  5          select replace(sys_connect_by_path(n,','),',','') str
  6            from t
  7           where level = 10
  8          connect by nocycle prior n <> n
  9         ) s,
10         (select 2 a,4 b, 4 c from dual
11           union all
12          select 4,2,4 from dual
13           union all
14          select 3,3,4 from dual
15         ) r
16   where to_number(substr(str,1,a)) + to_number(substr(str,a+1,b)) =  to_number(substr(str,a+b+1,c))
17  )
18  select *
19    from t1
20   where c = (select max(c) from t1)
21  /
STR                                                                                       A          B          C
-------------------------------------------------------------------------------- ---------- ---------- ----------
3459876021                                                                               34       5987       6021
3759846021                                                                               37       5984       6021
4359786021                                                                               43       5978       6021
4859736021                                                                               48       5973       6021
5934876021                                                                             5934         87       6021
5937846021                                                                             5937         84       6021
5943786021                                                                             5943         78       6021
5948736021                                                                             5948         73       6021
5973486021                                                                             5973         48       6021
5978436021                                                                             5978         43       6021
5984376021                                                                             5984         37       6021
5987346021                                                                             5987         34       6021
7359486021                                                                               73       5948       6021
7859436021                                                                               78       5943       6021
8459376021                                                                               84       5937       6021
8759346021                                                                               87       5934       6021
16 rows selected

lastwinner

newkid 发表于 2015-9-10 23:07
明白了，有点像以前那个猜数游戏，但是回馈信息太少了所以步骤将会很多。要证明一种策略是最少步骤是很困 ...

不需要证明最少，只需要说明最多XX步一定可以猜出就行了

lastwinner

lugionline 发表于 2015-9-11 16:23
这是其中一个，整数规划出来的,20分钟，不过我一开始假定了有一个 DCBA ，如果不假定，2个小时都没结果

...

“一开始假定了有一个 DCBA”是什么意思？
相当于给了一个start with的起点？

lastwinner

solomon_007 发表于 2015-9-17 13:37
前面有一行 4,2,2 写错了,应该是 4,2,4

SQL> with t as (select level-1 n from dual connect by level

分析不错，其实就8个可能

lugionline

lastwinner 发表于 2015-9-17 13:46
“一开始假定了有一个 DCBA”是什么意思？
相当于给了一个start with的起点？

就是最小的覆盖集中有一个元素是DCBA

lastwinner

lugionline 发表于 2015-9-17 14:20
就是最小的覆盖集中有一个元素是DCBA

不论排列，根据数字对称性，可将最基本的数字组合模型表述为以下五种
AAAA、AAAB、AABB、AABC、ABCD

每种的排列数为
AAAA：4
AAAB：(4*3)*4=48
AABB：(4*3)*6/2=36   （AA和BB对称，所以除以2）
AABC：(4*3*2)*12/2=144 （BC对称，所以除以2）
ABCD：4*3*2*1=24


AAAB是可以涵盖AAAA的情况的，反之亦然
显然，取{AAAA, AABB, ABCD}的全集，是一定可以覆盖到{AAAB, AABC}的全集的
现在问题就变成，如何在{AAAA, AABB, ABCD}中找到一个最小的子集
这样计算量就可以大幅降低了

这样的结果可能并不是最优的，那得到的结果集假定为X1，那么可从{AAAB, AABC}中寻找，是否存在有一个元素可以替换到X1的两个或两个以上的元素，若有则替换之，得到的结果集X2再次做迭代，直到找不到更多可替换的元素为止
————————————————————————————————
当然，这个方法也许无法找出最优的结果集，毕竟先就排除了{AAAB, AABC}，后续再通过找元素替换，也无法涵盖所有的可能性，例如找出三个元素来替换X1中的四个或四个以上的元素。这些情况无法完全枚举。

不过倒是可以试一试看看

lugionline

lastwinner 发表于 2015-9-17 15:29
不论排列，根据数字对称性，可将最基本的数字组合模型表述为以下五种
AAAA、AAAB、AABB、AABC、ABCD

AAAB是可以涵盖AAAA的情况的

这个显然不对，比方 BAAA 可以被 AAAA覆盖，但是不能被 AAAB覆盖

关于对称性的问题我也考虑过了，理论上我只要每次假定一种，然后每次花20分钟，只要所有可能的情况都算过，那就可以知道结果了，但是那天我刚好出去玩了，所以我宁愿让它跑上一天得到一个结果而不是一个个去试