算法设计第四章部分作业
算法第4-7章部分答案
第四章
第4题：
想法：
求两个正整数m和n的最小公倍数，由题目给出的提示可以知道，m和n的最小公倍数等于两个数的积除以它们的最大公约数。在第一张的事后要我们就已经用欧几里德算法求过两个数的最大公约数，所以对于题目4，我们就可以直接引用欧几里德算法辅助求最小公倍数。
算法：
输入：两个自然数m和n
输出：m和n的最小公倍数
1.r=m%n;
1.循环直到r=0
1.1m=n;
1.2n=r;
1.3r=m%n;
2.return n
3.调用2输出(m*n)/n
程序：
#include
int CommFactor2(int m, int n);//求两个数的最大公约数
int main()
{
int a, b, r,s;//r表示a,b两个数的最大公约数,s表示a,b的最大公倍数
cout<<"请输入两个自然数：";
cin>>a>>b;
r = CommFactor2(a, b);//调用函数求最大公约数
cout< s=a*b/r;//最大公约数与最大公倍数之间的关系 cout< return 0; } int CommFactor2(int m, int n)//返回两个数的最大公约数 { int r = m % n; while (r != 0) { m = n; n = r; r = m % n; } return n; } 第6题： 想法： 首先要建立一个大根堆，然后实现删除操作，关键是如何实现删除操作，我的想法是将要删除的元素和建立的大根堆的最后一个元素交换，然后再调用建立大根堆的函数将前n-1个函数进行大根堆操作 算法： 输入：要删除的元素的下标 输出：删除后排序好的大根堆 1.构造一个大根堆堆顺序函数SiftHeap（） 2.构造一个大根堆函数初始建堆函数HeapSort（），调用函数SiftHeap（） 3.建立初始大根堆 4.输入要删除的元素的下标 5.将要删除的元素与最后一个一个元素交换 6.建立前n-1个元素的大根堆 程序： //想法：先将已知序列排列成一个大根堆，删除某个元素后，将最后一个元素赋值给删除节点，然后再进行堆排序（堆排序只是有序排序中的一部分） #include void HeapSort(int r[ ], int n);//建立堆以及堆中元素整体排序 void SiftHeap(int r[ ], int k, int n);//堆排序函数 int main() { int m; int r[]={47,33,35,2,18,71,26,13}; int i,n=8; HeapSort(r, n);//调用函数建立一个大根堆 for( i=0;i<8;i++) cout< cout< cout<<"大根堆中要删除的元素的下标为:"; cin>>m;//输入大根堆中要删除的元素的下标 if(m<0||m>=n) cout<<"要删除的元素的不存在"< else { int temp; temp=r[m];//将该元素的下标与大根堆最后一个元素交换，然后将前n-1个元素进行大根堆排序即可 r[m]=r[n-1]; r[n-1]=temp; } HeapSort(r, n-1); for( i=0;i<7;i++) cout< return 0; } void SiftHeap(int r[ ], int k, int n) { int i, j, temp; i = k; j = 2 * i +1; //置i为要筛的结点，j为i的左孩子 while (j < n) //筛选还没有进行到叶子 { if (j < n-1 && r[j] < r[j+1]) j++; //比较i的左右孩子，j为较大者 if (r[i] > r[j]) //根结点已经大于左右孩子中的较大者 break; else { temp = r[i]; r[i] = r[j]; r[j] = temp; //将被筛结点与结点j交换 i = j; j = 2 * i+1; //被筛结点位于原来结点j的位置 } } } void HeapSort(int r[ ], int n) { int i; for (i = (n-1)/2; i >= 0; i--) //初始建堆，从最后一个分支结点至根结点SiftHeap(r, i, n) ; } 第7题： 想法： 求两个数的乘积，根据已知提示可以采用俄式乘法，即是采用减治法将被乘数一直减 小到1，同时将乘数以2倍的方式增大，同时将减去过程中产生的数累加最后一个求和 算法： 输入：两个正整数 输出:l两个数的乘积 1.构造一个俄式乘法函数fun（） 2.输入两个数，对两个数比较大小，将较小的数作为被乘数 3.判断被乘数的奇偶性，若是偶数则减半，若是技术则减1再减半 4.进行while循环做递归处理 5.返回最后的值 6.调用函数输出结果 程序： //俄式乘法算法 #include using namespace std; int fun(int a,int b) { int temp; if(a>b)//大乘小除，减少运算步骤 { temp=b; b=a; a=temp; } int count,s=0;//count用于存放结果，s用于存放计算过程中奇数a减1产生的累加值 while(a>1) { if(a%2==0)//若a为偶数 { a=a/2; b=b*2; } else if(a%2==1)//若a为奇数 { a=(a-1)/2; s+=b;//注意s和b的位置不可以交换哦，因为是b未加倍之前的累加和 b=b*2; } } count=a*b+s; return count; } int main() { int m,n; int sum; cout<<"请输入两个乘数:"; cin>>n>>m; sum=fun(n,m); cout<<"计算结果为:"; cout< return 0; } 第8题： 想法： 对于火柴游戏，如果起初所有火柴的数量是5的倍数，那么第一个人是不能赢的，如果要第一个人赢得游戏，那么，要在火柴数量不是5的倍数的情况下进行，不管第二个人拿几根火柴，只要第一个人拿的数量是n%5的模值即可赢得游戏！ 算法： 输入：火柴的数量和第二个让人拿的火柴数量 输出：第一个拿的火柴数量 1.构造fun()函数，让A拿的火柴数是第二个人拿完后的数量模5的值 2.判断n%5的值 3.如果模值不等于0，调用fun()函数 4.进行递归调用fu n知道火柴拿完为止 程序： //火柴问题，如果火柴根数是5的倍数，那么只要B不是傻瓜A就输定了！反之如果不是5的倍数，那么A每次只要拿n%5的模值就一定能赢 #include using namespace std; int fun(int n) { while(n>0) { int i,j; i=n%5; cout<<"A:"< n=n-i; if(n>0)//当A拿完之后还有火柴时B才可以拿 { cout<<"B:"; cin>>j; if(j<1||j>4) cout<<"出错了!您只能拿1—4根火柴:"< else { n=n-j; return fun(n);//递归调用函数 } } } } int main() { cout<<"请输入火柴根数:"; int n; cin>>n; if(n%5==0) cout<<"放弃吧!在B不是傻瓜的情况下A输定了!"< else fun(n); return 0; } 第10题： 想法： 这个想法是基于已知假币的轻重的情况下进行的，我假设假币比真币轻来进行试验，也可以假设假币比真币重，只需要稍微改写一下程序即可。首先，我将硬币分成3堆，用数组来存放硬币的重量，随便假设一个数组元素为假，用累加判断大小的方式来判断假币出现在哪一堆分组中，对可能出现的三种情况进行递归调用Coin（）函数来进行循环判断，直到找到假币为止 算法： 输入：一个数组用来存放硬币的重量 输出：假币的位置 1.构造Coin()函数，将硬币分成三堆，如果硬币数量是3的倍数则均分成3组，如果不是 则前两组分成n/3+1 2.累加比较重量来判断假币出现的地方 3.递归循环调用Coi n()函数 4.返回假币的下标 5.在主函数中调用Coi n()函数，输出结果 程序： #include const int N = 12; //假设求解12枚硬币问题 int a[N] = {2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2}; int Coin(int low, int high, int n); int main() { int i=Coin(0,11,12); cout<<"假币是第"< return 0; }//真币的重量是2，假币的重量是1 int Coin(int low, int high, int n) //在a[low]~a[high]中查找假币 { int i, num1, num2, num3; // num1、num2和num3存储3组硬币的个数 int add1 = 0, add2 = 0; //add1和add2存储前两组硬币的重量和 if (n == 1) //递归结束的条件 return low + 1; //返回的是序号，即下标加1 if (n % 3 == 0) //3组硬币的个数相同 num1 = num2 = n / 3; else num1 = num2 = n / 3 + 1; //前两组有n / 3 + 1 枚硬币 num3 = n - num1 - num2; for (i = 0; i < num1; i++) //计算第1组硬币的重量和 add1 = add1 + a[low + i]; for (i = num1; i < num1 + num2; i++) //计算第2组硬币的重量和add2 = add2 + a[low + i]; if (add1 < add2) //在第1组查找，下标范围是low~low+num1-1 return Coin(low, low + num1 - 1, num1); else if (add1 > add2) //在第2组查找，下标范围low+num1~low+num1+num2-1 return Coin(low + num1, low + num1 + num2 - 1, num2); else //在第3组查找，下标范围low+num1+num2~high Coin(low + num1 + num2, high, num3); } 第五章 第6题： 想法： 对于第6题，用分治法进行求解的话，若是采用循环赋值的方式，如果字符的个数和左移的位数成倍数关系，那么算法就比较容易实现，但是如果不成比例关系，算法写起来就比较麻烦，所以，我用了另一种方式，进行三次对称交换就可以完成算法。 算法： 1.输入：一个数组和左移位数 2.编写两个函数，一个是对称交换函数1，另一个是调用函数2，用函数2三次调用函 数1，完成整个对称交换过程。 3.调用函数2 4.输出：左移后的数组 程序： /*(升级版2)这个是用分治法将一个字符串(abcdefgh)左移3位(defghabc)，具体用到的方法是对称交换和调用函数*/ #include using namespace std; void fun(char *a,int m,int k)//（函数1）对称交换函数（注意函数1和函数2书写的顺序，不要写反了，先有函数1，再写函数2） { int temp; int i,j; for(i=m,j=k;i<=k;i++,j--) { if(i<=(m+k)/2) { temp=a[i]; a[i]=a[j]; a[j]=temp; } } } void xun(char a[],int k,int n)//（函数2）第二个调用函数，调用函数1 { fun(a,0,k-1);//第一次调用函数1，将(abc)对称交换得到(cba),最后a[]为(cbadefgh) fun(a,k,n-1);//第二次调用函数1，将(defgh)对称交换得到(hgfed),最后a[]为(cbahgfed) fun(a,0,n-1);//第三次调用函数1，将(cbadefgh)对称交换得到(defghabc),即最后a[]为(defghabc) } int main() { char a[1000]; cout<<"请输入一个数组:"< gets(a);//用cin>>a;也可以哟，不过配套的比较好看！ int k; cout<<"请输入左移位数:"< cin>>k; int n=strlen(a); xun(a,k,n); puts(a);//用cout< return 0; } 想法： 采用二分查找的方式进行递归查找，找到符合要求的数就输出 算法： 1.编写递归函数，用if---else语句，返回符合要求的函数下标 2.调用递归函数，寻找符合要求的值 3.输出找到的值 程序： /*用分治的方式查找有序序列中序列号等于元素的元素，此处可以采用二分查找的方式*/ #include using namespace std; int fun(int a[],int small,int big)//fun函数用于递归 { int equ1,equ2,mid,equ; if(a[small]==small+1) return small; else if(a[big]==big+1) return big; else { mid=(small+big)/2;//二分查找的方式， if(a[mid]>=mid+1)//因为序列式有序的，所以如果a[mid]>mid，那么要查找的元素不可能存在后一半元素中 { big=mid; equ1=fun(a,small,big);//递归调用fun函数 return equ1; } else { small=mid+1; equ2=fun(a,small,big); return equ2; } } } int main() { int equ; int a[]={-6,-2,3,5,6,7,67,89,102};//给出一个有序序列 equ=fun(a,0,8);//调用函数 cout< } 第六章 习题6： 第二题： 想法： 根据6.2图问题中的动态规划法，对于多段图的最短路径问题，将它划分成K段，每一段包含定点的一个子集，每个子集中的定点互不相邻，将其建立成一个加权矩阵，一段一段的进行局部最优求解，并且逐步覆盖，得到最短路径长度，最后再进行回溯，找到路径。算法： 输入：多段图的加权矩阵 输出：最短路径长度和路径 1.调用函数循环填表 2.考察定点的所有入边，选择最小的路径并保存下来 3.输出左端路径的长度 4.回溯，输出最短路径 程序： #include const int N = 20; const int MAX = 1000; int arc[N][N]; //存储弧上的权值 int Backpath(int n);//n代表顶点个数 int creatGraph(); int main() { int n = creatGraph( );//调用函数 int pathLen = Backpath(n);//调用函数 cout<<"最短路径的长度是："< return 0; } int creatGraph() { int i, j, k; int weight; int vnum, arcnum; cout<<"请输入顶点的个数和边的个数："; cin>>vnum>>arcnum; for (i = 0; i < vnum; i++) for (j = 0; j < vnum; j++) arc[i][j] = MAX; for (k = 0; k < arcnum; k++)//初始化多段图 { cout<<"请输入边的两个顶点和权值："; cin>>i>>j>>weight; arc[i][j] = weight; } return vnum;//返回顶点个数 } int Backpath(int n)//求个顶点的多段图最短路径的函数，返回最短路径长度 { int i, j, temp; int cost[N];//存放路径长度 int path[N];//存放路径 for(i = 0; i < n; i++) { cost[i] = MAX; path[i] = -1; } cost[0] = 0;path[0]=-1;//顶点0为起点 for(j = 1; j < n; j++)//执行填表工作 { for(i = j - 1; i >= 0; i--)//考察所有入边 { if (arc[i][j] + cost[i] < cost[j])//比较路径长度，短路径覆盖长路径（但是程序是将前面的所有都点都遍历一次，太过复杂，可以优化） { cost[j] = arc[i][j] + cost[i]; path[j] = i; } } } cout< i = n-1; while (path[i] >= 0)//依次输出path[i] { cout<<"<-"< i = path[i];//求得路径上顶点i的前一个顶点 } cout< return cost[n-1];//返回最短路径长度 } 第四题： 想法： 根据6.3.2最长公共子序列问题的分析，将该问题分解成两个矩阵问题进行求解，一个矩阵L(i, j)记载当前位置的最长公共子序列的长度，另一个矩阵S(i , j)记载求解过程中的状 态变化。两个矩阵都要分情况进行计算，最后再对S矩阵进行回溯，求解出公共子序列。算法： 1.初始化矩阵L的0行0列 2.填充矩阵L和S 3.建立一个数组Z存储公共子序列 4.输出最长公共子序列以及长度 程序： #include int L[10][10],S[10][10];//L(m,n)用于存放X={x1,x2,...,xm}和Y={y1,y2,...,yn}的最长公共子序列的长度 int CommonOrder(char x[ ], int m, char y[ ], int n, char z[ ]);//S(i,j)用于记载求解过程中的状态变化 int main() { //char x[]={'a', 'b', 'c', 'b', 'd', 'b'}; char A[]={'x', 'z', 'y', 'z', 'z', 'y','x'};//程序需要优化，因为输出的结果为1个，但是实际的结果可能有多个?????? //char y[]={'a','c', 'b', 'b', 'a', 'b', 'd', 'b', 'b'}; char B[]={'z','x', 'y', 'y', 'z', 'x', 'z'}; char z[10]; cout<<"长度为："< return 0; } int CommonOrder(char x[ ], int m, char y[ ], int n, char z[ ]) { int i, j, k; for (j = 0; j <= n; j++) //初始化第0行 L[0][j] = 0; for (i = 0; i <= m; i++) //初始化第0列 L[i][0]=0; for (i = 1; i <= m; i++)//建立矩阵L(m,n)和S(i,j) { for (j = 1; j <= n; j++) { if (x[i-1] == y[j-1]) { L[i][j] = L[i-1][j-1] + 1; S[i][j] = 1; } else if (L[i][j-1] >= L[i-1][j]) { L[i][j] = L[i][j-1]; S[i][j] = 2; } else { L[i][j] = L[i-1][j]; S[i][j] = 3; } } } i = m; j = n; k = L[m][n]; //将公共子序列存储到数组z[k]中 while (i >0 && j >0) { if (S[i][j] == 1) { z[k] = x[i-1]; k--; i--; j--; }//分三种情况进行回溯 else if (S[i][j] == 2) j--;//搜索S(i,j-1) else i--;//其它情况即是S[i][j] == 3时搜索S(i-1,j) } for (k =1; k <=L[m][n]; k++) //输出最长公共子序列 cout< cout< return L[m][n]; //返回公共子序列长度 } 第八题： 想法： 我觉得这个类似于最长公共组序列问题，可以用同样的方式进行求解。同样建立一个矩阵L来存储需要的货币的最小数量。算法的关键在于需要货币数量的算法设计，即是怎样来填充L的算法。 算法： 输入：货币种类数，货币价值，（这里要求重0开始输入，只是为了方便计算，0并不作它用）以及需要兑换的货币值 输出：兑换的最小货币个数 1.输入x value[i] z 2.比较j和value[i]的大小 2.1．当value[j]==i 将a[i][j]=1; 2.2．当value[j]>i 将a[i][j]=a[i][j-1]; 2.3．当value[j] 3.输出需要的最小货币 程序： //感觉有点类似于最长公共子序列问题 #include #define N 100000 #define M 20 int a[N][M]; //用于存放兑换的最小货币数量 int value[M]; using namespace std; int main()//假设货币分成4中，分别为1,5,10,20元，要兑换的是16元 { while(true) { int value[10];//自己修改的 int i,j,k; int x,y,z; cout<<"请输入货币种类的个数:"< cin>>x; cout<<"请从小到大输入货币的价值，其中第一个必须为0:"< for(i=0;i<=x;i++)//x为货币种类的个数 { cout<<"value["< //cin>>y;//不能用一个值进行输入,这样货币的value[]值会被最后一个值覆盖所以导致结果建立的矩阵为全1矩阵，不能达到算法目的 //value[y]; cin>>value[i];//自己修改的 } cout<<"请输入要兑换的钱的价值:"< cin>>z;//z为钱 for(j=0;j<=z;j++)//x+1列z+1行的矩阵 a[j][0]=0;//为首列赋值 for(k=0;k<=x;k++) a[0][k]=0;//为首行赋值 for(i=1;i<=z;i++)//这是整个算法的关键所在 { for(j=1;j<=x;j++) { if(value[j]==i)//货币值与要兑换值刚好相等，相当于将乘法换成加法，即碰到一个钱数等于兑换货币的自身价值时，返回到钱数减去该货币值的地方，其值再加1 a[i][j]=1;//货币数量加1,a[1][1]=1; else if(value[j]>i)//货币值大于要兑换值，如，要兑换的是3元，而已有货币面值是5元 a[i][j]=a[i][j-1]; else if(value[j] { int s; s=i-value[j]; a[i][j]=a[s][j]+1; }//货币值小于要兑换值,a[2][1]=2;(这里没有执行，为什么呢?) cout< } cout< } cout<<"兑换的最小货币个数是:"< } return 0; } 第九题：我在网络上找到地这个程序，实际上我并不怎么动，尤其是在最后是个三角形的时候，怎样来删除边？ 想法： .(1) 首先，移走一条边。 (2) 然后进行下面的操作：选中一条边E，该边有两个相邻的顶点，不妨称为V1和V2。对V1和V2顶点所标的整数按照E上所标运算符号(+或是×)进行运算，得到一个整数；用该整数标注一个新顶点，该顶点代替V1和V2 。持续进行此操作，直到最后没有边存在，即只剩下一个顶点。该顶点的整数称为此次游戏的得分(Score)。算法： 设所给的多边形的顶点和边的顺时针序列为op[1],v[1],op[2],v[2],op[3],…,op[n],v[n] 其中，op[i]表示第i条边所对应的运算符，v[i]表示第i个顶点上的数值，i=1~n。 在所给的多边形中，从顶点i（1<=i<=n）开始，长度为j（链中有j个顶点）的顺时针链p(i,j）可表示为v[i],op[i+1],…,v[i+j-1]，如果这条链的最后一次合并运算在op[i+s]处发生（1<=s<=j-1），则可在op[i+s]处将链分割为两个子链p(i,s)和p(i+s,j-s)。 设m[i,j,0]是链p(i,j)合并的最小值，而m[i,j,1]是最大值。若最优合并在op[i+s]处将p(i,j)分为两个长度小于j的子链的最大值和最小值均已计算出。 即： a=m[i,s,0] b=m[i,s,1] c=m[i,s,0] d=m[i,s,1] (1)当op[i+s]=’+’时 m[i,j,0]=a+c ；m[i,j,1]=b+d (2) 当op[i+s]=’*’时 m[i,j,0]=min{ac,ad,bc,bd} ；m[i,j,1]=max{ac,ad,bc,bd} 由于最优断开位置s有1<=s<=j-1的j-1中情况。初始边界值为m[i,1,0]=v[i] 1<=i<=n m[i,1,1]=v[i] 1<=i<=n 因为多变形式封闭的，在上面的计算中，当i+s>n时，顶点i+s实际编号为(i+s)modn。按上述递推式计算出的m[i,n,1]记为游戏首次删除第i条边后得到的最大得分。 程序： #include using namespace std; #define NMAX 100 int N,m[NMAX+1][NMAX+1][2],v[NMAX+1]; char op[NMAX+1]; void MinMax(int n,int i,int s,int j,int &minf,int &maxf); int PloyMax(int n,int& p); int main() { int p; cout<<"请输入多边形顶点数："< cin>>N; for(int i=1; i<=N; i++) { cout<<"请输入多边形顶点"< cin>>v[i]; m[i][1][0]=v[i]; m[i][1][1]=v[i]; cout<<"请输入多边形边"< cin>>op[i]; } cout<<"多边形游戏首次删除第"< return 0; } void MinMax(int n,int i,int s,int j,int &minf,int &maxf) { int e[5]; int a=m[i][s][0],b=m[i][s][1]; int r=(i+s-1)%n+1;//多边形的实际顶点编号 int c=m[r][j-s][0],d=m[r][j-s][1]; if(op[r-1]=='+') { minf=a+c; maxf=b+d; } else { e[1]=a*c; e[2]=a*d; e[3]=b*c; e[4]=d*b; minf=e[1]; maxf=e[1]; for(int r=2;r { if(minf>e[r])minf=e[r]; if(maxf } } } int PloyMax(int n,int& p) { int minf,maxf; for(int j=2;j<=n;j++) //迭代链的长度 { for(int i=1;i<=n;i++)//迭代首次删掉第i条边 { for(int s=1 ;s { MinMax(n,i,s,j,minf,maxf); if(m[i][j][0]>minf) m[i][j][0]=minf; if(m[i][j][1] } } } int temp=m[1][n][1]; p=1; for(int i=2 ;i<=n; i++) { if(temp { temp=m[i][n][1]; p=i; } } return temp; } 第七章 第七章作业 第一题： 想法： 利用单位价值最大算法进行求解。首先，需要定义三个数组，一个存放物品的价值，另一个存放物品的重量，第三个存放物品的单位价值。然后，利用冒泡排序将单位价值数组进行排序，重量和价值数组也随着排序。然后进行装包，以背包的最大容量作为约束条件，一次装入单位价值递减的物品，知道装满为止。 算法： 输出：排序前后单位价值，排序后重量和价值，以及背包装入物品的最大价值。 1.BubbleSort( )函数进行冒泡排序 2.KnapSack( )函数进行装包 3.for(int i = 0; a[i] < C; i++ )循环 a)x[i] = 1;//将第i个物品放入背包 b)maxValue += b[i]; c) C = C - a[i]; //背包剩余容量 d)结束循环后，进行分割处理x[i] = (double)C/a[i];//这里很重要，是将最后装入的物 品进行了分割的! 4.输出最大价值 程序： //用一个冒泡排序对重量和价值进行相应的排序，然后选择三中方式中的一种进行计算即可#include void BubbleSort(int a[ ],int b[ ],double c[], int n);//装包前进行冒泡排序 const int n = 7;//背包中的物品个数 double KnapSack(int a[ ], int b[ ],double c[], int n, int C);//装包方式，w[]中存放物品重量,v[]中存放物品价值 int main() { int i,a[]={2,3,5,7,1,4,1},b[]={10,5,15,7,6,18,3}; double c[7]; cout<<"排序前单位价值："; for(i=0;i<7;i++) { c[i]=(double )b[i]/(double)a[i]; cout< } cout< BubbleSort(a,b,c,7); cout<<"排序后单位价值："; for(i=0;i<7;i++) cout< cout< cout<<"排序后重量："; for(i=0;i<7;i++) cout< cout< cout<<"排序后价值："; for(i=0;i<7;i++) cout< cout< int C = 15;//背包容量 double value = KnapSack(a, b, c,7, C); cout<<"背包获得的最大价值是："< return 0; } void BubbleSort(int a[ ],int b[ ],double c[], int n) { int bound, exchange = n - 1; //第一趟起泡排序的区间是[0, n-1] while (exchange != 0) //当上一趟排序有记录交换时(一共要排序) { bound = exchange; exchange = 0; for (int j = 0; j < bound; j++) //一趟起泡排序区间是[0, bound] if (c[j] < c[j + 1]) //将重量小的往前面排列 { double temp = c[j]; c[j] = c[j + 1]; c[j + 1] = temp;//这里是用c[]进行排列比较的，所以必须对c[]进行排序，不能将c[]丢弃，这样在后面的序列比较中一直要用到排序，a[],b[]也才可以排序 int temp1 = a[j]; a[j] = a[j + 1]; a[j + 1] = temp1;//交换记录 int temp2=b[j]; b[j] = b[j + 1]; b[j + 1] = temp2;//交换记录 exchange = j; //记载每一次记录交换的位置 } } } double KnapSack(int a[ ], int b[ ],double c[], int n, int C)//装包函数 { double x[10] = {0}; //数组初始化为0 (物品可部分装入) double maxValue = 0;//背包存放物品的最大价值 for (int i = 0; a[i] < C; i++)//循环直到存放物品重量大于背包容量(w[i] > C) { x[i] = 1;//将第i个物品放入背包 maxValue += b[i]; C = C - a[i]; //背包剩余容量 } //cout< //cout< x[i] = (double)C/a[i];//这里很重要，是将最后装入的物品进行了分割的! //cout< maxValue += x[i] * b[i]; //cout< return maxValue; //返回背包获得的价值 } 第五题： 想法： 对于删数程序，要使剩余数字组成的新整数最小，等价于尽量删除高位上较大的数字。于是，对于程序的编写，要考虑到三中情况，一是前后两个数的大小，前一个数大于后一个数的，直接删除前一个数；二是各个位置上的数是从小到大排列的，只要控制输出即可；三是删除了所有前大后小的数后，还需要删除数的情况，只要结合第二种情况控制输出位数即可。 算法： 输入：一个正整数和要删除的数字个数 输出：输出删除后的整数 1.while( k)循环，进行删数 2.进行if(i < n )判断，条件成立，就进行删除训算 3.条件不成立就进行循环，同时n--;控制整数最后的输出位数 4.输出删除后的数 程序： #include #include using namespace std; int main() { int i,k,n; char a[10001]; cout<<"请输入一个正整数："; cin>>a; n = strlen(a); cout<<"请输入要删除的数字个数："; cin>>k; if(k > n) { cout<<0< k = 0; } while(#include #include using namespace std; int main() { int i,k,n; char a[10001]; cout<<"请输入一个正整数："; 第一课初识算法与程序设计 一、教学目标 1、知识与技能 （1）理解算法的概念，培养学生自我探索信息，高效获取信息的能力； （2）能初步利用算法解决简单的问题，培养学生的理论联系实际能力和动手操作能力。 2、情感、态度、价值观 学生在学习过程中，通过亲身经历体验获得对此算法的感性认识，培养学生自我获取信息、分析评 价信息、、表达呈现信息的能力，进一步提高其信息素养。 二、教学重点难点 重点：算法概念的理解 难点：如何科学合理的选择和设计算法。 三、教学策略与手段 以趣味性问题设置情境，激发学生探索解决问题的兴趣，与学生进行互动探讨，通过Flash演示材 料，比较直观地把抽象的问题简单化，使学生的思考逐步深入，从而总结出 算法的概念，学会如何设计 和选择算法，培养学生自主探究学习的能力。 四、教学过程（1课时） （一）我们来共同寻找下面一些生活中比较现实的问题的解决方法。 【问题一】天下真的有“不要钱的午餐”吗？ 某一餐馆门口海报上写着“不要钱的午餐”，规则如下：在三个月内，来宾必须凑够五个人，五人 每次来就餐必须按照不同的顺序坐，直到把所有可能的顺序都坐一遍，以后来吃饭就可永远免费” 。于 是有人想，这太容易了，每人每次坐不同的位置，吃五次不就行了？于是他就叫上自己的朋友参加这项 活动，可是，吃了十次之后，还没有吃上免费午餐，这是怎么回事呢？ 学生们感觉非常有意思，很快以小组为单位进行热烈的讨论并得出了破解问题的步骤：①第一个座位５ 个人都有坐的机会②第二个座位只有４个人中的任一个有坐的机会（一个人不能同时坐两个座位）③第 三个座位只有３个人中的任一个有坐的机会④第四个座位只有２个人中的任一个有坐的机会⑤第五个座 位只有１个人有坐的机会⑥计算：５×４×３×２×１＝１２０⑦得出结论：需要吃１２０次才有可能 《ACM算法与数据结构设计》课程大作业报告 题目：五位以内的对称素数 学生姓名 班级学号 学生学院计算机软件学院 学生专业计算机科学与技术 联系电话 电子邮 指导教师 指导单位计算机学院软件工程系 日期2011.5.24 注意事项 （1）课程大作业从《ACM算法与数据结构设计》课程实验二（2011年4月19日）或实验三（2011年5月10日）中任选一个课题完成。（2）课程大作业内容包括课题名称、课题内容和要求、课题分析、概要设计、详细设计、测试数据及其结果分析、调试过程中的问题、参考资料列表、课程小结等。 （3）课程报告可以打印，也可以手写，但前面两页内容、大作业撰写纲要、课程小结不可遗漏和更换。 （4）课程小结给出ACM程序设计过程的收获、遇到的问题，遇到问题解决问题过程的思考、程序调试能力的思考等，需要手写签字。（5）课程大作业提交时间为2011年5月24日（第14周星期二）晚19:00~20:00，地点：计算中心A机房。 一、课题名称： 五位以内的对称素数 二、课题内容和要求： 题目：判断一个数是否为对称且不大于五位数的素数。 要求：判断输入的一组数据（正整数）是否是五位以内的对称素数，逐个判断并输出“yes”或“no” 三、课题分析： 定义两个函数分别判断数据是否为素数（bool isprime(int n)），是否是对称数（bool issym(int n)）；在main()函数中利用if()语句来判断该数据是否是五位以内的数。只有同时满足三个条件，才能判断一个数据是五位以内的对称素数，输出“yes”；否则输出“no”。 输入输出方案： 输入: 输入数据含有不多于50个的正整数(0 《现代设计方法》课程习题集 西南科技大学成人、网络教育学院 版权所有 习题 【说明】：本课程《现代设计方法》（编号为09021）共有单选题,计算题,简答题, 填空题等多种试题类型，其中，本习题集中有[ 填空题,单选题]等试题类型未进入。 一、计算题 1. 用黄金分割法求解以下问题（缩小区间三次）。 342)(m in 2+-=x x x f ，给定初始区间[][]3,0,=b a ，取1.0=ε。 2. 用黄金分割法求解以下问题（缩小区间三次） 32)(m in 2+=x x f ，给定[][],1,2a b =-，取1.0=ε 3. 用黄金分割法求解以下问题（缩小区间三次） 432+=x )x (f min ，给定[][]40,b ,a =，取10.=ε。 4. 用黄金分割法求解以下问题（缩小区间三次）。 12)(m in 3+-=x x x f ，给定初始区间[][]3,0,=b a ，取5.0=ε 5. 用黄金分割法求解以下问题（缩小区间三次）。 107)(m in 2+-=x x x f ，给定初始区间[][]3,0,=b a ，取1.0=ε 6. 用梯度法求解无约束优化问题： 168)(m in 22221+-+=x x x X f ，取初始点[]T X 1,1)0(= ，计算精度1.0=ε。 7. 用梯度法求解96)(m in 12221+-+=x x x X f ，[]T X 1,1)0(= ，1.0=ε。 8. 用梯度法求解44)(m in 22221+-+=x x x X f ，[]T X 1,1)0(=，1.0=ε 。 9. 用梯度法求解无约束优化问题：1364)(m in 222 121+-+-=x x x x X f ，取初始点 第二部分算法与程序设计(选修) 主题1算法与程序设计 1.1算法 1.1.1计算机解决问题的过程 知识点1：人是如何解决问题的 【知识链接】 本考点要求学生达到“了解”水平。 解决问题的过程可以总结为：观察、分析问题，收集必要的信息，尝试按照一定的方法和步骤解决问题。一般来说，同一个问题可以有多种解决方法，但不同的方法有优劣之分。评价一种方法的优劣要与具体情况相结合。 要理解本考点的内容除了用教科书中“韩信点兵”的例子外，还可以举出其他一些例子，例如：最小公倍数问题、班级活动的设计等。 【技能扫描】 培养将生活中的实例整理成条理化步骤的好习惯，提高自己的逻辑思维和语言叙述能力。 体会逻辑关联词“如果……那么……”、“或者”、“并且”、“否则”的含义，能把这些逻辑关联词翻译成数学“语言”。 【典型题析】 1. 分析“这个人谁都不认识”的含义，体会同一种叙述在不同语境中可以表达不同的意思。 分析：第一种解释是在场的所有人都不认识这个人(这个人是被认识的对象)；第二种解释是这个人不认识在场的所有人。 2．张三有一杯咖啡，李四有一杯牛奶，在不交换杯子的前提下如何交换两人的饮料。 分析：设张三的杯子为X，李四的杯子为Y，找一个空杯子T。将X杯中的咖啡倒入T杯中，将Y杯中的牛奶倒入X杯中，再将T杯中的咖啡倒入Y杯中即可。可以写成X→T，Y→X，T→Y。 【模拟练习】 1．把从早晨起床到学校的过程整理成算法(解决问题的方法和步骤)并表述出来。 2．一个侦探逮捕了5个嫌疑犯b因为这5个人供出的作案地点各有出入，进一步审讯后，他们分别提出了如下的申明。 A：5个人当中有1个人说了谎。 B：5个人当中有2个人说了谎。 课程名称：机电产品现代设计方法 上课时间：2014年春季 雷达底座转台设计 姓名： 学号： 班级：1108103 所在学院：机电工程学院 任课教师：金天国张旭堂 1．设计任务 雷达底座转台设计：一个回转自由度，如下图1.1所示。 图1.1 承载能力：500kg 被测件最大尺寸： 台面跳动：0.02mm 台面平面度：0.02mm 台面布置T型槽，便于安装负载 方位转角范围： 具有机械限位和锁紧机构 角度位置测量精度： 角度位置测量重复性： 角速范围： 2．设计流程 根据机电产品现代设计方法，其设计流程大致如下图2.1所示。 图2.1 根据上图所示，整个设计过程可分为四个阶段：功能设计、总体方案设计、详细设计和设计。 功能设计部分，是在结合所给出的重要性的要求及用户可能的功能目标需求的前提下，对转台的功能进行定义分析，将每一个功能细化为一个个的功能元，利用QFD图对实现各种功能的所对应的技术的相对重要性进行分析，相对重要性较高的功能技术便是设计的重点所在。 总体方案设计部分，通过利用SysML语言来明确各部分之间的功能参数和参数约束关系，并完成草图的设计。 详细设计部分，需要使得零件实现其预定的功能，并保证其精度和强度的设计要求。在详细设计阶段主要是利用cad等三维建模软件，完成系统的3D图，并生产对应的2D图，完成整个设计。对于重要的零部件需要利用有限元软件进行仿真分析，保证其可靠性。最后还需要应用动力学和运动学仿真软件进行相关的动力学和运动学分析，确定设计系统满足功能目标要求。 设计总结部分，是对整个设计过程进行反思和总结，考虑整个设计过程中存在的不足和所运用的相关知识。 3.QFD需求-功能-技术分析 QFD(全称Qualification Function Deployment)，是用来对所设计的系统进行总体设计规划的工具。QFD主要功能是能够实现工程设计与消费者或用户需求之间的紧密连接，根据消费者需求和用户目标实现对设计过程的实时修改和控制，把用户的功能目标在整个设计过程中得以体现，并根据需求的重要性对整个系统做出相应的设计规划，有重点的进行设计。 本设计根据用户对于雷达底座转台的功能重要性的需求，首先给出其需求和功能之间的联系，如下图3.1所示的质量屋，屋顶为系统的功能，包括驱动元件的转速、体积、重量，及传动元件和传感器的可靠性等，左侧围用户对于系统的功能目标的需求，由用户直接给出的功能，如角度位置测量精度：、角度位置测量重复性：、角速范围： 等和用户潜在的功能需求，如人机交互、成本、节能等方面的需求组成。 图 3.1中各功能需求后面的数字代表着这些功能的相对重要性，即importance of whats，其数字越大代表其重要性越高，用户对于这些需求的重要性之和应该等于100。质量屋屋顶代表各部分功能之间的相互联系，分为positive、negative和不明确三种情况。 2017级《程序设计与算法综合实践》 期末大作业题目及评分标准 有如下情况之一者，为不及格。 （1）未能完成所选题目评分标准的最低要求。 （2）抄袭他人成果。 （3）大作业检查时不带电脑，或电脑没有C语言开发环境。 （4）出勤次数、课堂表现等不符合学校相关教学文件规定等其他情况。 备选题目目录 1.图书购买系统...............................................................................................................- 2 - 2.物流信息管理系统 ....................................................................................................- 3 - 3.PM2.5实时信息管理系统 ............................................................ - 5 - 4.电影评论系统 ............................................................................... - 6 - 5.游戏角色属性分析........................................................................ - 8 - 6.KTV点歌系统 ................................................................................ - 9 - 7.英语词斩系统 ............................................................................. - 11 - 8.校运动会成绩管理系统.............................................................. - 14 - 9.通讯录管理系统 ......................................................................... - 15 - 10.机票购买系统 ............................................................................. - 16 - 11.车辆销售管理系统...................................................................... - 17 - 12.饮品自动贩卖机系统.................................................................. - 18 - 选修1：算法与程序设计 第一单元算法 一、知识内容 （一）使用计算机解决问题的一般过程 考试要求：对所列知识要知道其内容及含义，并能用自己的语言或动作进行表达、判断和直接运用。 1．一般过程 （1）分析问题确定要使用计算机来“做什么”，即确定解题的任务。 （2）寻求解决问题的途径和方法。 （3）用计算机进行处理。 2．确定解决问题的方法及步骤化 确定了解决问题的方法后，必须把解决问题的方法步骤化，即用某种方式告诉计算机每个需做什么。 计算机开始计算之前，需把解决问题的程序存储在内存中。通常一个程序包括指令和数据两部分。 （1）指令部分：指令是对计算机操作类型和操作数地址做出规定的一组符号。 （2）数据部分：计算所需的原始数据、计算的中间结果或最终结果。 3．设计程序时需要考虑的问题 （1）数据的存储：计算所需要的原始数据、计算产生的中间结果需要存储在不同的变量中。 （2）计算的过程：把解决问题的方法步骤化，并用计算机能执行的指令来有序地实现对应的步骤。 （3）典型的指令类型有输入指令、输出指令、算术运算指令、逻辑运算指令和控制转移指令。（二）算法及算法的表示方法 考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。 1．算法的特征 （1）有穷性。一个算法必须保证它的执行步骤是有限的，即它是能终止的。 （2）确定性。算法中的每个步骤必须有确切的含义，不应当有模棱两可的。 （3）能行性。算法中的每一个步骤都要足够简单，能实际能作的，而且在能在有限的时间内完成。 （4）有0个或多个输入。 （5）有一个或多个输出。 （三）用自然语言和流程图表示算法 考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。 1．自然语言 就像写文章时所列的提纲一样，可以有序地用简洁的自然语言加数学符号来描述算法。 2．流程图 用国家颁布的标准（GB1526-89，ISO5807-1985）中规定的图示及方法来画流程图，常用的构件有如图所示。 基于贪心算法求解TSP问题 一、TSP问题 TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。所有的TSP问题都可以用一个图（Graph）来描述： V={c1, c2, …, ci, …, cn}，i = 1,2, …, n，是所有城市的集合.ci表示第i个城市，n为城市的数目； E={(r, s): r,s∈V}是所有城市之间连接的集合； C = {crs: r,s∈V}是所有城市之间连接的成本度量（一般为城市之间的距离）； 如果crs = csr, 那么该TSP问题为对称的，否则为非对称的。 一个TSP问题可以表达为： 求解遍历图G = (V, E, C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。 二、贪心算法 贪心算法，又名贪婪算法，是一种常用的求解最优化问题的简单、迅速的算法。贪心算法总是做出在当前看来最好的选择，它所做的每一个在当前状态下某种意义上是最好的选择即贪心选择，并希望通过每次所作的贪心选择导致最终得到问题最优解。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。 1、贪心算法的基本思路 从问题的某一个初始解触发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。大致步骤如下： 1）建立数学模型来描述问题； 2）把求解的问题分成若干个子问题 3）对每一个子问题求解，得到子问题的局部最优解 4）把子问题的局部最优解合成原问题的一个解 2、贪心算法的实现框架 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，而贪心策略适用的前提是：局部最优策略能导致产生全局最优解。 从问题的某一初始解出发； while （能朝给定总目标前进一步） { 利用可行的决策，求出可行解的一个解元素； } 由所有解元素组合成问题的一个可行解； 3、贪心算法存在的问题 1）不能保证求得的最后解是最佳的； 算法与程序设计（教科版）教案 1-1节计算机解决问题的过程 一、教学目标 1、知识与技能 （1）让学生了解算法、穷举法、程序设计语言、编写程序和调试程序等概念。 （2）让学生知道对现实问题的自然语言的描述，特别是类似程序设计语言的自然语言描述。 （3）让学生理解分析问题、设计算法、编写程序、调试程序这一用计算机解决问题的基本步骤，认识其在算法与程序设计中的作用。 2、方法与过程 （1）培养学生发现旧知识的规律、方法和步骤，并把它运用到新知识中去的能力。 （2）培养学生调试程序的能力。 （3）培养学生合作、讨论、观摩、交流和自主学习的能力。 3、情感态度和价值观 通过“韩信点兵”这个富有生动情节的实例和探究、讲授、观摩、交流等环节，让学生体验用计算机解决问题的基本过程。 二、重点难点 本节的重点用计算解决问题的过程中的分析问题、设计算法、和上机调试程序等步骤。用计算机解决问题的过程中的分析问题、设计算法也是本节的难点。 三、教学环境 1、教材处理 教学内容选用中华人民共和国教育部制订的《普通高中技术课程标准》（2003年4月版）中信息技术部分的选修模块1“算法与程序设计”第一章的第一课“计算机解决问题的过程”。教材选用《广东省普通高中信息技术选修一：算法与程序设计》第三章第一节，建议“算法与程序设计”模块在高中一年级下学期或高中二年级开设。 根据2003年4月版《普通高中技术课程标准》的阐述，“算法与程序设计”是普通高中信息技术的选修模块之1，它的前导课程是信息技术的必修模块“信息技术基础”。学生在“信息技术基础”模块里已经学习了计算机的基本操作，掌握了启动程序、窗口操作和文字编辑等基础知识。学生可以利用上述的基础知识，用于本节课的启动Visual Basic程序设计环境，输入程序代码，运行程序等操作。本节课“计算机解决问题的过程”是“算法与程序设计”模块的第一节课，上好这节课是使学生能否学好“算法与程序设计”这一模块的关键。本节课的教学目的是让学生理解分析问题、设计算法、编写程序和调试程序等用计算机解决问题的基本过程，认识其在算法与程序设计中的地位和作用，它也是后续课程如模块化程序设计、各种算法设计等课程的基础。 让学生在人工解题中发现分析问题、设计算法等步骤，并把它应用到用计算机解决问题中去，这是构建主义中知识迁移的方法。本节课还采用了探究、讲授、观摩、交流、阅读材料等多种教学活动的有机结合的方法。 2、预备知识 本节课相联系的旧知识是计算机的基本操作中鼠标、键盘操作，启动、关闭程序，窗口、菜单操作和文字编辑等基础知识，还有解决数学问题的步骤等知识。 3、硬件要求 《软件系统分析与设计》 期末大作业 选题名称：游戏平台管理系统设计人：徐文豪刘青海 赖超宇甘智宏 班级：软工143班 南昌大学软件学院 2016.6.1 目录 一、整体描述 (2) 二、需求分析 (3) 三、系统功能概况 (4) 四、类的属性与方法 (5) 五、系统界面界限 (11) 六、设计模型 (13) 七、设计原则 (17) 八、设计模式······················ 一、整体描述 随着移动通讯的发展，手机应用也越来越多，其中，游戏应用占据了很大的比重，游戏平台管理系统是整合了大量游戏应用，以及玩家线上交流的平台。 主要受众群：拥有移动端或电脑端的人群。 应用前景：移动互联的发展为游戏平台的发展提供了很大的生存空间，应用前景十分广阔 盈利方式：向平台中游戏的开发商收取一定的费用，游戏玩家向游戏中注入资金时，收取一定比例的游戏收入。 面临的困难：游戏平台前期的推广，提高游戏平台本身对开发商和游戏玩家的吸引力，游戏平台能否适应大部分游戏玩家的要求。 玩家首先要注册账号，然后就可以在上面下载游戏应用，上传自己的游戏资源。同时，根据玩家的活跃程度获取相应积分，用积分可以兑换游戏礼包，也会根据玩家等级在游戏装备上给与相应的优惠和等级奖励。玩家在每一款游戏的评论区都可以交流游戏经验，提出意见和建议，以便游戏及时更新，弥补相应不足。玩家也可以建立游戏工会，不同游戏的玩家都可以加入，分享自己的游戏心得或者转赠游戏装备或积分。 二、需求分析 时间when：游戏厂商：随时；注册用户：随时；管理人员：正常工作时间。 地点Where：游戏厂商，管理人员：工作地点；注册用户：随地 人员who：游戏厂商，管理人员，注册用户， What：游戏厂商：推广游戏，管理人员：扩大服务，盈利；注册人员：玩游戏。 Why：游戏厂商：推广力度不大，效果不好，管理人员：方便管理，注册用户：良好的游戏环境。 性能Performance：系统提供服务的效率，响应时间快，由于是手机端的APP吞吐量不需要太大。 成本Cost：实现系统需要付出的代价，耗费****元 时间Time：2016年6月3日 可靠性Reliability: 需要系统长时间正确运行的能力 安全性Security: 由于该平台会涉及资金的流动，所以需要对信息安全的保护能力。 合规性Compliance: 需要符合各种行业的标准，法律法规，规范。技术性Technology:要求基于安卓平台开发。 兼容性Compatibility:需要与一些支付平台进行兼容能力。还有对游戏的兼容性。 算法分析大作业 动态规划方法解 乘法表问题和汽车加油行驶问题目录 1.动态规划解乘法表问题 1.1问题描述------ 1.2算法设计思想------ 1.3设计方法------ 1.4源代码------ 1.5最终结果------ 2.动态规划解汽车加油行驶问题 2.1问题描述------ 2.2算法设计思想------ 2.3设计方法------ 2.4源代码------ 2.5最终结果------ 3.总结 1.动态规划解决乘法表问题 1.1问题描述 定义于字母表∑{a,b,c)上的乘法表如表所示： 依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。 例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。 试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。 1.2算法设计思想 设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。 设字符串的第 i 到第 j 位乘积为 a 的加括号法有result[i][j][a] 种， 字符串的第 i 到第 j 位乘积为 b 的加括号法有result[i][j][b] 种, 字符串的第 i 到第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。 则原问题的解是：result[i][n][a] 。 设 k 为 i 到 j 中的某一个字符，则对于 k 从 i 到 j ：result[i][j][a] += result[i][k][a] * result[k + 1][j][c] + result[i][k][b] * result[k + 1][j][c] + result[i][k][c] * result[k + 1][j][a]; result[i][j][b] += result[i][k][a] * result[k + 1][j][a] + result[i][k][a] * result[k + 1][j][b] + result[i][k][b] * result[k + 1][j][b]; result[i][j][c] += result[i][k][b] * result[k + 1][j][a] + result[i][k][c] * result[k + 1][j][b] + result[i][k][c] * result[k + 1][j][c]; 算法与程序设计思想 【基本信息】 【课标要求】 （一）利用计算机解决问题的基本过程 （1）结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。 （2）经历用自然语言、流程图或伪代码等方法描述算法的过程。 （4）了解程序设计语言、编辑程序、编译程序、连接程序以及程序开发环境等基本知识。 【学情分析】 高一年级的学生已具备了一定的观察、思考、分析和解决问题能力，也已有了顺序结构、分支结构、循环结构等知识的储备。因此，对于如何将解决问题的思路画成流程图已有一定的基础，但可能还不很熟练，尤其对刚学过的循环结构，教师在课堂上要注意引导。 『此处说“已有了顺序结构、分支结构、循环结构等知识的储备”，应该是指在必修部分对“计算机解决实际问题的基本过程”已有所体验与了解，或是指已学习过数学中相关模块的知识，这是本案例教学得以实施的必不可少的前提条件。』 【教学目标】 1.知识与技能： 建立求一批数据中最大值的算法设计思想，并将算法的设计思想用流程图表示出来。 2.过程与方法： 利用现实生活中比较身高的活动，以及对武术比赛中“打擂台”流程的逐步梳理，让学生学会从此类生活实际中提炼出求最大值的思想方法，即算法思想。 培养学生分析问题、解决问题的能力，让学生学会在面对问题时能梳理出解决问题的清晰思路，进而设计出解决某个特定问题的有限步骤，从而理解计算机是如何解决、处理某种问题的。 『在过程上，通过现实生活中的实例来引导学生总结“求最大值”的算法思想。过程的实现关键在于实例引用是否贴切，是否有利于学生向抽象结论的构建。本案例的实例选择是符合这一要求的。在方法上，注重培养学生分析、解决问题的一般能力，再次体验与理解应用计算机解决问题的基本过程，为后面更一步的学习打下基础，积累信心。』 3.情感态度与价值观： 最新文件---------------- 仅供参考--------------------已改成-----------word 文本 --------------------- 方便更改 赠人玫瑰，手留余香。 《现代设计方法》课程习题集 西南科技大学成人、网络教育学院 版权所有 习题 【说明】：本课程《现代设计方法》（编号为09021）共有单选题,计算题,简答题, 填空题等多种试题类型，其中，本习题集中有[ 填空题,单选题]等试题类型未进入。 一、计算题 1. 用黄金分割法求解以下问题（缩小区间三次）。 342)(m in 2+-=x x x f ，给定初始区间[][]3,0,=b a ，取1.0=ε。 2. 用黄金分割法求解以下问题（缩小区间三次） 32)(m in 2+=x x f ，给定[][],1,2a b =-，取1.0=ε 3. 用黄金分割法求解以下问题（缩小区间三次） 432+=x )x (f min ，给定[][]40,b ,a =，取10.=ε。 4. 用黄金分割法求解以下问题（缩小区间三次）。 12)(m in 3+-=x x x f ，给定初始区间[][]3,0,=b a ，取5.0=ε 5. 用黄金分割法求解以下问题（缩小区间三次）。 107)(m in 2+-=x x x f ，给定初始区间[][]3,0,=b a ，取1.0=ε 6. 用梯度法求解无约束优化问题： 168)(m in 22221+-+=x x x X f ，取初始点[]T X 1,1)0(= ，计算精度1.0=ε。 7. 用梯度法求解96)(m in 12221+-+=x x x X f ，[]T X 1,1)0(= ，1.0=ε。 8. 用梯度法求解44)(m in 22221+-+=x x x X f ，[]T X 1,1)0(=，1.0=ε 。 9. 用梯度法求解无约束优化问题：1364)(m in 222 121+-+-=x x x x X f ，取初始点[]T X 1,1)0(=，计算精度1.0=ε。 10. 用梯度法求解1212221422)(m in x x x x x X f --+=,[]T X 1,1)0(=，1.0=ε 。（请迭代两次） 11. 有三个可靠度均为0.9的子系统组成的并联系统，试比较纯并联及2/3[G]表决系统的可靠度。 12. 一个由2个子系统组成的系统，其可靠度指标为0.85，试按等同分配法分配子系统的可靠度：（1）组成串联系统，（2）组成并联系统。 13. 已知某零件的应力和强度均呈正态分布，零件强度：MPa 516=δμ（均值），MPa S 2.24=δ（标准差），应力：MPa 378=σμ（均值），Mpa S 5.41=σ（标准差），试计算零件的可靠度与失效概率。 14. 由应力分析表明，某零件所承受的应力是拉应力，可用正态分布来描述，MPa T 3500=μ，标准差MPa S T 400=。该零件在制造过程中所引起的残余应力也可用正态分布来描述，其均值MPa C 1000=μ，标准差MPa S C 150=。由强度分析表明，该零件的强度也服从正态分布，其均值MPa 5000=δμ。现要求出当保证该零件的可靠度不低0.999时，零件强度的标准差的最低值应为多少? 江苏省高中信息技术算法与程序设计VB(选修) 《算法与程序设计VB （选修）》 知识要点 相关知识点 （一）算法 1.定义 相关题解： 1算法：就是解决问题的方法和步骤。算法是程序设计的“灵魂”，算法+数据结构＝程序。 单选题 1、下列关于算法说法不正确的是( A ) A 、算法独立于任何具体的语言，BASIC 算法只能用BASIC 语言来实现 B 、解决问题的过程就是实现算法的过程 C 、算法是程序设计的“灵魂” D 、其它三项都正确 2．算法的描述方法： 1算法的描述：可分多种表达方法，一般用自然语言、流程图和伪代码进行描述。 2自然语言描述法：指用人们日常生活中使用的语言（本国语言），用自然语言描述符合我们的习惯，且容易理解。 3流程图描述：也称程序框图，它是算法的一种图形化表示方法。且描述算法形象、直观，更易理解。 4伪代码描述法：是介于自然语言和计算机程序语言之间的一种算法描述。是专业软件开发人员常用方法。 1" ( A 处理或运算的功 ( A ). B D 3、以下哪个是算法的描述方法?( A ) A 流程图描述法 B 枚举法 C 顺序法 D 列表法 4、以下哪个是算法的描述方法?( D ) A 顺序法 B 列表法 C 集合法 D 自然语言描述法 （二）程序设计基础 （1）常用高级编程语言：BASIC 、VB 、Pascal 、C 、C++、Java 1面向对象的程序设计语言：其中的对象主要是系统设计好的对象，包括窗体等、控件等 2控件：是指工具箱中的工具在窗体中画出的、能实现一定功能的部件，如文本框，命令按钮等。 对象属性＝属性值 对象中属性可以在设计界面时通过属性窗中设置，也可以在运行时通过程序代码设置,方法如下 例：给文本框“Txt123”的“Text”属性赋值为字符串“20”，代码如下 Txt123.text =”20” 变量＝对象.属性 如果要获取对象的状态或特性，这时就要读取对象的属性值，方法如下 例：读取文本框“txt123”的“Text”属性的代码如下 a = txt123.text 2方法 ［对象］.方法［参数名表］ 例：form.print ”欢迎使用” 该语句使用print方法在form1窗体中显示字符串“欢迎使用” 3事件及事件驱动 事件是对象对外部操作的响应，如在程序执行时，单击命令按钮会产生一个Click事件。如需要命令按钮响应Click 事件，就把完成Click事件功能的代码写到Click事件的事件过程中，与事件一一对应。 事件过程的形式如下： Private Sub 对象_事件名( ) ……………（事件过程代码） End Sub 一个简单的VB程序 求圆的周长和面积 Private Sub Command1_Click() Dim r As Single '定义r为单精度型 Dim c As Single '定义c为单精度型 Dim s As Single '定义s为单精度型 r = Val(Text1.Text) '输入半径r c = 2 * 3.14159 * r '计算周长 s = 3.14159 * r * r '计算面积 Text2.Text = c '输出周长 Text3.Text = s '输出面积 End Sub Private Sub Command2_Click() End '退出 End Sub相关题解： 单选题 1、下列关于程序设计说法正确的是( B )。 A、程序设计语言的发展经历了机器语言、汇编语言到高级语言的过程，比 《计算机系统结构》大作业 对并行算法的介绍和展望 专业计算机科学与技术 班级 111 学号 111425020133 姓名完颜杨威 日期 2014年4月17日 河南科技大学国际教育学院 对并行算法的介绍和展望 我们知道，算法是求解问题的方法和步骤。而并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。并行算法的研究涉及到理论、设计、实现、应用等多个方面，要保持并行算法研究的持续性和完整性，需要建立一套完整的“理论－设计－实现－应用”的学科体系，也就是所谓的并行算法研究的生态环境。其中，并行算法理论是并行算法研究的理论基础，包含并行计算模型和并行计算复杂性等；并行算法的设计与分析是并行算法研究的核心内容；并行算法的实现是并行算法研究的应用基础，包含并行算法实现的硬件平台和软件支撑技术等；并行应用是并行算法研究的发展动力，除了包含传统的科学工程计算应用外，还有新兴的与社会相关的社会服务型计算应用等。 并行算法主要分为数值计算问题的并行算法和非数值计算问题的并行算法。而并行算法的研究主要分为并行计算理论、并行算法的设计与分析、和并行算法的实现三个层次。现在，并行算法之所以受到极大的重视，是为了提高计算速度、提高计算精度，以及满足实时计算需要等。然而，相对于串行计算，并行计算又可以划分成时间并行和空间并行。时间并行即流水线技术，空间并行使用多个处理器执行并发计算，当前研究的主要是空间的并行问题。并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。任何一个并行算法必须在一个科学的计算模型中进行设计。我们知道，任何算法必须有计算模型。任何并行计算模型必须要有为数不多、有明确定义的、可以定量计算的或者可以实际测量的参数，这些参数可以构成相应函数。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。 经过多年的发展，我国在并行算法的研究上也取得了显著进展，并行计算的应用已遍布天气预报、石油勘探、航空航天、核能利用、生物工程等领域，理论研究与应用普及均取得了很大发展。随着高性价比可扩展集群并行系统的逐步成熟和应用，大规模电力系统潮流并行计算和分布式仿真成为可能。目前，并行算法在地震数据处理中应用已较为成熟，近年来向更实用的基于PC机群的并行技术发展.然而，在非地震方法中，并行算法应用较少见文献报道，研究尚处于初级研究阶段。在大地电磁的二维和三维正、反演问题上，并行计算技术逐渐得到越来越多关注和重视.随着资源和能源需求的增长，地球物理勘探向深度和广度快速发展，大幅增长的数据量使得高性能并行计算机和高效的并行算法在勘探地球物理学中的发展和应用将占据愈来愈重要的地位。计算机技术在生物医学领域已经广泛应用，实践证明，并行算法在生物医学工程的各个领域中具有广泛的应用价值，能有效提高作业效率。随着电子科学技术的发展，电磁问题变得越来越复杂，为了在有限的计算机资源条件下求解大规模复杂电磁问题，许电磁学家已 题目作业调度问题及算法分析 学院名称：计算机与信息工程学院 专业名称：计算机科学与技术 目录 《算法设计与分析》课程大作业.................................................................... 错误!未定义书签。一．动态规划算法解决流水作业调度. (4) 1、问题描述 (4) 2、算法分析 (4) 3. 算法的描述 (5) 4、部分算法实现 (6) 5. 运行结果 (8) 6、时空效率分析 (8) 二．贪心算法解多机调度问题 (8) 1、问题描述 (8) 2、算法分析 (9) 3.部分算法实现 (9) 4.计算复杂性分析 (11) 5. 运行结果 (12) 三．回溯法解决批作业调度问题 (12) 1.问题描述 (12) 2.算法思想 (13) 3. 部分算法实现 (14) 4.运行结果 (15) 5.时间复杂性分析 (15) 四．作业调度算法比较 (16) 五．课程学习总结 (16) 摘要： 在现代企业中，作业调度已成为提高资源利用率、从而提高企业运行效益的关键环节之一。把各个作业分配到车间现有的设备上，并确定它们的先后次序，这是一项复杂的工作本文就作业调度排序问题进行了研究，通过对几个经典作业调度算法的分析讨论，总结了各个算法对作业调度的求解过程，并给出了每个算法的复杂度及性能分析。 关键词：作业调度；动态规划；贪心算法；回溯法； 一．动态规划算法解决流水作业调度 1、问题描述 给定n 个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i 在机器j 上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。 2、算法分析 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 在一般情况下，机器M1开始加工S 中作业时，机器M2还在加工其他作业，要等时间t 后才可利用。将这种情况下完成S 中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 由流水作业调度问题的最优子结构性质可知， )}},{({min )0,(1i i n i b i N T a N T -+=≤≤（1） 46．关于下面流程图功能的描述正确的是：( ) A．输入一个数，若其大于0则输出该数，若其小于0则输出该数的相反数 B．输入一个数，若其小于或等于0则输出该数的相反数 C．输入一个数，输出其绝对值 D．以上答案都正确 47．鸡、兔共笼问题，有腿共60条，问鸡、兔各有多少只？下面鸡和兔只数最合理的范围是( ) (范围确定了循环的起始值和终止值) A．鸡：1到28，兔：1到14 B．鸡：2到28，兔：1到14 C．鸡：1到28，兔：2到14 D．鸡：2到28，兔：2到14 48. 在程序中需要将两个变量的值交换，以下四段流程图中，( )不能完成将变量X、Y的值互相交换。A．B．C．D． 49. 使用计算机解题的步骤，以下描述正确的是：( )。 A．正确理解题意→设计正确算法→寻找解题方法→编写程序→调试运行 B．正确理解题意→寻找解题方法→设计正确算法→编写程序→调试运行 C．正确理解题意→寻找解题方法→设计正确算法→调试运行→编写程序 D．正确理解题意→寻找解题方法→设计正确算法→编写程序→调试运行 50. 算法的特征是：有穷性、( )、能行性、有0个或多个输入和有一个或多个输出。 A．稳定性B．确定性C．正常性D．快速性 51. 可以用多种不同的方法来描述一个算法，算法的描述可以用：( ) A．流程图、分支和循环B．顺序、流程图和自然语言 C．流程图、自然语言和伪代码D．顺序、分支和循环 52. 算法中通常需要三种不同的执行流程，即：( ) A．连续模式、分支模式和循环模式B．顺序模式、结构模式和循环模式 C．结构模式、分支模式和循环模式D．顺序模式、分支模式和循环模式 53. 流程图是一种描述算法的方法，其中最基本、最常用的成分有：( ) A．处理框、矩形框、连接框、流程线和开始、结束符 B．菱形框、判断框、连接框、流程线和开始、结束符 C．处理框、判断框、连接框、圆形框和开始、结束符 D．处理框、判断框、连接框、流程线和开始、结束符 54. 算法的描述可以用自然语言，下面说法中正确的是：( ) A．所谓自然语言描述算法就是用人类语言加上数学符号，来描述算法 B．用自然语言描述算法有时存在“二义性” C．自然语言用来描述分支、循环不是很方便 D．以上说法都错误 55.关于程序中的变量，下面说法中错误的是：( )。 A．一旦将数据存入某变量，读取变量中的值，不会改变变量的内容 B．一旦将数据存入某变量，以后就不能将新的数据存入该变量 C．一旦将数据存入某变量，以后可以将新的数据存入该变量 D．一旦将数据存入某变量，只要不把新的数据存入，变量的内容不会改变 56. 程序通常需要三种不同的控制结构，即：顺序结构、分支结构和循环结构，下面说法正确的是：( ) A．一个程序只能包含一种结构 B．一个程序最多可以包含两种结构 C．一个程序可以包含以上三种结构中的任意组合 D．一个程序必须包含以上三种结构 57. 采用盲目的搜索方法，在搜索结果的过程中，把各种可能的情况都考虑到，并对所得的结果逐一进行判断，过滤掉那些不合要求的，保留那些合乎要求的结果，这种方法叫做( ) A．递推法B．枚举法C．选择法D．解析法 VB程序填空题算法与程序设计》选修教案
《ACM算法与数据结构设计》大作业
现代设计方法-习题集(含答案)
算法与程序设计
机电产品现代设计方法大作业
《程序设计与算法综合实践》期末大作业题目及评分标准
选修一算法与程序设计
算法设计大作业—求解Tsps问题
算法与程序设计(教科版)教案
软件系统分析与设计大作业
算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题#精选.
算法与程序设计教案
现代设计方法_习题集(含答案)(优选.)
算法与程序设计
对并行算法的介绍和展望——学期大作业
算法设计与分析课程大作业
算法与程序设计复习整理