例52  数字序列

问题描述

给出了一个正整数i。编写一个程序，以查找数字序列S1S2…Sk中位于位置i的数字。每组Sk由一系列从1到k的正整数组成。

例如，序列的前80位数字如下所示：

11212312341234512345612345671234567812345678912345678910123456789101112345678910

输入

输入文件的第一行包含一个整数t（1≤T≤10），测试用例的数量。

每个测试用例占一行，该行包含一个整数i（1≤i≤ 2147483647）

输出

每个测试用例输出一行，其中包含位于位置i的数字。

输入样例

2

8

3

输出样例

2

2

        （1）编程思路。

        先将整个数字序列112123123412345123456123456712345678123456789…分组如下

        1  12  123  1234  12345  123456  1234567  12345678  123456789…

        设a[i] 表示第i组数字序列的长度。显然有

        a[1] = 1， a[2] =2， a[3] = 3， …，a[9]=9，a[10]=11，a[11]=13，…。

        通过对比a[i]与a[i+1]发现，当i<9时，a[i+1]=a[i]+1；当10<i<99时，a[i+1]=a[i]+2；

        当100<i<999时，a[i+1]=a[i]+3；…，依次类推。

        用如下的循环可以求得第n个位置的数字应该在第i组中的位置值pos

          for (i=1, pos=n; a[i]<pos; i++)

               pos=pos-a[i];

        然后求出pos位置值的数字是第i组中的第j个数，并且确定其是第j个数的第几位，从而得到答案。

        上面定义的a数组还可用于确定pos位置的数字在某组中的哪一个数中，此时a[i]可表示前i个数的总长度（位数），a[1]=1表示1的长度为1，a[2]=2表示到第2个数的长度为2，即12的位数为2，…，a[11]=13表示到第11个数11的总长度为13，即1234567891011的位数为13。

        例如，要求序列第14个数是多少？

        14-a[1]-a[2]-a[3]-a[4]=4<a[5]，因此，第14个数字应该出现在第5组中，且位置值为4，它是第5组的第4个数的第1个数字，所以第14个数字是4。

        再如，要求序列第100个数是多少？

        100-a[1]-a[2]-a[3]-a[4]-a[3]-a[4]-a[5]-a[6]-a[7]-a[8]-a[9]-a[10]-a[11]-a[12]

         =100-(1+2+3+4+5+6+7+8+9+11+13+15) = 16 < a[13]，因此，第100个数字应该出现在第13组中，且在该组的位置值为16，而a[12]=15，a[13]=17，因此位置值16的数字应该出现在第13组的第13个数中，并且是第13个数的第16-15=1位，而第13个数13的第1位为1，所以第100个数字是1。

（2）源程序。

#include <stdio.h>

int main()

{

    int  a[31269];  // a[i] 表示第i组数字序列的长度

    int x=1,y=1;

    int i,j;

    for (i=1;i<=31268;i++)

       {

        a[i]=x;

        if (i==9||i==99||i==999||i==9999) y++;

        x+=y;

    }

    int t,n;

    scanf("%d",&t);

    while (t--)

       {

        scanf("%d",&n);

        int pos,index,digit[5],len;

           // 求得第n个位置在第i组中的下标值pos

        for (i=1, pos=n; a[i]<pos; i++)

               pos=pos-a[i];

        j=1;

           // pos位置值的数字是第i组中的第j个数字

        while (a[j]<pos) j++;

        // 第n个位置的数字是数j的第index位

        index=pos-a[j-1];

           len=0;

        while(j)

           {

           digit[len++]=j%10;

           j/=10;

        }

        printf("%d\n",digit[len-index]);

    }

    return 0;

}

习题52

52-1  第N个数字

问题描述

假设：

S1 = 1

S2 = 12

S3 = 123

S4 = 1234

……

S9 = 123456789

S10 = 1234567891

S11 = 12345678912

……

S18 = 123456789123456789

