[C语言结课作业]对于对商人过河用C语言实现的一次实践

warning: 这篇文章距离上次修改已过205天,其中的内容可能已经有所变动。

0xc0 起因

因为从来不去小课堂而且巨能哔哔,于是终于在这一天翻车了……

qq_pic_merged_1607512674555.jpgqq_pic_merged_1607512674555.jpg


事实证明,自己装出去的B跪着也要兑现,更何况我还在这死撑……
qq_pic_merged_1607512918072.jpgqq_pic_merged_1607512918072.jpg

warning:我巨亏!

0xc1

传统武德讲究点到为止,既然学长不讲武德,我也该开始着手处理这道题了。

12月9日突发情况……

qq_pic_merged_1607515857841.jpgqq_pic_merged_1607515857841.jpg


那么我们来看这道题:
33ISX{@XW}8@733CXS)XW45.jpg33ISX{@XW}[email protected])XW45.jpg

大致理解就是给出商人、仆从和船载量,然后输出解决方案,首先我们可以知道初值商人必然大于仆从数且船载量大于等于2,即:

int a,b,c;//master,servant,carriage;
scanf("%d%d%d",&a,&b,&c);
if (a<1||b<1||c<2||a<b){printf("Error!");return 0;}

解决方案按照学长的意思应该是给出对岸的人数二维集合和每次操作的二维集合,大概如下

int ta[50]={0},tb[50]={0},fa[50]={0},fb[50]={0};
int n=0,na,nb;//转移次数,转移商人数,转移仆从数;
int x=a,y=b;//标记当前此岸的(商人,仆从),当为(0,0)时结束;

end:
printf("Path:");
for(int i=0;;){
    if(x!=0||y!=0){
        printf("(%d,%d),",x,y);
  x=x-ta[i]+fa[i];y=y-tb[i]+fb[i];
  }
    if(x==0&&b==0){
        printf("(0,0)\n");
 break;  }
}
printf("Method:");
for(int i=0;;){
    if(ta[i]!=0||tb[i]!=0)printf("(%d,%d),(%d,%d),",ta[i],tb[i],fa[i],fb[i]);
 if(ta[i]==0&&tb[i]==0)printf("end");
}

本题最难的地方在于船载量非定值,这意味着每次的运输来回不一定都是c,对于多次来回,我们在保证对岸商人数大于等于仆从数时保证此岸商人数尽量等于仆从。
对于初始条件我们不妨先分为4种情况,

for(;;){
int condition=0;
if (isEven(c))condition+=1;//fun1来判断是奇数还是偶数,fun2执行判断分析;
if (isEven(a-b))condition+=2;
switch (condition) {
    case 0:
        goto cond1;
 break; case 1:
        goto cond2;
 break; case 2:
        goto cond3;
 break; case 3:
        goto cond4;
 break;}}

此处condition为我们的条件变量,如果船载量是偶数则+1,如果商人仆从差值等于偶数则+2。
我们先从cond1即商人-仆从为奇数而船载量为奇数部分开始考虑。鉴于开船需要至少一人,因此这一人在什么时候该是谁才能使来回次数最小便是我们首先要考虑的。但无论如何,我们把划船的人先抛出去的话,剩下的问题就和cond4没区别,同理cond2cond3也可以相互转化,最终我们总能把问题简化为m名商人,n名随从和2人载量的情况。因此我们先构造一个这样的函数,使得这个问题可以递归解决。

点击量3157次
最后修改于:2021年11月05日 12:20

添加新评论