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

lastwinner

原帖由 newkid 于 10-10-1 00:21 发表


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

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

最常用的不就是2、8、10、16互转么
兔子也说过你做过进制转换的，不过下午找了一下没找见，原来在这儿啊！
进制转换，如果from_base与to_base不正好是n次方或n次幂的关系，那通常就会用十进制来做中间介质
就像我要将16进制转换为8进制，我就得用10进制或者2进制作为中间介质

你那里的方法，如果碰到24进制之类的，也一样要定义10及以上的数字在24进制中如何表示呀！不比我这方法方便多少嘛

lastwinner

原帖由 lastwinner 于 10-9-30 17:00 发表
…………
长度为n位的所有二进制数，1出现的次数a1(n)为：.....................(2)
当n=1时，a1(n)=1
当n>1时，a1(n)=……=(n+1)*2^(n-2)

…………

对于[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
…………

依据之前的推论，得
[0,9999]转换成的二进制数中，1总共有S1个
S1=a1(1)+a1(2)+a1(3)+...+a1(13)
    +(a1(1)+a1(2)+a1(3)+...+a1(10))+2^10*1
    +(a1(1)+a1(2)+a1(3)+...+a1(9))+2^9*2
    +(a1(1)+a1(2)+a1(3)+...+a1(8))+2^8*3
    +(a1(1)+a1(2)+a1(3)+a1(4))+2^4*4
   =64608

0的总个数S0也自然容易推得：
S0=123618-64608=59010

newkid

我也是先转成10进制再变成目标进制，但我用的是逐位取模而不是你的REPLACE方法，所以我可以适用非2^n进制。

lastwinner

原帖由 newkid 于 10-10-1 01:03 发表
我也是先转成10进制再变成目标进制，但我用的是逐位取模而不是你的REPLACE方法，所以我可以适用非2^n进制。

嗯，对的，转其他进制我也会采取这个办法的
现在这个办法只是方便将16进制/8进制等2^n进制和2进制之间互转

newkid

原帖由 newkid 于 2010-9-30 23:40 发表
奥数哥还在不？为了不让你国庆闲得慌，挑战这个难题怎么样？
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能否搞定：
四个神经元（可以相同也可以不同）可以组成多少种不同的记忆体？

四个神经元组合成的记忆体，我暂时算出答案566.
如果这一步对了，下一步就是如何把它们组合成大图使得边最少（共享的边最多）。

newkid

四个神经元的连接方法有六种：
*-*
| |
* *

*-*
|\
* *

*-*
| |
*-*

*-*
|/|
* *

*-*
|/|  
*-*


*-*
|X|
*-*

需要把不同的组合分配上去。

newkid

#13 Colored Balls


You have 111 balls of five different colors. There is at least one ball of each color. You are placing these balls randomly into 11 boxes, on the condition that each box contains at least one ball. You can deduce that in any such placement at least one of the boxes must contain at least X balls of the same color.

What is the maximum possible value for X?

你有五种不同颜色的111个球，每种颜色至少一个。你把球随机放到11个盒子里，每个盒子至少一个球。你可以推断出，不管如何摆放，至少有一个盒子具有相同颜色的X个球。X可能的最大值是多少？

newkid

按我的理解，每种颜色的个数对你是已知的，但是分配方法是未知的。那么为了追求X的最大值就必须使得颜色尽可能集中，这种情况是 1+2+3+4+5*107, 即有107个相同颜色的球。不管怎么分布，至少有一个盒子有至少22个这种颜色的球。

如果颜色个数未知，那么至少是1*22+2*22+3*22+4*22+5*23, 至少有23个相同颜色的球。不管怎么分布，至少有一个盒子有至少5个这种颜色的球。

lastwinner

你的1、2、3、4、5表示的是不同的颜色吧？


这个题的意思显然是求一个最小值
盒子是11个，平均分的话，有一个盒子里会有11个球，其他10个盒子都是10个球
假设颜色分布也很均衡，则对于5种颜色，根据抽屉原则，每个10个球的盒子里，最少都有两个球的颜色是相同
对于11个球的盒子而言，这个数字是3，因为第11个球无论是什么颜色，都会使得该盒子中具有相同颜色的球的个数达到3

对于另外一个极端情况，颜色分布不均衡，假设4种颜色都只有1个球，而剩余107个球都是第5种颜色
所以至少有一个盒子具有相同颜色的6个球

综上，结果应该是3（或者，颜色分布未知，那结果就是3～6）

newkid

对啊，我本来是想着颜色编号，后来糊涂了，竟然用5作为盒子数去算。应该用11, 这样我的两个答案就是 CEIL(107/11)=10 和 CEIL(23/11)=3