软件技术算法.pptx

《软件技术算法.pptx》由会员分享，可在线阅读，更多相关《软件技术算法.pptx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、0 复习与讨论复习与讨论1）什么是链表？）什么是链表？软件技术 链表是一种组织有序数据的数据结构链表是一种组织有序数据的数据结构 通过指针将一系列数据结点连接成一条数据链通过指针将一系列数据结点连接成一条数据链 结点中只有一个指向后继节点的指针为单链表结点中只有一个指向后继节点的指针为单链表第1页/共32页复习与讨论复习与讨论2）链表有什么特点？）链表有什么特点？软件技术 链表比数组具有更好的动态性链表比数组具有更好的动态性 插入、删除操作灵活方便（如文本编辑时）插入、删除操作灵活方便（如文本编辑时）链表中各节点在内存中可以不是连续存放的链表中各节点在内存中可以不是连续存放的（数组则一定是连续

2、存放的）（数组则一定是连续存放的）第2页/共32页复习与讨论复习与讨论3）怎样建立链表？）怎样建立链表？软件技术 使用指向结构体的指针，如：使用指向结构体的指针，如：struct stu*next；使用结构体作为链表的数据结点使用结构体作为链表的数据结点 动态开辟内存动态开辟内存 创建新结点创建新结点 连接链条连接链条第3页/共32页复习与讨论复习与讨论4）怎样输出链表？）怎样输出链表？软件技术 利用循环利用循环 利用指针利用指针 指向结点的数据成员指向结点的数据成员第4页/共32页复习与讨论复习与讨论5）怎样建立）怎样建立可调数组？可调数组？软件技术 定义指针定义指针 开辟内存开辟内存 利用

3、数组与指针之间的关系，得到可调利用数组与指针之间的关系，得到可调数组数组第5页/共32页1 算法的概念算法的概念1）程序的概念）程序的概念 议程：事先议定的步骤议程：事先议定的步骤 程序：特指计算机程序程序：特指计算机程序有计划、有步骤地有计划、有步骤地完成某些计算或操作完成某些计算或操作（运筹帷幄）（运筹帷幄）软件技术第6页/共32页算法的概念算法的概念2）算法的概念）算法的概念 软件技术领域：如插入、删除、更新、查找、排序等操作（主要是非数软件技术领域：如插入、删除、更新、查找、排序等操作（主要是非数值计算方法）值计算方法）机械工程领域：常用循环、迭代、数值积分、解方程等数值计算方法机械工

4、程领域：常用循环、迭代、数值积分、解方程等数值计算方法软件技术第7页/共32页算法的概念算法的概念3）算法的意义）算法的意义计算机的特点计算机的特点 计算机的运算速度很快计算机的运算速度很快 计算机不会自己解方程计算机不会自己解方程 十几年前美国孩子的评价：十几年前美国孩子的评价：一个孩子说计算机真聪明，能帮我做许多事情一个孩子说计算机真聪明，能帮我做许多事情另一个孩子说计算机真笨，离开了软件什么也不会做！另一个孩子说计算机真笨，离开了软件什么也不会做！软件技术第8页/共32页算法的概念算法的概念算法的重要性算法的重要性 软件是计算机的灵魂，而算法则是软件的核心软件是计算机的灵魂，而算法则是软

5、件的核心 界面固然很重要，但界面终究是外表，不是核心界面固然很重要，但界面终究是外表，不是核心 算法是编程的基础（程序也是算法）算法是编程的基础（程序也是算法）机械工程领域的算法问题相对简单机械工程领域的算法问题相对简单如：公式，循环，迭代，优化等如：公式，循环，迭代，优化等软件技术第9页/共32页算法的概念算法的概念算法的特性算法的特性有穷性有穷性（有穷步骤、有穷时间）、（有穷步骤、有穷时间）、确定性确定性（没有二义性，可重复）、（没有二义性，可重复）、可行性可行性（能（能实现）、实现）、输入输入（零个或多个）、（零个或多个）、输出输出（一个或多个）（一个或多个）算法设计的要求算法设计的要求

6、正确性、可读性、健壮性、效率与低存储量需求正确性、可读性、健壮性、效率与低存储量需求算法效率的度量：算法效率的度量：时间复杂度、空间复杂度时间复杂度、空间复杂度软件技术第10页/共32页算法的概念算法的概念注意保护运算精度注意保护运算精度 如采用列主元高斯消去法如采用列主元高斯消去法 或采用全主元高斯消去法或采用全主元高斯消去法 数值积分时的分点不要过细数值积分时的分点不要过细软件技术第11页/共32页2 循环算法循环算法1）一重循环）一重循环 求求1+2+100=?要点：累加器清零要点：累加器清零请高手现场编程！请高手现场编程！n!=12(n-1)n=?要点：累乘器置要点：累乘器置1，大的阶

