编程竞赛题目（一）
本帖最后由 厚积薄发 于 2010-5-6 18:40 编辑Sorting It All OutDescription
An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.
Input
Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.
Output
For each problem instance, output consists of one line. This line should be one of the following three:
Sorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.
where ** is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.
输入样例
4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0
输出样例
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
Source
East Central North America 2001
程序解题1：
//By Jackie Cheung
#include <iostream>
#include <string>
#include <cassert>
typedef struct tagNODE
{
char val;
struct tagNODE* link;
}NODE;
using namespace std;
void Marshall(bool** arrary,int n)
{
for(int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
if(true==arrary)
for (int k=0;k<n;k++)
{
arrary=arrary || arrary;
}
}
}
};
bool SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
Seq=static_cast<char>('a'+nIndex);
bool bFlag=false;
if(1==nLeft)
{
Seq='\0';
return true;
}
for (int i=0;i<n;i++)
{
if(true==array)
{
bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
}
if(true==bFlag)
return true;
}
return false;
};
int main()
{
int nSeqLen;
int nRelNum;
cout<<"Input the length of the sequence:"<<endl;
cin>>nSeqLen;
cout<<"Input the number of relations between the elements:"<<endl;
cin>>nRelNum;
//1:if nRelNum<nSeqLen-1,then the relation can not be determined!
if(nRelNum<nSeqLen-1)
{
cout<<"The relation can not be determined!"<<endl;
return 0;
}
string* strRelations=new string;
char* Seq=new char;
bool** array=new bool*;
for(int i=0;i<nRelNum;i++)
{
cout<<"Input the "<<i+1<<"th relation:"<<endl;
cin>>strRelations;
}
for (int i=0;i<nSeqLen;i++)
{
array=new bool;
for (int j=0;j<nSeqLen;j++)
array=false;
}
//The main loop
for (int i=0;i<nRelNum;i++)
{
char a=strRelations;
char b=strRelations;
assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
array=true;
Marshall(array,nSeqLen);
//Check for Inconsistency after every relation
for (int m=0;m<nSeqLen;m++)
{
if(true==array)
{
cout<<"Inconsistency found after"<<i+1<<"th relation!"<<endl;
delete []strRelations;
for(int k=0;k<nSeqLen;k++)
delete []array;
delete []array;
delete []Seq;
return 0;
}
}
//Check for the determined sequence after every relation
for (int j=0;j<nSeqLen;j++)
{
if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
{
cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
delete []strRelations;
for(int m=0;m<nSeqLen;m++)
delete []array;
delete []array;
delete []Seq;
return 0;
}
}
}
//If the program has come to here ,then the relationship hasn't been determined!!!
cout<<"The relation can not be determined!"<<endl;
delete []strRelations;
for(int m=0;m<nSeqLen;m++)
delete []array;
delete []array;
delete []Seq;
return 0;
}
程序解题二：#include"stdio.h"
void main()
{
int n_m;
char re,
temp;
int i=0,j=0;
scanf("%d%d",&n_m,&n_m);
for( ;j<n_m;j++)
scanf("%s",&re);
while(n_m!=0&&n_m!=0)
{
i++;
scanf("%d%d",&n_m,&n_m);
for( int f=0;f<n_m;f++,j++)
scanf("%s",&re);
}
i=0;
j=0;
for( ;n_m!=0&&n_m!=0;i++)
{
int a=0,b=0,l=1;
for(a=j;a<j+n_m-1;a++)
for(b=a+1;b<j+n_m;b++)
{
if(re==re&&re==re&&re!=re||re==re&&re==re&&re==re)
{
l=0;
printf("Inconsistency found after %d relations.\n",n_m);
break;
}
}
if(l==0)
continue;//Inconsistency found after x relations.
else{
if(n_m<n_m-1)
{
printf("Sorted sequence cannot be determined.\n");
l=0;
}
else
{
if(n_m==n_m-1)
{
int k=0,p=0;
for( ;k<n_m-1;k++)
for(p=k+1;p<n_m;p++)
if(re==re||re==re)
{
printf("Sorted sequence cannot be determined.\n");
break;
l=0;
}
}
}
if(l==0)
continue;//Sorted sequence cannot be determined.
else
{
for(int k=0;k<n_m;k++)
temp=k+65;
for(k=0;k<n_m;k++,j++)
{
int t1=0,t2=0;
for(int s=0;s<n_m;s++)
{
if(temp==re)
t1=s;
if(temp==re)
t2=s;
}
if((t1>t2)&&re=='<')
{
char t3=temp;
temp=temp;
temp=t3;
}
}
int count=0;
for(int s=0;s<n_m-1;s++)
for(int d=j-n_m;d<j;d++)
if(re==temp&&re==temp)
{
count++;
break;
}
if(count==n_m-1)
{
printf("Sorted sequence determined after %d relations:",n_m);
for(int f=0;f<n_m;f++)
printf("%c",temp);
printf("\n");
}
else
printf("Sorted sequence cannot be determined.\n");
}
}
}
}
来源：编程爱好者acm题库
页:
[1]