昨在pkuoj上作了题目1019
内容就是有一个数列以1 1 2 1 2 3 1 2 3 4…..这样的规律排列下去 求数列第i个数字是什么
数列前80项是11212312341234512345612345671234567812345678912345678910123456789101112345678910
当然 每个数字就是一个项
难点就在多位数(>=2位)时数字被拆开….
http://acm.pku.edu.cn/JudgeOnline/problem?id=1019 这个是原题描述
以下是用c++编的正确答案
c++:
#include<iostream.h>
int main()
{
long a[5]={0,45,9045,1395495,189414495};
long b[5]={0,9,189,2889,38889};
long c[5]={0,10,100,1000,10000};
long d[5]={1,10,100,1000,10000};
unsigned long i,j,k,n,t;
cin>>t;while(t–)
{
cin>>n;
for(i=1;i<5;i++)
if(n<=a[i])break;
n-=a[i-1];
for(k=0,j=1;k<n;j++)
k=b[i-1]*j+i*j*(j+1)/2;
–j;
cout<<j<<endl;
cout<<n<<endl;
n=n-b[i-1]*(j-1)-i*j*(j-1)/2;
cout<<n<<endl;
for(i=1;i<5;i++)
if(n<=b[i])break;
if(i==1)cout<<n<<endl;
else
{
n-=b[i-1];
k=(n-1)/i+c[i-1];
cout<<k/d[i-(n-1)%i-1]%10<<endl;
}
}
return 0;
}
我又用c按上面的算法写了下 可是输出的结果就和上面的不同了。。。
c:
#include <stdio.h>
int main()
{
long a[5]={0, 45, 9045, 1395495, 189414495};
long b[5]={0, 9, 189, 2889, 38889};
long c[5]={0, 10, 100, 1000, 10000};
long d[5]={1,10,100,1000,10000};
long i,j,k,n,t;
scanf(“%ld”,&t);
while(t–)
{
scanf(“%ld”,&n);
for ( i = 1; i < 5; i++)
if (n <= a[i]) break;
n -= a[i - 1];
for (k = 0, j = 1; k < n; j++)
k = b[i - 1] * j + i * j * (j + 1) / 2;
–j;
printf(“%ld\n”,j);
printf(“%ld\n”,n);
n = n - b[i - 1] * (j - 1) - i * j * (j - 1) / 2;
printf(“%ld\n”,n);
for(i = 1; i < 5; i++)
if (n <= b[i]) break;
if (i == 1)
printf(“%ld\n”,n);
else
{
n -= b[i-1];
k = (n-1) / i + c[i-1];
printf(“%ld\n”,k/d[i-(n-1)%i-1]%10);
}
}
}
输入的数据起初都还相同 但是输入21474483647及以左的若干数据时输出就不相同了 问什么会出现这种情况呢 ?好诡异 我自己分析不出来 求教高手!!!
>> 本文固定链接: http://www.vcgood.com/archives/2562
这个算法太有想象力了,不大看得懂。
代码中这两个地方不同
unsigned long i,j,k,n,t;
long i,j,k,n,t;
有符号long型,最大值就是2147483647!
另外此算法有错误!
原题要求输入
2 <- 表示后面输入的数字的个数
8 <- 输出第八位上的数字 这里为2
3 <- 输出第三位上的数字 这里为2
算法输出为
2
8
4 - 8的输出
8 -
2 -
2 -
2
2 + 2的输出
2 +
1 +
1 +
回楼上管理员
谢谢啦 原来是i j k n t 不够用了 我真是太马虎了 。。。
呵呵 程序里多余的输出是用来调试和比较的
这么麻烦的程序你也完全看了 真是太感动了