例51  第n个回文数

问题描述

回文是向前和向后读相同的单词、数字或短语。例如，“anna”是一个回文。数字也可以是回文（例如151或753357）。此外，数字可以按大小排序。前几个回文数字是：1，2，3，4，5，6，7，8，9，11，22，33，…。

数字10不是回文（即使您可以将其写为010），但不允许将零作为前导数字。

输入

输入由一系列行组成，每行包含一个整数值i（1<=i<=2*10^9）。该整数值i表示要输出的回文数的序号，其中1表示第一个回文数（1），序号2表示第二个回文数（2），依此类推。输入由包含0的行终止。

输出

对于每个输入值i，输出第i个回文数。

输入样例

1

12

24

0

输出样例

1

33

151

        （1）编程思路。

        1位和2位的回文数各有9个（最高位为1~9），3位和4位的回文数各有90个（高两位为10~99），5位和6位的回文数各有900个（高3位为100~999），…。

        定义数组long long f[30]保存k位回文数的基数10^((k-1)/2)，即f[1]=f[2]=1，f[3]=f[4]=10，f[5]=f[6]=100，…。

        计算出第n个回文数是几位数，一个简单循环即可完成。例如，n=24，由于n>9*f[1]，所以n至少是2位以上的回文数，len=2，n=n-9=15；由于n>9*f[2]，所以n至少是3位以上的回文数，len=3，n=n-9=6；由于n<9*f[3]，所以n是一个3位回文数。

        确定了第n个回文数对应的位数后，将数对半，对半后，对前半段进行填数，后半段的数字只要将前半段反向输出即可。

        例如，第24个回文数是3位回文数中的第6个数，3位回文数前半段为前2位（10~99），第6个数为15，后半段为1，故第24个回文数为151。

（2）源程序。

#include <stdio.h>

#include <string.h>

int main()

{

    long long f[30]={0,1,1};

    int i,j;

    for (i=3; i<30; i++)

    {

        if (i&1) f[i] = f[i-1]*10;

        else f[i] = f[i-1];

    }

    long long n;

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

    {

        int k = 1;                  //  k表示回文串数字的位数

        while(n > f[k]*9)

        {

            n-=9*f[k++];

        }

        int mid = (k+1)/2;

        long long ans = 1;

        for (i=1, j=0; i<=mid; i++)   // 第一位到中间那一位

        {

            if (i==1) j=1;      //  i为1，因为首位不能为0，所以要从1开始

            else  j = 0;       //  j表示第i位要填的数字

            while (n > f[k])

            {

               n -= f[k];

               j++;

            }

            k -= 2;    // 除了第i位和i相对称的那一位，中间还有几位

            if (i==1)  ans = j;

            else  ans = ans*10 + j;

        }

        printf("%lld",ans);

        if (k&1) ans /= 10;    //  位数为奇数，最中间的数只输出一次

        while (ans)

        {

           printf("%lld",ans%10);

           ans /= 10;

        }

        printf("\n");

    }

    return 0;

}

习题51

51-1  Moo

        本题选自洛谷题库 （https://www.luogu.org/problem/ P1885）

题目描述

奶牛 Bessie 最近在学习字符串操作，它用如下的规则逐一的构造出新的字符串：

S(0) =S(0)= moo

S(1) =S(0)+ m + ooo + S(0) = moo + m ++ ooo + moo = moomooomoo

S(2) = S(1)+ m + oooo + S(1) =moomooomoo + m + oooo + moomooomoo = moomooomoomoooomoomooomoo

Bessie 就这样产生字符串，直到最后产生的那个字符串长度不小于读入的整数 N 才停止。

通过上面观察，可以发现第 k 个字符串是由：第 k-1个字符串 + m+ (k+2 个 o))+ 第 k−1 个字符串连接起来的。

现在的问题是：给出一个整数 N (1≤N≤10⁹ )，问第 N 个字符是字母 m 还是 o？

输入格式

一个正整数 N。

输出格式

一个字符，m 或者 o。

输入样例

11

输出样例

m

        （1）编程思路。

        设字符串S(i)的长度为Len[i]，由字符串的构造规律知：

        Len[0]=0+1+2   （前面没有子串，有1个m和2个0）

        Len[1]=len[0]+1+3+len[0]  （前后均有子串S[0]，中间有1个m和3个O）

        更一般地，Len[k]=len[k-1]+1+(k+2)+len[k-1] = 2*len[k-1]+(k+1)+2

        要求第 N 个字符是字母 m 还是 o，先得看达到N个字符的最短字符串是S(?)。

        由样例解释知：字符串 S(0) 是moo，现在要求第11 个字符，显然字符串 S(0) 不够长；同样S(1) 的长度是 10，也不够长； S(2) 的长度是25，够长了，S(2) 的第11 个字符是 m，所以答案就输出 m。

        要求达到N个字符的最短字符串是S(?)，可以采用如下的循环

        int  t=0,k=1;    // 初始值，表示字符串为S(0)，其中t表示前面子串的长度

        while (n>2*t+k+2)

        {

            t=2*t+2+k;

            k++;

        }

        退出循环后，正好求得满足要求的字符串S(k-1)，这个字符串有三个部分构成：第1部分为子串S(k-2)，长度为t，这1部分都存在（即n的值肯定大于t）；第2部分为1个m加上k+1个o，如果n的值在这个范围中，则可以直接确定第N个字符是什么，当n==t+1时，字符为m，当n<=t+k+2，字符为o（从t+2到t+k+2这k+1个字符是o）；第3部分又是子串S(k-2)，此时n>t+k+2，去掉第1部分和第2部分后，n=n-(t+k+2)，再到子串S(k-2)中去确定第n个字符是什么，继续进行上面的循环。

        （2）源程序。

