软考笔记（下午题）——算法设计与C语言实现-创新互联

4.算法设计与C语言实现

程序设计语言的基本成分
创新互联自2013年创立以来，是专业互联网技术服务公司，拥有项目网站设计、成都网站建设网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元岳西做网站,已为上家服务,为岳西各地企业和个人服务,联系电话:18982081108

数据成分：指一种程序设计语言的数据和数据类型。数据分为常量、变量、全局量、局部量。数据类型有整型、字符型、双精度、单精度浮点型、布尔型等。
运算成分：指明允许使用的运算符号及运算规则。包括算术运算、逻辑运算、关系运算、位运算等。
控制成分：指明语言允许表述的控制结构。包括顺序结构、选择结构、循环结构。
传输成分：指明语言允许的数据传输方式。如赋值处理、数据的输入输出等。
函数：C程序由一个或多个函数组成，每个函数都有一个名字，其中有且仅有一个名字为main的函数作为程序运行时的起点。函数是程序模块的主要成分，是一段具有独立功能的程序。函数使用涉及三个概念：函数定义、函数声明（先声明后使用）、函数调用。
传值调用：将实参的值传递给形参，形参的改变不会导致调用点所传的实参的值改变。实参可以是合法的变量、常量和表达式。
传址调用：即引用调用，将实参的地址传递给形参，即相当于实参存储单元的地址引用，因此其值改变的同时就改变了实参的值。实参不能为常量，只能是合法的变量和表达式。
因此，在编程时，要改变参数值，就传址，不改变，就传值。

算法分析

算法的复杂度
时间复杂度是一个大概的规模表示，一般以循环次数表示，O(n)说明执行时间是n的正比，另外，log对数的时间复杂度一般在查找二叉树的算法中出现。渐进符号O表示一个渐进变化程度，实际变化必须小于等于O括号内的渐进变化程度。

分治法

递归：指子程序（函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。
递归的两个基本要素：边界条件；递归模式。
分治法：对于一个规模为n的问题，若该问题可以容易的解决则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归的解决这些子问题，然后将各子问题的解合并得到原问题的解。
步骤：分解—求解—合并。
凡是涉及到分组解决的都是分治法（二分查找、归并排序等）

回溯法

动态规划法

在求解问题中，对于每一步决策，列出各种可能的局不解，再依据某种判定条件，舍弃哪些肯定不能得到最优解的局部解，在每一步都经历筛选，以每一步都是最优解来保证全局是最优解。
本质也是将复杂的问题划分成一个个子问题，与分治法不同的是每个子问题间不是相互独立的，并且不会都相同。
常用于求解具有某种最优性质的问题

贪心法

总是做出在当前来说是最好的选择，而并不从整体上加以考虑，他只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择，因此耗费时间少，一般可以快速得到满意的解，但得不到最优解。
局部贪心，只针对当前的步骤取最优，而非整体考虑。
判断此类算法，就看算法是否每一步都取最优，并且整体题意没有透漏出最终结果是最优的。

解题技巧

代码填空
算法、时间复杂度：涉及到分组就是分治法，局部最优就是贪心法，整体规划最优就是动态规划法，迷宫类的问题是回溯法；时间复杂度就是看C代码中的for循环层数和每一层的循环次数，涉及到二分必然有O(logn)。
特殊值计算

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网页标题：软考笔记（下午题）——算法设计与C语言实现-创新互联
链接分享：http://cdiso.cn/article/cdsspi.html