Euler Project 挨个做- 之三 (Q79-?)

tree_new_bee

先用excel来模拟做下题目中的示例：
131        673        234        103        18
201        96        342        965        150
630        803        746        422        111
537        699        497        121        956
805        732        524        37        331

第一步， 假设只能向右向下，用Q81的方法找出最短路径和，得到如下的值：
131        804        1038        1141        1159
332        428        770        1735        1309
962        1231        1516        1938        1420
1499        1930        2013        2059        2376
2304        2662        2537        2096        2427

然后， 按顺序检查每个单元格的下右单元，如果比原来加的值小， 则该单元需要修改。 修改后，用第一步的方法让后续节点全部更新。
这样， 找到了(1,3)单元，该单元下方的770小于左方的804, 所以将(1,3)的1038更新成770+234=1004, 然后将这个点右下方的所有点更新一遍，成为：
131        804        1004        1107        1125
332        428        770        1735        1275
962        1231        1516        1938        1386
1499        1930        2013        2059        2342
2304        2662        2537        2096        2427

然后，我们继续检查，发现(4,3)的右侧比较小， 所以同上一样进行更新， 更新后又可以发现(5,3)的右边比较小，继续更新， 最后：

131        804        1004        1107        1125
332        428        770        1735        1275
962        1231        1516        1808        1386
1499        1930        2013        1929        2342
2304        2662        2490        1966        2297

这样，最终结果为2297， 与示例中红色字加起来的结果相同。

newkid

tree_new_bee 发表于 2012-2-18 08:44
说起来简单，是因为有以前的基础。这问题与q15思路一样，都是找到到每一个点的最小路径。只是15中每段路的 ...

我没细看，以为你只是比较单元里的两个数，如果比较的是两条路径那就没问题了。

vicky987654321

GOOD！

〇〇

tree_new_bee 发表于 2012-2-17 23:09
81,82,83是一个系列的， 只是难度越来越大。

Q81本身很简单， 就是处理这个文件麻烦点，不过处理好了， ...

和前面的三角塔一个思路
http://www.itpub.net/thread-1377410-2-1.html
92楼

〇〇

90题,
立方体数字对

在一个立方体的六个面上分别标上不同的数字（从0到9），对另一个立方体也如法炮制。将这两个立方体按不同的方向并排摆放，我们可以得到各种各样的两位数。

例如，平方数64可以通过这样摆放获得：



事实上，通过仔细地选择两个立方体上的数字，我们可以摆放出所有小于100的平方数：01、04、09、16、25、36、49、64和81。

例如，其中一种方式就是在一个立方体上标上{0, 5, 6, 7, 8, 9}，在另一个立方体上标上{1, 2, 3, 4, 8, 9}。

在这个问题中，我们允许将标有6或9的面颠倒过来互相表示，只有这样，如{0, 5, 6, 7, 8, 9}和{1, 2, 3, 4, 6, 7}这样本来无法表示09的标法，才能够摆放出全部九个平方数。

在考虑什么是不同的标法时，我们关注的是立方体上有哪些数字，而不关心它们的顺序。

{1, 2, 3, 4, 5, 6}等价于{3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6}不同于{1, 2, 3, 4, 5, 9}

但因为我们允许在摆放两位数时将6和9颠倒过来互相表示，这个例子中的两个不同的集合都可以代表拓展集{1, 2, 3, 4, 5, 6, 9}。

对这两个立方体有多少中不同的标法可以摆放出所有的平方数？

〇〇

90题不知错在哪
with t as(select l from (select level-1 l from dual connect by level<=9)where l not in(7,9)),
t1(a,b,lv) as(select power(2,a.l),power(2,b.l),1 from t a,t b where a.l<b.l and a.l||b.l
in('01','04','06','16','25','36','46','18')
union all
select a+power(2,a.l),b+power(2,b.l),lv+1 from t a,t b ,t1 where a.l<b.l and a.l||b.l
in('01','04','06','16','25','36','46','18') and bitand(a,power(2,a.l))=0 and bitand(b,power(2,b.l))=0
and lv<6)
select count(*) from t1 where lv=6;

〇〇

〇〇 发表于 2016-11-30 11:22
90题不知错在哪
with t as(select l from (select level-1 l from dual connect by level

明白了,错得很多,
1 不是只允许出现平方中包含的数字
2 不是每步加入的都要有新平方数
实际上最后判断就够了

〇〇

〇〇 发表于 2016-11-30 11:57
明白了,错得很多,
1 不是只允许出现平方中包含的数字
2 不是每步加入的都要有新平方数

凑了半天,终于出结果了,很难看,主要是应付6,9可以互换
with t as(select level-1 l from dual connect by level<=10),
t1(a,p,lv) as(select l,power(2,l),1 from t
union all
select l,p+power(2,l),lv+1 from t1,t where a<l and lv<6),
a as(select p pa from t1 where lv=6),
b as(select pa pb from a),
s as(select power(2,substr('0104061625364618',level*2-1,1))s1,
power(2,substr('0104061625364618',level*2,1))s2 from dual connect by level<=8),
j as(select pa,pb from a,b where pa<pb and not exists(select 1 from s where bitand(pa,s1)*bitand(pb,s2) =0
and bitand(pa,s2)*bitand(pb,s1)=0))
select count(*) from (
select pa,pb from j
union  
select least(pa-64+512,pb),greatest(pa-64+512,pb) from j where bitand(pa,512)=0 and bitand(pa,64)<>0
union  
select least(pa,pb-64+512),greatest(pa,pb-64+512) from j where bitand(pb,512)=0 and bitand(pb,64)<>0
union  
select pa-64+512,pb-64+512 from j where bitand(pb,512)=0 and bitand(pb,64)<>0 and bitand(pa,512)=0 and bitand(pa,64)<>0
);

〇〇

〇〇 发表于 2016-11-30 13:45
凑了半天,终于出结果了,很难看,主要是应付6,9可以互换
with t as(select level-1 l from dual connect b ...

受到了http://blog.csdn.net/hikean/article/details/50811085 启发
with t as(select level-1 l from dual connect by level<=10),
t1(a,p,lv) as(select l,power(2,l),1 from t
union all
select l,p+power(2,l),lv+1 from t1,t where a<l and lv<6),
a as(select p ,decode (bitand(p,64+512),64,p+512,512,p+64,p)pa from t1 where lv=6), --p actual ,pa expand
b as(select p,pa pb from a),
s as(select power(2,substr('0104061625364618',level*2-1,1))s1,
power(2,substr('0104061625364618',level*2,1))s2 from dual connect by level<=8),
j as(select pa,pb from a,b where pa<pb and not exists(select 1 from s where bitand(pa,s1)*bitand(pb,s2) =0
and bitand(pa,s2)*bitand(pb,s1)=0))
select count(*) from (
select pa,pb from j
);

〇〇

实际上,对于排除了9,pa可以写成decode (bitand(p,64+512),512,p+64,p)pa