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

lastwinner

1、
2^1=2
2^2=4
2^3=8
2^4=16
2^5=32
.......
2^10=1024
2^13=8192


2、
2^n-2^(n-1)=2^(n-1)
9999-8192+1=1808

3、总共需要写下的0和1的数量记为S：
S=1*2+sum(n*2^(n-1))+14*1808, (2>=n>=13)
excel之，得123618

newkid

你现在EXCEL玩得很溜啊？

ORACLE的LOG会有误差，ROUND 4 位以内都得不到正确结果。
改用POWER:

SELECT SUM(d)+2
  FROM (SELECT LEVEL L FROM DUAL CONNECT BY LEVEL<=9999)
      ,(SELECT LEVEL+1 D,POWER(2,LEVEL) P1,POWER(2,LEVEL+1)-1 P2 FROM DUAL CONNECT BY LEVEL<=LOG(2,9999))
WHERE l BETWEEN p1 and p2
;

newkid

连接可以去掉：
SELECT SUM(D*(LEAST(P2,9999)-P1+1))+2
  FROM (SELECT LEVEL+1 D,POWER(2,LEVEL) P1,POWER(2,LEVEL+1)-1 P2 FROM DUAL CONNECT BY LEVEL<=LOG(2,9999));

lastwinner

不是了，Excel五六年前就这水平了，到现在都没啥长进
关键动作：输入1，序列，power，相邻行做减法，sumproduct得结果

笔记本慢啊，开个excel比启动oracleservicelw要快多了
nite

newkid

国庆长假开始了？OO跑哪里玩了？
题目太简单不过瘾，我来出附加题：这些数字中总共有多少个0，多少个1?

lastwinner

原帖由 newkid 于 10-9-30 08:46 发表
国庆长假开始了？OO跑哪里玩了？
题目太简单不过瘾，我来出附加题：这些数字中总共有多少个0，多少个1?

明天才开始呢，最早也要今天下午才算开始
这个附加题并不难，刚才不是得出总位数了嘛
现在只要列出所有数的二进制表示，视为字符串，然后去掉所有的0或1后计算长度，并求长度之和，就可以分别得出0、1的个数

当然，这是暴力法了

nlrte13

原帖由 newkid 于 2010-9-30 08:46 发表
国庆长假开始了？OO跑哪里玩了？
题目太简单不过瘾，我来出附加题：这些数字中总共有多少个0，多少个1?

求1的个数：
10000/2 +                                   （2^0位）
10000/2 +                                   （2^1位）
10000/2 +                                   （2^2位）
10000/2 +                                   （2^3位）
9984/2 +                                     （2^4位）
9984/2 +                                     （2^5位）
9984/2 +                                     （2^6位）
9984/2 +                                     （2^7位）
( 9984/2 + 16 ) +                        （2^8位）
( 9216/2 + 256 + 16 ) +              （2^9位）
( 8192/2 + 512 + 256 + 16 ) +    （2^10位）
8192/2 +                                     （2^11位）
8192/2 +                                     （2^12位）
( 10000 - 8192 ) =                      （2^13位）
64608

0的个数 = 123618 - 64608 = 59010

lastwinner

0
1      --x<2^1，0，1个，1，1个
10
11     --2^1<=x<2^2，0，1个，1，3个
100
101
110
111    --2^2<=x<2^3，0，4个，1，8个
1000
1001
1010
1011
1100
1101
1110
1111   --2^3<=x<2^4，0，12个，1，20个

观察以上0～15对应的二进制数，可得
长度为n位的二进制数的范围为： 当n=1时，为x<2^n
                              当n>1时，为2^(n-1)=<x<2^n

长度为n位的所有二进制数，0出现的次数a0(n)为：.....................(1)
当n=1时，a0(n)=1
当n>1时，a0(n)=(n-1)*2^(n-1)/2=(n-1)*2^(n-2)

长度为n位的所有二进制数，1出现的次数a1(n)为：.....................(2)
当n=1时，a1(n)=1
当n>1时，a1(n)=n*2^(n-1)-a0(n)=n*2^(n-1)-(n-1)*2^(n-2)=(n+1)*2^(n-2)

(1)和(2)从数学归纳法的角度也容易证明，此处略。

在[8192,9999]区间内，因为9999<8192*2-1，故而无法直接用上式计算该区间内的数字对应的二进制数，到底出现了多少个0和多少个1，但我们可以采用一个变通的方式来达到目的：

9999-8192+1=1808，转换为2进制是11100010000
即1808=2^10+2^9+2^8+2^4，而8192=2^13
对于[8192, 8192+2^10)，可看作2^10之内的所有二进制再加2^13，该区间内的数字有多少个1多少个0可以转换为求2^10内有多少个1多少个0，在最后的结果上，1出现的次数再加上2^10*1，0出现的次数因涉及到补0，故而直接计算比较麻烦（程序做起来就是一个循环而已）

对于[8192+2^10, 8192+2^10+2^9)，可看作2^9之内的所有二进制再加2^13+2^10，该区间内的数字有多少个1可以转换为求2^9内有多少个1，在最后的结果上，1出现的次数再加上2^9*2

以此类推
对于[8192+2^10+2^9, 8192+2^10+2^9+2^8)，1出现的次数为2^8内有多少个1，在此结果上，1出现的次数再加上2^8*3
对于[8192+2^10+2^9+2^8, 9999)，1出现的次数为2^4内有多少个1，在此结果上，1出现的次数再加上2^4*4

_________________________________________________
先推到这里，晚上再计算个数

〇〇

数学归纳法？

zhangweicai74

~~我看看看不懂~~