|
http://www./blog/archives/202 人有十個手指，用手指的伸屈來計數(shù)非常方便。但一旦對象的數(shù)目超過10個了，手指頭就不夠用了。當(dāng)然，有人會想到還有腳趾頭。搬弄腳趾頭是不現(xiàn)實的，數(shù)手指頭只需要站著比劃一下就可以了，數(shù)腳趾頭還需要坐下來慢慢研究。一種好的方法是每次數(shù)完了十個指頭后在什么地方做一個標(biāo)記，比如在地上放一個木棒。人們可以把這根木棒想像成一個“大指頭”，它相當(dāng)于十個指頭。這樣，我有37個MM就被表示成了地上3個木棒加上我7個手指頭。哈哈，你的MM數(shù)只有兩根木棒加4個手指頭，于是我的MM比你的多。久而久之，人們就只接受0到9這十個數(shù)字了，再大的數(shù)就用幾個數(shù)字合起來表示。這種“滿十進(jìn)一”的數(shù)字系統(tǒng)就叫做十進(jìn)位制。 如果人只有八個手指頭又會怎樣呢？那我們現(xiàn)在很可能正在使用八進(jìn)制，數(shù)學(xué)發(fā)展起來后我們最終只接受八個數(shù)字，而大于8的數(shù)字就用更高一級的計量單位表示。代表這八個數(shù)字的很可能是些星際之門里的怪符號，這里為了便于敘述，我們?nèi)匀皇褂冒⒗當(dāng)?shù)字的0到7來表示。于是，人類數(shù)數(shù)的方式將變?yōu)椋?,1,2,3,4,5,6,7,10,11,12,13,14,15,16,17,20,...。這里，數(shù)字8被記作10，數(shù)字64則用100代替。在這個數(shù)學(xué)世界里，6+5=13，因為6+1得到的數(shù)已經(jīng)是一位數(shù)中最大的了，再加的話只能“進(jìn)一位”了?！皾M八進(jìn)一”將成為數(shù)學(xué)運(yùn)算的基本法則。 如果人有12根手指，12進(jìn)制將成為更難想像的事。在12進(jìn)制中，人類會把10和11直接想成是一個“數(shù)字”。研究的進(jìn)位制大于10時，大于9的數(shù)字我們習(xí)慣上用大寫字母ABC來表示。這樣，自然數(shù)序列里將多出兩個符號A和B來，數(shù)數(shù)的方式變?yōu)?..,8,9,A,B,10,11,12,...。 我們自然會想，人類生活中究竟有沒有其它的進(jìn)位制呢？當(dāng)然有。比如，時間和角度就是60進(jìn)位制，60秒=1分。還有更怪的，計算機(jī)的儲存容量單位是1024進(jìn)制的，1MB=1024KB。當(dāng)然，這也是有原因的。我們在研究幾何時常常需要用到1/2，1/3，1/4或者1/6，我們希望這些分?jǐn)?shù)在角度進(jìn)制下恰好都是整數(shù)以便于運(yùn)算。于是，角度的進(jìn)位制就變成了60。為什么時間也是60進(jìn)位制呢？因為時間和角度密切相關(guān)，你看看你的手表就知道了（別告訴我你的手表是數(shù)字型的）。為什么鐘和手表又要用圓形表盤的方式來表示時間呢？其實人自古以來計算時間都是用的圓形盤面，因為地球繞太陽旋轉(zhuǎn)和地球的自轉(zhuǎn)使得時間具有了周期性。 計算機(jī)使用二進(jìn)制，因為計算機(jī)元件只有兩種狀態(tài)（開和關(guān)，或者說通電和斷電），因此計算機(jī)只認(rèn)0和1兩個數(shù)字。1024是2的冪，又比較接近1000符合人的習(xí)慣，因此把1024當(dāng)成了計算機(jī)容量的進(jìn)位制。 前段時間有人在OIBH上問，為什么紙幣的面值都是1*10^n、2*10^n、5*10^n呢。有人回答說這樣的貨幣系統(tǒng)可以使得某種貪心方法正確。確實有這個結(jié)論，這樣的貨幣系統(tǒng)使得解決“湊錢和找零時最少使用多少張紙幣”這一問題的貪心算法（不斷拿最大面額的紙幣）是正確。但用這一點來解釋我們的問題顯然是可笑的，人們首先考慮的并不是如何方便地使用最少紙幣，而是如何方便地得到總面額。一個只有1元紙幣和7元紙幣的貨幣系統(tǒng)同樣滿足貪心性質(zhì)，但顯然傻子才會設(shè)計出這種別扭的貨幣系統(tǒng)來。因此，我的回答是“紙幣的面值取10的約數(shù)，這樣的話湊錢和找零最方便”。但是，有人會問，要是我們使用的進(jìn)位制不是10怎么辦？換句話說，如果我們使用的是23進(jìn)位制，除1和本身外沒有其它約數(shù)的話，又該怎樣設(shè)置貨幣系統(tǒng)呢。答案非常出人意料，如果我們使用的是23進(jìn)位制的話，我們很可能根本發(fā)展不出數(shù)學(xué)這門學(xué)科來。10=1+2+3+4，是前四個正整數(shù)的和；10又是2和5的積；這樣的進(jìn)位制非常適合數(shù)學(xué)的發(fā)展。同樣地，6=1+2+3，6=2*3，因此可能正在使用六進(jìn)制的昆蟲們很容易發(fā)展出數(shù)學(xué)來（六足動物的數(shù)學(xué)非常強(qiáng)，不是有人發(fā)現(xiàn)了蜜蜂蜂巢的六邊形樣式設(shè)計是最科學(xué)的么）。大家看過《計算機(jī)中的上帝》(Calculating God)嗎？那里面構(gòu)造了這樣一種生物：他有23根手指。這種別扭的數(shù)字最多只能讓人聯(lián)想到喬丹和染色體，除此之外沒有任何特性。這給這種生物的數(shù)學(xué)發(fā)展帶來不可逾越的困難。而事實上，這種生物恰好又沒有發(fā)展數(shù)學(xué)的必要性。他就好像人類一樣，對較小的物體個數(shù)具有直接感知的能力。人類可以直接感知的物體數(shù)量一般不超過6。也就是說，如果你眼前有3個，或者5個東西，你不需要數(shù)，看一眼就知道有多少個；但當(dāng)你眼前出現(xiàn)的物體數(shù)目達(dá)到7個或者8個時，你就必須要數(shù)一數(shù)才知道個數(shù)了。而我們所說的生物面對的物體數(shù)目多達(dá)46個時仍然可以一眼分辨出多少來，數(shù)目超過46后就統(tǒng)稱為“很多”了。直接感知數(shù)目達(dá)到50甚至60多的生物個體就扮演著該種族中的僧侶角色。46這個數(shù)字對于種族的生存已經(jīng)完全足夠了，他們在組建部落時總會保證部落的個體數(shù)不超過這個數(shù)字。因此，這種生物不需要數(shù)數(shù)的能力，他們也就無須發(fā)展數(shù)學(xué)了。他們不知道30加30等于多少，從某種意義上說他們甚至不知道一加一等于幾，因為他們頭腦中根本沒有數(shù)字這個概念。作為一種補(bǔ)償，他們對事物的感知能力相當(dāng)敏銳。他們甚至直接憑直覺感知到了相對論，因為他們的思維不受演繹邏輯的束縛。 下文將介紹兩套進(jìn)制轉(zhuǎn)換的方法，然后介紹這兩套方法在小數(shù)轉(zhuǎn)換上的應(yīng)用。更多的進(jìn)位制相關(guān)應(yīng)用你可以在文后的習(xí)題部分中體會到。 在講進(jìn)位制時，大多數(shù)教材會教大家二進(jìn)制和十進(jìn)制如何互換。今天我就偏不這樣講，我要和那些教材講得一樣了我還不如不寫今天這些東西。二進(jìn)制雖然常用，但比較特殊，很可能會了二進(jìn)制但仍然不會其它進(jìn)制；我們今天當(dāng)一回蜜蜂，看看六進(jìn)制和十進(jìn)制怎么互相轉(zhuǎn)換。學(xué)會這個后，任意進(jìn)制間的轉(zhuǎn)換你就應(yīng)該都會了。 說起進(jìn)位制時往往要回到最根本的一些計數(shù)方法上。這篇日志是我第237篇日志。數(shù)字“237”表示兩個百，加上三個十，加上七個單位一。我們把它們分別叫百位、十位和個位，同一個數(shù)字在不同數(shù)位上表示的實際數(shù)量不同。用一個式子表示上面的意思就是，237=2*100+3*10+7。這就是進(jìn)位制的實際意義。 現(xiàn)在，假如我是一只勤勞的蜜蜂。我寫237篇日志是肯定不可能的了，因為我的數(shù)學(xué)世界里根本沒有7這個數(shù)字。那就說我寫了235篇日志吧。結(jié)合前面所說的東西，“十位”上的數(shù)表示有多少個6，“百位”上的數(shù)表示有多少個36（后面提到的十位、百位打引號表明這不是十進(jìn)制中的“十”和“百”）。于是，六進(jìn)制下的235就應(yīng)該等于2*6^2+3*6+5。這個算式你用什么進(jìn)制算出答案就相當(dāng)于把六進(jìn)制中的235轉(zhuǎn)換為了什么進(jìn)制。不過你要把這個式子當(dāng)成別的進(jìn)制算是不大可能的，算之前你估計得重新背一遍乘法口訣表（注意我為什么不說是“九九”乘法口訣表）。這就是我們?yōu)槭裁匆话阒谎芯渴M(jìn)制與其它進(jìn)制互換的原因。我們用熟悉的十進(jìn)制進(jìn)行計算，得出2*6^2+3*6+5=72+18+5=95。這是按定義進(jìn)行進(jìn)制轉(zhuǎn)換的方法。六進(jìn)制的235等于十進(jìn)制的95，我們記作(235)6=(95)10。那個6和10是下標(biāo)，應(yīng)該像H2O的2一樣小小地寫在下面。我就懶得排版了，反正轉(zhuǎn)貼個幾次就成Plain Text了。 下面的任務(wù)是，考慮怎么把(95)10變回(235)6。使用六進(jìn)制計算13*10+5可以得到235（十位上的9相當(dāng)于六進(jìn)制中的13），但我們說過六進(jìn)制計算很麻煩。下面我們給出一種把十進(jìn)制轉(zhuǎn)換為六進(jìn)制的方法，仔細(xì)思考你會發(fā)現(xiàn)這種方法顯然是正確的。我們把所有6的冪從小到大寫出來：1,6,36,216,...。216遠(yuǎn)遠(yuǎn)超過95了，因此95的六進(jìn)制不可能是四位數(shù)。95里面有兩個36，因此在最高位上寫個“2”。去掉兩個36，95里只剩23。23里有三個6，數(shù)字3將填寫在第二位上，去掉這三個6最后所剩的5留給最末位。換句話說，我們不斷尋找最大的x使得6^x不超過當(dāng)前數(shù)，當(dāng)前數(shù)減去6^x并在右起第x+1位上加一。這事實上是前面六進(jìn)制轉(zhuǎn)十進(jìn)制的逆過程。 上面的進(jìn)制互換方法是一套方法，這是我們所介紹的第一套方法。這套方法的特點是正確性很顯然，但是計算比較復(fù)雜，又費馬達(dá)又費電。我們需要一個計算更方便的進(jìn)制轉(zhuǎn)換方法。下面介紹的就是進(jìn)制轉(zhuǎn)換的第二套方案。 再一次回到一個很基礎(chǔ)的問題：在十進(jìn)制中，為什么乘以10相當(dāng)于在數(shù)的末尾加一個0？我們同樣會聯(lián)想到位運(yùn)算：為什么二進(jìn)制左移一位（末尾加一個0）相當(dāng)于乘以2？事實上，這個結(jié)論普遍存在于所有進(jìn)位制中：k進(jìn)制數(shù)的末尾加個0，相當(dāng)于該數(shù)乘以k。證明方法非常簡單，乘以一個k就相當(dāng)于進(jìn)位制展開式的每個指數(shù)都加一，也就相當(dāng)于所有數(shù)字左移一位。六進(jìn)制235=2*6^2+3*6+5，乘以6的話式子將變?yōu)?*6^3+3*6^2+5*6，也即2350。利用這個性質(zhì)，六進(jìn)制235可以很快轉(zhuǎn)為十進(jìn)制：235相當(dāng)于2后面添0，加上3，再添一個0，再加上5，寫為算式即(2*6+3)*6+5=95。把(2*6+3)*6+5展開來，得到的式子和前面的那種計算方法(2*6^2+3*6+5)一模一樣，但這里的計算方式更簡便一些。如果寫成程序，六進(jìn)制字符串t轉(zhuǎn)為十進(jìn)制數(shù)a只需要一句話就可以完成： for i:=1 to length(t) do a:=a*6+ord(t[i])-48;使用這種方法將十進(jìn)制變回六進(jìn)制是一個徹頭徹尾的逆向操作：當(dāng)前數(shù)不斷除以6并把余數(shù)作為新的最高位。比如，95除以6等于15余5，余數(shù)5就是個位，15除以6的余數(shù)3作為“十位”，最終的商2是“百位”。這叫做短除法，是最常見的方法，網(wǎng)上隨處可見。 下面說一下進(jìn)位制中的小數(shù)。前面的東西如果理解了，小數(shù)進(jìn)制的轉(zhuǎn)換將順理成章地進(jìn)行下去。六進(jìn)制中的0.1相當(dāng)于十進(jìn)制的1/6，因為六進(jìn)制中的0.1、0.2、0.3、0.4、0.5五個數(shù)把區(qū)間0到1均分為了6分。同樣地，(0.05)6=(5/36)10。你會發(fā)現(xiàn)，一個“十分位”代表1/6，一個“百分位”代表1/6^2，之前的很多結(jié)論仍然成立。六進(jìn)制小數(shù)12.345就等于1*6^1+2*6^0+3*6^(-1)+4*6^(-2)+5*6^(-3)，通過負(fù)指數(shù)把進(jìn)制轉(zhuǎn)換的整數(shù)部分和小數(shù)部分聯(lián)系在了一起。(12.345)6轉(zhuǎn)為十進(jìn)制后居然變成了無限小數(shù)，其實這并不奇怪，這只是一個約數(shù)的問題：同樣是三分之一，在我的六進(jìn)制下正好分干凈(0.2)，但在你十進(jìn)制下就總也分不完，總要剩一點留給下一位(0.333333...)。這里有一些小數(shù)進(jìn)制轉(zhuǎn)換的實例。可以看到，一個進(jìn)制下的有限小數(shù)很可能是另一個進(jìn)制下的無限循環(huán)小數(shù)。另一個有趣的例子在這里。 既然前面所說的第一套方法中六進(jìn)制轉(zhuǎn)十進(jìn)制對于小數(shù)仍然成立，那么第一套方法的十進(jìn)制轉(zhuǎn)六進(jìn)制也可以直接在小數(shù)上使用。如果你嫌無限小數(shù)很別扭，用分?jǐn)?shù)進(jìn)行操作是一種不錯的選擇。具體操作方法和前文敘述一模一樣。針對純小數(shù)的進(jìn)制轉(zhuǎn)換，我們把前文的描述換種方法再說一遍：不斷尋找最小的正整數(shù)x使得1/6^x不超過當(dāng)前數(shù)，當(dāng)前數(shù)減去1/6^x并在小數(shù)點后第x位上加一。我就不再舉例子了，下面主要討論第二套方法在小數(shù)上的應(yīng)用。 我們曾說過，在k進(jìn)制末尾加0相當(dāng)于該數(shù)乘以k?？上н@對小數(shù)沒有用，小數(shù)后你加它八百個“0”這個數(shù)仍然不變。其實，“末尾加0”只是這種性質(zhì)反映在整數(shù)上的一種現(xiàn)象而已，我們還需要看到更本質(zhì)的東西（還記得高二哲學(xué)么）。考慮到小數(shù)的乘k和除k，不難想到這種性質(zhì)的實質(zhì)是小數(shù)點的移動，整數(shù)的末尾加0其實是小數(shù)點向右移動一位的結(jié)果。顯然小數(shù)也有類似的結(jié)論：將k進(jìn)制小數(shù)的小數(shù)點左移一位，相當(dāng)于該數(shù)除以k。比如，十進(jìn)制中3.14除以10就變成了0.314。結(jié)論的證明和原來完全相同：除以k后展開式中的指數(shù)全部減一，相當(dāng)于所有數(shù)右移一位。有了這個結(jié)論，我們的方法就出來了。來看六進(jìn)制12.345如何轉(zhuǎn)換為十進(jìn)制。由于這種方法對整數(shù)和小數(shù)的處理方法有一些不同，轉(zhuǎn)進(jìn)制時我們通常對整數(shù)部分和小數(shù)部分分別進(jìn)行操作。先把12轉(zhuǎn)成十進(jìn)制的8，然后單獨考慮小數(shù)部分。0.345可以看作是數(shù)字“5”的小數(shù)點左移，加上4后小數(shù)點再次左移，再加上3并最后一次左移小數(shù)點；寫成算式即((5/6+4)/6+3)/6。展開這個式子，實質(zhì)與前面的方法仍然一樣。小數(shù)部分十進(jìn)制轉(zhuǎn)六進(jìn)制依然是徹頭徹尾的逆向操作：當(dāng)前數(shù)不斷乘以6并取出整數(shù)部分寫下來。 這里有一個實例供大家參考，這個例子中的進(jìn)制轉(zhuǎn)換保證不涉及無限循環(huán)小數(shù)。1/4在十進(jìn)制和六進(jìn)制下的表示肯定都是有限小數(shù)，因為4的唯一一個因子2同樣也是10和6的因子。先看0.25怎么變成六進(jìn)制：0.25*6=1.5，取出1，留下0.5；0.5*6=3，沒有小數(shù)部分了，因此(0.25)10就等于(0.13)6?，F(xiàn)在我再把它變回去：(3/6+1)/6=(0.5+1)/6=1.5/6=0.25。這不是徹頭徹尾的逆操作嗎？ 每年NOIp前總有人問負(fù)進(jìn)位制。事實上，如果你搞清了上面的問題，負(fù)進(jìn)位制將非常好理解。負(fù)進(jìn)位制有一個非常奇特的功能：它可以表示出負(fù)數(shù)但不需要用負(fù)號。一個負(fù)進(jìn)制數(shù)可能是負(fù)數(shù)，也可能是正數(shù)。比如，負(fù)六進(jìn)制下的12等于十進(jìn)制下的-4，而負(fù)六進(jìn)制下的123等于1*(-6)^2+2*(-6)^1+3，即十進(jìn)制下的27。是正是負(fù)取決于位數(shù)的奇偶：若該數(shù)有偶數(shù)位，則該數(shù)為負(fù)數(shù)；若有奇數(shù)位，則該數(shù)為正數(shù)。原因很簡單，小數(shù)點每右移一位，相當(dāng)于這個數(shù)乘以-6；從一位數(shù)開始，乘奇數(shù)次后該數(shù)的位數(shù)變成偶數(shù)且值為負(fù)，乘偶數(shù)次該數(shù)仍有奇數(shù)位且值仍為正。由于末尾添0的性質(zhì)（小數(shù)點移位的性質(zhì)）仍然成立，負(fù)六進(jìn)制與十進(jìn)制的轉(zhuǎn)換依然是上面的方法：(123)-6=(1*(-6)+2)*(-6)+3=(27)10。十進(jìn)制轉(zhuǎn)負(fù)六進(jìn)制？還是那句話：徹頭徹尾的逆操作。找到最小的非負(fù)整數(shù)x使得當(dāng)前數(shù)減x能被6整除，這個x將作為新的最高位寫到結(jié)果中，然后當(dāng)前數(shù)減去x再除以-6。在這里我不說“余數(shù)”這個詞，因為當(dāng)除數(shù)為負(fù)數(shù)時對余數(shù)的定義很模糊。不再舉例子了，例子都舉煩了，自己把(123)-6=...=(27)10那一行倒過去看就是例子了。 當(dāng)然，還有更神奇的：-1+i進(jìn)制可以表示出復(fù)數(shù)來，因為-1+i的冪有時含有虛數(shù)有時不含虛數(shù)。運(yùn)算和轉(zhuǎn)換依然和上面這些東西一樣，我也就不多說了。 進(jìn)位制的問題結(jié)束了。我們這里是以六進(jìn)制為例進(jìn)行的說明，但是不要忘記，最有趣的仍然是二進(jìn)制。與二進(jìn)制有關(guān)的趣味問題遍地都是。舉個例子，你可以在這里的第三題看到一個二進(jìn)制的經(jīng)典應(yīng)用。 文章最后還是那三句話： Matrix67原創(chuàng) 轉(zhuǎn)貼請注明出處 請大家?guī)兔π?br> 這次的錯別字可能很多，因為我不是用的紫光，而是用的fcitx，沒辦法使用原來的詞庫了。 講解也可能有漏洞，很多東西是我突然想到，即興寫下的。大家?guī)兔m錯??！ 附一：四道進(jìn)位制練習(xí)題及其簡略解答 下面這些題目是在我公布的那個課件里的，是我收集的一些很不錯的具有代表性的題目，講課時已經(jīng)用過多次了。 1. 證明：Σ(n=1 to ∞)6^( (2-3n-n^2)/2 )是無理數(shù)。 解答：用六進(jìn)制表示此數(shù)，該數(shù)顯然為無理數(shù)。 2. 在哪一種進(jìn)制中，35與58互質(zhì)？ 解答：由于出現(xiàn)了數(shù)字8，因此進(jìn)位制至少為9。事實上，35和58在任何不小于9的進(jìn)位制下都互質(zhì)，因為輾轉(zhuǎn)相減不會出現(xiàn)“不夠減”的情況，任何進(jìn)制下最終都得1。 3. 證明：沒有一種進(jìn)制使三位數(shù)aaa恰等于a^3。 解答：設(shè)此數(shù)為k進(jìn)制，則ak^2+ak+a=a^3。此方程無整數(shù)解。 4. 在哪一種進(jìn)制中，792可以被297整除？ 解答：這道題目非常有趣。在任何一種進(jìn)制下，200的四倍都已經(jīng)超過792，300的兩倍都還不足792。那么，792只可能是297的三倍。設(shè)進(jìn)位制為k，問題轉(zhuǎn)化為解方程7k^2+9k+2=3*(2k^2+9k+7)。 附二：進(jìn)位制笑話不完全收集:) 1. What would the value of 190 in hexadecimal BE? 2. If only DEAD people understand hexadecimal, how many people understand hexadecimal? 3. There are only 10 types of people in the world — those who understand binary, and those who don't. 4. There are only 10 types of people in the world — those who understand trinary, those who don't, and those who mistake it for binary. 5. Why do mathematicians think Halloween and Christmas are the same? Because 31 Oct = 25 Dec. |
|
|
