下载文档原格式
第2章算法——程序的灵魂2第章算法——程序的灵魂算法+数据结构=程序数据结构对数据的描述。
在程序中要指定用到哪些数据，以及这些数据的类型和数据的组织形式。
算法对操作的描述。
即要求计算机进行操作的步骤沃思数据结构程序设计方法语言工具算法程序员算法广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。
对同一个问题，可以有不同的解题方法和步骤。
为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。
数值运算的目的是求数值解。
由于数值运算往往有现成的模型，可以运用数值分析方法，因此对数值运算的算法的研究比较深入，算法比较成熟。
非数值运算算法算法计算机在非数值运算方面的应用远超在数值运算方面的应用。
非数值运算的种类繁多，要求各异，需要使用者参考已有的类似算法，重新设计解决特定问题的专门算法。
数值运算算法1.算法算法定义算法特征定义：现实生活中解决问题时，一般都要制订一个针对具体问题的步骤和方法，以此为据去实现目标。
将为了解决问题所制订的步骤、方法称为算法(Algorithm)。
算法描述：计算下面的分段函数。
（1）输入x的值；（2）判断x是否大于0，若大于0，则y为2x-1，然后转第5步；否则进行第3步；（3）判断x是否等于0，若等于0，则y为0，然后转第5步；否则进行第4步；（4）y 为3x+1；（5）输出y的值后结束。
C语言程序设计1.算法算法定义算法特征特征：（1）有穷性：算法中所包含的步骤必须是有限的，不能无穷无止，应该在一个人所能接受的合理时间段内产生结果；（2）确定性：算法中的每一步所要实现的目标必须是明确无误的，不能有二义性；（3）有效性：算法中的每一步如果被执行了，就必须被有效地执行。
例如，有一步是计算X除以Y的结果，如果Y为非0值，可有效执行，但如果Y为0值，则无法得到有效执行；（4）有零或多个输入：根据算法的不同，有的在实现过程中需要输入一些原始数据，而有些算法可能不需要输入原始数据；（5）有一个或多个输出：设计算法的最终目的是为了解决问题，为此，每个算法至少应有一个输出结果，来反应问题的最终结果。
第7章算法程序与计算系统之灵魂练习题答案解析导读：遍历算法和贪心算法求得的解是不一样的，贪心算法是求精确解，而遍历算法是求近似解，答案：C解释：，本题考查对贪心算法与遍历算法的简单理解，贪心算法：一定要做当前情况下的最好选择，该贪心算法的解为14，贪心算法与遍历算法的解不会总是完全相同，算法只会做当前情况下最优选择，遍历算法将会出现组合爆炸，贪心算法的计算速度更快，详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件，以致于计算(D)对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求精确解，执行更快一些，而遍历算法是求近似解，执行更慢一些；答案：C 解释：本题考查对贪心算法与遍历算法的简单理解贪心算法：一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”。
如果以A城市为起点，选择最近的下一点，为B城市。
以B城市为起点，选择最近的下一个城市，可以选择C或D，以选择D为例。
以D为起点，选择最近的下一点，为C城市。
最后回到A。
整个过程的花费为：14。
于是，该贪心算法的解为14。
而通过遍历可知，该问题的最优解为A-B-C-D-A，花费为13。
可见，贪心算法与遍历算法的解不会总是完全相同。
而贪心3算法只会做当前情况下最优选择，其时间复杂度为n级别。
而遍历则会将各种情况考虑在内，其时间复杂度为（n-1）！级别当城市的数量变多时，遍历算法将会出现组合爆炸。
故，相比之下，贪心算法的计算速度更快。
所以(C)选项是正确的。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)关于TSP，下列说法不正确的是_____。
(A)TSP问题的一个可能解就是n个城市的一个组合<t1, t2,="" …,="" tn="">，其中任何两个ti，tj都对应不同的城市。
若要求得最优解，则必须对所有的组合，即所有可能解进行比较。
