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

newkid

人肉很强，咱们笨人用笨办法：

SELECT SUM(LENGTH(bit)) total
      ,SUM(LENGTH(bit)-NVL(LENGTH(REPLACE(bit,'1')),0)) one
      ,SUM(LENGTH(bit)-NVL(LENGTH(REPLACE(bit,'0')),0)) zero
  FROM (  SELECT n
                ,bit
          FROM (SELECT 0 n,CAST('0' AS VARCHAR2(100)) bit FROM DUAL)
             MODEL RETURN ALL ROWS
               DIMENSION BY (n)
               MEASURES (bit)
               RULES (
                 bit[FOR n FROM 1 TO 9999 INCREMENT 1] =
                         CASE WHEN SUBSTR(bit[cv()-1],-1,1)='0' THEN TO_CHAR(bit[cv()-1]+1)
                              ELSE (NVL(RTRIM(bit[cv()-1],'1'),'0')+1)||RPAD('0',LENGTH(bit[cv()-1])-NVL(LENGTH(RTRIM(bit[cv()-1],'1')),0),'0')
                         END
                     )
       )
;


     TOTAL        ONE       ZERO
---------- ---------- ----------
    123618      64608      59010

注意我只是模拟了二进制的加一，没有必要做进制转换。

同样的算法在递归WITH居然行不通，BUG真不少。

WITH t (n,bit) AS (
   SELECT 0,'0' FROM DUAL
   UNION ALL
   SELECT n+1
         ,CASE WHEN SUBSTR(bit,-1,1)='0' THEN TO_CHAR(bit+1)
               ELSE (NVL(RTRIM(bit,'1'),'0')+1)||RPAD('0',LENGTH(bit)-NVL(LENGTH(RTRIM(bit,'1')),0),'0')
          END
   FROM t
   WHERE n<6
  )
SELECT bit FROM t;

BIT
----------
0
1
10
11
100
101
200         ---------- 出错了

newkid

原来又是字符串长度的故障，加了CAST就好了：
WITH t (n,bit) AS (
   SELECT 0,CAST('0' AS VARCHAR2(100)) FROM DUAL
   UNION ALL
   SELECT n+1
         ,(NVL(RTRIM(bit,'1'),'0')+1)||RPAD('0',LENGTH(bit)-INSTR(bit,'0',-1),'0')
   FROM t
   WHERE n<9999
  )
SELECT SUM(LENGTH(bit)) total
      ,SUM(LENGTH(bit)-NVL(LENGTH(REPLACE(bit,'1')),0)) zero
      ,SUM(LENGTH(bit)-NVL(LENGTH(REPLACE(bit,'0')),0)) one
FROM t;

     TOTAL       ZERO        ONE
---------- ---------- ----------
    123618      64608      59010



MODEL中的CASE也可以简化一下：
SELECT SUM(LENGTH(bit)) total
      ,SUM(LENGTH(bit)-NVL(LENGTH(REPLACE(bit,'1')),0)) zero
      ,SUM(LENGTH(bit)-NVL(LENGTH(REPLACE(bit,'0')),0)) one
  FROM (  SELECT n
                ,bit
          FROM (SELECT 0 n,CAST('0' AS VARCHAR2(100)) bit FROM DUAL)
             MODEL RETURN ALL ROWS
               DIMENSION BY (n)
               MEASURES (bit)
               RULES (
                 bit[FOR n FROM 1 TO 9999 INCREMENT 1] = (NVL(RTRIM(bit[cv()-1],'1'),'0')+1)||RPAD('0',LENGTH(bit[cv()-1])-INSTR(bit[cv()-1],'0',-1),'0')
                     )
       )
;

lastwinner

呵呵，先给个今天兔子说的方法
with test2
as
(select level-1 n
  from dual
  connect by level <= 10000
)
select sum( nvl(length(replace(replace(replace( translate(to_char(n,'FMXXXXXXXX')
,'24839AC657DEB0','1112222223333'),'2','11'),'3','111'),'F','1111')),0) ) n_total_1s
from test2
/

