第三讲  函数

一  函数声明与调用  

1  函数调用

主调（客户）函数与被调（服务器）函数 函数调用时的参数与返回值 例一： Swap( a, b ); 例二： n = Add( a, b );  

2  函数原型

函数的实现与调用格式说明：作为函数接口 一般出现在头文件中 格式： 函数返回值类型 函数名称( 形式参数列表 ); 例一： int Add( int x, int y ); 例二： void Swap( int x, int y ); 例三： void Compute();  

二  函数定义

1  函数实现

函数定义，使用编程语言给出函数的执行步骤

2  函数返回值

函数完成后带回来的结果 主调函数可以使用

3  谓词函数

返回 bool 类型值的函数 表达某项任务是否完成或某个条件是否满足

4  函数重载  

定义同名但参数不完全相同的函数

示 例:

 int Max( int x, int y );
 char Max( char x, char y );
 bool Max( bool x, bool y );

三  函数调用规  

1  参数传递机制

• 值传递

• 形式参数在函数调用时才分配存储空间，并接受实际参数的值

• 实际参数可以为复杂的表达式，在函数调用前获得计算

• 形式参数与实际参数可同名，也可不同名

• 参数较多时，实际参数值逐一赋值，它们必须保持数目、类型、 顺序的一致

• 值的复制过程是单向不可逆的，函数内部对形式参数值的修改 不会反映到实际参数中去

• 函数参数一般为函数输入集的一部分，函数输出集一般使用返 回值表示，只有使用特殊的手段才可以将函数参数作为函数输 出集的一部分  

• 引用传递

2  函数调用栈框架  

第四讲  算法

一  算法概念与特征

1  算法基本概念

• 算法定义：解决问题的方法与步骤

• 设计算法的目的：给出解决问题的逻辑描述，根据算法描述进行实际编程

2  算法特征

• 有穷性：算法在每种情况下都可以在有限步后终止

• 确定性：算法步骤的顺序和内容没有二义性

• 输入：算法有零个或多个输入

• 输出：算法至少具有一个输出

• 有效性：所有操作具有明确含义，并能在有限时间内完成  

二  算法描述

• 伪代码

• 流程图（程序框图）

三  算法设计与实现

1  算法设计与实现

• 构造算法解决问题

• 按照自顶向下、逐步求精的方式进行

• 使用程序设计语言编程实现  

四  递归算法

1  递归问题的引入

• 递推公式：数学上非常常见 例一：阶乘函数： 1! = 1， n! = n × (n-1)! 例二：斐波那契数列函数： f(1) = f(2) = 1， f(n) = f(n-1) + f(n-2)

• 递推函数一定是分段函数，具有初始表达式

• 递推函数的计算逻辑：逐步简化问题规模

2  递归的工作步骤

• 递推过程：逐步分解问题，使其更简单

• 回归过程：根据简单情形组装最后的答案  

3  循环与递归的比较  

• 循环使用显式的循环结构重复执行代码段，递归使用重复的函数调用执行代码段

• 循环在满足其终止条件时终止执行，而递归则在问题简化到最简单情形时终止执行

• 循环的重复是在当前迭代执行结束时进行，递归的重复则是在遇到对同名函数的调用时进行

五  容 错

1  定义

• 允许错误的发生

2  错误的处理

• 很少见的特殊情况或普通错误：忽略该错误不对程序运行结果产生影响

• 用户输入错误：通知用户错误性质，提醒用户更正输入

• 致命错误：通知用户错误的性质，停止执行

3  典型容错手段

• 数据有效性检查

• 程序流程的提前终止  

六  算法复杂度  

1  引入算法复杂度的目的

• 度量算法的效率与性能

2  大 O 表达式

• 算法效率与性能的近似表示（定性描述）

• 算法执行时间与问题规模的关系

3  表示原则

• 忽略所有对变化趋势影响较小的项，例如多项式忽略高阶项之外的所有项

• 忽略所有与问题规模无关的常数，例如多项式的系数  

4  标准算法复杂度类型  

• O(1)：常数级，表示算法执行时间与问题规模无关

• O(log(n))：对数级，表示算法执行时间与问题规模的对数成正比

• O(sqrt(n))：平方根级，表示算法执行时间与问题规模的平方根成正比

• O(n)：线性级，表示算法执行时间与问题规模成正比

• O(n*log(n))： nlog(n) 级，表示算法执行时间与问题规模的nlog(n) 成正比

• O(n2)：平方级，表示算法执行时间与问题规模的平方成正比

七  练习

 #include<iostream>
 #include<cmath>
 
 using namespace std;
 bool IsPrime( unsigned int n );
 
 int main()
 {
     int n,i;
     cout << "Please enter a number n(n > 1):";
     cin >> n;
     cout << n << " = ";
     for(i = 2;i <= n;i++)
     {
         while(n % i == 0)
         {
             if(IsPrime( i ))
             {
                 cout <<  i;
                 n /=i;
                 if(n != 1)
                 cout << "*";
             }
         }
     }
     cout << endl;
     return 0;
 }
 
 bool IsPrime( unsigned int n )
 {
     unsigned int i = 2, t = (unsigned int)sqrt(n) + 1;
     if(n == 2)
     return true;
     if( n % 2 == 0 )
     return false;
     while( i <= t )
     {
         if( n % i == 0 )
         return false;
         i += 2;
     }  
     return true;
 } #include<iostream>
 #include<cmath>
 
 using namespace std;
 
 int main()
 {
     int n,i;
     cout << "Please enter a number n(n > 1):";
     cin >> n;
     cout << n << " = ";
     for(i = 2;i <= n;i++)
     {
         while(n % i == 0)
         {
             
             cout <<  i;
             n /=i;
             if(n != 1)
             cout << "*";
         }
     }
     cout << endl;
     return 0;
 }
 //不用判断因数是否为素数也可以