A1.

算法说明：

1、定义一个结构类型team，代表一组警卫；结构成员为两个整形数i和j，由警卫的编号组成。

2、定义一个结构类型为team的数组men[]来记录可搭档的每组警卫的编号。

3、以字符格式输入，有字符型数组num[]接收，首先接收第一个警卫的编号字符，遇到空格符后，接收第二个警卫的编号字符；遇到回车后，接收下一组警卫的编号。（由标志flag来确定）

4、由函数change()和chartonum()将num[]中的字符转换为数字，存入men[]中的各个成员变量中；

5、由函数line()使用“字典序法”对各组的“检查计算的顺序”进行排序。

6、当排好一次序时，就进行一次计算分析，有函数plan()完成，返回这次能够成功安排值班工作的最大组数；循环计算各次的结果。

7、比较记录下最大组数maxnum和相关的各组q_max[]；然后输出。

#include "stdio.h" #include "string.h" struct team // 一组警卫的结构 { int i; int j; }; void line(struct team *men, int m, int n); // 组合排序 int rank(int m); // 求m! int plan(struct team *men, int queue[], int m, int n); // 对组合进行计算分析 int change(char *num); // 字符转换为数字 int chartonum(char ch); // 同上 void main() { int n; printf("警卫人员总数 n ( n<=222 )\n"); scanf("%d", &n); getchar(); // 消除回车的影响 struct team *men = new struct team [n*(n-1)/2]; printf("输入可以一起工作的警卫人员的编号 \n"); printf("( 每行输入一个组，中间用空格分开，以ctrl+z结束)：\n"); char ch; char *num = new char [4]; int flag = 1; int m, k; m = k = 0; while((ch = getchar())!=EOF) { if(ch==' ') // 完成一组中第一个输入 { flag = 1; num[k] = '\0'; k = 0; } else if(ch=='\n') // 完成一组的输入 { flag = 2; num[k] = '\0'; k = 0; } else { num[k] = ch; k++; continue; } if(flag==1) { men[m].i = change(num); } else if(flag==2) { men[m].j = change(num); m++; } else { continue; } } line(men, m, n); delete []men; } void line(struct team *men, int m, int n) { int *queue = new int [m]; int *q_temp = new int [m]; int *q_max = new int [m]; for(int k = 0; k<m; k++) // 预先设定组顺序 { queue[k] = k; } int total = rank(m); // 可选择的组的总数 int maxnum = 0; while(total--) // 字典序法：求出各组的全排列 ( total = m! ) { k = plan(men, queue, m, n); // 对每个序计算分析 if(maxnum<k) { maxnum = k; for(k = 0; k<maxnum; k++) // 将queue数组中的值赋给q_max { q_max[k] = queue[k]; } } if(total) // total==0 不再进行排序 { for(k = m-2; k>=0; k--) { if(queue[k+1]>queue[k]) { break; } } int temp = m; int flag = 0; // 字典序法中的逆向中，大于第一逆序数的最小数位置 for(int l = m-1; l>k; l--) { if(queue[l]>queue[k] && queue[l]<temp) { flag = l; temp = queue[l]; } } queue[flag] = queue[k]; queue[k] = temp; for(l = 0; l<m; l++) // 将queue数组中的值赋给q_max { q_temp[l] = queue[l]; } for(l = m-1; l>k; l--) { q_temp[l] = queue[k+m-l]; } for(l = 0; l<m; l++) // 将q_max数组中的值赋给queue { queue[l]= q_temp[l]; } } } printf("\nOutput:\n"); printf("安排警卫组数的最大值： %d\n", maxnum); printf("各组如下：\n"); for(k = 0; k<maxnum; k++) { printf("%4d, %4d\n\n", men[q_max[k]].i, men[q_max[k]].j); } delete []queue; delete []q_temp; delete []q_max; } int plan(struct team *men, int queue[], int m, int n) { int *standard = new int [n]; for(int k = 0; k<n; k++) { standard[k] = k+1; } // 所有警卫序号 for(k = 0; k<m; k++) { if(standard[men[queue[k]].i-1]!=0 && standard[men[queue[k]].j-1]!=0) { standard[men[queue[k]].i-1] = standard[men[queue[k]].j-1] = 0; } else { break; } } delete []standard; return k; } int change(char *num) { int i, total; i = strlen(num); total = 0; for(int j = 0; j<i; j++) { total = total*10+chartonum(num[j]); } return total; } int chartonum(char ch) { switch(ch) { case '1': return 1; break; case '2': return 2; break; case '3': return 3; break; case '4': return 4; break; case '5': return 5; break; case '6': return 6; break; case '7': return 7; break; case '8': return 8; break; case '9': return 9; break; default: return 0; break; } } int rank(int m) { if(m==1 || m==0) { return 1; } else { return m*rank(m-1); } }

