数学建模社区-数学中国

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

---

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

* R/ O. O  y2 ~' x! C8 t
5 N. ^; I9 `; `/ p3 d" z: \Sorting It All OutDescription
& C6 K: B3 \5 W9 S. N9 j9 t
# e3 X& n; t! k. e5 w4 l; 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.
2 {! X1 n: W% v. `) I4 L/ |7 NInput

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

9 K, V  P1 a9 B1 SFor each problem instance, output consists of one line. This line should be one of the following three:
. o) n5 @" b  e  o% p8 ^$ i- s
, D" R* j* Z& {9 b0 M' ^  N( N) Y# SSorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
/ y2 c3 m0 a( E6 n' l5 [Inconsistency found after ** relations.
, q: T' R' K$ x, E
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.
; z! d7 G) D/ q9 [8 h+ Q/ u" x
7 Z* ?! D+ G9 T4 z输入样例

9 u7 \5 D5 {* ]) o4 6
8 X, E% R, o# }. ]8 \A<B
  S1 `% |$ U/ J! F1 P* XA<C
+ v% i4 F2 A6 p% ?' g( b5 j, sB<C
C<D
B<D
: p& v6 c% X; f9 W" w* a+ GA<B
3 2
  \7 c& i2 c2 y# WA<B
B<A
/ C, e$ S  o0 L5 k9 l9 L26 1
A<Z
0 0

输出样例

( S  r6 W; }' T* N. X4 b/ cSorted sequence determined after 4 relations: ABCD.
% A4 p5 n# T0 B! WInconsistency found after 2 relations.
Sorted sequence cannot be determined.

Source

East Central North America 2001

程序解题1：

/ W( q5 n0 \- U- c//By Jackie Cheung
#include <iostream>
6 f5 |% c& m5 B- ]#include <string>
#include <cassert>
! `, u. M4 W7 B, f5 a3 f3 @typedef  struct tagNODE
{
6 \, B0 N+ ^" y, \4 }    char val;
' G7 ~5 U: b& ^  _2 b    struct tagNODE* link;
$ Y8 Q" {0 j/ ?}NODE;
using namespace std;
void Marshall(bool** arrary,int n)
{
5 i* U8 r! Y; q" \! L- O; y% S$ H    for(int i=0;i<n;i++)
- f* ]' E! L' m" b; Q' j    {
& D% y9 \/ p( M+ W# _3 g        for (int j=0;j<n;j++)
4 j8 Y1 y/ c6 M7 ]  c+ w        {
  F$ Q: g/ ]# Y  r            if(true==arrary[j])
6 C! t" E; ~) A- O2 T                for (int k=0;k<n;k++)
                {
0 U' ^+ g1 r9 p6 C' @                    arrary[j][k]=arrary[j][k] || arrary[k];
$ Y( v' _5 e& C5 A/ n$ V6 b                }
        }
    }
: n5 T) C+ [9 Z- b: Q) y( g8 v+ T};
2 f; i; |( U3 ^, |  }7 ?" n( T- [bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
5 ]" G1 M* L* H% s{
- j9 |9 y3 b& `8 i& V9 x( Y0 X    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
& j2 x/ c" l$ N6 s3 |    if(1==nLeft)
    {
' y7 R4 E' h- A& y        Seq[n]='\0';
        return true;
    }
    for (int i=0;i<n;i++)
    {
        if(true==array[nIndex])
( U) k2 H8 t3 G8 \        {
6 \1 m- E: d' m1 K            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
        if(true==bFlag)
            return true;
    }
$ C( \$ s, V7 t9 h4 c# G+ v$ o    return false;
};
4 Q& T0 {. ?  |5 j/ n) hint main()
; V8 }, L# r0 N) K/ Y& D8 y$ r4 X{
9 V9 _4 X4 t9 ~# d1 x    int nSeqLen;
    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
5 K2 e  `1 A! w$ n9 c    cin>>nSeqLen;
8 S7 ?$ O" S0 U) Y- [    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
. C; U/ o3 V0 l4 A    if(nRelNum<nSeqLen-1)
    {
: n' _+ x7 k) O8 U1 q4 p; }) b9 {% X        cout<<"The relation can not be determined!"<<endl;
0 W$ Q3 i. ]' a# L0 A        return 0;
    }
- w* n; I' z* b3 E( I3 c( ]    string* strRelations=new string[nRelNum];
- C( p" |# t0 m4 M  A. C    char* Seq=new char[nSeqLen+1];
2 X6 W3 v6 t6 B4 S$ i8 U    bool** array=new bool*[nSeqLen];
6 J% Y, ]! R. g7 s2 ^; M. k, A
5 I; O& r" e( N/ ~    for(int i=0;i<nRelNum;i++)
    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
    }
2 [% x/ V4 j2 z3 ?! A4 M1 Z   
    for (int i=0;i<nSeqLen;i++)
/ V5 O$ n( c% X1 u2 G+ c    {
0 R8 i+ i% x- d$ [        array=new bool[nSeqLen];
/ i8 g. g; ]6 }: M. Y        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
    }
6 P; Y# M4 S; j    //The main loop
    for (int i=0;i<nRelNum;i++)
    {
: ^1 ?( X+ O$ ]+ N5 y+ i0 y        char a=strRelations[0];
! I' T( ]1 O7 ]5 Y2 Z        char b=strRelations[2];
6 o5 Y, H! I7 n7 H' ?; B        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
1 C. g1 u7 r  r) B1 g+ I, d6 G        array[a-'a'][b-'a']=true;
+ ^3 s! v- h0 D4 E. w. _
        Marshall(array,nSeqLen);
$ B4 p' Z2 p( T; u7 }
        //Check for Inconsistency after  every relation
: c4 T& x& ^( y* s4 o7 |! ^        for (int m=0;m<nSeqLen;m++)
        {
            if(true==array[m][m])
            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
3 }/ K+ x. [: ~8 w  {) ~; |                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
2 X! S( q3 m- e* f8 g                        delete []array[k];
( D0 Q' V3 H3 }8 A$ Z                    delete []array;
1 s0 M# M, ]/ O9 N" O7 |, O                    delete []Seq;
                    return 0;
9 ~, O0 q9 R. H" t. |; i/ n
            }
# v/ o; b; D+ s. H) m' k8 ]( w! Q        }

! X9 b" e, o' _        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
3 h# m# C, W6 Y/ A        {
+ O0 E. q  W. R$ j            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
6 N3 {) ]" [4 w7 `            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
- n7 _) i! t# T& s% o+ x                delete []strRelations;
$ M3 Q( O* L9 S9 Q, c                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
% s5 N6 s& J9 T+ {$ Q                delete []array;
' a& H1 R3 P+ T9 a# t) p                delete []Seq;
5 S$ f8 J4 b  w                return 0;
            }
        }
% K. Q8 P  d, |
/ ]  U( o3 U. k  ~+ A
    }
