算法程序的灵魂.ppt

由三种基本结构派生出来的结构：ANp2YB根据表达式p的值进行选择ABp=p1p=p2…MNp=pmp=pn第31页，共45页，星期日，2025年，2月5日例2.11将例2.1的求5!算法用N-S图表示。直到i51?t输出t2?it*i?ti+1?ii51?t开始2?it*i?ti+1?i结束NY第32页，共45页，星期日，2025年，2月5日关于算法程序的灵魂第1页，共45页，星期日，2025年，2月5日2.1什么是算法2.2简单的算法举例2.3算法的特性2.4怎样表示一个算法2.5结构化程序设计方法第2页，共45页，星期日，2025年，2月5日著名计算机科学家沃思(NikiklausWirth)提出一个公式：数据结构+算法=程序描述数据结构的类型、组织形式描述对数据的操作步骤第3页，共45页，星期日，2025年，2月5日2.1什么是算法1.“算法”:为解决一个问题而采取的方法和步骤对同一个问题，可以有不同的解题方法和步骤为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法2.计算机算法可分为两大类别：数值运算算法(目的是求数值解)非数值运算算法(事务管理领域)第4页，共45页，星期日，2025年，2月5日2.2简单的算法举例例2.1求1×2×3×4×5可以用最原始的方法进行：步骤1：先求1*2，得到结果2。步骤2：将步骤1得到的乘积2再乘以3，得到结果6。步骤3：将6再乘以4，得24。步骤4：将24再乘以5，得120。这就是最后的结果。例2.1求1×2×3×4×5×…×1000太繁琐第5页，共45页，星期日，2025年，2月5日S1：使p=1，或写成1?pS2：使i=2，或写成2?iS3：使p与i相乘，乘积仍放在变量p中，可表示为：p*i?pS4：使i的值加1，即i+1?iS5：如果i不大于5，返回重新执行S3；否则，算法结束最后得到p的值就是5!的值若是1000，求什么？若求1×3×5×7×9×1133221111!相当于i≦11例2.1求1×2×3×4×5改进的算法：设变量p为被乘数变量i为乘数用循环算法求结果第6页，共45页，星期日，2025年，2月5日例2.2有50个学生，要求将成绩在80分以上的学生的学号和成绩输出。用ni代表第i个学生学号，gi表示第i个学生成绩S1：1?iS2：如果gi≥80，则输出ni和gi，否则不输出S3：i+1?iS4：如果i≤50，返回到步骤S2，继续执行，否则，算法结束第7页，共45页，星期日，2025年，2月5日例2.3判定2000—2500年中的每一年是否闰年，并将结果输出。闰年的条件：(1)能被4整除，但不能被100整除的年份都是闰年，如2008、2012、2048年(2)能被400整除的年份是闰年，如2000年不符合这两个条件的年份不是闰年(例如2009、2100年)设year为被检测的年份。算法表示如下：S1：2000?yearS2：若year不能被4整除，则输出year的值和“不是闰年”。然后转到S6S3：若year能被4整除，不能被100整除，则输出year的值和“是闰年”。然后转到S6S4：若year能被400整除，则输出year的值和“是闰年”，然后转到S6S5:其他情况输出year的值和“不是闰年”S6：year+1?yearS7：当year≤2500时，转S2，否则停止第8页，共45页，星期日，2025年，2月5日year不能被4整除非闰年year被4整除，但不能被100整除闰年year被100整除，又能被400整除闰年其他非闰年逐渐缩小判断的范围第9页，共45页，星期日，2025年，2月5日例2.4求规律：①第1项的分子分母都是1②第2项的分母是2，以后每一项的分母子都是前一项的分母加1③笫2项前的运算符为“-”，后一项前面的运算符都与前一项前的运算符相反第10页，共45页，星期日，2025年，2月5日例2.4求S1：sign=1S2：sum=1S3：deno=2S4：sign=(-1)*signS5：term=sign*(1/deno)S6：sum=sum+termS7：deno=deno+1S8：若deno≤100返回S4；否则算法结束sign—当前项符号term—当前项的值