数学建模社区-数学中国

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

---

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

/ H6 v" R# q+ s# ^; l
Sorting It All OutDescription
7 ?; @$ p8 h$ R4 M" n, t
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
& Y4 F' A' ?2 J+ `
For each problem instance, output consists of one line. This line should be one of the following three:
9 v6 r) H! x$ k' r' a, U
" E, f7 B1 V1 _/ N7 N1 JSorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.

0 F9 M, p  ^7 lwhere ** 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.
- J! f) }! O; @, F0 C/ x& E8 h
* l6 V! Q# Z, M% c输入样例

, G2 p* [$ }/ l# ]4 6
3 w6 R# s0 ~/ D# |6 z: xA<B
: @' m' j! v* X; ?3 QA<C
B<C
! Y' s0 S' J1 V" W5 G3 wC<D
' ?8 s; I$ u) R! `3 U! g' e5 \B<D
) m4 F4 y# m! i$ F. D# K  [  T) eA<B
3 2
7 k* ^$ J' F! @0 uA<B
* W+ ]1 F! \% X0 e& lB<A
26 1
( C, v& C) j0 H; yA<Z
0 0
& r6 I' q! q+ g) i0 {* q3 |

输出样例

3 ]( ^- I2 j2 z2 ^: PSorted sequence determined after 4 relations: ABCD.
. o4 D4 h0 n4 H  O+ KInconsistency found after 2 relations.
% e$ _1 e0 I# i3 c& `: KSorted sequence cannot be determined.

Source

East Central North America 2001

程序解题1：

0 d& T7 r1 |: }. ~- y: l//By Jackie Cheung
#include <iostream>
#include <string>
1 j' n. {0 H4 F: l) E. ?#include <cassert>
typedef  struct tagNODE
{
    char val;
0 |* g4 W- e5 @$ {5 `: m9 j    struct tagNODE* link;
}NODE;
using namespace std;
& E! Z8 m. a' R7 Uvoid Marshall(bool** arrary,int n)
{
    for(int i=0;i<n;i++)
. o# W& A& c3 R    {
7 I, y$ ]) z3 e        for (int j=0;j<n;j++)
" M9 y+ N- o3 |        {
            if(true==arrary[j])
                for (int k=0;k<n;k++)
                {
( T0 o( w: d# D                    arrary[j][k]=arrary[j][k] || arrary[k];
: _% ], z2 h& b8 R                }
$ S- O% O3 e. @6 n+ w, a3 }        }
, s+ |  Q* F: y5 G) u8 y    }
};
bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
* I7 ]  j2 {& S    bool bFlag=false;
' Q$ z7 v/ G/ H& \  f    if(1==nLeft)
    {
% x4 f, ^0 m8 p0 W        Seq[n]='\0';
        return true;
; n; l# X( U* h" Q    }
    for (int i=0;i<n;i++)
    {
5 k4 H- G, V3 c8 R- @3 a1 t        if(true==array[nIndex])
        {
0 C: v6 P- [! Z$ D4 W$ f# U            
2 A% j! @7 ?4 b; R' L            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
' d8 `) @4 A, B        if(true==bFlag)
2 B- t! ~+ {0 H+ q& D( ]  |! j# r            return true;
    }
    return false;
8 `' v0 ]3 C9 I$ f  M2 ^2 F% V' U};
int main()
{
/ z3 Z6 P! y* }" ^! E6 p7 L; Q  m4 `    int nSeqLen;
4 g: P1 J; y, ?/ [& V3 y, s" Z    int nRelNum;
* Y3 s. [8 F9 N& r5 z+ d. z& Z# H    cout<<"Input the length of the sequence:"<<endl;
, K0 L) `/ H8 M/ g. Y# Y    cin>>nSeqLen;
1 T, X! P" f/ D1 V' K3 B; T7 A    cout<<"Input the number of relations between the elements:"<<endl;
( i  H$ v  Y, ?% h    cin>>nRelNum;
& P! k  F  l( j# S! p    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
7 w# k8 l+ f  l8 ~' {7 h& _    if(nRelNum<nSeqLen-1)
7 f% T# R! U1 V% `    {
        cout<<"The relation can not be determined!"<<endl;
        return 0;
    }
- Z5 Q3 K" Y& L- o1 s    string* strRelations=new string[nRelNum];
2 s4 Y0 r1 ]! S# s2 t6 ]0 D    char* Seq=new char[nSeqLen+1];
9 ]" I+ _$ z0 y/ |& U$ |0 Y! C5 s# |% y" ?    bool** array=new bool*[nSeqLen];

    for(int i=0;i<nRelNum;i++)