#include <stdio.h>

int main()

{

    int n;

    scanf("%d",&n);

    while (1)

    {

        int t=0,k=1;

        while (n>2*t+k+2)

        {

            t=2*t+2+k;

            k++;

        }

        if (n==t+1)

        {

           printf("m\n");

           break;

        }

        if (n<=t+k+2)

        {

            printf("o\n");

            break;

        }

        n=n-t-k-2;

        t=0;

        k=1;

    }

    return 0;

}

51-2  无限字符串

问题描述

给定一个字符串，让后面的字符旋转一次（每一次正确的旋转，最后一个字符都会成为新的第一个字符）。也就是说，给定一个初始字符串，之后的每一步都会增加当前字符串的长度。

例如，初始字符串为COW，第1次旋转后变为COWWCO，第2次旋转后变为 COWWCOOCOWWC，…。

给定初始字符串和索引值N，请确定旋转生成的无限字符串中位置N的字符。

输入格式

输入包括一个字符串和一个整数N。该字符串包含最多30个大写字母，N≤10¹⁸。

输出格式

输出从初始字符串生成的无限字符串中的位置N的字符。第一个字符是 N=1。

输入样例

COW  8

输出样例

C

        （1）编程思路。

        观察无限字符串的构造规律可以发现：每一次旋转，增长的部分的第1位跟原部分的最后一位相同，增长部分的第2位到最后一位跟原部分的第1位到倒数第2位相同。

        以样例为例：COW--->COWWCO---->COWWCOOCOWWC。可以发现第1次旋转后，生成字符串的第1位到第2位与第5位到第6位相同。第2次旋转增长后，字符串的第1位到第5位与第8位到第12位相同。所以可以不断的把前面一半不用的删除掉，最后剩下初始字符串时输出对应字符即可。

        以样例为例描述计算过程。N=8，原始字符串长度len=3，第1次增长后串长为6，第2次增长后串长为12。由于，3<(N=8)<12，因此可以将前面一般丢掉N=N-12/2=6，由于剩余字符串OCOWWC的最高位是前一半的最低位，也需丢掉（或相当移到最低位），即N=N-1=5；此时3<N<6，因此同样可以将前面一般丢掉N=N-6/3-1=1；此时N<=3，对应初始字符串中第1个字符，输出str[n-1]即可。故输出为字符C。

        再以N=11为例，原始字符串长度len=3，第1次增长后串长为6，第2次增长后串长为12。由于，3<(N=11)<12，因此可以将前面一般丢掉N=N-12/2-1=4；此时3<N<6，因此同样可以将前面一般丢掉N=N-6/3-1=0，由于N=0实际上是原字符串中最后一个字符，由此置N=len=3；此时N<=3，对应初始字符串中第3个字符，输出str[n-1]即可。故输出为字符W。

       （2）源程序。

#include <stdio.h>

#include <string.h>

int main()

{

    char str[31];

    long long n;

    scanf("%s%lld",str,&n);

    long long len=strlen(str);

    while (len<n)

    {

        long long i=len;

        while (n>i*2) i*=2;

        n=n-(i+1);

        if (n==0) n=i;

    }

    printf("%c",str[n-1]);

    return 0;

}

51-3  无穷的序列

题目描述

有一个无穷序列如下：

110100100010000100000…

请你找出这个无穷序列中指定位置上的数字。

输入格式

第一行一个正整数N（N≤1500000），表示询问次数；

接下来的N行每行一个正整数Ai（Ai≤10^9），Ai表示在序列中的位置。

输出格式

N行，每行为0或l，表示序列第Ai位上的数字。

输入样例

4

3

14

7

6

输出样例

0

0

1

0

         （1）编程思路。

        先将整个无穷序列110100100010000100000……分为如下无限个区间

        1  10  100  1000  10000  100000……

        显然第n个区间有n个数字，并且1只出现在每个区间的第一位。

        前n个区间累计一共有(n+1)*n/2个数字。所以每1个数字“1”出现的位置一定是在(n*n+n)/2+1，考虑到第1位的数字“1”，可修改位置为(n*n-n)/2+1。

        对于每个输入的数字ai，如果 (n*n-n)/2+1=a（ n ≥0 ）有整数解就是1，否则就是0。

        方程 n²-n+2-2a=0的解为 n=(1+sqrt(8*a-7))/2   或  n=(1-sqrt(8*a-7))/2

        非负整数解只可能为  n=(1+sqrt(8*a-7))/2

        若 n*n-n==2*a-2，则数字为“1”，否则为“0”。

       （2）源程序。

#include <stdio.h>

#include <math.h>

int main()

{

    int n,ai,t;

    scanf("%d",&n);

    while (n--)

    {

        scanf("%d",&ai);

        t=(1+sqrt(8*ai-7))/2;

        if (t*t-t==2*(ai-1))

            printf("1\n");

        else

            printf("0\n");

    }

    return 0;

}