UC知道求算法 C++
来源：百度知道 编辑：UC知道 时间：2024/06/18 08:23:57
10、 已知用邻接矩阵表示的无向图（graph g ），编写算法：统计该图g 的边数。
11、 某一机器中有n 个零件。每个零件有三个供应商，来自供应商j的零件i的重量为Wi ,j，其价格为Ci , j（1≤j≤3）。机器的价格等于所有零件价格之和，其重量也为各零件重量之和。设计一个动态规划算法，以决定在总价格不超过C的条件下，从哪些供应商购买零件能组成最轻的机器。（提示：可设w (i, j) 为价格低于j 时由零件i 到n 组成的最轻机器）。算法的复杂性是多少？
12、 已知有向图G=<V，E>，试设计一算法以判断是否对于任意两点u和v，至少存在一条从u到v或v到u的路径，并分析其复杂度。
13、 一个猎人带着一只狼、一头羊和一筐青菜欲乘一独木舟渡河，因独木舟太小，猎人一次至多只能带狼、羊或青菜之一渡河，但当与猎人不在河的同一边时，狼会吃掉羊、羊会吃掉青菜。试设计一个算法，帮猎人寻找一种渡河的次序让其不受损失地将狼、羊和青菜带过河去。
11、 某一机器中有n 个零件。每个零件有三个供应商，来自供应商j的零件i的重量为Wi ,j，其价格为Ci , j（1≤j≤3）。机器的价格等于所有零件价格之和，其重量也为各零件重量之和。设计一个动态规划算法，以决定在总价格不超过C的条件下，从哪些供应商购买零件能组成最轻的机器。（提示：可设w (i, j) 为价格低于j 时由零件i 到n 组成的最轻机器）。算法的复杂性是多少？
12、 已知有向图G=<V，E>，试设计一算法以判断是否对于任意两点u和v，至少存在一条从u到v或v到u的路径，并分析其复杂度。
13、 一个猎人带着一只狼、一头羊和一筐青菜欲乘一独木舟渡河，因独木舟太小，猎人一次至多只能带狼、羊或青菜之一渡河，但当与猎人不在河的同一边时，狼会吃掉羊、羊会吃掉青菜。试设计一个算法，帮猎人寻找一种渡河的次序让其不受损失地将狼、羊和青菜带过河去。
13题：
注释写在了后面,主要思想是设置了两个数组。left[3]表示没过河的集合，right[3]表示已经过河的集合。0，1，2分别表示菜，羊，狼，-2表示空（比如白菜过河了那么left[0]就等于-2)。输出结果中用x to left 和x to right表示元素的运动方向。
程序如下：
#include <stdio.h>
#include <math.h>
int kong(int left[])
//判断是否全都过河了，0表示没全过河，1表示全过河了
{
int i;
for(i=0;i<3;i++)
{
if(left[i]!=-2)
return 0;
}
return 1;
}
void ltor(int left[],int right[])
//到对岸时选一个元素
{
int i;
for(i=0;i<3;i++)
if(left[i]!=-2)
{
if(abs(left[(i+1)%3]-left[(i+2)%3])!=1)
//此句中如果两数相减有绝对值为一的元素情况说明有吃与被吃的关系存在，即不能运该元素
{
right[i]=left[i];
left[i]=-2;
printf("%d to right\n",i);
}
}
}
void rtol(int left[],int right[])
//从对岸回去时选一个元素
{
int i;
for(i=0;i<3;i++)
if(abs(right[(i+1)%3]-right[(i+2)%3])==1)
//如果有两数之差有绝对值为一的情况，说明人必须带回一个元素回去，不然有吃东西会被吃掉
{
left[(i+1)%3]=right[(