7、乘整形数会溢出，大的阶乘整形数会溢出请高手现场编程！请高手现场编程！软件技术第12页/共32页循环算法循环算法一重循环求和示例一重循环求和示例软件技术第13页/共32页循环算法循环算法2）二重循环）二重循环 矩阵乘法矩阵乘法 输出一个矩阵输出一个矩阵 输出乘法口诀表（用输出乘法口诀表（用springtf和和MessageBox）软件技术第14页/共32页循环算法循环算法输出乘法口诀表（用输出乘法口诀表（用springtf和和MessageBox）软件技术void CMyDlg:OnOK()CDialog:OnOK();第15页/共32页循环算法循环算法3）三重循环）三重循环高斯消去法解线性方程

8、组：消去、回代高斯消去法解线性方程组：消去、回代 算例：算例：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软件技术第16页/共32页消去消去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)conti

9、nue;for(jj=kk+1;jj=N2;jj+)AAiijj=AAiijj-AAiikk*AAkkjj;AAiikk=0;return 0;软件技术第17页/共32页回代回代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;软件技术第18页/共32页调用调用CNumView:CNumView()/TODO:add construction code h

10、eredouble 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第19页/共32页输出输出软件技术第20页/共32页3 迭代算法迭代算法1）确定性方法）确定性方法 如解一元二次方程，解线性方程组的高斯消去法如解一元二次方程，解线性方程组的高斯消去法

11、 经过确定的，有限个步骤，能够得到解经过确定的，有限个步骤，能够得到解软件技术第第1 1步步第第2 2步步第第i i步步第第i+1i+1步步第第n n步步第21页/共32页迭代算法迭代算法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!+软件技术第22页/共32页迭代算法迭代算法3）赋值语句的特殊性）赋值语句的特殊性 赋值语句不是方程赋值语句不是

12、方程如如 i=i+1;赋值语句的迭代功能赋值语句的迭代功能有一个时间（或迭代次数）的概念，还是：有一个时间（或迭代次数）的概念，还是：i=i+1;左边的左边的 i 和右边的和右边的 i 不是一个不是一个 i，迭代次数不同，迭代次数不同软件技术ii+1第23页/共32页迭代算法迭代算法4）迭代算法的特点）迭代算法的特点 运算的次数不定，根据精度决定是否停止运算的次数不定，根据精度决定是否停止 结果是一个极限值结果是一个极限值 初始点或中间误差不影响最终结果的精度初始点或中间误差不影响最终结果的精度软件技术第24页/共32页迭代算法迭代算法5）如何构造迭代算法）如何构造迭代算法 找到规律找到规律

13、利用循环利用循环 必需收敛必需收敛软件技术第25页/共32页迭代算法迭代算法6）猜数游戏）猜数游戏 框图框图 软件软件软件技术是(Yes)是(Yes)否(No)否(No)是(Yes)否(No)输入猜数区间OnOk参数赋初值计算第一个分点大于分点？区间代换成右半段计算下一个分点区间代换成左半段计算下一个分点区间小于2？区间小于2？区间下限作为答案并输出总提问次数区间上限作为答案并输出总提问次数第26页/共32页迭代算法迭代算法7）二分法求根）二分法求根 方程方程y=x3-3x+1 框图框图 软件软件软件技术否(No)否(No)否(No)是(Yes)是(Yes)是(Yes)输入区间a，b最大迭代次

14、数M精度Ep，令k=0k=k+1xk=(ak+bk)/2(ak+bk)/2bk-akEpbk-akEp？输出结果xk结束f(ak)*f(xk)f(ak)*f(xk)MkM？输出迭代失败信息第27页/共32页迭代算法迭代算法8）迭代法解超越方程）迭代法解超越方程 方程方程I=(M/Km)Ki+I0 软件软件软件技术第28页/共32页迭代算法迭代算法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=-f

15、h;for(jj=1;jj=ii;jj+)jc=jc*jj;ww=ww*wx;m_EDIT2=m_EDIT2+fh*ww/jc;UpdateData(false);软件技术第29页/共32页迭代算法迭代算法泰勒级数泰勒级数sin(x)=x/1-x3/3!+x5/5!-x7/7!+void DHK:OnChangeEdit1()UpdateData(true);ii=-1;fh=-1;m_EDIT2=0;UpdateData(false);软件软件软件技术第30页/共32页4 作业作业1）什么是算法？）什么是算法？2）循环算法有什么特点？）循环算法有什么特点？3）迭代算法有什么特点？）迭代算法有什么特点？软件技术第31页/共32页感谢您的观看！第32页/共32页