前几年有一个电影叫做Robot Stories，讲述有关机器人与人的四个独立的小故事。记得当时《科幻世界》上曾对这个电影有过介绍。下面这段视频是电影的片头动画，非常有意思：

。

    今天的最后一篇日志了，仍然是翻译的cut-the-knot。发完我就睡觉去了。

    这里已经有五种证明根号2是无理数的方法了。现在我们算是介绍第六种方法了。
    一个有限小数的平方绝对不可能变成整数，因为小数部分不可能消失。观察有限小数的小数部分最后一个数字你会发现结论是显然的，平方后它总会产生新的“最后一位”。
    下面证明，(n/m)^2不可能等于2。n/m不可能是整数，于是把它写成小数形式，而有限小数的平方不可能是整数。如果n/m不是有限小数的话，可以把它转换成另外的进制使得n/m是有限小数，因而上面的结论仍然成立。一个进制下的无限小数可能是另一个进制下的有限小数。比如，把分数n/m转化为m进制，得到的小数肯定是有限小数。

    人有十个手指，用手指的伸屈来计数非常方便。但一旦对象的数目超过10个了，手指头就不够用了。当然，有人会想到还有脚趾头。搬弄脚趾头是不现实的，数手指头只需要站着比划一下就可以了，数脚趾头还需要坐下来慢慢研究。一种好的方法是每次数完了十个指头后在什么地方做一个标记，比如在地上放一个木棒。人们可以把这根木棒想像成一个“大指头”，它相当于十个指头。这样，我有37个MM就被表示成了地上3个木棒加上我7个手指头。哈哈，你的MM数只有两根木棒加4个手指头，于是我的MM比你的多。久而久之，人们就只接受0到9这十个数字了，再大的数就用几个数字合起来表示。这种“满十进一”的数字系统就叫做十进位制。
    如果人只有八个手指头又会怎样呢？那我们现在很可能正在使用八进制，数学发展起来后我们最终只接受八个数字，而大于8的数字就用更高一级的计量单位表示。代表这八个数字的很可能是些星际之门里的怪符号，这里为了便于叙述，我们仍然使用阿拉伯数字的0到7来表示。于是，人类数数的方式将变为：0,1,2,3,4,5,6,7,10,11,12,13,14,15,16,17,20,…。这里，数字8被记作10，数字64则用100代替。在这个数学世界里，6+5=13，因为6+1得到的数已经是一位数中最大的了，再加的话只能“进一位”了。“满八进一”将成为数学运算的基本法则。
    如果人有12根手指，12进制将成为更难想像的事。在12进制中，人类会把10和11直接想成是一个“数字”。研究的进位制大于10时，大于9的数字我们习惯上用大写字母ABC来表示。这样，自然数序列里将多出两个符号A和B来，数数的方式变为…,8,9,A,B,10,11,12,…。

    我们自然会想，人类生活中究竟有没有其它的进位制呢？当然有。比如，时间和角度就是60进位制，60秒=1分。还有更怪的，计算机的储存容量单位是1024进制的，1MB=1024KB。当然，这也是有原因的。我们在研究几何时常常需要用到1/2，1/3，1/4或者1/6，我们希望这些分数在角度进制下恰好都是整数以便于运算。于是，角度的进位制就变成了60。为什么时间也是60进位制呢？因为时间和角度密切相关，你看看你的手表就知道了（别告诉我你的手表是数字型的）。为什么钟和手表又要用圆形表盘的方式来表示时间呢？其实人自古以来计算时间都是用的圆形盘面，因为地球绕太阳旋转和地球的自转使得时间具有了周期性。
    计算机使用二进制，因为计算机元件只有两种状态（开和关，或者说通电和断电），因此计算机只认0和1两个数字。1024是2的幂，又比较接近1000符合人的习惯，因此把1024当成了计算机容量的进位制。

    前段时间有人在OIBH上问，为什么纸币的面值都是1*10^n、2*10^n、5*10^n呢。有人回答说这样的货币系统可以使得某种贪心方法正确。确实有这个结论，这样的货币系统使得解决“凑钱和找零时最少使用多少张纸币”这一问题的贪心算法（不断拿最大面额的纸币）是正确。但用这一点来解释我们的问题显然是可笑的，人们首先考虑的并不是如何方便地使用最少纸币，而是如何方便地得到总面额。一个只有1元纸币和7元纸币的货币系统同样满足贪心性质，但显然傻子才会设计出这种别扭的货币系统来。因此，我的回答是“纸币的面值取10的约数，这样的话凑钱和找零最方便”。但是，有人会问，要是我们使用的进位制不是10怎么办？换句话说，如果我们使用的是23进位制，除1和本身外没有其它约数的话，又该怎样设置货币系统呢。答案非常出人意料，如果我们使用的是23进位制的话，我们很可能根本发展不出数学这门学科来。10=1+2+3+4，是前四个正整数的和；10又是2和5的积；这样的进位制非常适合数学的发展。同样地，6=1+2+3，6=2*3，因此可能正在使用六进制的昆虫们很容易发展出数学来（六足动物的数学非常强，不是有人发现了蜜蜂蜂巢的六边形样式设计是最科学的么）。大家看过《计算机中的上帝》(Calculating God)吗？那里面构造了这样一种生物：他有23根手指。这种别扭的数字最多只能让人联想到乔丹和染色体，除此之外没有任何特性。这给这种生物的数学发展带来不可逾越的困难。而事实上，这种生物恰好又没有发展数学的必要性。他就好像人类一样，对较小的物体个数具有直接感知的能力。人类可以直接感知的物体数量一般不超过6。也就是说，如果你眼前有3个，或者5个东西，你不需要数，看一眼就知道有多少个；但当你眼前出现的物体数目达到7个或者8个时，你就必须要数一数才知道个数了。而我们所说的生物面对的物体数目多达46个时仍然可以一眼分辨出多少来，数目超过46后就统称为“很多”了。直接感知数目达到50甚至60多的生物个体就扮演着该种族中的僧侣角色。46这个数字对于种族的生存已经完全足够了，他们在组建部落时总会保证部落的个体数不超过这个数字。因此，这种生物不需要数数的能力，他们也就无须发展数学了。他们不知道30加30等于多少，从某种意义上说他们甚至不知道一加一等于几，因为他们头脑中根本没有数字这个概念。作为一种补偿，他们对事物的感知能力相当敏锐。他们甚至直接凭直觉感知到了相对论，因为他们的思维不受演绎逻辑的束缚。

    下文将介绍两套进制转换的方法，然后介绍这两套方法在小数转换上的应用。更多的进位制相关应用你可以在文后的习题部分中体会到。

    在讲进位制时，大多数教材会教大家二进制和十进制如何互换。今天我就偏不这样讲，我要和那些教材讲得一样了我还不如不写今天这些东西。二进制虽然常用，但比较特殊，很可能会了二进制但仍然不会其它进制；我们今天当一回蜜蜂，看看六进制和十进制怎么互相转换。学会这个后，任意进制间的转换你就应该都会了。
    说起进位制时往往要回到最根本的一些计数方法上。这篇日志是我第237篇日志。数字“237”表示两个百，加上三个十，加上七个单位一。我们把它们分别叫百位、十位和个位，同一个数字在不同数位上表示的实际数量不同。用一个式子表示上面的意思就是，237=2*100+3*10+7。这就是进位制的实际意义。
    现在，假如我是一只勤劳的蜜蜂。我写237篇日志是肯定不可能的了，因为我的数学世界里根本没有7这个数字。那就说我写了235篇日志吧。结合前面所说的东西，“十位”上的数表示有多少个6，“百位”上的数表示有多少个36（后面提到的十位、百位打引号表明这不是十进制中的“十”和“百”）。于是，六进制下的235就应该等于2*6^2+3*6+5。这个算式你用什么进制算出答案就相当于把六进制中的235转换为了什么进制。不过你要把这个式子当成别的进制算是不大可能的，算之前你估计得重新背一遍乘法口诀表（注意我为什么不说是“九九”乘法口诀表）。这就是我们为什么一般只研究十进制与其它进制互换的原因。我们用熟悉的十进制进行计算，得出2*6^2+3*6+5=72+18+5=95。这是按定义进行进制转换的方法。六进制的235等于十进制的95，我们记作(
235)6=(95)10。那个6和10是下标，应该像H2O的2一样小小地写在下面。我就懒得排版了，反正转贴个几次就成Plain Text了。
    下面的任务是，考虑怎么把(95)10变回(235)6。使用六进制计算13*10+5可以得到235（十位上的9相当于六进制中的13），但我们说过六进制计算很麻烦。下面我们给出一种把十进制转换为六进制的方法，仔细思考你会发现这种方法显然是正确的。我们把所有6的幂从小到大写出来：1,6,36,216,…。216远远超过95了，因此95的六进制不可能是四位数。95里面有两个36，因此在最高位上写个“2”。去掉两个36，95里只剩23。23里有三个6，数字3将填写在第二位上，去掉这三个6最后所剩的5留给最末位。换句话说，我们不断寻找最大的x使得6^x不超过当前数，当前数减去6^x并在右起第x+1位上加一。这事实上是前面六进制转十进制的逆过程。
    上面的进制互换方法是一套方法，这是我们所介绍的第一套方法。这套方法的特点是正确性很显然，但是计算比较复杂，又费马达又费电。我们需要一个计算更方便的进制转换方法。下面介绍的就是进制转换的第二套方案。

    再一次回到一个很基础的问题：在十进制中，为什么乘以10相当于在数的末尾加一个0？我们同样会联想到位运算：为什么二进制左移一位（末尾加一个0）相当于乘以2？事实上，这个结论普遍存在于所有进位制中：k进制数的末尾加个0，相当于该数乘以k。证明方法非常简单，乘以一个k就相当于进位制展开式的每个指数都加一，也就相当于所有数字左移一位。六进制235=2*6^2+3*6+5，乘以6的话式子将变为2*6^3+3*6^2+5*6，也即2350。利用这个性质，六进制235可以很快转为十进制：235相当于2后面添0，加上3，再添一个0，再加上5，写为算式即(2*6+3)*6+5=95。把(2*6+3)*6+5展开来，得到的式子和前面的那种计算方法(2*6^2+3*6+5)一模一样，但这里的计算方式更简便一些。如果写成程序，六进制字符串t转为十进制数a只需要一句话就可以完成：
