gzwzm06

C++博客 :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評(píng)論 :: 0 Trackbacks

POJ 2402--Palindrome Numbers

#include <cstdio>
2

#include <cmath>
3

const int MAX = 20;
4

__int64 arr_bit[MAX]; //記錄i個(gè)位有幾個(gè)回文數(shù)
6

char strNum[50]; //保存結(jié)果
7

void Cal()
9

{
10

int i, j;
11

__int64 t;
12

arr_bit[1] = 9;
14

for ( i = 2; i <= MAX; ++i )
16

{
17

arr_bit[i] = arr_bit[i - 1];
18

t = 9;
19

for ( j = 0; j < (i >> 1) - 1; ++j )
20

t *= 10;
21

if ( i % 2 != 0 ){
22

t *= 10;
23

}
24

arr_bit[i] += t;
25

}
26

}
27

void GetNum(const __int64& n)
29

{
30

//對(duì)少于100的數(shù)直接輸出
31

if ( n <= 9 )
32

{
33

printf("%I64d\n", n);
34

}
35

else if ( n <= 18 )
36

{
37

printf("%I64d%I64d\n", (n - 9), (n - 9));
38

}
39

else {
40

int i, pos, wh, t, k;
41

__int64 del;
42

//找出當(dāng)前數(shù)有多少個(gè)位
44

for ( i = 3; i <= MAX; ++i )
45

{
46

if ( arr_bit[i] >= n )
47

{
48

pos = i;
49

break;
50

}
51

}
52

//pos個(gè)位的第幾個(gè)
54

del = n - arr_bit[pos - 1] - 1;
55

wh = pos >> 1;
57

if ( pos % 2 == 0 ) {
59

wh--;
60

}
61

//確定每個(gè)位
63

t = (int)pow(10, wh);
64

strNum[0] = strNum[pos - 1] = (int)(del / t) + 1 + '0';
65

del = del % t;
66

for ( i = wh - 1, k = 1; i >= 0; --i, ++k )
68

{
69

t = (int)pow(10, i);
70

strNum[k] = strNum[pos - k - 1] = (int)(del / t) + '0';
71

del = del % t;
72

}
73

strNum[pos] = '\0';
75

printf("%s\n", strNum);
77

}
79

}
81

int main()
83

{
84

__int64 n;
85

Cal();
87

while ( true )
89

{
90

scanf("%I64d", &n);
91

if ( n == 0 )
93

break;
94

GetNum(n);
96

}
97

return 0;
98

}
99

100

101

102

posted on 2009-03-29 15:00 巫閱讀(242) 評(píng)論(0) 編輯收藏引用所屬分類: 數(shù)學(xué)

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: POJ 2402--Palindrome Numbers Pku 3258--River Hopscotch(二分枚舉法)

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

gzwzm06

常用鏈接

留言簿(3)

隨筆檔案

文章分類

文章檔案

搜索

最新評(píng)論