A4.

算法说明：

1、数据有文件test.txt输入，以字符形式依次存入数组num[]中。

2、通过函数change()和chartonum()将字符装换为整形数（同题1）存在m、n中，m为带50元钞票的观众人数，n为带100元钞票的观众人数。

3、由函数ticketline()列出所有组合，存在数组p[]中，以0代表50元的观众，1代表100元的观众。由“字典序法”排列出所有组合。

4、每排列出一种组合方式，就由函数ticketbuy()进行计算分析，使用标志flag表示售票处的50元钱的张数，如果为负则排列出错，返回0，说明组合不可行；如果非负，返回1，则说明组合可行。

5、记录下可行的次数，并输出。

#include "stdio.h" #include "string.h" void ticketline(int m, int n); // 列出所有组合 int ticketbuy(char *line, int len); // 检验每一种组合是否可行 int rank(int i); // i的阶乘 int change(char *num); // 字符转换为数字 int chartonum(char ch); // 同上 void main() { int m, n; char ch; char *num = new char[6]; FILE *fp; if((fp = fopen("test.txt", "r"))==NULL) { printf("输入文件出错!"); return; } int i, j; i = j = 0; while((ch = fgetc(fp))!=EOF) //反序读入 { if(ch!=' ' && ch!='\n') { num[i] = ch; i++; num[i] = '\0'; continue; } else if(ch==' ') { m = change(num); // 50 i = 0; continue; } else { n = change(num); // 100 i = 0; } // m, n 都处理完了，在进行下面的票务处理 if(m!=0 || n!=0) { j++; printf("Test #%d: (50) %d, (100) %d\n", j,m,n); ticketline(m, n); } else { printf("文件已处理完毕"); return; } } delete []num; fclose(fp); } void ticketline(int m, int n) { if(m<0 || n<0) { printf("输入文件内容出错!"); } int i, j; char *p = new char[m+n+1]; // 最理想的安排：00……0011……11 for(i = 0; i<m; i++) { p[i] = '0'; // 50元的购票者：0 } for(i = m; i<m+n; i++) { p[i] = '1'; // 100元的购票者：1 } p[m+n] = '\0'; char *pp = new char[m+n+1]; // 最差的安排：11……1100……00 for(i = 0; i<n; i++) { pp[i] = '1'; } for(i = n; i<m+n; i++) { pp[i] = '0'; } pp[m+n] = '\0'; char *temp = new char[m+n+1]; // 中间变量 temp[m+n] = '\0'; int sum = 0; while(strcmp(pp, p)>0) // !!!!字典序法!!!! { if(ticketbuy(p, m+n)) { sum++; } for(i = m+n-2; i>=0; i--) // 从后向前找第一个逆序 { if(p[i+1]>p[i]) { break; } } for(j = m+n-1; j>i; j--) // 从后想前找第一个100元的购票者 { if(p[j] == '1') { break; } } p[j] = '0'; p[i] = '1'; strcpy(temp, p); for(j = m+n-1; j>i; j--) { temp[j] = p[i+1+m+n-1-j]; } strcpy(p, temp); } if(ticketbuy(p, m+n)) { sum++; } delete []p; // 删除分配的空间 delete []pp; delete []temp; sum *= rank(m)*rank(n); // 全排列 = 组合数 * m! * n! printf("排队方法总数：%d\n\n", sum); } int ticketbuy(char *line, int len) { int flag = 0; for(int i = 0; i<len; i++) { if(line[i]=='0') { flag++; } else { flag--; } if(flag<0) { return 0; } } if(flag<0) { return 0; } else { return 1; } } int rank(int i) { if(i==1 || i==0) { return 1; } else { return i*rank(i-1); } } int change(char *num) { int i, total; i = strlen(num); total = 0; for(int j = 0; j<i; j++) { total = total*10+chartonum(num[j]); } return total; } int chartonum(char ch) { switch(ch) { case '1': return 1; break; case '2': return 2; break; case '3': return 3; break; case '4': return 4; break; case '5': return 5; break; case '6': return 6; break; case '7': return 7; break; case '8': return 8; break; case '9': return 9; break; default: return 0; break; } }

