Euler Project 挨个做- 之二 (Q51-Q78)

tree_new_bee

OO把生成素数表的SQL锤炼得快到极致了。

生成100万的素数表， 仅比我的seive_numlist函数慢一点而已。


newkid的写法，比我写的简洁多了， 不愧为装修大师。


[ 本帖最后由 tree_new_bee 于 2010-12-30 11:48 编辑 ]

tree_new_bee

Q52 Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order.

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.


这个人肉就知道一个：
1/7,.. 6/7 的小数部分就是了。
1/7 = 0.142857

不过，142857是不是最小的一个需要验证。

tree_new_bee

简单验证一下：

with t as (
select level r from dual
connect by
translate('0123456789',level||level*2||level*3||level*4||level*5||level*6||'0123456789', level||level*2||level*3||level*4||level*5||level*6)
<> translate('0123456789',level||'0123456789', level)
)
select max(r)+1 from t


  MAX(R)+1
----------
    142857

Executed in 2.718 seconds

tree_new_bee

Q53 How many values of C(n,r), for 1 ≤ n ≤ 100, exceed one-million?

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, ^(5)C_(3) = 10.

In general,
^(n)C_(r) =        
n!
r!(n−r)!
        ,where r ≤ n, n! = n×(n−1)×...×3×2×1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: ^(23)C_(10) = 1144066.

How many, not necessarily distinct, values of  ^(n)C_(r), for 1 ≤ n ≤ 100, are greater than one-million?

tree_new_bee

这个题简单。
只不过为了避开大数运算， 我们只要计算10为底的对数就可以了。

with tn as (select rownum n, sum(log(10,rownum)) over(order by rownum) pl  from dual connect by rownum<=100)
,t1 as (select tn.n n, tr.n r, tn.pl - (tr.pl+tnr.pl)
from tn, tn tr, tn tnr where tr.n<tn.n and tnr.n+tr.n = tn.n
and tn.pl - (tr.pl+tnr.pl) > 6)
select count(*) from t1

  COUNT(*)
----------
      4075

Executed in 0.25 seconds

tree_new_bee

Q54 How many hands did player one win in the game of poker?

题目太长，就不抄过来了。 把玩法解释一下：

就是常见的5张牌的游戏：
牌的大小按照以下顺序：
单点
对子
两对
三个相同
顺子
同花
三带二
四个相同
同花顺

文件中给定1000手牌(每行有10张牌的信息， 前5张是玩家A的牌， 后5张是玩家B的牌)， 判断玩家A赢多少手。


这是一道非常麻烦的题。 要考虑的东西很多。 除了牌型大小外， 还要考虑同牌型的情况下大小比较。

tree_new_bee

依然用external table 读文件。 把数据准备好， 以便大家一起思考。

create  table euler_poker(
  p1 varchar2 (15),
  p2 varchar2 (15)
    )
  ORGANIZATION EXTERNAL (
         TYPE ORACLE_LOADER
         DEFAULT DIRECTORY euler_dir
         ACCESS PARAMETERS
         (
           records delimited by '\n'
           badfile euler_dir:'poker%a_%p.bad'
           logfile euler_dir:'poker%a_%p.log'
           fields
                   (p1 position(1:15) char,
                   p2 position(16:30) char )
         )
         LOCATION ('euler_poker.txt')
  );

newkid

#23的TRANSLATE用得很神啊！这就是OO所说的SQL中的想象力。
Q54看不太懂，A和B都一下子把五张牌出掉，只比较一次？用CASE算出9种等级不就行了？

tree_new_bee

原帖由 newkid 于 2010-12-30 21:41 发表
#23的TRANSLATE用得很神啊！这就是OO所说的SQL中的想象力。
Q54看不太懂，A和B都一下子把五张牌出掉，只比较一次？用CASE算出9种等级不就行了？

不光是牌型等级的问题。
比如说， A和B都有2对， 那要比那大对的大小， 如果大对的大小相同， 比小对的大小， 小对也相同， 要比单张中最大的。 例如 33448 > 33446
对于3个相同， 4个相同， 或者3+2的牌型，比较简单。 因为3/4个相同的部分两个玩家不会相同， 所以直接比3/4相同的部分大小就行。 例子：44425 > 333AK
顺子，要比顺子大小   例子:  89TJQ > 45678
同花或者全部都是单点， 要从最大的牌开始比， 一直比到分出大小为止。 例子： 在同样是同花或者同样非同花的情况下： 378JA > 278JA

所以， 算起来非常麻烦。

我的思路是， 写一个函数poker_rank, 给出一手牌作为参数， 能算出一个综合分值， 这个分值综合了牌型和牌型组成部分各种信息， 直接比较这个分值就能决定大小。

[ 本帖最后由 tree_new_bee 于 2010-12-30 22:06 编辑 ]

newkid

等级作为排序第一列，第二列就直接比牌好了，把牌先按大小排序。比如 34567 用76543表示。