POJ 1019 Number Sequence

Number Sequence

Description

A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2...Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another.

For example, the first 80 digits of the sequence are as follows:
11212312341234512345612345671234567812345678912345678910123456789101112345678910

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)

Output

There should be one output line per test case containing the digit located in the position i.

Sample Input

2
8
3
Sample Output

2
2

解决方案：

对于这题，我们要用到math.h中的log10函数。在这里，我们有个规律，对于每一个正整数value，其位数等于log10(value) + 1.

我们用一个数组a来保存每个子串的位数（如子串123456789101112的位数为15）.

我们用一个数组b来保存每个子串以及此子串之前所有的位数。

由于i有其取值范围，故我们可以选择数组维数大小为32000

下面就开始寻找特定位置上的那个数了。

1.首先根据所输入的位置来确定在哪个子串中。

2.确定是字串的哪个数。

3.再确定是该数的第几位。

4.然后输出之。

具体代码如下(gcc编译时加上-lm参数)：

POJ 1019

 1 #include <stdio.h>
 2 #include <time.h>
 3 #include <math.h>
 4 #include <stdlib.h>
 5 //log10(n)就可以求出n的位数
 6 #define LEN 32000
 7 unsigned int a[LEN];
 8 unsigned int b[LEN];
 9 int main()
10 {
11     a[0] = 0;
12     a[1] = 1;
13     b[0] = 0;
14     b[1] = 1;
15     int i;
16     for(i = 2; i < LEN; i++)
17     {
18         a[i] = a[i-1] + log10((double)i) + 1;
19         b[i] = b[i-1] + a[i];
20     }
21 
22     unsigned int cases;
23     unsigned int n;
24     scanf("%u", &cases);
25     while(cases--)
26     {
27         scanf("%u", &n);
28         unsigned int j;
29         for(j = 0; j < LEN; j++)
30             if(n <= b[j])
31                 break;
32         //在字串中的位置
33         unsigned int remain = n - b[j-1];
34 
35         unsigned int value;
36         unsigned int sum = 0;
37         for(value = 1; value < LEN; value++)
38         {
39             sum += 1+log10((double)value);
40             if(sum >= remain)
41                 break;
42         }
43         //value的位数
44         unsigned int value_bits = 1+log10((double)value);
45         unsigned int position = remain - (sum - value_bits);
46         //求value的第position位
47         char* str = (char*)malloc(10*sizeof(char));
48         int temp = value;
49         int stri = 0;
50         while(temp)
51         {
52             int temp1 = temp%10;
53             str[stri++] = temp1 + '0';
54             temp = temp/10;
55             
56         }
57         str[stri] = '\0';
58         if(position == value_bits)
59             printf("%c\n", str[0]);
60         else
61             printf("%c\n", str[position - 1]);
62     }
63     return 0;
64 }