; {+ m  p, C( f7 I- |    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
6 H  G! s% `! V, `0 D    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
9 A" M2 ]9 }9 E$ ^& U        delete []array[m];
    delete []array;
    delete []Seq;
   
    return 0;
7 c+ k: x' ~& k% O  K2 [}
% D3 Z! ?5 H- X  o% n; v0 V
程序解题二：#include"stdio.h"
% `8 |  k8 g: Xvoid main()
+ P! S( i- u- f+ d6 ?' P: T2 ]6 \; G{
    int n_m[100][2];
    char re[1000][3],
0 h; o6 r/ m1 w! D' g7 t. Q' Y    temp[26];
, v+ W" ]& @, F, ?" E' U' n; s" H    int i=0,j=0;
# r; |( X7 k7 W# q/ t    scanf("%d%d",&n_m[0],&n_m[1]);
! ]6 w$ G3 I8 y5 P3 s1 Y9 H- [, P    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
: g: @1 M2 k) V    while(n_m[0]!=0&&n_m[1]!=0)
    {
    i++;
) o9 J- Z, ]  f/ q% j  Q    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
& k, e& V# q! Y  Z    }
/ n- H- t4 E; Y    i=0;
$ M- h# W" _( p1 L, I  V5 y. p    j=0;
   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
% V; v) w4 w$ _; h       int a=0,b=0,l=1;
       for(a=j;a<j+n_m[1]-1;a++)
* q4 `6 v- w1 @+ N& ^4 L         for(b=a+1;b<j+n_m[1];b++)
         {
6 d$ a0 r7 C; o" d  [              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])
            {
- [1 X7 S2 V+ {8 W            l=0;
! f4 q9 w0 B4 Y0 j# B            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
            }
         }
      if(l==0)
          continue;//Inconsistency found after x relations.
3 n/ G" a4 X+ L% W6 x3 G1 p) D    else{
+ x4 u2 D$ b2 Q/ \7 K$ c           if(n_m[1]<n_m[0]-1)
        {
% R0 T7 `1 k, |/ G            printf("Sorted sequence cannot be determined.\n");
            l=0;
        }
6 Q3 p/ g" p% l6 r* Y        else
        {
6 F; _2 d  Y/ }5 m5 ?) @2 L' @! j          if(n_m[1]==n_m[0]-1)
          {   
" `) j4 k) l& N$ A2 s! z/ G              int k=0,p=0;
, c% t( n. o: m5 t+ m* y5 D4 F              for( ;k<n_m[1]-1;k++)
& o( c, q$ Z5 i5 o, H1 w' Z, ^: `                  for(p=k+1;p<n_m[1];p++)
                      if(re[0]==re[0]||re[2]==re[2])
                      {
( I+ |  Y, h/ H% V* c8 r* t: d                      printf("Sorted sequence cannot be determined.\n");
                      break;
                      l=0;
                      }
          }
        }
8 h. ~3 R3 x* V" u        if(l==0)
4 p9 E- M, I) h) K/ `        continue;//Sorted sequence cannot be determined.

1 X  e$ p" Z! ?, f- N+ F        else
         {
7 E' Z5 C' ?4 f/ K8 y           
) I5 V* N; s. o) ?6 O            for(int k=0;k<n_m[0];k++)
, e$ s4 F  D2 E             temp[k]=k+65;
. _$ L7 A  H: h            for(k=0;k<n_m[1];k++,j++)
            {
                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
$ s3 f( H8 {8 q, n              {
               if(temp==re[0])
                   t1=s;
                      if(temp==re[2])
" j7 G9 R5 X4 {                   t2=s;
              }
: d6 [4 b1 v2 d! S              if((t1>t2)&&re[1]=='<')
              {
                char t3=temp[t1];
0 s) j& M% U2 `0 e, }. r, q                temp[t1]=temp[t2];
                temp[t2]=t3;
              }
            }
; C! X. r' W$ J) \6 B3 P' j        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
, E/ E9 r  R; ~1 X( I/ W7 C) f3 s* l            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
                count++;
                break;
            }
' M- A9 k9 L* X) e2 B4 U- d            if(count==n_m[0]-1)
            {
& A0 Y, o* K) R4 D* K                printf("Sorted sequence determined after %d relations:",n_m[1]);
4 k) i0 A0 Z7 i8 N                for(int f=0;f<n_m[0];f++)
' r& E- C3 I0 b8 J0 l                  printf("%c",temp[f]);
                 printf("\n");
5 o4 C. G; d. }1 T            }
            else
' J0 O' ]2 f. S: J! }# k, ~# o/ z* K               printf("Sorted sequence cannot be determined.\n");
        }
    }
    }
/ t7 Z: t2 m6 r7 X}
- {3 t/ Z) Y: L! ^- G/ t1 O  n/ C
" Q% [8 @7 m& a8 M8 j  H



* M2 d% z" \7 F+ W( L
  u: ~/ p/ w* H% H( l0 U4 o
; u6 z6 o6 U5 s0 X* v" I- |

来源：编程爱好者acm题库

---

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

Powered by Discuz! X2.5