虽然比较简洁，但是很暴力

lastwinner

原帖由 〇〇 于 10-9-30 17:49 发表
数学归纳法？

是啊，否则你怎么证明n=8，n=9等时候，公式还成立呢？

newkid

原帖由 lastwinner 于 2010-9-30 23:07 发表
呵呵，先给个今天兔子说的方法
with test2
as
(select level-1 n
  from dual
  connect by level  

这方法好，稍微改一下就可以做二进制转换了。

lastwinner

原帖由 newkid 于 10-9-30 23:17 发表

这方法好，稍微改一下就可以做二进制转换了。

看到这个sql之前，我已经给出一个方法了
准备整理之后新写个帖子，呵呵

游客，如果您要查看本帖隐藏内容请回复

newkid

奥数哥还在不？为了不让你国庆闲得慌，挑战这个难题怎么样？
http://tieba.baidu.com/f?kz=883265251
作者：生肖迷宫

一种极端抽象的模型，虽然其难度已经早就不适合普通智力题玩家，但对数学家或者软件高手来说，这是一道非常难得的好题：
假设从6种神经元中挑出6个（有可能是1到6种），用神经纤维连接两两之间，使这6个神经元之间的连接符合某种规则，（比如说A-B、B-C、C-A、 A-E、D-A、D-F）就形成了一个特点的记忆元，多联少联都不对。当然神经元与这6个外其它神经元的连接并不影响这6个内部之间组合。假设现在有足够的神经元，尚无神经纤维连接，请问你至少需要多少个纤维才能保证形成过某种特定的记忆元？（形成过的意思就是包括在放纤维过程中形成过，后来又可能多联了而失去的情况。）

举个例子，假设现有某个连接如下：
A-B
| |
B-C-C-D
当再加一个神经变成
A-B
|/|
B-C-C-D
就是另一个记忆体，
当与别的神经元相连，如图
A-B
|/|
B-C-C-D
|
F
那么前一个记忆体依然有效，并且同时产生多个新的记忆体，如
A-B
|/|
B-C-C
|
F
或
A
|
B-C-C-D
|
F
等等。

涉及到图论、拓扑学，估计有了答案我也看不懂。

把这道题的第一步先简化一下，看看SQL能否搞定：
四个神经元（可以相同也可以不同）可以组成多少种不同的记忆体？

newkid

原帖由 lastwinner 于 2010-9-30 23:34 发表


看到这个sql之前，我已经给出一个方法了
准备整理之后新写个帖子，呵呵

**** 本内容被作者隐藏 *****

哈哈，我先挑挑毛病，你的t1未经排序就用了ROWNUM, 不是很正宗。
我就写16个REPLACE, 虽然难看点，效率也比你高。

lastwinner

原帖由 newkid 于 10-9-30 23:52 发表

哈哈，我先挑挑毛病，你的t1未经排序就用了ROWNUM, 不是很正宗。
我就写16个REPLACE, 虽然难看点，效率也比你高。

但事实证明我的是没问题的
我的还可以广泛用于其他2^n进制转换为2进制的计算

等到32进制，那你写32个replace？根本不灵活嘛

[ 本帖最后由 lastwinner 于 2010-10-1 00:09 编辑 ]

newkid

原帖由 lastwinner 于 2010-10-1 00:06 发表


但事实证明我的是没问题的
我的还可以广泛用于其他2^n进制转换为2进制的计算

等到32进制，那你写32个replace？根本不灵活嘛

老兄！你只不过是占了to_char(&num,'FMXXXXXX') 的便宜，如果不是碰巧16进制可以REPLACE成二进制，你的方法就是废纸一堆。你倒是转个其他进制的看看？

我以前做过的进制转换：
http://www.itpub.net/viewthread. ... ;page=1#pid13891773