A5.

算法说明：

1、定义两个结构类型，结构equiment表示全部设备的情况，结构runner表示需要运行的设备的情况。

2、定义一个结构为equiment的数组equ[]，以字符的型式输入名称，以整形数字的型式输入额定电量；分别存在equ[]的成员变量中。

3、定义一个结构为runner的数组user[]，以字符的型式输入名称，以整形数字的型式输入开、关时间；分别存在equ[]的成员变量中。  与此同时，由函数search()在equ[]中搜索相应的设备，将其额定电量记录在user[]的成员变量中。

4、具体的工作计算过程由函数work()完成；比较每个时段的用电总量，并记录下最大的用电总量和时间，如果用电总量超过极限值，怎输出超过时间和所需总量；如果各时段都没超过，则输出用电总量。

#include "stdio.h" #include "string.h" struct equipment // 设备名称和额定电量 { char name[30]; int elec; }; struct runner // 使用的设备的名称，开关时间和额定电量 { char name[30]; int si; int ei; int elec; }; int search(struct runner p, struct equipment *q, int n); //在设备列表里查找相应的设备 void work(struct runner *p, int lim, int k); // 计算结果 void main() { int n, k, p; printf("设备总数 n ( n<50000 )：\n"); scanf("%d", &n); struct equipment *equ = new struct equipment [n]; //动态分配内存地址 printf("\n各设备名称 name 和 额定电量需求 pi ( pi<500 watts ): \n"); for(int i = 0; i<n; i++) { int equ_flag = 1; // 设备情况输入标志 int j = 0; while(equ_flag) { equ[i].name[j] = getchar(); if(equ[i].name[j] == ' ') { equ_flag = 0; } j++; } equ[i].name[j] = '\0'; scanf("%d", &equ[i].elec); } int work_flag = 1; // 工作情况标志 while(work_flag) { printf("\n输入运行的设备总数 k 及 最大供电量 p ( k<2500 1<=p<800000)：\n"); scanf("%d%d", &k, &p); struct runner *user = new struct runner [k]; printf("\n输入各运行设备的名称及开、关时间：\n"); for(int i = 0; i<k; i++) { int user_flag = 1; // 使用设备情况输入标志 int j = 0; while(user_flag) { user[i].name[j] = getchar(); if(user[i].name[j] == ' ') { user_flag = 0; } j++; } user[i].name[j] = '\0'; // 字符串结尾 scanf("%d%d", &user[i].si, &user[i].ei); user[i].elec = search(user[i], equ, n); if(user[i].elec == 0) { work_flag = 0;// 输入的需使用的设备未在设备列表中找到 printf("\n"); break; } } if(work_flag) //输入的需使用的设备未找到时，不进行工作计算 { work(user, p, k); } int again_flag = 1; // 重复输入标志 char ch; while(again_flag) { getchar(); // 消除‘回车’的影响 printf("是否还有输入(y or n)： "); ch = getchar(); printf("\n"); if(ch=='y' || ch=='Y') { work_flag = 1; again_flag = 0; } else if(ch=='n' || ch=='N') { work_flag = 0; again_flag = 0; } else { printf("\n输入有错误，请从新输入!\n"); again_flag = 1; } } delete []user; } delete []equ; } int search(struct runner p, struct equipment q[10], int n) { for(int i = 0; i<n; i++) { if(!(strcmp(p.name, q[i].name))) { return q[i].elec; } } printf("\n未找到正确的设备!\n"); return 0; } void work(struct runner *p, int lim, int k) { printf("\nOutput:"); int sum, e_max, t_max, i; sum = e_max = t_max = i = 0; for(i = 0; i<=24; i++) { for(int j = 0; j<k; j++) { if(p[j].si<=i && p[j].ei>=i) { sum += p[j].elec; } } if(e_max<sum) { e_max = sum; t_max = i; } if(e_max>lim) { printf("\nThe power will be out at time %d,\n", t_max); printf("because the power is %d watts and over loaded!\n\n", e_max); break; } sum = 0; // 归0 } if(e_max<=lim) { printf("\nThe maximum power needed is %d watts!\n\n", e_max); } }