数学建模社区-数学中国

标题: 编程竞赛题目（一） [打印本页]

---

作者: 厚积薄发    时间: 2010-5-6 18:35
标题: 编程竞赛题目（一）

4 t. ]4 u: F! |# |; M& U& }9 x8 y
Sorting It All OutDescription

( x! F9 \  ]( Q( U$ H' v$ Z' M2 PAn 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.
1 d6 `0 m. S, S* I( B) LInput
; q: a2 i2 E2 b4 n5 V2 v4 N
) y& x; i  q! `9 ^/ x5 YInput 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

& y* f2 ^$ y9 {( k$ kFor each problem instance, output consists of one line. This line should be one of the following three:

' n) F1 p# _3 w( E7 g' VSorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.
+ h0 [. ^  P& M: o3 R
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.

输入样例

* x2 ]2 J  F$ B! ]7 G, F% y: y4 6
! d2 i& Q4 O4 c' Z' bA<B
1 k6 o: a, |, \( t8 @A<C
B<C
) Q: L3 i8 b* sC<D
B<D
% X  R0 q+ ?0 {$ FA<B
2 t9 K- g/ ^* |3 2
/ h+ a. e0 P& T. |" B/ D6 gA<B
+ K" w- y0 ?6 GB<A
26 1
; f. a) S8 q7 ^4 uA<Z
0 0

输出样例

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
4 d# r7 [- A% C$ l6 a1 FSorted sequence cannot be determined.

Source
9 d' X9 i/ j/ |% T4 @
East Central North America 2001

  n- W! U* K+ Z; u4 J* c" N7 [) Q" o% U

程序解题1：

//By Jackie Cheung
#include <iostream>
#include <string>
#include <cassert>
typedef  struct tagNODE
; n! j) U5 l" s0 ]{
    char val;
) Q: a4 V1 Y5 t6 |9 T- j    struct tagNODE* link;
" x. ^. g  {& Y* b: S$ j- s}NODE;
; o  y6 t, T; c2 |using namespace std;
4 j& T- r4 G2 v- d9 F" yvoid Marshall(bool** arrary,int n)
{
" M8 z9 @# D" S' f' k' |4 @" C1 g    for(int i=0;i<n;i++)
    {
" T& B! N6 A6 B: X7 U& x        for (int j=0;j<n;j++)
        {
5 I; f5 \  _, A, F            if(true==arrary[j])
                for (int k=0;k<n;k++)
2 |4 d: y; H( Q  A                {
" C+ q, a/ O# ^4 W- ^$ t( S                    arrary[j][k]=arrary[j][k] || arrary[k];
) p' U, g2 j" }) E& I                }
        }
% V( H, r/ ?- }# a    }
};
) m* g: z) o; p/ @bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
/ J6 d, `3 c: V9 h/ ^, e    if(1==nLeft)
5 r. U* q3 d8 {$ _0 I9 V1 N    {
        Seq[n]='\0';
) c/ i5 I0 c- O  \. D' q        return true;
8 C" d2 P8 a1 K' h8 @- U    }
+ p( b5 O4 z% c3 j* C0 ~8 F5 s" B* s    for (int i=0;i<n;i++)
/ n! R3 ?7 V  Q    {
        if(true==array[nIndex])
$ R# y0 ^7 C) Y" h& u& t        {
            
: f5 v. N& s7 x/ a; K: ?! X2 J1 P# @            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
7 I* a4 f" W& n# y3 i        }
        if(true==bFlag)
            return true;
    }
) d% \# k8 k: u    return false;
};
int main()
{
% L/ ~6 \% B' J" |0 J    int nSeqLen;
6 m0 }8 m1 }3 l, W2 B+ R: v    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
: z) Q: u! I9 ^  K. X$ G, I* A    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
7 B  z3 G9 H7 f    if(nRelNum<nSeqLen-1)
    {
7 T1 u+ G+ C+ m' m- b8 I        cout<<"The relation can not be determined!"<<endl;
1 w8 U/ N# _+ ^; e$ k        return 0;
7 x/ F9 D  @: Z- v    }
    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
7 `$ X* ?0 J' [9 B, H    bool** array=new bool*[nSeqLen];

    for(int i=0;i<nRelNum;i++)
4 H8 E/ ^! f( J4 y! ^# |+ Y    {
7 d4 u" H$ J, l& Y$ x5 `        cout<<"Input the "<<i+1<<"th relation:"<<endl;
' \3 a" p5 h& m1 A/ X' ~" u        cin>>strRelations;
    }
   
5 O2 M7 |" |+ ^( [7 [6 U: c& X8 V    for (int i=0;i<nSeqLen;i++)
    {
        array=new bool[nSeqLen];
# Z0 ~, r5 U$ s1 k        for (int j=0;j<nSeqLen;j++)
) F8 e2 y* e( y* ^9 T9 I3 _& p: s            array[j]=false;
- I9 x: B. E8 j4 K: `- b0 k( O# r    }
/ o. T+ q# c( c/ J    //The main loop
    for (int i=0;i<nRelNum;i++)
1 `; }3 x# J% E/ ^3 y    {
7 U* M  P/ b8 J( _$ }        char a=strRelations[0];
0 U& e  |1 O0 [3 \; c6 D+ E        char b=strRelations[2];
2 }( `4 H+ I/ T$ Z  x/ {        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;
( W/ u, }  _4 Z( B5 x5 O# G! @% b4 {
        Marshall(array,nSeqLen);

$ R, f2 P1 W& s. }        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
7 B6 |) i' x. |  F' L& [' F# o        {
            if(true==array[m][m])
            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
5 A2 M6 H. E' |& D  m, O5 J  p                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
                    delete []array;
                    delete []Seq;
                    return 0;
# Z8 I" b. S! I; A
            }
/ f% o, n+ X5 E4 S* J        }

        //Check for the determined sequence after  every relation   
9 Q# ?  ]) q7 }0 j- i# q/ W' H0 ]( I        for (int j=0;j<nSeqLen;j++)
7 d; ]3 H' D# F: x: l. ?& p0 h' b" n        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
: [) {9 l  _4 E6 s' O. _0 }+ y            {
( d; \5 o" K/ K5 m; Z9 W                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
, i6 m9 K  @5 h( J% A                delete []strRelations;
+ Z# A8 Q1 y# y- K5 \                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
                delete []array;
- a* v" V& K: O/ a& [0 D7 `7 @                delete []Seq;
8 B" C; i6 p7 x1 V                return 0;
            }
, ^% `7 F, H2 S        }


    }
- L: I# F- @2 z0 S( s; q3 w    //If the program has come to here ,then the relationship hasn't been determined!!!
9 p. H* o: M2 o5 x4 d8 k    cout<<"The relation can not be determined!"<<endl;
    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
! Y7 W  H" M2 F; }% _9 F        delete []array[m];
    delete []array;
    delete []Seq;
   
    return 0;
& ^- H! }- O! S) g9 e. T" ?}

程序解题二：#include"stdio.h"
void main()
3 x- Y- E+ o: V( k; |+ J$ d{
    int n_m[100][2];
    char re[1000][3],
! W- i* y9 W" _! k" k    temp[26];
7 q+ f! J2 G& U; ?    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
6 V' i+ _, a' W! J3 ]    for( int f=0;f<n_m[1];f++,j++)
# N4 W3 @9 k& Z' I/ I    scanf("%s",&re[j]);
    }
    i=0;
    j=0;
0 o  S) C5 [$ N: X7 G& u/ f" w   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
4 w  L! _7 S: L; ]/ K0 D    {
, s7 h. R9 n6 H( L) x0 p/ ~       int a=0,b=0,l=1;
$ O& |: o! T. J7 }9 x6 R8 i       for(a=j;a<j+n_m[1]-1;a++)
4 ?# F8 r! C& {$ W! m" U4 }* e         for(b=a+1;b<j+n_m[1];b++)
" S* ]2 @1 d7 ?: ~. E         {
+ j" T; `4 E- t$ [. N              if(re[a][0]==re[0]&&re[a][2]==re[2]&&re[a][1]!=re[1]||re[a][0]==re[2]&&re[a][2]==re[0]&&re[a][1]==re[1])
            {
            l=0;
* Y# L4 e' U/ u' B            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
            }
         }
      if(l==0)
          continue;//Inconsistency found after x relations.
: n4 R% ~5 n- d" C5 `4 s    else{
3 w: M* i7 y+ i6 a8 R           if(n_m[1]<n_m[0]-1)
3 \. v9 @4 Z& M        {
            printf("Sorted sequence cannot be determined.\n");
* ~" [1 X! V' Q% h4 m4 ]            l=0;
        }
        else
) ~0 F. G! W- U- w( p        {
0 Q* H+ ^, [3 C+ Q          if(n_m[1]==n_m[0]-1)
! g) C* b, z9 w( J          {   
$ M) K% v$ Z/ k; F9 T, T              int k=0,p=0;
              for( ;k<n_m[1]-1;k++)
                  for(p=k+1;p<n_m[1];p++)
+ `  ~4 ]7 R. c- r% E; ]                      if(re[0]==re[0]||re[2]==re[2])
" I( e3 _' A. A2 _; H                      {
9 j* H) c* v% p1 W( Z9 s% i- ^                      printf("Sorted sequence cannot be determined.\n");
" V2 v5 O5 w2 i7 v# m& ^                      break;
                      l=0;
                      }
% ]: ^$ m; e& E" @0 ?$ v& f          }
4 h" c# H: W! n        }
        if(l==0)
        continue;//Sorted sequence cannot be determined.
4 S, [/ u, g. r- u, U8 J
2 j; r5 @! g0 w9 z$ H7 u" s: s5 \        else
# `) x8 c4 h9 P0 n3 O2 M+ p         {
) v- [9 N; O) a' O           
- O3 }# G! ]$ d6 J, T( I            for(int k=0;k<n_m[0];k++)
$ ]" t, V- {. W" T5 c2 i) I' j+ ]             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
            {
6 A' f5 }( m: P  J7 l* A; I                int t1=0,t2=0;
( L9 q* H4 P! A: s& }              for(int s=0;s<n_m[0];s++)
              {
               if(temp==re[0])
* \" B- ]9 e# y* v* _                   t1=s;
                      if(temp==re[2])
+ n  @8 L: p+ x: [                   t2=s;
5 L  N6 G6 @+ N$ b$ Z% b$ N9 G              }
              if((t1>t2)&&re[1]=='<')
2 }* _. c& ^$ Z& ^/ _, i              {
6 a; F; H0 J9 J3 n- o# d# A. w# b                char t3=temp[t1];
                temp[t1]=temp[t2];
) i1 g/ T4 z- e0 c' Z& I                temp[t2]=t3;
              }
            }