S19 = 1234567891234567891

……

现在我们把所有的串连接起来

S = 1121231234……123456789123456789112345678912……

那么你能告诉我在S串中的第N个数字是多少吗？

输入

输入首先是一个数字T，代表有T次询问。

接下来的T行每行有一个整数N（1 <= N < 2^31）。

输出

对于每个N，输出S中第N个对应的数字。

输入样例

6

1

2

3

4

5

10

输出样例

1

1

2

1

2

4

        （1）编程思路。

        由于数字序列中只是数字1~9循环，因此本题比例52简单。

        设a[i] 表示第i组数字序列的长度。显然有 a[i]=i。先求出第n个数字在第i组，将前面各组的数字个数都减掉，剩余的数就是在第i组的位置，再对这个位置除9取余即可。

        （2）源程序。

#include <stdio.h>

int main()

{

    int t;

    scanf("%d",&t);

    while (t--)

    {

        int n;

        scanf("%d",&n);

        int a=1;   // 第1组1个数

        while (n>a)

        {

          n-=a;    // 减去上面每组的数字个数

          a++;

        }

        n=n%9;

        if(n==0) n=9;

        printf("%d\n",n);

    }

    return 0;

}

52-2  第M个整数

问题描述

将1~n这n个正整数按字典顺序进行排序。字典排序的含义为：从最高位开始比较。1开头的数排在最前面，然后是2开头的数，然后是3开头的数，……最高位相同的数字，按同样的逻辑比较次高位，……，以此类推。

给定一个整数m，返回排序后第m个整数是多少？

例：给定整数为n=13，m=5，那么字典排序结果为：1,10,11,12,13,2,3,4,5,6,7,8,9，序列中第5个整数为13。

输入

输入包括多行，每行是两个整数N和M（1≤M≤N≤10⁶）。

输出

对每行输入，输出一行，该行是第M个整数。

输入样例

11 4

200 25

100000000888888879 1000000000

输出样例

2

120

100000001

        （1）编程思路。

先观察一下，若n=210，按字典序排列依次为

1 10 100 101 102 103 104 105 106 107 108 109

11 110 111 112 113 114 115 116 117 118 119

12 120 121 122 123 124 125 126 127 128 129

13 130 131 132 133 134 135 136 137 138 139

14 140 141 142 143 144 145 146 147 148 149

15 150 151 152 153 154 155 156 157 158 159

16 160 161 162 163 164 165 166 167 168 169

17 170 171 172 173 174 175 176 177 178 179

18 180 181 182 183 184 185 186 187 188 189

19 190 191 192 193 194 195 196 197 198 199

2 20 200 201 202 203 204 205 206 207 208 209

21 210 22 23 24 25 26 27 28 29

3 30 31 32 33 34 35 36 37 38 39 4 40 41 42 43 44 45 46 47 48 49

5 50 51 52 53 54 55 56 57 58 59 6 60 61 62 63 64 65 66 67 68 69

7 70 71 72 73 74 75 76 77 78 79 8 80 81 82 83 84 85 86 87 88 89

