算法分析与设计第三章课后练习题.doc

/*题目描述：设计蛮力算法求解小规模的线性规划问题，假设约束条件为：（1）x+y=4;(2)x+3y+0;y=0，使目标函数 3x+5y取得最大值 */*思路：用两个for遍历用一个if比较找出最大的。 */#includeusing namespace std;int main()int i,x,y,s,temp = 0;for(y = 0;y = 6;y+)for(x = 0;x = 6;x+)if(x +y) = 4)&(x + 3 * y) temp) temp = s; couttempendl;return 0;#include#includeusing namespace std;int main() long int a,b,c,d;/因为这4件商品的价格肯定存在不是整数的，所以可以将其扩大100倍进行处理 for(a=1;a711;a+)for(b=1;b=a;b+)for(c=1;c=b;c+)d=711-a-b-c;if(a*b*c*d=711*1000000)/4个数相乘就要扩大10的8次方倍 coutdouble(a)/100 double(b)/100 double(c)/100 double(d)/100endl;/将结果强制转换成双精度类型再除以100即可return 0;/*题目描述：分式化简，设计算法，将一个给定的真分数化简为最简分数形式，比如：将9/27化简为1/3，如果分子 ，分母是比较大的数又将如何处理？ */*想法：分式化简，就是找到分子分母的最大公约数，再用分子分母除以这个最大公约数，得到新的分子分母。 */*算法；输入：分式 a/b输出：最简分数1.while循环找到a,b的最大公约数2.分别用分子分母除以最大公约数3.输出最简分数 */#includeusing namespace std;int main ()int a,b,m,n,r;char c;cina;cinc;cinb;m = b;n = a;r = m % n;while(r != 0 ) m = n;n = r;r = m % n;a = a / n;b = b / n;couta/b;return 0;#includeusing namespace std;int rcreat(int n) /输入单链表int *s,*r,*p;int i;p = NULL;for(i = 1;i s-data;if(p = NULL) p=s;elser-next = s;r = s;r-next = NULL;return p;int chazhao(int *p,int n) /查找相同的元素int i;int *s,*r;s = p;r = p-next;while(r != NULL) & (r-data = s-data)int dele(*r,s-data);int dele(int *head,elemtype x) /删除相同的元素int *p,*q;q = head;p = head-next;while(p != NULL) & (p-data != x)q = p;p = p-next;q-next = p-next;delete(p);int main()int num;cinnum;int rcreat(num);/*题目描述：设计算法，在数组rn中删除重复的元素，要求移动元素的次数较少并使剩余元素间的相对次序保持不变。 */*思路；首先我们不能找到相同的就盲目的删除 ，先把它标记出来， */#includeusing namespace std;int main()int r10000;int a,b,c,d,i,j,n;cinn;for(i = 1;i ri;for(i = 1;i n-1;i+) /两个for循环找到相同的值 if(ri)for(j = i+1;j n;j+)if(ri = rj) /如果值相同，就用false标记rj = false;for(i = 1;ri;i+); /找到第一个标记 for(j = i+1;j = n;)if(!rj)ri+ = rj+;elsej+;n = i;for(i = 1;i n;i+) /输出数组coutri ; coutendl;return 0;#includeusing namespace std;int main ()int an11;int x4,y,m;int a,b,c,d,e,f,g,h,i,j,p,q,k,s,temp = 0;for(h = 123;h 988;h+)for(i = 2;i 9;i+) if(h % i = 0) /首先判断是否能整除，优化程序 y = h; for(m = 1;m 4;m+) xm = y % 10; y = y / 10; if(x1 != x2 & x1 != x3 & x2 != x3 & x1 != i & x2 != i & x3 != i) / 判断之前的4位数是否重复，优化程序 for(f = 12;f 99;f+) for(g = 2;g 9;g+) for(j = 12;j 99;j+) s = f * g + h / i - j; if(s = 0) a = f; b = g; c = h; d = i; e = j; an0 = a % 10; a = a/10; an1 = a % 10; an2 = b; an3 = c % 10; c = c / 10; an4 = c % 10; c = c / 10; an5 = c % 10; c = c / 10; an6 = d; an7 = e % 10; e = e / 10; an8 = e % 10; for(p = 0;p 8;p+) for(q = p+1;q 9;q+) if(anp anq) temp = anq; anq = anp; anp = temp; for(k = 0;k 9;k+) s = s*10 + ank; if(s = 987654321) coutf g h i jendl; return 0;/*题目描述：设计算法：判断一个大数能否被11整除，可以思考不同的算法*/*思路；对于大数的除法，我们才用分块相除。 */*算法：输入：输入一个字符串；输出：是否能被整除1.一个循环把所有的字符串都来整除112.判断余数是否*/#includeusing namesp