2000.11请你编程

oldbug
2000年 第45期 

　　大家好！《请你编程》又与你们见面了。《请你编程》得到了广大朋友的关心和支持，我在这里表示衷心的感谢。《请你编程》是一个读者朋友直接参与的栏目，是一个体现自我的园地，希望有编程愿望的朋友，无论是编程高手，还是初学者都能参与进来，我们将会认真对待每一份作品。下面请看2000.6期江苏读者江骞的程序。
　　美食家俱乐部程序的基本思路是：
　　1．定义四个数组：
　　int one[16]; //标示16个人是否已安排好，0表示还未安排好，1表示已安排好。
　　int two[16][16]; //记录任意两者是否已同过一桌。
　　int three[16][16][16];//记录任意三者是否已同过一桌。
　　int four[16][16][16][16];//记录任意四者是否已同过一桌。
　　2．读出文件gourmet.txt中的数据，初始化数组two、three、four；
　　3．产生一个当天未上桌的人a；
　　4．产生第二个当天未上桌的人b；
　　5．判断是否a、b还未同过桌，若同过则重做4；
　　6．同理产生c、d；
　　7．如果可以产生，则记录到数组，输出并保存；否则输出不可产生排序法，退出。
　　本程序由：VC6.0编成，DOS环境下执行通过。
　　源程序如下：
　　// 排人.cpp : Defines the entry point for the application.
　　＃include <stdio.h>
　　＃include <stdlib.h>
　　＃include <conio.h>
　　int one[16]; //标识16个人是否已安排好，0表示还未安排好，1表示已安排好。
　　int two[16][16]; //记录任意两者是否已同过一桌。
　　int three[16][16][16]; //记录任意三者是否已同过一桌。
　　int four[16][16][16][16];//记录任意四者是否已同过一桌。
　　int num=0;   //计数器，输出格式用
　　void definevalue（int a，int b，int c，int d） //复值函数，将已同过一桌的人的对应数组置1。
　　{
　　two[a][b]=1;
　　two[b][c]=1;
　　two[c][d]=1;
　　two[a][c]=1;
　　two[a][d]=1;
　　two[b][d]=1;
　　three[a][b][c]=1;
　　three[a][b][d]=1;
　　three[a][c][d]=1;
　　three[b][c][d]=1;
　　four[a][b][c][d]=1;
　　}
　　void output（int a，int b，int c，int d，int out_count）  //输出函数，将算出的值在屏幕上显示，并存盘。
　　{
　　FILE ＊fp;
　　printf（″％c％c％c％c″，a＋65，b＋65，c＋65，d＋65）;
　　if（num％4==3）
　　printf（″\n″）;
　　else printf（″\t″）;
　　if（（fp=fopen（″gourmet.txt″， ″r＋″））==NULL）
　　{
　　printf（″File of gouret.txt is not opened.\n″）;
　　exit（1）;
　　}
　　fseek（fp，0，SEEK_END）;
　　if（num％4==0）
　　fprintf（fp，″\n″）;
　　else
　　fprintf（fp，″ ″）;
　　fprintf（fp，″％c％c％c％c″，a＋65，b＋65，c＋65，d＋65）;
　　fclose（fp）;
　　num＋＋;
　　}
　　void init（） //初始化函数，用于清零四个数组。
　　{
　　int i，j，k，l;
　　for （i=0;i<13;i＋＋）
　　{
　　one[i]=0;
　　for（j=1;j<14＆＆j!=i＆＆i<j;j＋＋）
　　{
　　two[i][j]=0;
　　for（k=2;k<15＆＆k!=j＆＆k!=i＆＆j<k;k＋＋）
　　{
　　three[i][j][k]=0;
　　for（l=3;l<16＆＆l!=i＆＆l!=j＆＆l!=k＆＆k<l;l＋＋）
　　four[i][j][k][l]=0;
　　}
　　}}}
　　void readfile（）   //读文件函数，用于将已给数据读出。
　　{
　　int i，a=0，b=0，c=0，d=0;
　　FILE ＊fp;
　　if（（fp=fopen（″gourmet.txt″， ″r″））==NULL）
　　{
　　printf（″File of gouret.txt is not opened.\n″）;
　　exit（1）;
　　}
　　for（i=0;i<12;i＋＋）
　　{fseek（fp， （i＊5）＋int（i/4）， SEEK_SET）;
　　fscanf（fp， ″％c％c％c％c″， ＆a，＆b，＆c，＆d）;
　　definevalue（a－65，b－65，c－65，d－65）;}
　　fclose（fp）;}
　　int produce（int first）    //从当天还未在桌上吃饭的人中选人。
　　{
　　int e=0，i;
　　for（i=first;i<16;i＋＋）
　　{if（one[i]==0）
　　{e=i;
　　return（e）; //选中。
　　}}
　　return（－1）; //无人可选。
　　}
　　void table（int first，int tab_count）   //产生一桌四个人。
　　{ int a，b，c，d;
　　b=a=produce（first）;    //从first开始产生第一个人，第二个人记住。
　　do
　　{do
　　{c=b=produce（b＋1）;  //从第一个人开始产生第二个人，第三个人记住。
　　if（b==－1） //如果不能产生第二个人则报不能排，退出。
　　{ printf（″\nIt is not possible to complete this schedule.\n″）;
　　getch（）;
　　exit（1）;}
　　}
　　while（two[a][b]==1）;  //产生的第二个人已经和第一个人同桌过。
　　do
　　{do
　　{d=c=produce（c＋1）;  //从第二个人开始产生第三个人，第四个人记住。}
　　while（（c!=－1）＆＆（three[a][b][c]==1||two[a][c]==1||two[b][c]==1））;  //产生的第三个人已经和第二或第一个人同桌过。
　　do
　　{     d=produce（d＋1）;    //从第三个人开始产生第四个人，}
　　while（（c!=－1）＆＆（d!=－1）＆＆（four[a][b][c][d]==1||two[a][d]==1||two[b][d]==1||two[c][d]==1||three[a][b][d]==1||three[a][c][d]==1||three[b][c][d]==1））;
　　//产生的第四个人已经和第三、第二或第一个人同桌过。}
　　while（（c!=－1）＆＆（d==－1））;}
　　while（c==－1）;
　　one[a]=1; //标志已排好的四人上过桌。
　　one[b]=1;
　　one[c]=1;
　　one[d]=1;
　　definevalue（a，b，c，d）;
　　output（a，b，c，d，tab_count）;}
　　void calculate（int cal_count）  //计算排序的调用次数。
　　{int i;
　　for（i=0;i<13;i＋＋）
　　if（!one[i]）
　　table（i，cal_count）;}
　　void day（int date） //可以在此处通过修改参数达到算出不同天数的排序。
　　{int count;
　　count=（date＋3）＊4;
　　calculate（count）; }
　　void main（）
　　{int date，i;
　　init（）;
　　readfile（）;
　　for（date=0;date<2;date＋＋）
　　{num=0;
　　day（date）;
　　for（i=0;i<16;i＋＋）
　　one[i]=0;}
　　getch（）;}
　　本期请你编程题目
　　动物园要把M只狼和N只狗（N>=M）从一条河的西岸送到河的东岸。只有一条小船可以送它们过去。但是，这条船一次最多只能坐2只动物，最少必须要坐1只动物。但是，由于狗比较弱小，当某一边岸上的狗的数目少于狼的数目（如果狗的数目不为零的话）的时候，狼就会欺负狗。所以，在运送的过程中必须保持两边岸上狗的数目都不少于狼的数目。我们现在利用两个m、n和一个字母P表示运送过程中每一步骤的状态：m、n表示该步骤中在西岸上狼和狗的数目，字母P可以取两个值（W、E），W表示该步骤中船在西岸、E表示该步骤中船在东岸。作为初始状态，可以表示为（M，N，W）。
　　很明显，假设一开始有2只狼、2只狗，船在西岸，这时候状态表示为（2，2，W），如果把2只狼运送过去，则下一步状态为西岸上没有狼，只有2只狗，船在东岸，表示为（0，2，E）。当最后状态演变成为（0，0，E）的时候，就可以认为全部运送成功。当最后状态无法演变成为（0，0，E）的时候，可以认为这是一个无法完成的任务。现在就请你编一个程序来帮动物园解决这个问题。程序要求如下：
　　输入：输入数据从文本文件zoo.txt中读取，格式为若干行，每行包括两个整数M、N，表示有M只狼和N只狗，（10>=N>=M>=1），两数之间用空格分开。当M=N=0的时候，表示输入数据结束。
　　输出：输出到屏幕上，对于某一组输入数据M、N，如果不可能运送成功，输出字符串：“不可能的任务”。否则按每步（m，n，P）的格式输出运送过程中每步状态，m、n表示该步步骤中在西岸上狼和狗的数目，字母P可以取两个值（W、E），W表示该步步骤中船在西岸、E表示该步步骤中船在东岸，每步状态输出一行。一组数据输出完毕后输出一空行与下一组输出数据分开。
　　输入范例：
　　2 2
　　0 0
　　输出范例：
　　（2，2，W）
　　（0，2，E）
　　（1，2，W）
　　（1，0，E）
　　（2，0，W）
　　（0，0，E）
　　本期题目由上海的oldbug提供。

 