' ~  T0 g: S. g        int count=0;
& k+ c! ?: q" t/ L9 P        for(int s=0;s<n_m[0]-1;s++)
& l& w1 e3 p( J        for(int d=j-n_m[1];d<j;d++)
6 o; r' Q; p; Y1 U            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
! m: h3 P" v" T% u- q. y                count++;
' o) [! |- r/ R" [# P6 |$ |                break;
0 }0 F6 i& A3 W9 q* K% u1 G            }
            if(count==n_m[0]-1)
            {
2 b7 g, b0 I0 z                printf("Sorted sequence determined after %d relations:",n_m[1]);
                for(int f=0;f<n_m[0];f++)
                  printf("%c",temp[f]);
                 printf("\n");
1 E2 f& `0 z* A  S% U8 v            }
            else
               printf("Sorted sequence cannot be determined.\n");
        }
, E  g% L& K0 U- v; _; g    }
    }
8 o4 ^; A0 ^8 v/ S}
6 k1 W7 v& n8 [- K6 }" |
3 L  ]5 K5 r4 o
3 ~- b1 p: p4 Z9 R( l2 g
( B0 w: t9 b; ^* A



1 K/ W2 a1 n9 k3 R+ I" Z
5 v8 L5 G) W9 e8 Z

来源：编程爱好者acm题库

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5