問題描述
列印所有不超過n(取n<256)的其平方具有對稱性質的數(也稱回文數)。
問題分析
對於要判定的數n計算出其平方後(存於a),按照“回文數”的定義要將最高位與最低位、次高位與次低位……進行比較,若彼此相等則為回文數。此演算法需要知道平方數的位數,再一一將每一位分解、比較,此方法對於位數已知且位數不是太多的數來說比較適用。
此問題可借助陣列來解決。將平方後的(a的)每一位進行分解,按從低位到高位的順序依次暫存到陣列中,再將陣列中的元素按照下標從大到小的順序重新將其組合成一個數眾(如n=15,則a=225且k=522),若k等於n×n則可判定n為回文數。
演算法設計
從低位到高位將某一整數拆分。對於一個整數(設變數名為a)無論其位數多少,若欲將最低位拆分,只需對10進行求模運算a%10,拆分次低位首先要想辦法將原來的次低位作為最低位來處理,用原數對10求商可得到由除最低位之外的數形成的新數,且新數的最低位是原數的次低位,根據拆分最低位的方法將次低位求出a/10、a%10,對於其他位上的數演算法相同。
利用這個方法要解決的一個問題就是,什麼情況下才算把所有數都拆分完?當拆分到只剩原數最高位時(即新數為個位數時),再對10求商的話,得到的結果肯定為0,可以通過這個條件判斷是否拆分完畢。根據題意,應將每次拆分出來的資料儲存到陣列中,原數的最低位存到下標為0的位置,次低位存到下標為1的位置……依次類推。
程式段如下:
for (i=0; a!=0; i++)
{
m[i] = a % 10;
a /= 10;
}
將陣列中元素重新組合成一新數。拆分時變數a的最高位仍然儲存在陣列中下標最大的位置,根據“回文數”定義,新數中資料的順序與a中資料的順序相反,所以我們按照下標從大到小的順序分別取出陣列中的元素組成新數k,由幾個數位組成一個新數時只需用每一個數位乘以所在位置對應的權值然後相加即可,在程式設計過程中應該有一個變數t來儲存每一位對應的權值,個位權值為1,十位權值為10,百位權值為100……,所以可以利用迴圈,每回圈一次t的值就擴大10倍。對應程式段如下:
for( ; i>0; i--)
{
k += m[i-l] * t;
t *= 10;
}
下面是完整的程式碼:
#include<stdio.h>
int main()
{
int m[16], n, i, t, count=0;
long unsigned a, k;
printf("No. number it's square(palindrome)n");
for( n=1; n<256; n++ ) /*窮舉n的取值範圍*/
{
k=0; t=1; a=n*n; /*計算n的平方*/
for( i=0; a!=0; i++ ) /*從低到高分解數a的每一位存於陣列m[1]~m[16]*/
{
m[i] = a % 10;
a /= 10;
}
for(; i>0; i--)
{
k += m[i-1] * t; /*t記錄某一位置對應的權值 */
t *= 10;
}
if(k == n*n)
printf("%2d%10d%10dn", ++count, n, n*n);
}
return 0;
}
執行結果:
No. number it's square(palindrome)
1 1 1
2 2 4
3 3 9
4 11 121
5 22 484
6 26 676
7 101 10201
8 111 12321
9 121 14641
10 202 40804
11 212 44944