9 90 91 92 93 94 95 96 97 98 99

        定义b[i]保存位数不超过i的整数的个数。显然，b[1]=10（即0~9这10个），b[2]=110（即1位的0~9，2位的00~99），b[3]=1110，…，b[10]=11111111110，…。这个数字的作用在于确定以某个数字k开头的不同位数的个数有多少。例如，要确定以数字1开头的长度不超过4位的整数有多少个？首先，整数1肯定是一个，置cnt=1，以后可以看成在1的后面依次扩充1位、扩充2位和扩充3位得到，cnt=cnt+b[3]=1111，即以数字1开头的长度不超过4位的整数有1111个。再例如，要确定以数字1开头的长度不超过4位且小于1234的整数有多少个？首先，整数1肯定是一个，置cnt=1，以后可以看成在1的后面依次扩充1位、扩充2位和扩充3位得到，但扩充3位后得到的4位数可能超过1234，而扩充1位或2位得到的2位数或3位数肯定小于1234，所以cnt=cnt+b[2]=111（扩充1~2位），再计算扩充3位的情况，cnt=cnt+(1234%1000)+1=346，即以数字1开头的长度不超过4位且小于1234的整数有346个。若要确定以数字2开头的长度不超过4位且小于1234的整数，则cnt=1，cnt=cnt+b[2]=111，计算扩充3位时，由于2>1234/1000，即以2开头的4位数均大于1234，这样以数字2开头的长度不超过4位且小于1234的整数只有111个。

        求按字典序排列的第M个数时，从高位到低位，每位从小到大进行枚举填充数字，枚举时按上面的介绍计算以数字k开头的长度不超过len位且值不超过N的整数的个数，从而确定该位填写的数字。在填充过程中注意判断前导零的情况以及最大值边界的情况。

        为方便理解源程序代码，下面用四个实例的构造来说明。

        例如，设n=120，m=25。要求的整数的位数最多3位，先构造最高位，设填充1，以1开头的且小于120的整数有32个（1，10~19，100~120），m=25<32，所以1~120字典序中的第25个整数最高位一定是1，确定了一位后，m=m-1=24；之后确定次高位，以0开头且小于n的两位整数有11个（0，00~09，因为最高位已确定为1，非0，所以这里的0不是前导0），m=m-11=13，以1开头的数字有11个（1,10~19），m=m-11=2，以2开头的数字有11个（2,20~29），m=2<11，所以，次高位填写2，填写后，m=m-1=1；之后，确定最低位，以数字0开头的1位数只有1个，m<=1，所以最低位确定为0，填写后m=m-1=0，构造结束。1~120字典序中的第25个整数为120。

         再如，设n=2345，m=1680。以1开头且小于n的整数有1111个，m=m-1111=569，以2开头且小于n的整数有457个，其中1位数1个，2位数10个，3位数100个，4位数346个（2，20~29，200~299，2000~2345），m=569-457=112，以3开头且小于n的整数有111个，m=112-111=1，以4开头的数字有111个，m=1<111，所以1~2345字典序中的第1680个整数的最高位一定为4，填写后，m=m-1=0，m等于0，填写结束。所以结果为4。

        又如，设n=2345，m=1675。先构造最高位，以1开头且小于n的整数有1111个，m=m-1111=564，以2开头且小于n的整数有457个，m=564-457=107，以3开头且小于n的整数有111个，m=107<111，所以1~2345字典序中的第1675个整数最高位一定是3，确定了一位后，m=m-1=106；之后确定次高位，符合要求的以0~8开头的数各有11个（注意：以3开头的4位数均大于2345），m=m-9*11=7，以9开头的数有11个（即39，390~399这11个数），m=7<11，所以1~2345字典序中的第1680个整数的次高位一定为9，填写后，m=m-1=6；之后以0~4开头的1位数各1个，m=m-5*1=1，填写5，填写后m=m-1=0，m等于0，填写结束。所以结果为395。

         又如，设n=2345，m=1564。先构造最高位，以1开头且小于n的整数有1111个，m=1564-1111=453，以2开头且小于n的整数有457个，m=453<457，所以1~2345字典序中的第1564个整数最高位一定是2，确定了一位后，m=m-1=452；之后确定次高位，以0，1，2开头且小于n的3位以内整数各有111个，m=m-3*111=119，以3开头的3位以内整数有57个（3，30~39，300~345），m=m-57=62，之后符合要求的以4~8开头的数各有11个，m=m-5*11=7，以9开头的数有11个，m=7<11，所以1~2345字典序中的第1564个整数的次高位一定为9，填写后，m=m-1=6；之后以0~4开头的1位数各1个，m=m-5*1=1，填写5，填写后m=m-1=0，m等于0，填写结束。所以结果为295。

        （2）源程序。

#include <stdio.h>

