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

newkid

我看来看去没有看到。他还是肉眼观察的结果。现在用归纳法来证明一下：
N个点分为两组，每一组中两两不相连。当N为偶数时为设第一、二组点数为k和k, 奇数则为k+1和k. 归纳起点可以是四边形或五边型。
第N+1个点加入时, 把它和第一组所有点连起来。新加入的边数为k或k+1. 这样得到的总边数就是那个最大值。因为原来第一组内两两不相连，这些新加的边不会构出三角形。
而新加入的第N+1个点和第二组没有任何关系，因此可以把它纳入第二组。第一组的数量没有发生变化，新增的边都是连到新增的点，因此原来组内“两两不相连”的状态没有改变。
因此在N+1的情况下，用上述办法仍然可以构造出两组两两不相连的点，并对N+2重复同样的做法。

nlrte13

原帖由 newkid 于 2010-10-26 22:22 发表
我看来看去没有看到。他还是肉眼观察的结果。现在用归纳法来证明一下：
N个点分为两组，每一组中两两不相连。当N为偶数时为设第一、二组点数为k和k, 奇数则为k+1和k. 归纳起点可以是四边形或五边型。
第N+1个点加入时, 把它和第一组所有点连起来。新加入的边数为k或k+1. 这样得到的总边数就是那个最大值。因为原来第一组内两两不相连，这些新加的边不会构出三角形。
而新加入的第N+1个点和第二组没有任何关系，因此可以把它纳入第二组。第一组的数量没有发生变化，新增的边都是连到新增的点，因此原来组内“两两不相连”的状态没有改变。
因此在N+1的情况下，用上述办法仍然可以构造出两组两两不相连的点，并对N+2重复同样的做法。

这不就是鹦鹉哥的方法么 ^^

newkid

原帖由 nlrte13 于 2010-10-27 09:42 发表



这不就是鹦鹉哥的方法么 ^^

你脑瓜好使，我猜他自己都还没整明白呢，你已经想通了。


本周的题目没什么意思：
#16
Generating 9-Letter Codes

You will generate 9-letter codes changing the places of letters in the word TRANSFORM. The condition is that none of the letters in the generated codes will be on the same place as they were on the word TRANSFORM.

How many different codes can be generated?

Example: If the same question was asked for 4-letter codes with the letters of the word DATA, the answer would be 2: ADAT, ATAD.

SELECT COUNT(*)
  FROM (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=9)
WHERE LEVEL=9
START WITH rn>1
CONNECT BY NOCYCLE LEVEL<>rn AND LEVEL<=9 AND rn<>PRIOR rn;

  COUNT(*)
----------
    133496

nlrte13

哈哈，过奖过奖~

这个题我算的结果是50988，又和你不一样了

方法是：
[ 7! - C(1,5)*6! + C(2,5)*5! - C(3,5)*4! + C(4,5)*3! - C(5,5)*2! ] * C(2,7)
= ( 5040 - 3600 + 1200 - 240 + 30 - 2 ) * 21
= 2428 * 21
= 50988

lastwinner

有个字符R是重复的
题目意思是将TRANSFORM这个单词的九个字母打乱顺序，使得新生成的组合中的每一个字母都和原先这位置上的不一样

若这样理解正确，那我看newkid的sql就有问题，因为没考虑到R出现了两次……

lastwinner

原帖由 newkid 于 10-10-27 21:56 发表

你脑瓜好使，我猜他自己都还没整明白呢，你已经想通了。

我图画出来后，我就想明白了
不过我没想明白为毛这样就是最大的捏～～
你们的证明我还没时间看呢- -

[ 本帖最后由 lastwinner 于 2010-10-28 16:58 编辑 ]

newkid

我太轻敌了，竟然没看到有两个R:

SELECT COUNT(DISTINCT SYS_CONNECT_BY_PATH(CODE,','))
  FROM (SELECT ROWNUM rn,DECODE(ROWNUM,8,2,ROWNUM) code FROM DUAL CONNECT BY ROWNUM<=9)
WHERE LEVEL=9
START WITH rn>2
CONNECT BY NOCYCLE LEVEL<>code AND (LEVEL,CODE) NOT IN ((8,2)) AND LEVEL<=9 AND rn<>PRIOR rn;

COUNT(DISTINCTSYS_CONNECT_BY_PATH(CODE,','))
--------------------------------------------
                                       50988

奥数哥人肉无敌！

lastwinner

原帖由 nlrte13 于 10-10-28 15:06 发表
哈哈，过奖过奖~

这个题我算的结果是50988，又和你不一样了

方法是：
[ 7! - C(1,5)*6! + C(2,5)*5! - C(3,5)*4! + C(4,5)*3! - C(5,5)*2! ] * C(2,7)
= ( 5040 - 3600 + 1200 - 240 + 30 - 2 ) * 21
= 2428 * 21
= 50988

你的算法解释一下？
一加一减看着倒是像是那么一回事儿，不过我不了解其中的算法缘由
如果是我，我会这么考虑：（问题简化成abcd重新排列后每个字母所在位置都与原字母不重合）
则第一个位置可能的选择是：C(1,3)
第二个位置可能的选择是：(C(1,3)*1/3+C(1,2)*2/3)  --表示如果第一个位置恰好选择的是b，则第二个位置就可以从剩下的3个字母中任选一个；如果不是b，则可选字母就只有2个了
第三个位置可能的选择是：
     如果第前两个中有选到c和d，概率是2/P(2,4)=2/12，则第三个位置可能的选择就是C(1,2)
       如果第前两个中有选到c而没有d或者有d而没有c，概率是8/12，则第三个位置可能的选择就是C(1,1)
       如果第前两个中没选到c也没选d，概率是2/12，则第三个位置可能的选择就是C(1,1)
…………………………………………
然后我就晕了@@@@@@@@@@@



这是我的sql解答
SCOTT@lw.lw> select count(*) xp from (SELECT ROWNUM id, decode(rownum,8,2,9,8,ro
wnum) rn FROM DUAL CONNECT BY ROWNUM<=9) where level=9 start with id>1 connect b
y nocycle (level<>rn and level<=7 or level=8 and rn<>2 or level=9 and rn<8) and
id<>prior id;

        XP
----------
    101976

已用时间:  00: 00: 05.31


正好是你的2倍
个数虽然不会是newkid算的那么多，但也不至于是你算的这么少吧？

lastwinner

汗，我也轻敌了
RR互相颠倒位置对结果没影响，所以count(*)直接除以2就行了

nlrte13

[ 7! - C(1,5)*6! + C(2,5)*5! - C(3,5)*4! + C(4,5)*3! - C(5,5)*2! ] * C(2,7)

7! 是去掉两个R，剩下7个字母任意放的组合数
C(1,5)*6! 是7个字母中的6个字母任意放，另一个固定放在不能放的位置，C(1,5)意思是这样的位置共有5个
以此类推
C(2,5)*5! 是7个字母中的5个字母任意放，另外两个固定放在不能放的位置，C(2,5)表示这样的组合位置有10个
。。。
。。。
C(2,7) 就是两个R，可以有21种放法