POJ1019-Number Sequence

来源:转载

转载请注明出处:優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的正整数最大极限值( ),所以对于n用int定义就足矣。但是s[31268]存在超过2147483647的位数,因此要用unsigned 或long 之类的去定义s[]

 

详细的解题思路请参照程序的注释。

其中数学难点有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)

所以当传参的类型不是doublefloat时,必须强制转换为其中一种类型,否则编译出错。一般建议用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 }
我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863 || 我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b || 我的新浪微博:http://weibo.com/lyy289065406 || 我的腾讯微博:http://t.qq.com/lyy289065406 || 我的QQ空间:http://user.qzone.qq.com/289065406 || 我的百度空间:http://hi.baidu.com/you289065406/home || 我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


分享给朋友:
您可能感兴趣的文章:
随机阅读: