【演算法趣題】Q01 迴文十進位數

來自專欄 Python程序員

作者：簡單的happy Python愛好者社區專欄作者

博客專欄：簡單的happy

前言

【演算法趣題】是來自圖靈程序設計叢書絕雲譯的《程序員的演算法趣題》，書中是用Ruby實現的。這裡是用python來實現。

迴文數

如果把某個數的各個數字按相反的順序排列，得到的數和原來的數相同，則這個數就是「迴文數」。例如 123454321 就是一個迴文數。

問題描述

求用十進位、二進位、八進位表示都是迴文數的所有數字，大於十進位數10的最小值。

例）9（十進位數） = 1001（二進位數） = 11（八進位數）

例中的十進位數9小於10，因此不符合要求。

思路

因為二進位也是一個迴文數，則二進位數的最高位和最低位相等，如果是0，明顯不對，則只能1.二進位的最低位是1，對應的十進位一定是奇數。

舉個例子，給定十進位數13，求對應的二進位的過程如下：

13/2=6 余 1 （餘數對應二進位的最低位）

6/2=3 余 0

3/2=1 余 1

1/2=0 余 1

從下往上排列餘數後就可以得到二進位數1101。（最低位是1，則第一個除法的餘數是1，即十進位數/2的餘數是1，則該十進位數定是奇數）

因此，可以從11 開始，按順序搜索，找到符合條件的數。

JavaScript實現

書中有個用JavaScript版本實現，我嵌套在html代碼里，代碼如下：

/* 為字元串類型添加返回逆序字元串的方法 */ String.prototype.reverse = function(){ return this.split("").reverse().join("");}/* 從11開始搜索 */var num = 11;while(true){ if((num.toString() ==num.toString().reverse()) && (num.toString(2) ==num.toString(2).reverse(2)) && (num.toString(8) ==num.toString(8).reverse(8))){ document.write("<p>十進位數：",num,"</p>"); document.write("<p>二進位數：",num.toString(2),"</p>"); document.write("<p>八進位數：",num.toString(8),"</p>"); break; } /* 只搜索奇數，每次加2 */ num += 2;}

python3實現

python3中十進位數轉化為二進位數和八進位數的函數分別為bin()和oct().

ten = 15two = bin(ten)eight = oct(ten)print(str(ten))print(str(two))print(str(eight))150b11110o17

python中對字元串s的逆序可用 s[::-1]表示：

a = 12345s = str(a)s[::-1]54321

由於Python3中的二進位數以0b開頭，八進位數以0o（python2中是以0開頭的，注意區分）開頭，所以轉換成字元串後要剔除前綴，剩下數字再來做是否迴文的判斷。

判斷十進位數，對應是二進位數和八進位數是否都是迴文，寫了個函數：

def isAllHuiwen(a): ten = str(a) two = str(bin(a))[2:] eight = str(oct(a))[2:] if ten == ten[::-1] and two == two[::-1] and eight == eight[::-1]: print("十進位數："+ten) print("二進位數："+two) print("八進位數："+eight) return True else: return False

因此該問題比較好解決了：

num = 11while True: if(isAllHuiwen(num)): break else: num = num + 2

結果為：

十進位數：585二進位數：1001001001八進位數：1111

推薦閱讀：