求算法 C++

显示全部楼层 · 2008-6-27 14:43: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=，试设计一算法以判断是否对于任意两点u和v，至少存在一条从u到v或v到u的路径，并分析其复杂度。
13、一个猎人带着一只狼、一头羊和一筐青菜欲乘一独木舟渡河，因独木舟太小，猎人一次至多只能带狼、羊或青菜之一渡河，但当与猎人不在河的同一边时，狼会吃掉羊、羊会吃掉青菜。试设计一个算法，帮猎人寻找一种渡河的次序让其不受损失地将狼、羊和青菜带过河去。

千问 · 2008-6-27 14:43:57

13题：注释写在了后面,主要思想是设置了两个数组。left[3]表示没过河的集合，right[3]表示已经过河的集合。0，1，2分别表示菜，羊，狼，-2表示空（比如白菜过河了那么left[0]就等于-2)。输出结果中用x to left 和x to right表示元素的运动方向。程序如下： #include#includeint kong(int left[]) //判断是否全都过河了，0表示没全过河，1表示全过河了 { int i; for(i=0;i<3;i++) { if(left!=-2) return 0; } return 1; }

千问 · 2008-6-27 14:43:57

又一个来找作业答案了…………坚决不理！