数学建模社区-数学中国

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

---

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

8 Q& w) x  `/ M8 K, J% W
+ Y5 S$ B* m6 TSorting It All OutDescription
% B" R8 H% z! |3 i4 q' B
: Q  [$ V( v# R7 B% MAn 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.
' @* N; ~7 Y% Z4 ]3 MInput

' Q! ]- m! I; }& W; {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
: A! Y- [, {. K
For each problem instance, output consists of one line. This line should be one of the following three:

: e3 c5 k4 G5 v; [# LSorted sequence determined after ** relations: yyy...y.
0 j/ m. w, C; ]9 y2 ^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.

8 d+ \' a4 M7 H; r2 J7 T4 E* j9 y# |0 l输入样例

. ~3 S7 ]/ D6 ?' C# h5 u4 6
+ z( Z. g4 f/ SA<B
, {' O; u9 l8 f* BA<C
. f6 @! p; s9 ^) u, KB<C
0 z/ |4 K" H$ t! i$ B" U$ vC<D
+ u! M5 @  d/ Q& f. FB<D
A<B
3 2
A<B
5 {, y& o" O0 X6 Y) v5 q3 BB<A
1 L" V- j0 a! o0 k1 i1 ?2 I26 1
( n9 H1 o. P' Y+ G: RA<Z
* w. E7 M* k, F3 j0 0
/ r5 t3 H: p& z) U, ?; }* e

输出样例

Sorted sequence determined after 4 relations: ABCD.
: C- d" S& ^! IInconsistency found after 2 relations.
" }1 |, g) ~5 u2 ?' {1 kSorted sequence cannot be determined.

Source

) F$ ^; L( |/ c* }. k) QEast Central North America 2001

程序解题1：

0 T( X0 k& g, q/ L& B- `4 ^& b8 W0 \//By Jackie Cheung
#include <iostream>
- i0 L0 p* M. l/ l: R#include <string>
#include <cassert>
- Z0 W* R: U5 q6 Z1 Q& ktypedef  struct tagNODE
6 l8 M& W7 w+ x! K+ M{
    char val;
% c! t4 [+ L; I% T: j% N4 ^    struct tagNODE* link;
- u$ A; [! z: H8 l( c) C}NODE;
using namespace std;
void Marshall(bool** arrary,int n)
1 k0 `0 ~8 T; k& V/ z9 ~{
  G; D# v( G$ P* H    for(int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
9 u% G  }. {& l5 h; Z( s6 h        {
            if(true==arrary[j])
" ~* h/ E3 z$ I+ B+ t  M, \                for (int k=0;k<n;k++)
  s0 R# s( C8 I                {
+ D! `% X8 F' ^- Z# n                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
( o; y  f* |9 q" ?        }
    }
};
) `$ k: B. I9 X# a; l( }, }1 obool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
3 h) ?2 ^* \) Z4 D6 ^# {3 ~    bool bFlag=false;
    if(1==nLeft)
; I4 r8 i7 t, M* P6 M5 s& S8 y$ N    {
) w! B- r+ S" f  F1 J+ U( l+ [        Seq[n]='\0';
        return true;
    }
    for (int i=0;i<n;i++)
+ M) R9 ~6 \5 L8 ^3 K& \    {
" e+ I4 M' B, H8 a% U- N# d2 _9 h% d        if(true==array[nIndex])
        {
            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
9 B0 ?- i1 ~) z& `$ P2 {        }
        if(true==bFlag)
            return true;
    }