. i; s4 D7 c9 Y8 Z3 S    {
6 {! ]( K9 t) Y4 k        cout<<"Input the "<<i+1<<"th relation:"<<endl;
7 g* J; k8 {9 \/ g) q: S6 t        cin>>strRelations;
$ M# [) L1 o/ y: j5 c4 o    }
) I; l: @; A- i6 l" q( Y, K- k   
    for (int i=0;i<nSeqLen;i++)
9 l, Z) [0 _- h, x( n% r6 r7 V    {
! n8 I" c# D) k$ \* s3 H        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
) g/ t$ v3 Q3 {, r1 p! U9 _0 v0 d    }
3 X! Z4 |- H# k" r. w    //The main loop
  j" Z; h* I6 g# h5 [% C    for (int i=0;i<nRelNum;i++)
    {
# F! z% ?4 k7 M4 ~0 W+ M5 c        char a=strRelations[0];
( b. B7 h' ?7 n3 k4 L        char b=strRelations[2];
4 J  X8 H  t$ l* c        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
7 i! @) j$ g! ?4 C        array[a-'a'][b-'a']=true;
( H+ u2 ^$ [+ X3 M( N6 s( d- h
7 {7 K3 m8 Z; U% n; I        Marshall(array,nSeqLen);
$ p) b+ q2 t4 ^2 t) H6 y+ ]0 R/ h  L
        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
, d6 M6 ?  c9 S        {
            if(true==array[m][m])
            {
; I1 Q, j" R9 K                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
. B8 l0 ~9 T  i( t9 u4 ], A                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
! m. i- M+ H; Z                        delete []array[k];
# D& |/ Z% M, i- \/ {9 v                    delete []array;
. f$ Q% p+ T! K/ t4 n; {                    delete []Seq;
) `% G: b" J3 N0 y2 t                    return 0;

) d+ z5 J9 |3 F( `, i+ _            }
* U( [8 ~- l. B9 e/ R        }

. U1 ~% z: |& y  e        //Check for the determined sequence after  every relation   
$ u  e- C: A( `! J# m. n1 g        for (int j=0;j<nSeqLen;j++)
$ Q3 F9 ?+ o3 O: w        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
+ v# z2 Z9 A7 `3 o                delete []strRelations;
6 C3 B6 L# \! ]& e8 M' k1 k9 R0 O                for(int m=0;m<nSeqLen;m++)
7 D0 |" d  S  c2 n                    delete []array[m];
                delete []array;
                delete []Seq;
                return 0;
- N( P  \6 G1 r# T6 ?2 i! f            }
) j0 N2 A3 l. v, y; ^2 T; s        }


1 u; o6 x% q& S4 v. U4 y4 V4 q    }
    //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[m];
    delete []array;
    delete []Seq;
   
    return 0;
* \9 A' v. Q0 g8 v8 u: ^) m}
2 X  S/ O4 I; D3 G& ]% z: H
程序解题二：#include"stdio.h"
  F7 @0 _. V& w# i& Rvoid main()
) i! K. t! ?  S. x+ C8 g3 B9 M{
. w1 j& s/ q" i    int n_m[100][2];
    char re[1000][3],
5 n9 H. i+ |6 O$ R- }4 O) y; N    temp[26];
7 G) R4 o: f' {; F- D  `% d    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
# R. X: @2 h6 g    for( ;j<n_m[1];j++)
+ v) X8 r. k" @    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
: I; q( ~' Z7 \    {
- D8 O& r. x( Z( e    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
; Q, `+ V1 W2 I+ B! C6 t/ v! F    for( int f=0;f<n_m[1];f++,j++)
( v' I3 k: ?7 w' W/ u' ?    scanf("%s",&re[j]);
3 Q. Z6 V# R7 H, A* H/ c    }
8 S* F6 \2 y1 F; z7 h    i=0;
2 H$ w" g3 I! t3 k7 i9 n    j=0;
   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
5 |9 q, K( z0 F  I& [    {
       int a=0,b=0,l=1;
$ a, p9 j' Y: D# ~2 ]       for(a=j;a<j+n_m[1]-1;a++)
" M( n2 m  L# h! j0 V         for(b=a+1;b<j+n_m[1];b++)
" g; H, ~1 ?( f& R+ `         {
              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])
. p7 C$ t7 t" h3 L( w. S            {
            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
. b3 e; ~  K5 k, n  D0 y+ b, R            break;
            }
- i7 I4 i2 g% _+ C6 f# n6 b         }
      if(l==0)
          continue;//Inconsistency found after x relations.
    else{
           if(n_m[1]<n_m[0]-1)
+ G! R6 X* D7 z' C: G( W+ b        {
            printf("Sorted sequence cannot be determined.\n");
( D6 k" S# }8 x) ?# m7 H            l=0;
7 r' e8 d5 o. o: q" \. t        }
        else
5 W  r* f, g* O! Q, D6 {        {
7 B  j! |8 G5 O5 q7 p. t$ i+ S/ N          if(n_m[1]==n_m[0]-1)
7 S7 {6 t) E/ d          {   
3 C" r9 V- Y' ]8 \              int k=0,p=0;
9 D& j+ ]( j/ A2 Q8 R              for( ;k<n_m[1]-1;k++)
                  for(p=k+1;p<n_m[1];p++)
1 U& H! W+ E4 p* a# O7 X" l                      if(re[0]==re[0]||re[2]==re[2])
; Y0 p, f- @6 m( s0 r$ X! Y3 k                      {
                      printf("Sorted sequence cannot be determined.\n");
                      break;
                      l=0;
) E. d2 B/ A$ f% q                      }
          }
        }
        if(l==0)
        continue;//Sorted sequence cannot be determined.
* ~9 U; f7 ]$ K
) ^& A1 V/ F  f        else
         {
           
: d0 _& s5 G* E/ z/ {2 x' S3 k; L3 i8 [4 U            for(int k=0;k<n_m[0];k++)
' X* j8 ^0 ^2 \! v- R# [# F+ B             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
  I% S9 w" N$ x6 S# E1 M            {
                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
- y) b( M+ R6 z9 |              {
               if(temp==re[0])
                   t1=s;
+ e) W# d3 q6 s0 q  O7 ?                      if(temp==re[2])
                   t2=s;
              }
              if((t1>t2)&&re[1]=='<')
              {
* b* k" q% g4 L, X8 k                char t3=temp[t1];
$ j( I# i$ G7 h5 N% \                temp[t1]=temp[t2];
                temp[t2]=t3;
% o; S( P; U! q* B! l8 ?              }
            }
6 h# j/ a$ P7 p. y$ {6 m        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
3 m. A; a: V# _            if(re[d][0]==temp&&re[d][2]==temp[s+1])
/ p' ]! s4 [, _6 z$ Y- D4 N            {
7 \+ T  u3 @0 G; x  y( ~! J5 Y- l                count++;
                break;
5 I3 t7 v* ^+ F) ]            }
+ t6 \: H/ I1 i+ ~            if(count==n_m[0]-1)
            {
                printf("Sorted sequence determined after %d relations:",n_m[1]);
                for(int f=0;f<n_m[0];f++)
8 F: B" }' t2 J; P9 g                  printf("%c",temp[f]);
                 printf("\n");
            }
            else
( Q: T8 O4 k, m8 B               printf("Sorted sequence cannot be determined.\n");
3 J+ q+ ?$ l2 ?6 e/ [) M  v        }
+ E1 P/ f2 k) |6 g9 Y! D. Z    }
# L. U& H  B9 R  ^1 _( c! g1 ^5 N    }
% |. g+ M1 K& `7 {2 R- A$ J}


2 R: m, o& Z$ x9 r( Q% e
7 \/ Z& F* C: G4 }+ w- e/ ]

" i7 o* `6 v- N4 W


2 x# n. [1 D# L4 J8 \

来源：编程爱好者acm题库

---

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

Powered by Discuz! X2.5