typedef long long LL;

int main()

{

    LL n, m;

    LL a[19]={1},b[19]={0};

    int i,j;

    for (i=1; i<=18; i++)

    {

        a[i] = a[i-1]*10;

        b[i] = a[i]+b[i-1]; 

    }

    while (scanf("%lld%lld",&n,&m)!=EOF)

    {

        LL tmp=n;

        int len=0;

        while (tmp)

        {

           len++;

           tmp/=10;

        }

        LL ans=0;

        for (i=0; i<len; i++)   // 从高位开始构造

        {

           int res;

           for (j=((i==0)?1:0); j<=9; j++) // 从小的数开始构造

           {

               tmp = (ans*10+j)<=n;

               if (len-i-2 > 0) tmp += b[len-i-2];  // 长度小于len的数有几个

               if (len-i-1 > 0)              // 长度等于len的数有几个

               {

                  if (ans*10+j < n/a[len-i-1])

                      tmp += a[len-i-1];

                  else if (ans*10+j == n/a[len-i-1])

                      tmp += n%a[len-i-1]+1;

               }

               if (m>tmp) m-= tmp;

               else

               {

                  res = j;

                  break;

               }

           }

           ans = ans*10+res;

           m--;                 // 每选了一个数就减一

           if (m==0)  break;

        }

        printf("%lld\n",ans);

    }

    return 0;

}

52-3  有趣的数

问题描述

将1到N的正整数集合中的元素按照字典序排列，例如当N=11时，其顺序应该为：1,10,11,2,3,4,5,6,7,8,9。

定义K在N个数中的位置为Q(N,K)，例如Q(11,2)=4。现在给出整数K和M，要求找到最小的N，使得Q(N,K)=M。

输入

输入包括多行，每行是两个整数K和M。

输出

每组输入输出一行，该行是最小的N，如果不存在这样的N就输出0。

输入样例

2 4

100000001 1000000000

输出样例

11

100000000888888879

        （1）编程思路。

        先确定整数K的最小位置。

        例如，k=120时，排在它前面的1位数有1个（1），2位数有3个（10、11和12），3位数有20个（100~119），因此120的最小位置pos=1+3+20+1=25。

        再例如K=1680，排在它前面的1位数有1个（1），2位数有7个（10~16），3位数有20个（100~168），4位数有20个（1000~1680），因此1680的最小位置pos=1+7+69+681=758。

        求出K的最小位置pos后，将pos和 M 进行比较。

        若 pos=M，那么只要出现了K 就可以使得K的位置是M，因此N的最小值就是K。

        若 pos>M，无解，因为pos是K的最小位置。不存在其他的位置比pos还要小。

        若 pos<M，说明还有字典序排在K前面的数，但是位数小于等于K的已经穷举完了，因此肯定有位数大于K的数排在K的前面。逐步增加位数，同时更新最小位数。当某个时刻 pos≥M ，先将pos减回去，算出M 与pos之间的差，再加上 10^x（x是当前位数），最后减去 1（因为从 0 开始算），就是 N的最小值。

       （2）源程序。

#include <stdio.h>

int main()

{

    long long  m,k;

    while (scanf("%lld%lld",&k,&m)!=EOF)

    {

        long long pos=0;

        long long p=1;

        while (k>=p) p*=10;

        p/=10;

        long long temp1=k;

        long long temp2=p;

        while (temp1>0)

        {

            pos+=temp1-temp2+1;

            temp1/=10;

            temp2/=10;

        }

        if (pos>m) printf("0\n");

        else if (pos==m) printf("%lld\n", k);

        else

        {

            long long temp=k*10;

            p*=10;

            if (temp-p==0)

            {

                printf("0\n");

                continue;

            }

            while (pos-p+temp<m)

            {

                pos=pos-p+temp;

                temp*=10;

                p*=10;

            }

            p+=m-pos-1;

            printf("%lld\n", p);

        }

    }

       return 0;

}