计算第N位的形如12321的可逆数
我是先把1位,2位~100位数中各含几个可逆数算出来,计入数组num,然后根据输入的N位置,算出该数有几位,并处于什么位置。依次通过取整取余得出结果。
如要求出第24位,因为1位数和2位数中各含9个可逆数,所以所要求的数位于3位数中的第6个
先用6对num【1】取整(三位数的个数其实就是最高和最低位从1到9,而中间只是1位数的个数加1(0)),
取整后得0,而0代表第一组1位数,所以应该加1,从而将1放入我们要输出的数组。接着6对num【1】取余后是6,因为已经是最中间位了,所以就把5存入。输出后得出151!
期间我也得到了很多WA,是因为没有考虑到一些情况,大家要仔细啊!!!
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
long long int num[101];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
num[1]=9;num[2]=9;int j=0,k=0;
for (int i=3;i<=100;i++) //相应位数中有多少个对称数
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (i%2==1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
num[i]=9*(num[i-2]+pow(10.0,j++));
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
num[i]=9*(num[i-2]+pow(10.0,k++));
}
}
long long int n;
while (scanf("%lld",&n)!=EOF&&n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
long long int sum=0,index;
int len;
for (int i=1;i<101;i++) //计算位数
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
sum+=num[i];
if (n<=sum)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
len=i;
sum-=num[i];
break;
}
}
index=n-sum;
char output[100];
int kk=0;bool start=true;
for (int j=len;j>0;j-=2)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ((j==1||j==2)&&start) //一位或二位时直接记录
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
output[kk++]=index+'0';
break;
}
if ((j==1||j==2)&&start==false)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (index==0) //余数为0时刚好为该位数中的最大数
output[kk++]='9';
else
output[kk++]=index+'0'-1;
break;
}
if(len%2==1) //位数为奇数时
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(start)
output[kk++]=index/(num[j-2]+(long long int)pow(10.0,(j-1)/2-1))+'0'+1; //开始时若整除为零,实际上是1
else
output[kk++]=index/(num[j-2]+(long long int)pow(10.0,(j-1)/2-1))+'0';
index%=(num[j-2]+(long long int)pow(10.0,(j-1)/2-1));
if (index==0&&output[kk-1]!='0')
output[kk-1]-=1;
else if (index==0&&output[kk-1]=='0') //余数为零即最大值
output[kk-1]='9';
start=false;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(start)
output[kk++]=index/(num[j-2]+(long long int)pow(10.0,(j-2)/2-1))+'0'+1;
else
output[kk++]=index/(num[j-2]+(long long int)pow(10.0,(j-2)/2-1))+'0';
index%=(num[j-2]+(long long int)pow(10.0,(j-2)/2-1));
if (index==0&&output[kk-1]!='0')
output[kk-1]-=1;
else if (index==0&&output[kk-1]=='0')
output[kk-1]='9';
start=false;
}
}
for (int i=0;i<len/2;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("%c",output[i]);
}
if (len%2==1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for (int i=len/2;i>=0;i--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("%c",output[i]);
}
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for (int i=len/2-1;i>=0;i--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("%c",output[i]);
}
}
printf("\n");
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)