- P# m5 K0 N: ]7 I$ q: t    return false;
};
3 v2 j7 y) m5 sint main()
{
    int nSeqLen;
    int nRelNum;
: Q. q' Z! ~2 h, a5 v0 [2 R    cout<<"Input the length of the sequence:"<<endl;
    cin>>nSeqLen;
! O$ ]" n6 r1 O2 I5 G. K, N    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
, F+ g( W6 f, T5 V! Z; j    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
    if(nRelNum<nSeqLen-1)
    {
. E2 X7 E2 {' y        cout<<"The relation can not be determined!"<<endl;
        return 0;
    }
    string* strRelations=new string[nRelNum];
: n; V  Z& X) T7 }    char* Seq=new char[nSeqLen+1];
8 h! O" B1 s+ ~    bool** array=new bool*[nSeqLen];
' ?4 n7 E" U- |5 f
& D7 q) r. y. Z/ \. o3 c    for(int i=0;i<nRelNum;i++)
: V; t  ^& y- u1 P/ P: E& U    {
# z3 @2 \' j7 l  {) b; p        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
5 U. b  g/ }! c0 i1 p9 A    }
   
    for (int i=0;i<nSeqLen;i++)
! n$ v/ F3 z  I/ t8 d3 N3 q    {
: V# J/ R- C( I, ^        array=new bool[nSeqLen];
: F6 c9 [; Z2 v        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
  y6 N1 n6 }5 O+ C; t    }
1 L& B8 X& S) T3 n7 e    //The main loop
    for (int i=0;i<nRelNum;i++)
    {
) w+ X# a3 I. l/ `: _        char a=strRelations[0];
        char b=strRelations[2];
$ d; J7 @) @" `7 A4 j' {        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
4 `, ~" w- U/ d8 j1 B        array[a-'a'][b-'a']=true;

( t( }" q  u0 P' M/ n% @        Marshall(array,nSeqLen);

% |) A. Z$ U: j        //Check for Inconsistency after  every relation
& U" `3 U5 ]! z, L( w( N        for (int m=0;m<nSeqLen;m++)
2 \6 R$ `- o* @6 r% o) q8 r% X3 Q+ l+ W        {
            if(true==array[m][m])
+ f% D6 m) w. E3 f2 s) O6 ~            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
# C" a; e1 H7 x2 o9 @                    delete []strRelations;
- c$ ~6 A$ [& g+ L9 @                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
7 ]4 U( [' v  K                    delete []array;
                    delete []Seq;
                    return 0;
% v" j# Q& e% g2 q
/ U6 {& B' g6 Q5 e: z: H8 g' j, E0 s            }
+ o& d! u; g( U/ m" `% W% W        }

1 |$ F! w: X& ?# h5 m" a4 a5 B        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
- Y) e3 R9 T! M* B        {
$ m2 u& _7 E2 n% S9 h1 D            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
( w: C* N0 j& h) X) z3 I. j- ]                for(int m=0;m<nSeqLen;m++)
" y. h! {3 A, X- H, D* \                    delete []array[m];
                delete []array;
1 V) G) Y2 F- `' q                delete []Seq;
% x- D. [, x9 c0 p$ a                return 0;
            }
# M, `* Q; `- @8 |0 A) I& V        }
) p# }; W; V2 P6 I7 }: T

    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
5 s+ Q$ r4 b( u    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
5 N( L6 M  z3 B- p  w        delete []array[m];
    delete []array;
7 H+ H$ b( i' q" y" ]2 Z) R  i( ^" ^    delete []Seq;
   
    return 0;
7 Z! j# O2 k  R2 D# G  s$ \9 s& O}

5 d3 ]8 A, ]; O0 Z) ~程序解题二：#include"stdio.h"
void main()
{
    int n_m[100][2];
    char re[1000][3],
: [( j' c' [8 M, N* i4 A    temp[26];
    int i=0,j=0;
! D1 l: T" F6 t) w( ~/ E    scanf("%d%d",&n_m[0],&n_m[1]);
    for( ;j<n_m[1];j++)
' j2 |. m+ i4 W5 y( R    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
5 n# {4 M7 D# r/ T% J    i=0;
    j=0;
   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
0 y6 w1 Z$ z% E4 B       int a=0,b=0,l=1;
* i2 d% w) ^& t/ l4 ^% c- N) e       for(a=j;a<j+n_m[1]-1;a++)
3 ]' T; [" x$ ^: J         for(b=a+1;b<j+n_m[1];b++)
( u* A+ N8 }) s1 f         {
              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])
            {
4 R$ H0 e- D" W. Y9 Y) a$ u            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
3 L4 M7 V6 [0 d2 Q            }
         }
: V& V( E1 z1 L& X7 q; C4 d  V      if(l==0)
: \/ E& Y  _" @9 y          continue;//Inconsistency found after x relations.
    else{
           if(n_m[1]<n_m[0]-1)
+ [" u0 y0 o. d4 z) r0 Q$ p        {
  q7 {. ]: k0 R/ a+ B. F6 E( i            printf("Sorted sequence cannot be determined.\n");
            l=0;
0 j% y) U$ j3 e( Y8 G* H7 C, s- W        }
2 Z+ ~2 r1 @& ~1 c! }, g% l1 Z        else
1 z! l8 W1 S$ o        {
          if(n_m[1]==n_m[0]-1)
! b1 `. s; b( a" j7 z$ ^( Y          {   
              int k=0,p=0;
              for( ;k<n_m[1]-1;k++)
" O" ?5 D; r  s5 F                  for(p=k+1;p<n_m[1];p++)
                      if(re[0]==re[0]||re[2]==re[2])
                      {
+ ?* w$ ?, ?* ^: [$ [                      printf("Sorted sequence cannot be determined.\n");
1 t1 V: ]$ S% r5 c$ X0 E                      break;
                      l=0;
                      }
          }
        }
