C语言解决四人/多人过桥问题

article/2025/9/11 21:14:59

参加笔试的时候遇到一道经典的算法题，四人过桥问题。当时没写出来😅。
四人过桥问题：在一个黑夜里，有四个人需要过桥，每次只能通过两人，其中一人必须拿着手电筒；但只有一个手电筒，所以过桥后必须有一个人拿手电筒回来，其他人才能继续过桥。四人过桥的速度分别为：1，2，5，10(分钟);要最慢的那个人过了桥才算真正过桥。求怎样才能最快的全部人都过桥？

#include <stdio.h>
#include <stdbool.h>
int sum = 0;
/*** @description: 过桥-------num,m,sum都是为了打印才设置的参数，可有可无* @param {int} data   存放每个人过桥需要的时间的数组* @param {bool} flat  记录每个人是否过桥的标志，true表示已经过桥，false表示没有过桥* @param {int} num    记录过桥和回来的人的顺序* @param {int} count  总人数* @param {int} n      已经过桥的人数* @param {int} time   记录过桥的总时间* @param {int} m      记录过去或回来的次数* @return {*}*/
void Cross_bridg(int data[],bool flat[],int num[],int count,int n,int time,int m)
{if(n > count)//当过去的人数大于总人数时，退出---不会执行到return;if(n == count)//当过桥的人数等于总人数时，打印信息{printf("%d\n",time);for(int i = 0;i < m;i++){printf("%d",num[i]);if(i%3 == 1)printf("-->\t");else if(i%3 == 2)printf("<--\t");elseprintf(",");}sum++;printf("\n-----------------------------------------sum : %d\n",sum);return;  //递归的回归条件}int k = 0;//这部分默认data数组是已经有序的--从小到大；否则这部分要改一下,重新写获取最小值的代码for(k = 0;k < count;k++)//从已经过桥的人当中选择过桥时间最短的人拿手电筒回来---有点贪心算法感觉，这样可以少运行很多{if(flat[k]){time   += data[k];//回来的人的时间也要算法到过桥的总时间里flat[k] = false;//将回来的人从已经过桥的人当中去除n--;num[m++] = data[k];break;}}int max   = 0;int temp  = 0;int temp1 = 0;for(int i = 0;i < count;i++)//从未过桥的人中选择一个{if(flat[i])//判断这个人是否未过桥continue;flat[i]   = true;for(int j = 0;j < count;j++)//从未过桥的人中选择一个{if(flat[j])//判断这个人是否未过桥continue;max = data[i] > data[j] ? data[i] : data[j];//从这两人中选择过桥时间最大的加入到总时间中if((temp == (data[i] + data[j])) && temp1 == max)//这个判断可以减少一半重复项,例如 1，2 和 2，1continue;flat[j]  = true;//标志为已过桥temp     = data[i] + data[j];temp1    = max;num[m]   = data[i];num[m+1] = data[j];Cross_bridg(data,flat,num,count,n+2,time+max,m+2);//递归//从深一层递归回归后，这里就属于另一种情况的判断，记得将这两人的标志恢复，否则会影响到其它判断flat[j]  = false;}flat[i]   = false;}if(k < count)flat[k] = true;//记得恢复标志return;
}int main()
{int data[] = {1, 2, 5,10};int num[20] = {0};bool flat[4] = {0};Cross_bridg(data,flat,num,4,0,0,0);return 0;
}