轉載請注明出處：優 YoU ? http://user.qzone.qq.com/289065406/blog/1301527312
大致題意：
有一串數字串，其規律為
1 12 123 1234 12345 123456 1234567 12345678 123456789 12345678910 1234567891011 123456789101112······k
輸入位置 n ，計算這一串數字第 n 位是什么數字，注意是數字，不是數！ 例如 12345678910 的第 10 位是 1 ，而不是 10 ，第 11 位是 0 ，也不是 10 。總之 多位的數 在序列中要被拆分為幾位數字，一個數字對應一位。
解題思路：
首先建議數學底子不好的同學，暫時放一放這題，太過技巧性了，連理解都很困難
模擬分組，把 1 看做第 1 組， 12 看做第 2 組， 123 看做第 3 組 …… 那么第 i 組就是存放數字序列為 [1,i] 的正整數，但第 i 組的長度不一定是 i
已知輸入查找第
n
個位的
n
的范圍為
(1 ≤ n ≤ 2147483647)
，那么至少要有
31268
個組才能使得數字序列達到有第
2147483647
位
注意：
2147483647
剛好是
int
的正整數最大極限值
(
詳細的解題思路請參照程序的注釋。
其中數學難點有
2
：
(int)log10((double)i)+1
(i-1)/(int)pow((double)10,len-pos)%10
非常技巧性的處理手法，其意義已在程序中標明
另外要注意的就是
log()
和
pow()
函數的使用
兩個都是重載函數，函數原型分別為
double log(double)
float log(float)
double pow(double , double)
float pow(float ,float)
所以當傳參的類型不是
double
或
float
時，必須強制轉換為其中一種類型，否則編譯出錯。一般建議用
double
1
//
Memory Time
2
//
476K 0MS
3
4
#include
<
iostream
>
5
#include
<
math.h
>
6
using
namespace
std;
7
8
const
int
size
=
31269
;
9
10
unsigned a[size];
//
a[i] 表示第i組數字序列的長度
11
unsigned s[size];
//
s[i] 表示前i組數字序列的長度
12
//
第i組存放的數字序列為 [1,i]的正整數，但第i組的長度不一定是i
13
//
例如數字13要被看做1和3兩個位，而不是一個整體
14
15
/*
打表，預先獲取第2147483647個位的序列分組情況
*/
16
17
void
play_table(
void
)
18
{
19
a[
1
]
=
s[
1
]
=
1
;
20
for
(
int
i
=
2
;i
<
size;i
++
)
21
{
22
a[i]
=
a[i
-
1
]
+
(
int
)log10((
double
)i)
+
1
;
//
log10(i)+1 表示第i組數字列的長度 比 第i-1組 長的位數
23
s[i]
=
s[i
-
1
]
+
a[i];
//
前i組的長度s[i] 等于 前i-1組的長度s[i-1] + 第i組的長度a[i]
24
}
//
log()是重載函數，必須對int的i強制類型轉換，以確定參數類型
25
return
;
26
}
27
28
/*
計算序列第n個位置上的數字
*/
29
30
int
compute(
int
n)
31
{
32
int
i
=
1
;
33
while
(s[i]
<
n)
34
i
++
;
//
確定整個數字序列的第n個位置出現在第i組
35
36
int
pos
=
n
-
s[i
-
1
];
//
pos為 整個數字序列的第n個位置 在 第i組中的下標值
37
38
int
len
=
0
;
39
for
(i
=
1
;len
<
pos;i
++
)
//
從第1組開始遍歷第i前的每一個組，利用log10(i)+1遞推第i組的長度
40
len
+=
(
int
)log10((
double
)i)
+
1
;
//
len為第i組(n所在的組)的長度
41
42
return
(i
-
1
)
/
(
int
)pow((
double
)
10
,len
-
pos)
%
10
;
43
//
之所以i-1，是因為前面尋找第i組長度時，i++多執行了一次
44
//
i=i-1 此時i剛好等于第n位個置上的數 （數是整體，例如123一百二十三，i剛好等于123，但n指向的可能是1，2或3）
45
//
pos為n指向的數字在第i組中的下標值
46
//
len為第i組的長度
47
//
那么len-pos就是第i組中pos位置后多余的數字位數
48
//
則若要取出pos位上的數字，就要利用(i-1)/pow(10,len-pos)先刪除pos后多余的數字
49
//
再對剩下的數字取模，就可以得到pos
50
//
例如要取出1234的2，那么多余的位數有2位：34。那么用1234 / 10^2，得到12，再對12取模10，就得到2
51
52
}
//
pow()是重載函數，必須對int的i強制類型轉換，以確定參數類型
53
54
int
main(
void
)
55
{
56
play_table();
57
58
int
test;
59
cin
>>
test;
60
while
(test
--
)
61
{
62
int
n;
63
cin
>>
n;
64
cout
<<
compute(n)
<<
endl;
65
}
66
return
0
;
67
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