for i:=1 to length(t) do a:=a*6+ord(t[i])-48;
    使用这种方法将十进制变回六进制是一个彻头彻尾的逆向操作：当前数不断除以6并把余数作为新的最高位。比如，95除以6等于15余5，余数5就是个位，15除以6的余数3作为“十位”，最终的商2是“百位”。这叫做短除法，是最常见的方法，网上随处可见。

    下面说一下进位制中的小数。前面的东西如果理解了，小数进制的转换将顺理成章地进行下去。六进制中的0.1相当于十进制的1/6，因为六进制中的0.1、0.2、0.3、0.4、0.5五个数把区间0到1均分为了6分。同样地，(0.05)6=(5/36)10。你会发现，一个“十分位”代表1/6，一个“百分位”代表1/6^2，之前的很多结论仍然成立。六进制小数12.345就等于1*6^1+2*6^0+3*6^(-1)+4*6^(-2)+5*6^(-3)，通过负指数把进制转换的整数部分和小数部分联系在了一起。(12.345)6转为十进制后居然变成了无限小数，其实这并不奇怪，这只是一个约数的问题：同样是三分之一，在我的六进制下正好分干净(0.2)，但在你十进制下就总也分不完，总要剩一点留给下一位(0.333333…)。这里有一些小数进制转换的实例。可以看到，一个进制下的有限小数很可能是另一个进制下的无限循环小数。另一个有趣的例子在这里。
    既然前面所说的第一套方法中六进制转十进制对于小数仍然成立，那么第一套方法的十进制转六进制也可以直接在小数上使用。如果你嫌无限小数很别扭，用分数进行操作是一种不错的选择。具体操作方法和前文叙述一模一样。针对纯小数的进制转换，我们把前文的描述换种方法再说一遍：不断寻找最小的正整数x使得1/6^x不超过当前数，当前数减去1/6^x并在小数点后第x位上加一。我就不再举例子了，下面主要讨论第二套方法在小数上的应用。
    我们曾说过，在k进制末尾加0相当于该数乘以k。可惜这对小数没有用，小数后你加它八百个“0”这个数仍然不变。其实，“末尾加0”只是这种性质反映在整数上的一种现象而已，我们还需要看到更本质的东西（还记得高二哲学么）。考虑到小数的乘k和除k，不难想到这种性质的实质是小数点的移动，整数的末尾加0其实是小数点向右移动一位的结果。显然小数也有类似的结论：将k进制小数的小数点左移一位，相当于该数除以k。比如，十进制中3.14除以10就变成了0.314。结论的证明和原来完全相同：除以k后展开式中的指数全部减一，相当于所有数右移一位。有了这个结论，我们的方法就出来了。来看六进制12.345如何转换为十进制。由于这种方法对整数和小数的处理方法有一些不同，转进制时我们通常对整数部分和小数部分分别进行操作。先把12转成十进制的8，然后单独考虑小数部分。0.345可以看作是数字“5”的小数点左移，加上4后小数点再次左移，再加上3并最后一次左移小数点；写成算式即((5/6+4)/6+3)/6。展开这个式子，实质与前面的方法仍然一样。小数部分十进制转六进制依然是彻头彻尾的逆向操作：当前数不断乘以6并取出整数部分写下来。
    这里有一个实例供大家参考，这个例子中的进制转换保证不涉及无限循环小数。1/4在十进制和六进制下的表示肯定都是有限小数，因为4的唯一一个因子2同样也是10和6的因子。先看0.25怎么变成六进制：0.25*6=1.5，取出1，留下0.5；0.5*6=3，没有小数部分了，因此(0.25)10就等于(0.13)6。现在我再把它变回去：(3/6+1)/6=(0.5+1)/6=1.5/6=0.25。这不是彻头彻尾的逆操作吗？

    每年NOIp前总有人问负进位制。事实上，如果你搞清了上面的问题，负进位制将非常好理解。负进位制有一个非常奇特的功能：它可以表示出负数但不需要用负号。一个负进制数可能是负数，也可能是正数。比如，负六进制下的12等于十进制下的-4，而负六进制下的123等于1*(-6)^2+2*(-6)^1+3，即十进制下的27。是正是负取决于位数的奇偶：若该数有偶数位，则该数为负数；若有奇数位，则该数为正数。原因很简单，小数点每右移一位，相当于这个数乘以-6；从一位数开始，乘奇数次后该数的位数变成偶数且值为负，乘偶数次该数仍有奇数位且值仍为正。由于末尾添0的性质（小数点移位的性质）仍然成立，负六进制与十进制的转换依然是上面的方法：(123)-6=(1*(-6)+2)*(-6)+3=(27)10。十进制转负六进制？还是那句话：彻头彻尾的逆操作。找到最小的非负整数x使得当前数减x能被6整除，这个x将作为新的最高位写到结果中，然后当前数减去x再除以-6。在这里我不说“余数”这个词，因为当除数为负数时对余数的定义很模糊。不再举例子了，例子都举烦了，自己把(123)-6=…=(27)10那一行倒过去看就是例子了。
    当然，还有更神奇的：-1+i进制可以表示出复数来，因为-1+i的幂有时含有虚数有时不含虚数。运算和转换依然和上面这些东西一样，我也就不多说了。

    进位制的问题结束了。我们这里是以六进制为例进行的说明，但是不要忘

    不少人可能为找不到非传统题型的练习题而头疼。这几天我专门发出一些用于省选集训的题目供大家参考。