- ~1 y: x. W9 ^* ?2 x+ _4 g0 l* k& e        if(l==0)
        continue;//Sorted sequence cannot be determined.
5 t. w- m& C, S, H$ w
: t* J3 p2 e/ p( o% t; _" y# z( f! V        else
; R6 ^! x  P' H7 x         {
5 G5 p- j7 G5 G- o5 J( s           
$ L9 K9 P- F0 y8 `2 }! |            for(int k=0;k<n_m[0];k++)
% s' |! s: {2 `- }             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
            {
- e. I/ y" S2 _" }1 I                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
              {
7 q3 S& q. @( I: }" Q7 b" t               if(temp==re[0])
/ _! z: \) I' z/ Y                   t1=s;
                      if(temp==re[2])
2 W( C; c5 r% ^( z# H! \                   t2=s;
              }
0 a* O( Z& M8 ~+ k8 c5 K              if((t1>t2)&&re[1]=='<')
* Z# |( g- X4 B( N' ~# j4 `              {
$ H7 J: E% e* v! k5 w4 _7 @$ A                char t3=temp[t1];
                temp[t1]=temp[t2];
                temp[t2]=t3;
              }
% M2 p0 h! |3 y            }
* U0 u% q; Q, J1 x9 G        int count=0;
) b& Y- K9 l- `        for(int s=0;s<n_m[0]-1;s++)
  G. ~% U- }- K1 \+ `        for(int d=j-n_m[1];d<j;d++)
" t, i2 m# \+ M# H, u) |            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
                count++;
                break;
# y2 ?5 E2 a/ u5 g* {            }
            if(count==n_m[0]-1)
4 h+ _- j$ E* F; y4 B5 Q            {
                printf("Sorted sequence determined after %d relations:",n_m[1]);
" z+ p5 r2 \3 t/ a                for(int f=0;f<n_m[0];f++)
                  printf("%c",temp[f]);
: A; b: c# S7 O5 W* B                 printf("\n");
            }
            else
/ B' L5 S% v* B" P- F9 [( B. l               printf("Sorted sequence cannot be determined.\n");
5 O0 C3 n2 n, s        }
    }
    }
}
8 x) K2 D% S8 s/ Y) O2 c
: L1 i% P& Z- c" x8 f% B' ]7 Z3 ?. ?  h

+ S  H* j, D- e' R! _
. u3 h/ Y8 b8 h* B+ s, J9 M7 ?
# U9 A+ Q  h7 Y) L3 \# e

# H+ q! r, N9 R. q& V; I
0 t" _0 I( ], g) u2 k& B

来源：编程爱好者acm题库

---

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

Powered by Discuz! X2.5