例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≤109 )，問第 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≤1018，
輸出格式
輸出從初始字串生成的無限字串中的位置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，
方程 n2-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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/412905.html
標籤：其他