Problem 1: cell 手机
题目来源：USACO Contest FEB06 Gold (Translated by Matrix67)

问题描述
    奶牛们已经开始使用手机交流了，但它们发现手机的按键设计不适合它们的蹄子。它们想设计一个新的手机，让它的按键更少，但是更大。
    它们喜欢普通手机的一个功能：词语联想。每个按键都有一些字母和它对应，打出一个单词只需要按对应的按键。因为一个按键可能对应多个字母，因此某些单词可能会发生“歧意”。不过，大多数时候这种歧意可以通过用字典判断的方法来消除。
    考虑到奶牛们在自定义一款新的手机，它们还需要用奶牛字母表替换英文字母表。神奇的是，奶牛字母表中的字母恰好是英语字母表中的前L个字母，即使顺序也一样。它们想知道如何把这些字母分配给B个按键(1<=B<=L)使得在字典中不会产生歧意的单词最多。就像普通的手机一样，他们希望每个按钮上的字母都是字母表中一段连续的字母。

    这是一个答案提交类的题目。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件cell.3.in相对应的输出文件应该为cell.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入数据
    第一行：一个整数N，表示这是第N个输入文件。
    第二行：两个用空格隔开的整数：B和L
    第三行：D，字典中的单词数(1<=D<=1000)
    第四行到第D+3行：每一行包含一个字典中的单词，用1到10个大写字母表示。这些单词按照字典序给出，并且保证没有重复。

