UC知道几道C语言题目
来源：百度知道 编辑：UC知道 时间：2024/05/21 17:47:49
唉，期末急着要交作业了~~但是我不会做啊！不交就要挂了！ 555555……
希望各位高手能帮忙！ 小弟谢谢了！
3、求相处融洽旅游队的最多游客人数
某个旅行社要将许多游客组成若干队出游，如把某些相互相处不融洽的游客组成一个队会影响旅游质量。为此，旅行社在组队前先设法获取各游客之间能否融洽相处的信息，以便组队时尽量将不能融洽相处的游客分在不同的队中。
现要求编写程序输入游客人数和全部游客能否相互融洽相处的信息，程序输出都能融洽相处的队的最多游客人数。
设有n位游客，全部游客能否融洽相处的信息由n行组成，每行是n个0和1字符。如下面的输入，有6位游客，第一行的第二个字符为1，表示第一位游客不能和第二位游客融洽相处。对于以下输入，你的程序将找到能一起融洽相处最多人数是3位游客。
6
010001
100100
000110
011000
001001
100010
[提示]采用背包问题的递归求解方法。对每位游客i考虑加入一个融洽相处的队和不加入队的两种情况。首先，对于游客i，若他与当前方案中哪些融洽相处的游客j(0<=j<i)也都能融洽相处，则，程序要考虑把游客i也包含在当前方案中。其次，若当前方案的预期最多人数多于目前已找到的方案的人数，则程序还要考虑游客i不包括在当前方案中。
对于全局的表示相互是否能融洽相处的字符串数组(char *a[])和人数n。找解算法的函数模型可选为： void search(int i, int p)
其中i表示当前递归考虑i号游客，p是当前方案期望都能融洽相处的游客最多是p人。
函数还将使用以下工作变量：工作数组option[]存储目前已找到的方案，该方案的人数是maxp人；当前正在形成的方案的游客选择情况存于工作数组opt[]中。
7、按以下贪婪法求解货郎担问题。货郎担问题是指给定一个无向图，并已知各边的权，要在这个图中找一个闭合回路，使回路经过图中的每一个点，而回路各边的权之和为最小。
求解货郎担问题的贪婪算法如下：
{ 1、输入无向图上的点数n（设各点依次自0开始顺序连续编号）；
2、顺序输入各顶点的
希望各位高手能帮忙！ 小弟谢谢了！
3、求相处融洽旅游队的最多游客人数
某个旅行社要将许多游客组成若干队出游，如把某些相互相处不融洽的游客组成一个队会影响旅游质量。为此，旅行社在组队前先设法获取各游客之间能否融洽相处的信息，以便组队时尽量将不能融洽相处的游客分在不同的队中。
现要求编写程序输入游客人数和全部游客能否相互融洽相处的信息，程序输出都能融洽相处的队的最多游客人数。
设有n位游客，全部游客能否融洽相处的信息由n行组成，每行是n个0和1字符。如下面的输入，有6位游客，第一行的第二个字符为1，表示第一位游客不能和第二位游客融洽相处。对于以下输入，你的程序将找到能一起融洽相处最多人数是3位游客。
6
010001
100100
000110
011000
001001
100010
[提示]采用背包问题的递归求解方法。对每位游客i考虑加入一个融洽相处的队和不加入队的两种情况。首先，对于游客i，若他与当前方案中哪些融洽相处的游客j(0<=j<i)也都能融洽相处，则，程序要考虑把游客i也包含在当前方案中。其次，若当前方案的预期最多人数多于目前已找到的方案的人数，则程序还要考虑游客i不包括在当前方案中。
对于全局的表示相互是否能融洽相处的字符串数组(char *a[])和人数n。找解算法的函数模型可选为： void search(int i, int p)
其中i表示当前递归考虑i号游客，p是当前方案期望都能融洽相处的游客最多是p人。
函数还将使用以下工作变量：工作数组option[]存储目前已找到的方案，该方案的人数是maxp人；当前正在形成的方案的游客选择情况存于工作数组opt[]中。
7、按以下贪婪法求解货郎担问题。货郎担问题是指给定一个无向图，并已知各边的权，要在这个图中找一个闭合回路，使回路经过图中的每一个点，而回路各边的权之和为最小。
求解货郎担问题的贪婪算法如下：
{ 1、输入无向图上的点数n（设各点依次自0开始顺序连续编号）；
2、顺序输入各顶点的
背包问题递归算法：
/*#include <stdio.h>
#define N 100 //物品总种数不是常量，没法根据它来决定数组的长度，只有先定义个长度了
int n;//物品总种数
double limitW;//限制的总重量
double totV;//全部物品的总价值
double maxv;//解的总价值
int option[N];//解的选择
int cop[N];//当前解的选择
struct {//物品结构
double weight;
double value;
}a[N];
//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值
void find(int i,double tw,double tv)
{
int k;
//物品i包含在当前方案的可能性
if(tw+a[i].weight <= limitW){
cop[i]=1;
if(i<n-1)find(i+1,tw+a[i].weight,tv);
else{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv;
}
}
cop[i]=0;
//物品i不包含在当前方案的可能性
if(tv-a[i].value>maxv){
if(i<n-1)find(i+1,tw,tv-a[i].value);
else{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv-a[i].value;
}
}
}
void main()
{
int k;
double w,v;
printf("输入物品种数:");
scanf("%d",&n);
printf("输入各物品的重量和价值: