Time Limit:1000MS Memory Limit:65536K
Total Submit:0 Accepted:0
Description
The sequence 1, 1010, 2012, 10021 may not look like an arithmetic sequence(等差数列), but it is one in base 3.Likewise, the sequence 11, 33, 55 is clearly an arithmetic sequence in base 10, but it is also one in base 6. For this problem, you will be given a sequence of numbers and you must write an Arithmetic Confirmation Machine to determine the smallest base under which the numbers form an arithmetic sequence.
Input
Input will consist of multiple problem instances. The first line will contain a single integer 2≤ n≤5 indicating the number of values in the sequence. The next line will contain the n numbers in strictly increasing order, separated by a single blank. A value of n = 0 will terminate the input. All numbers will be positive and made up of the digits 0-9 exclusively, and no number will have more than 5 digits.
Output
Output for each instance should consist of one line of either the form
Minimum base = x.
where x is the the smallest base≤10 which results in an arithmetic sequence, or you should output
No base <= 10 can be found.
Sample Input
4
1 1010 2012 10021
3
11 33 55
4
11 33 55 77
5
10 160 340 520 1000
5
10 160 340 520 10000
0
Sample Output
Minimum base = 3.
Minimum base = 6.
Minimum base = 8.
Minimum base = 7.
No base <= 10 can be found.
Source
----------------解决方案--------------------------------------------------------
任何一组进制下的数构成等差数列转换成别的进制之后还是等差数列(公差也换成这个进制下的数).
所以我认为全部换成10进制来做更好.(进制做循环)再判断是否等差.
----------------解决方案--------------------------------------------------------
谢了
[此贴子已经被作者于2007-10-29 15:56:45编辑过]
----------------解决方案--------------------------------------------------------
等差不就是两数之间的差值是一样的啊
----------------解决方案--------------------------------------------------------
#include<iostream>
using namespace std;
int convert_10(int num ,int m);
int Solve(int data[]);
int convert_10(int num ,int m)
{
int sum=0,temp=1;
while(num>0)
{
if(num%10>=m)
{
return -1;
}
sum+=(num%10)*temp;
temp*=m;
num/=10;
}
return sum;
}
int Solve(int data[],int n)
{
int i,j,k,a[3],c[n-1];
for(i=2;i<=16;i++)
{
int flag=1,suger=1;
for(j=0;j<n;j++)
{
a[j]=convert_10(data[j],i);
if(a[j]==-1)
{
flag=0;
break;
}
}
for(j=0;j<n-1;j++)
c[j]=a[j+1]-a[j];
for(j=1;j<n-1;j++)
if(c[j]!=c[j-1])
suger=0;
if(flag!=0&&suger==1)
{
return i;
}
}
return 0;
}
int main()
{
int data[100];
int n,i,answer;
while(cin>>n&&n!=0)
{
for(i=0;i<n;i++)
{
cin>>data[i];
}
answer=Solve(data,n);
if(answer>0&&answer<=10)
cout<<"Minimum base = "<<answer<<"."<<endl;
else
cout<<"No base <= 10 can be found."<<endl;
}
return 0;
}
[此贴子已经被作者于2007-10-29 15:55:31编辑过]
----------------解决方案--------------------------------------------------------