输出数据
    第一行：字典中具有唯一的按钮序列的单词数。
    第二行到第B+1行：其中的第n行包含有第n个按钮上的字母，用大写的字母按照字典的顺序表示。所有行必须按照字典序排列，每个字母出现恰好一次。如果有多个最优解，选用第一个按键上字母最多的解。如果最优解仍然不唯一，考虑第二个按键上字母最多，依此类推。

样例输入(cell.1.in)
1
3 13
11
ALL
BALL
BELL
CALK
CALL
CELL
DILL
FILL
FILM
ILL
MILK

样例输出(cell.1.out)
7
AB
CDEFGHIJK
LM

样例说明
    第一个按键上只有AB两个字母，第二个按键上含有C到K，第三个按键上为LM。单词CELL、DILL、FILL和FILM的输入都是2233，其它7个单词的输入都是唯一的。

题解(Ctrl+A)：
    这道题目……搜索，乱搞。

Problem 2: selfstr 自描述序列
题目来源：Matrix67根据经典问题改编

问题描述
    “这句话里有1个数字零，2个数字一，1个数字二，0个数字三”。

    在N(N>=2)进制中只允许0到N-1这N个数字出现。一个N位的N进制数（允许有前导0）可以由另一个同样多位的数来描述。我们定义一个N位N进制数的描述序列为：左起第i个数字为原数中数字i-1出现的次数。
    例如，在4进制中，0023的描述序列为2011，因为0023中有2个0，0个1，1个2和1个3。
    我们惊奇地发现，4进制数1210的描述序列是它本身！我们称这样的数叫做“自描述序列”。

    你需要编写程序计算出在某个进制下的自描述序列。一个进制下的自描述序列可能有很多个，你只需要给出其中一个即可。
    这是一个答案提交类的问题。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件selfstr.3.in相对应的输出文件应该为selfstr.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入格式
    输入数据只有一个正整数N

