shiyandaima

  1 //jidaxiangronglei
  2 #include<iostream>
  3 #include<iostream>
  4 #include<iomanip>
  5 #include<string>
  6 using namespace std;
  7 //-----------------------------------------------
  8 int main()
  9 {
 10       int i,j;
 11     string CollectionA,RelationA;
 12     cout<<"请输入已知的集合:
";
 13     cin>>CollectionA;
 14     cout<<"请输入该集合上的一个关系:
";
 15     cin>>RelationA;
 16     string setA;
 17     int DimentionA=0;
 18     for(i=0;i<CollectionA.length();i++)
 19         if(CollectionA[i]>='a'&&CollectionA[i]<='z')
 20         {
 21             setA+=CollectionA;
 22             DimentionA++;
 23         }
 24         string* CollA=new string[DimentionA*2];
 25         for(i=0;i<DimentionA;i++)
 26             CollA[i]=setA[i];
 27         string relaA;
 28         for(i=0;i<RelationA.length();i++)
 29             if(RelationA[i]>='a'&&RelationA[i]<='z')
 30                 relaA+=RelationA[i];
 31         int** Matrix=new int*[DimentionA];
 32         for(i=0;i<DimentionA;i++)
 33             Matrix[i]=new int[DimentionA];
 34         for(i=0;i<DimentionA;i++)
 35             for(j=0;j<DimentionA;j++)
 36                 Matrix[i][j]=0;
 37         for(i=0;i<relaA.length();i+=2)//将关系中转为对应的矩阵
 38             Matrix[relaA[i]-'a'][relaA[i+1]-'a']=1;
 39         cout<<"该关系的对应矩阵为:"<<endl;
 40         for(i=0;i<DimentionA;i++)
 41             for(j=0;j<DimentionA;j++)
 42             {
 43                 cout<<Matrix[i][j]<<"  ";
 44                 if(j==DimentionA-1)
 45                     cout<<endl;
 46             }
 47         cout<<endl;
 48         cout<<"该矩阵可简化为:"<<endl;
 49         for(i=1;i<DimentionA;i++)
 50             for(j=0;j<i;j++)
 51             {
 52               cout<<Matrix[i][j]<<"  ";
 53               if(j==i-1)
 54               cout<<endl;
 55             }
 56         cout<<endl;
 57         if(DimentionA==1)
 58         {
 59             cout<<"该关系的极大相容类为:{"<<CollA[0]<<"}"<<endl;
 60             return 0;
 61         }
 62         int Dimen=DimentionA;
 63         int DimenA=DimentionA;
 64         string strA,strB,strC;
 65         if(DimentionA>1)
 66         {
 67             for(i=DimenA-2;i>=0;i--)
 68             {
 69                 for(j=i+1;j<DimenA;j++)
 70                     if(Matrix[j][i]==1)
 71                         strA+=char('a'+j);
 72                 for(j=0;j<DimentionA;j++)
 73                 {
 74                     for(int k=0;k<CollA[j].length();k++)
 75                         for(int m=0;m<strA.length();m++)
 76                             if(CollA[j][k]==strA[m])
 77                                 strB+=strA[m];
 78                     if(strB.length()!=0)
 79                     {
 80                         strC=strB;
 81                         strB=char('a'+i);
 82                         strB+=strC;
 83                         CollA[Dimen]=strB;
 84                         Dimen++;
 85                         strC="";
 86                         strB="";
 87                     }
 88                 }
 89                 strA="";
 90                 DimentionA=Dimen;
 91                 int flag=0;
 92                 for(j=0;j<DimentionA;j++)
 93                    for(int k=j+1;k<DimentionA;k++)
 94                    {
 95                         for(int l=0;l<CollA[j].length();l++)
 96                             for(int m=0;m<CollA[k].length();m++)
 97                                 if(CollA[j][l]==CollA[k][m])
 98                                     flag++;
 99               if(flag!=0&&flag==CollA[j].length())
100                {
101                     CollA[j]="";
102                     Dimen--;
103                 }
104           if(flag!=0&&flag==CollA[k].length())
105               {
106                     CollA[k]="";
107                     Dimen--;
108               }
109               flag=0;    
110         }
111         for(j=0;j<DimentionA;j++)
112             for(int k=0;k<DimentionA-1;k++)
113             if(CollA[k]==""&&CollA[k+1]!="")
114                 {
115                     CollA[k]=CollA[k+1];
116                     CollA[k+1]="";
117                 }
118         DimentionA=Dimen;
119         for(j=0;j<DimentionA;j++)
120         cout<<setw(5)<<CollA[j];
121         cout<<endl;
122     }
123 }
124        cout<<endl;
125        cout<<"该关系的极大相容类有:";
126         for(i=0;i<DimentionA;i++)
127         {
128             cout<<"{";
129             for(j=0;j<CollA[i].length();j++)
130             {
131                 cout<<CollA[i][j];
132                 if(j!=CollA[i].length()-1)
133                 cout<<",";
134             }
135             cout<<"}";
136             if(i!=DimentionA-1)
137             cout<<",";
138         }
139         cout<<endl;
140         return 0;
141 }

  1 //migong
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 typedef enum { ERROR, OK } Status;
  5 typedef struct
  6 {
  7     int row, line;
  8 }PosType;
  9 
 10 typedef struct
 11 {
 12     int  di, ord;
 13     PosType seat;
 14 }SElemType;
 15 
 16 typedef struct
 17 {
 18     SElemType * base;
 19     SElemType * top;
 20     int        stacksize;
 21 }SqStack;
 22 
 23 Status InitStack(SqStack &S);
 24 Status Push(SqStack &S, SElemType &a);
 25 Status Pop(SqStack &S, SElemType &a);
 26 Status StackEmpty(SqStack S);
 27 Status MazePath(int maze[12][12], SqStack &S, PosType start, PosType end);
 28 void Initmaze(int maze[12][12], int size);
 29 void printmaze(int maze[12][12], int size);
 30 Status Pass(int maze[12][12], PosType CurPos);
 31 void Markfoot(int maze[12][12], PosType CurPos);
 32 PosType NextPos(PosType CurPos, int Dir);
 33 void printpath(int maze[12][12], SqStack S, int size);
 34 void main(void)
 35 {
 36     SqStack S;
 37     int size, maze[12][12];
 38     for (int n = 0; n < 10; n++)
 39     {
 40         printf("创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于50):
");
 41         scanf("%d", &size);
 42         if (size < 1 || size>10)
 43         { 
 44             printf("输入错误!");
 45             return;
 46         }
 47         Initmaze(maze, size);
 48         printmaze(maze, size);
 49         PosType start, end;
 50         printf("输入入口行坐标和列坐标:");
 51         scanf("%d", &start.row); 
 52         scanf("%d", &start.line);
 53         printf("输入出口行坐标和列坐标:");
 54         scanf("%d", &end.row);
 55         scanf("%d", &end.line);
 56         if (MazePath(maze, S, start, end))
 57             printpath(maze, S, size);
 58         else
 59             printf("找不到通路!

");
 60     }
 61 }
 62 Status MazePath(int maze[12][12], SqStack &S, PosType start, PosType end)
 63 {
 64     PosType curpos;
 65     int curstep;
 66     SElemType e;
 67     InitStack(S);
 68     curpos = start;
 69     curstep = 1;
 70     do {
 71         if (Pass(maze, curpos))
 72         {
 73             Markfoot(maze, curpos);
 74             e.di = 1;
 75             e.ord = curstep;
 76             e.seat = curpos;
 77             Push(S, e);
 78             if (curpos.row == end.row && curpos.line == end.line)
 79                 return OK;
 80             curpos = NextPos(curpos, 1);
 81             curstep++;
 82         }
 83         else
 84         {
 85             if (!StackEmpty(S))
 86             {
 87                 Pop(S, e);
 88                 while (e.di == 4 && !StackEmpty(S))
 89                 {
 90                     Markfoot(maze, e.seat);
 91                     Pop(S, e);
 92                 }
 93                 if (e.di < 4)
 94                 {
 95                     e.di++;
 96                     Push(S, e);
 97                     curpos = NextPos(e.seat, e.di);
 98                 }
 99             }
100         }
101     } while (!StackEmpty(S));
102     return ERROR;
103 }
104 void Initmaze(int maze[12][12], int size)
105 {
106     char select;
107     printf("选择创建方式 A:自动生成 B:手动创建
");
108 label:scanf("%c", &select);
109     if (select == 'a' || select == 'A')
110     {
111         for (int i = 0; i < size + 2; i++)
112             maze[0][i] = 1;
113         for (int i = 1; i < size + 1; i++)
114         {
115             maze[i][0] = 1;
116             for (int j = 1; j < size + 1; j++)
117                 maze[i][j] = rand() % 2;
118             maze[i][size + 1] = 1;
119         }
120         for (int i = 0; i < size + 2; i++)
121             maze[size + 1][i] = 1;
122     }
123     else if (select == 'b' || select == 'B')
124     {
125         printf("按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):
", size, size);
126         for (int i = 0; i < size + 2; i++)maze[0][i] = 1;
127         for (int i = 1; i < size + 1; i++)
128         {
129             maze[i][0] = 1;
130             for (int j = 1; j < size + 1; j++)
131                 scanf("%d", &maze[i][j]);
132             maze[i][size + 1] = 1;
133         }
134         for (int i = 0; i < size + 2; i++)
135             maze[size + 1][i] = 1;
136     }
137     else if (select == '
')
138         goto label;
139     else printf("输入错误!");
140 }
141 void printmaze(int maze[12][12], int size)//
142 {
143     printf("

");
144     printf("显示所建的迷宫(#表示外面的墙):
");
145     for (int i = 0; i < size + 2; i++)
146         printf("%c ", '#');
147     printf("
");
148     for (int i = 1; i < size + 1; i++)
149     {
150         printf("%c ", '#');
151         for (int j = 1; j < size + 1; j++)
152         {
153             printf("%d ", maze[i][j]);
154         }
155         printf("%c", '#');
156         printf("
");
157     }
158     for (int i = 0; i < size + 2; i++)
159         printf("%c ", '#');
160     printf("
");
161 
162 }
163 
164 void printpath(int maze[12][12], SqStack S, int size)
165 {
166     printf("

通路路径为:
");
167     SElemType * p = S.base;
168     while (p != S.top)
169     {
170         maze[p->seat.row][p->seat.line] = 2;
171         p++;
172     }
173     for (int i = 0; i < size + 2; i++)
174         printf("%c ", '#'); printf("
");
175     for (int i = 1; i < size + 1; i++)
176     {
177         printf("%c ", '#');
178         for (int j = 1; j < size + 1; j++)
179         {
180             if (maze[i][j] == 2) 
181                 printf("%c ", '0');
182             else              
183                 printf(" ");
184         }
185         printf("%c", '#');
186         printf("
");
187     }
188     for (int i = 0; i < size + 2; i++)
189         printf("%c ", '#'); 
190     printf("

");
191 
192 }
193 
194 Status Pass(int maze[12][12], PosType CurPos)
195 {
196     if (maze[CurPos.row][CurPos.line] == 0)
197         return OK;
198     else 
199         return ERROR;
200 }
201 void Markfoot(int maze[12][12], PosType CurPos)
202 {
203     maze[CurPos.row][CurPos.line] = 1;
204 }
205 PosType NextPos(PosType CurPos, int Dir)
206 {
207     PosType ReturnPos;
208     switch (Dir)
209     {
210     case 1:
211         ReturnPos.row = CurPos.row;
212         ReturnPos.line = CurPos.line + 1;
213         break;
214     case 2:
215         ReturnPos.row = CurPos.row + 1;
216         ReturnPos.line = CurPos.line;
217         break;
218     case 3:
219         ReturnPos.row = CurPos.row;
220         ReturnPos.line = CurPos.line - 1;
221         break;
222     case 4:
223         ReturnPos.row = CurPos.row - 1;
224         ReturnPos.line = CurPos.line;
225         break;
226     }
227     return ReturnPos;
228 }
229 Status InitStack(SqStack &S)
230 {
231     S.base = (SElemType *) malloc(100 * sizeof(SElemType));
232     if (!S.base)return ERROR;
233     S.top = S.base;
234     S.stacksize = 100;
235     return OK;
236 }
237 Status Push(SqStack &S, SElemType &a)
238 {
239     *S.top++ = a;
240     return OK;
241 }
242 Status Pop(SqStack &S, SElemType &a)
243 {
244     if (S.top == S.base)
245         return ERROR;
246     a = *--S.top;
247     return OK;
248 }
249 
250 Status StackEmpty(SqStack S)
251 {
252     if (S.top == S.base)
253         return OK;
254     return ERROR;
255 }

  1 //erchashu
  2 #include<iostream>
  3 #include<iomanip>
  4 #include<vector>
  5 using namespace std;
  6 
  7 typedef vector<char>Collection;
  8 typedef vector<vector<char>>Matrix;
  9 
 10 void Coll_Print(Collection C);
 11 void Matrix_Print(Matrix M);
 12 
 13 int Coll_ChLocate(Collection C,char ch);
 14 bool Coll_ChFind(Collection Ca,char ch);
 15 bool Matrix_ColFind(Matrix M,Collection C);
 16 bool Coll_Belong(Collection Ca,Collection Cb);
 17 Collection Coll_Or(Collection Ca,Collection Cb);
 18 Collection Coll_And(Collection Ca,Collection Cb);
 19 Matrix Matrix_Or(Matrix Ma,Matrix Mb);
 20 Matrix Matrix_Minus(Matrix Ma,Matrix Mb);
 21 void Make_MCC(Collection Ca,vector<Collection>&pi,vector<vector>R);
 22 
 23 void Coll_Print(Collection C)
 24 {
 25     cout<<"{";
 26     for(int i=0;i<C.size();i++)
 27     {
 28         cout<<C[i];
 29         if(i!=C.size()-1)
 30             cout<<",";
 31     }
 32     cout<<"}";
 33 }
 34 
 35 void Matrix_Print(Matrix M)
 36 {
 37     cout<<"{";
 38     for(int i=0;i<M.size();i++)
 39     {
 40         Coll_Print(M[i]);
 41         if(i!=M.size()-1)
 42             cout<<",";
 43     }
 44     cout<<"}"<<endl;
 45 }
 46 
 47 int Coll_ChLocate(Collection C,char ch)
 48 {
 49     for(int i=0;i<C.size();i++)
 50         if(C[i]==ch)
 51             return i;
 52         return -1;
 53 }
 54 
 55 bool Coll_ChFind(Collection Ca,char ch)
 56 {
 57     for(int i=0;i<Ca.size();i++)
 58     {
 59         if(Ca[i]==ch)
 60             return true;
 61     }
 62     return false;
 63 }
 64 
 65 bool Matrix_CoFind(Matrix M,Collection C)
 66 {
 67     for(int i=0;i<M.size();i++)
 68         if(M[i]==C)
 69             return true;
 70         return false;
 71 }
 72 
 73 bool Coll_Belong(Collection Ca,Collection Cb)
 74 {
 75     if(Ca.size()>Cb.size())
 76         return false;
 77     else
 78     {
 79         for(int i=0;i<Ca.size();i++)
 80         {
 81             if(!Coll_ChFind(Ca,Ca[i]))
 82                 return false;
 83         }
 84         return false;
 85     }
 86 }
 87 
 88 Collection Coll_Or(Collectin ca,Collection Cb)
 89 {
 90     int main=(Ca.size()>Cb.size()?Cb.size():Ca.size());
 91 
 92     Collection CB=(Ca.size()>Cb.size()?Ca:Cb);
 93     Collection CS=(ca.size()>Cb.size()?Cb:Ca);
 94 
 95     Collection Cc;
 96 
 97     for(int i=0;i<min;i++)
 98     {
 99         if(Coll_ChFind(CB,CS[i]))
100             Cc.push+back(CS[i]);
101     }
102     return Cc;
103 }
104 
105 Collection Coll_And(Collection Ca,Collection Cb)
106 {
107     int min=(Ca.size()>Cb.size()?Cb.size():Ca.size());
108 
109     Collection CB=(Ca.size()>Cb.size()?Ca:Cb);
110     Collection CS=(Ca.size()>Cb.size()?Cb:Ca);
111 
112     for(int i=0;i<min;i++)
113     {
114         if(!Coll_ChFind(CB,CS[i]))
115             CB.push_back(CS[i]);
116     }
117     return CB;
118 }
119 
120 Matrix Matrix_Or(Matrix Ma,Matrix Mb)
121 {
122     int min=(Ma.size()>Mb.size()?Ma.size());
123     Matrix MB=(Ma.size()>Mb.size?Ma:Mb);
124     Matrix MS=(Ma.size()>Mb.size()?Mb:Ma);
125 
126     for(int i=0;i<min;i++)
127         if(!Matrix_ColFind(MB,MS[i]))
128             MB.push_back(MS[i]);
129 
130         return MB;
131 }
132 
133 Matrix Matrix_Minus(Matrix Ma,Matrix Mb)
134 {
135     int i,min=(Ma.size()>Mb.size()?Mb.size():Ma.size());
136     Matrix Mc;
137     for(i=0;i<min;i++)
138     {
139         if(!Matrix_ColFind(mb,Ma[i]))
140             Mc.push_back(ma[i]);
141     }
142     if(min==Ma.size())
143         return Mc;
144     else
145     {
146         for(;i<Ma.size();i++)
147             Mc.push_back(Ma[i]);
148         return Mc;
149     }
150 }
151 
152 void Make_MCC(Collection Ca,vector<Collection>&pi,vector<vector<bool>> R)
153 {
154     int n=Ca.size(),i,j,k;
155     Collection A=ca,Xi;
156     Collection S,S1,S2,Col_temp,Col_temp2;
157     vector<Collection>Mat_temp1,Mat_temp2;
158 
159     if(n==1)
160     {
161         cout<<"Can not Careate the MCC!
";
162         return;
163     }
164     for(i=n-1;i>1;i--)
165     {
166         Xi.clear();
167         Xi.push_back(Ca[i-1]);
168 
169         A.clear();
170         for(j=i+1;j<=n;j++)
171         {
172             if(R[j-1][i-1])
173                 A.push_back(Ca[j-1]);
174         }
175         for(k=0;k.pi.size();k++)
176         {
177             S=pi[k];
178             if((Coll_And(S,A)).size()!=0)
179             {
180                 Col.temp1.clear();
181                 Col.temp2.clear();
182 
183                 Col_temp1=Coll_And(S,A);
184                 Col_temp2=Coll_Or(Xi,Col_temp);
185 
186                 Mat_temp1.clear();
187                 Mat.temp1.push_back(Col_temp2);
188 
189                 pi=Matrix_Or(pi,Mat_temp1);
190             }
191         }
192         for(i=0;i<pi.size();i++)
193         {
194             S1.clear();
195             s1=pi[i];
196             for(j=0;j<pi.size();j++)
197             {
198                 S2.clear();
199                 S2=pi[j];
200                 if(Coll_BeLong(S1,S2))
201                 {
202                     Mat_temp2.clear();
203                     Mat.temp.push_back(S1);
204                     pi=Matrix_Minus(pi,Mat_temp2);
205                 }
206             }
207         }
208     }
209 }