软件技术05算法.pptx

机械工程软件技术基础机械工程软件技术基础第五讲第五讲 算法算法1太原科技大学太原科技大学陶元芳陶元芳 2010.8软件技术0 复习与讨论复习与讨论1）什么是链表？）什么是链表？软件技术 链表是一种组织有序数据的数链表是一种组织有序数据的数据结构据结构 通过指针将一系列数据结点连通过指针将一系列数据结点连接成一条数据链接成一条数据链 结点中只有一个指向后继节点结点中只有一个指向后继节点的指针为单链表的指针为单链表复习与讨论复习与讨论2）链表有什么特点？）链表有什么特点？软件技术 链表比数组具有更好的动链表比数组具有更好的动态性态性 插入、删除操作灵活方便插入、删除操作灵活方便（如文本编辑时）（如文本编辑时）链表中各节点在内存中可链表中各节点在内存中可以不是连续存放的以不是连续存放的（数组则一定是连续存放的）（数组则一定是连续存放的）复习与讨论复习与讨论3）怎样建立链表？）怎样建立链表？软件技术 使用指向结构体的指针，使用指向结构体的指针，如：如：struct stu*next；使用结构体作为链表的使用结构体作为链表的数据结点数据结点 动态开辟内存动态开辟内存 创建新结点创建新结点 连接链条连接链条复习与讨论复习与讨论4）怎样输出链表？）怎样输出链表？软件技术 利用循环利用循环 利用指针利用指针 指向结点的数据成员指向结点的数据成员复习与讨论复习与讨论5）怎样建立）怎样建立可调数组？可调数组？软件技术 定义指针定义指针 开辟内存开辟内存 利用数组与指针之间的利用数组与指针之间的关系，得到可调数组关系，得到可调数组1 算法的概念算法的概念1）程序的概念）程序的概念 议程：事先议定的步骤议程：事先议定的步骤 程序：特指计算机程序程序：特指计算机程序有计划、有步骤地有计划、有步骤地完成某些计算或操作完成某些计算或操作（运筹帷幄）（运筹帷幄）软件技术算法的概念算法的概念2）算法的概念）算法的概念 软件技术领域：如插入、删除、更新、查找、软件技术领域：如插入、删除、更新、查找、排序等操作（主要是非数值计算方法）排序等操作（主要是非数值计算方法）机械工程领域：常用循环、迭代、数值积分、机械工程领域：常用循环、迭代、数值积分、解方程等数值计算方法解方程等数值计算方法软件技术算法的概念算法的概念3）算法的意义）算法的意义计算机的特点计算机的特点 计算机的运算速度很快计算机的运算速度很快 计算机不会自己解方程计算机不会自己解方程 十几年前美国孩子的评价：十几年前美国孩子的评价：一个孩子说计算机真聪明，能帮我做许多一个孩子说计算机真聪明，能帮我做许多事情事情另一个孩子说计算机真笨，离开了软件什另一个孩子说计算机真笨，离开了软件什么也不会做！么也不会做！软件技术算法的概念算法的概念算法的重要性算法的重要性 软件是计算机的灵魂，而算法则是软件的核心软件是计算机的灵魂，而算法则是软件的核心 界面固然很重要，但界面终究是外表，不是核心界面固然很重要，但界面终究是外表，不是核心 算法是编程的基础（程序也是算法）算法是编程的基础（程序也是算法）机械工程领域的算法问题相对简单机械工程领域的算法问题相对简单如：公式，循环，迭代，优化等如：公式，循环，迭代，优化等软件技术算法的概念算法的概念算法的特性算法的特性有穷性有穷性（有穷步骤、有穷时间）、（有穷步骤、有穷时间）、确定性确定性（没有二（没有二义性，可重复）、义性，可重复）、可行性可行性（能实现）、（能实现）、输入输入（零个（零个或多个）、或多个）、输出输出（一个或多个）（一个或多个）算法设计的要求算法设计的要求正确性、可读性、健壮性、效率与低存储量需求正确性、可读性、健壮性、效率与低存储量需求算法效率的度量：算法效率的度量：时间复杂度、空间复杂度时间复杂度、空间复杂度软件技术算法的概念算法的概念注意保护运算精度注意保护运算精度 如采用列主元高斯消去法如采用列主元高斯消去法 或采用全主元高斯消去法或采用全主元高斯消去法 数值积分时的分点不要过细数值积分时的分点不要过细软件技术2 循环算法循环算法1）一重循环）一重循环 求求1+2+100=?要点：累加器清零要点：累加器清零请高手现场编程！请高手现场编程！n!=12(n-1)n=?要点：累乘器置要点：累乘器置1，大的阶乘整形数会溢出，大的阶乘整形数会溢出请高手现场编程！请高手现场编程！软件技术循环算法循环算法一重循环求和示例一重循环求和示例软件技术循环算法循环算法2）二重循环）二重循环 矩阵乘法矩阵乘法 输出一个矩阵输出一个矩阵 输出乘法口诀表（用输出乘法口诀表（用springtf和和MessageBox）软件技术循环算法循环算法输出乘法口诀表（用输出乘法口诀表（用springtf和和MessageBox）软件技术void CMyDlg:OnOK()CDialog:OnOK();循环算法循环算法3）三重循环）三重循环高斯消去法解线性方程组：消去、回代高斯消去法解线性方程组：消去、回代 算例：算例：1.1 x1+1.95 x2+2.38 x3=8.15,2.4 x1+4.9 x2+9.1 x3=15.4,3.8 x1-3.9 x2-4.5 x3=33.5软件技术消去消去int XQ(double AA5,int NN,int MM)int N2,ii,jj,kk;double CC;N2=NN+MM;for(kk=1;kk=NN;kk+)CC=1.0/AAkkkk;for(jj=kk;jj=N2;jj+)AAkkjj=AAkkjj*CC;for(ii=kk+1;ii=NN;ii+)if(kk=NN)continue;for(jj=kk+1;jj=N2;jj+)AAiijj=AAiijj-AAiikk*AAkkjj;AAiikk=0;return 0;软件技术回代回代int HD(double AA5,int NN,int MM)int N2,ii,jj,kk;N2=NN+MM;for(ii=NN+1;ii=1;kk-)for(jj=kk+1;jj=NN;jj+)AAkkii=AAkkii-AAkkjj*AAjjii;AAkkjj=0;return 0;软件技术调用调用CNumView:CNumView()/TODO:add construction code heredouble AA55=0,0,0,0,0,0,1.1,1.95,2.38,8.15,0,2.4,4.9,9.1,15.4,0,3.8,-3.9,-4.5,33.5;XQ(AA,3,1);OutArray(A=,AA,3,4);HD(AA,3,1);OutArray(A=,AA,3,4);还缺哪个函数？（输出）还缺哪个函数？（输出）软件技术主程序主程序子程序子程序2子程序子程序1子程序子程序3子程序子程序4输出输出软件技术3 迭代算法迭代算法1）确定性方法）确定性方法 如解一元二次方程，解线性方程组的高斯消去法如解一元二次方程，解线性方程组的高斯消去法 经过确定的，有限个步骤，能够得到解经过确定的，有限个步骤，能够得到解软件技术第第1 1步步第第2 2步步第第i i步步第第i+1i+1步步第第n n步步迭代算法迭代算法2）迭代算法）迭代算法 三等分角度问题三等分角度问题1/2-1/4+1/8-1/16+1/32-1/64+1/128-1/256+.函数值计算问题函数值计算问题计算器是怎样计算函数值的？用泰勒级数！计算器是怎样计算函数值的？用泰勒级数！如：如：sin(x)=x/1-x3/3!+x5/5!-x7/7!+软件技术迭代算法迭代算法3）赋值语句的特殊性）赋值语句的特殊性 赋值语句不是方程赋值语句不是方程如如 i=i+1;赋值语句的迭代功能赋值语句的迭代功能有一个时间（或迭代次数）的概念，还是：有一个时间（或迭代次数）的概念，还是：i=i+1;左边的左边的 i 和右边的和右边的 i 不是一个不是一个 i，迭代次数不同，迭代次数不同软件技术ii+1迭代算法迭代算法4）迭代算法的特点）迭代算法的特点 运算的次数不定，根据精度决定是否停止运算的次数不定，根据精度决定是否停止 结果是一个极限值结果是一个极限值 初始点或中间误差不影响最终结果的精度初始点或中间误差不影响最终结果的精度软件技术迭代算法迭代算法5）如何构造迭代算法）如何构造迭代算法 找到规律找到规律 利用循环利用循环 必需收敛必需收敛软件技术迭代算法迭代算法6）猜数游戏）猜数游戏 框图框图 软件软件软件技术是是(Yes)是是(Yes)否否(No)否否(No)是是(Yes)否否(No)输入猜数区间输入猜数区间OnOk参数赋初值参数赋初值计算第一个分点计算第一个分点大于分点？大于分点？区间代换成右半段区间代换成右半段计算下一个分点计算下一个分点区间代换成左半段区间代换成左半段计算下一个分点计算下一个分点区间小于区间小于2？区间小于区间小于2？区间下限作为答案区间下限作为答案并输出总提问次数并输出总提问次数区间上限作为答案区间上限作为答案并输出总提问次数并输出总提问次数迭代算法迭代算法7）二分法求根）二分法求根 方程方程y=x3-3x+1 框图框图 软件软件软件技术否否(No)否否(No)否否(No)是是(Yes)是是(Yes)是是(Yes)输入区间输入区间a，b最大迭代次数最大迭代次数M精度精度Ep，令，令k=0k=k+1xk=(ak+bk)/2(ak+bk)/2bk-akEpbk-akEp？输出结果输出结果xk结束结束f(ak)*f(xk)f(ak)*f(xk)MkM？输出输出迭代失败信息迭代失败信息迭代算法迭代算法8）迭代法解超越方程）迭代法解超越方程 方程方程I=(M/Km)Ki+I0 软件软件软件技术迭代算法迭代算法9）泰勒级数算例）泰勒级数算例sin(x)=x/1-x3/3!+x5/5!-x7/7!+void DHK:OnOK()UpdateData(true);wx=m_EDIT1*3.1415926/180.0;ii=ii+2;jc=1;ww=1;fh=-fh;for(jj=1;jj=ii;jj+)jc=jc*jj;ww=ww*wx;m_EDIT2=m_EDIT2+fh*ww/jc;UpdateData(false);软件技术迭代算法迭代算法泰勒级数泰勒级数sin(x)=x/1-x3/3!+x5/5!-x7/7!+void DHK:OnChangeEdit1()UpdateData(true);ii=-1;fh=-1;m_EDIT2=0;UpdateData(false);软件软件软件技术4 作业作业1）什么是算法？）什么是算法？2）循环算法有什么特点？）循环算法有什么特点？3）迭代算法有什么特点？）迭代算法有什么特点？软件技术