输出格式
    输出N个字符，它表示N进制下的自描述序列。在高于10的进位制下，大于9的数字请用大写字母表示。
    如果有多种可能的解，你只需要输出其中一个。
    如果该进制下无解，请输出“NONE”。

样例输入(selfstr.1.in)
4

样例输出(selfstr.1.out)
1210

题解：
    这道题太有意思了！首先，你需要先算几个小数据。你会发现，算到N>=6后，渐渐有规律了：

   N   N进制下的自描述序列
   4    1210 or 2020
   5    21200
   6    NONE
   7    3211000
   8    42101000
   9    521001000

    事实上，这道题目就是考你当搜索到一些解后能不能找到规律得到所有解。这里我们发现，对所有N>6，至少存在一个解为R21(0…0)1000，其中R=N-4，中间0的个数为N-7。结论显然正确。
    有可能除了这个之外存在其它的解，因此我们仍然需要写一个check来核对答案。

Problem 3: relation 大小关系
题目来源：Matrix67根据经典问题改编

问题描述
    用关系“ < ”和“ = ”将3个数a、b、c依次序排列时，有13种不同的序列关系：
      a=b=c, a=b<c, a<b=c, a<b<c, a<c<b
      a=c<b, b<a=c, b<a<c, b<c<a, b=c<a
      c<a=b, c<a<b, c<b<a

    用这两种关系连接N个数有多少种不同的方案？

    这是一个答案提交类的问题。所有选手将得到10个输入数据，你只需要在你自己的计算机上计算出你的答案，然后把你的答案提交上来。与输入文件relation.x.in相对应的输出文件应该为relation.x.out，这里x表示一个1到10之间的数。

输入格式
    输入一个整数，表示N。

输出格式
    输出用小于和等于符号将N个数进行有序排列的方案数。

样例输入(relation.1.in)
3

样例输出(relation.1.out)
13

题解：
    组合数学+高精度。由于数据规模很小，我就直接搞成了答案提交类的题目。
    下面给出两种递推方法：
    Solution 1: N个数中必然存在一个最大的“等价类”，如果这个等价类里有k个数，那么剩下的数就有F(N-k)种排列方案。别忘了我们需要枚举这k个数是哪k个数。于是，F(N)
=C(N,1)F(N-1)+C(N,2)F(N-2)+C(N,3)F(N-3)+ … +C(N,N)F(0)
    Solution 2: 用F[ i, j]表示 i个数中有j 个等价类的排列方案（就是说有j-1个小于符号）。第 i个数有可能并入了F[i-1, j]中的 j个等价类中的一个，也有可能不与任何一个已有的数相等，独自成为一个等价类插入F[i-1, j-1]里产生的 j个空位中。于是，F[ i,j ]=F[i-1, j]*j + F[i-1,j-1]*j。

其它问题：
    如何用Cena评测答案提交类问题？
        见http://www.matrix67.com/blog/article.asp?id=176
    这些题的数据哪里有？
        第一题：http://ace.delos.com/FEB06，GOLD DIVISION里面的第三个
        第二题：自己写check，不需要数据
        第三题：http://www.research.att.com/~njas/sequences/b000670.txt，吓死你

Matrix67原创
转贴请注明出处