函数

为什么要使用函数？

例题1：分别求出从1到10，从20到30以及35到45的整数和。

int sum = 0, i;
for(i  = 1; i<=10;i++)
    sum += i;
printf("Sum from 1 to 10 is %d", sum);

int sum = 0, i;
for(i  = 20; i <= 30;i++)
    sum += i;
printf("Sum from 20 to 30 is %d", sum);

int sum = 0, i;
for(i  = 35; i <= 45;i++)
    sum += i;
printf("Sum from 35 to 45 is %d", sum);

int sum(int i1, int i2){
    int sum = 0, i;
       for(i = i1; i <= i2; i++)
        sum += i;
    return sum;
}

void main(){
    
    printf("Sum from 1 to 10 is %d", sum(1, 10));
    printf("Sum from 20 to 30 is %d", sum(20, 30));
    printf("Sum from 35 to 45 is %d", sum(35, 45));

}

函数定义的一般形式

函数定义

函数的定义由函数名称、参数、返回值类型以及函数体组成。

定义的语法如下

返回值类型 函数名(参数列表){
    //函数体
}

函数是一组代码的集合，用来实现一个特定的功能

int max(int num1, int num2){
    
    int result;
    
    if (num1 > num2){
        result = num1;
    }else{
        result = num2;
    }
    return result;
}

int z = max(x, y);

没有函数体的函数，称为空函数。空函数的一般形式为：

类型标识符 函数名(){
    
}
//例如：
void dummy(){
    
}
//主调函数调用空函数时，只表明这里要调用一个函数，但函数本身什么工作也不做，等以居扩充函数功能时补充上。

例题2：max函数的实现

#include "stdio.h"

int max(int num1, int num2){
    int result;
    if (num1 > num2){
        result = num1;
    }else{
        result = num2;
    }
    return result;
}

int main(void){

    int i = 5;
    int j = 2;
    int k = max(i, j);

    printf("The maximum between %d and %d is %d\n", i, j, k);


    return 0;
}

函数的调用

函数的调用形式

函数调用语句把函数调用单独作为一个语句。如printt_star();这时不要求函数带回值，只要求函数完成一是的操作。
函数的表达式函数调用出现在另一个表达式中，如c-max(a，b)：这时要求函数带回一本确定的值以参加表达武的运算。
函数参数函数调用作为为一个函数调用时的实参。如m=max(a，max(b，e)；，又如：printf (‘%d”， max (a，b))；

形式参数与实际参数

在调用有参函数时，主调函数和被调用函数之间有数据传递关系。
在定义函数时函数名后面括号中的变量名称为“形式参数〞（简称“形参”）或中虚拟参数”。
在主调函数中调用一个函数时，國数名后面括号中的参数称为“实际参数”（简称“实参”）。实际参数可以是常量、变量或表达式，但要求它们有确定的值。
实参与形参的类型应相同或斌值兼容。赋值兼容是指实参与形参类型不同时能按不同类型数值的赋值规则进行转换。

例题3：对被调用的函数作声明1

#include "stdio.h"

int main(){
    float add(float x, float y);//对被调用函数add的声明

    float a, b, c;
    scanf("%f, %f", &a, &b);
    c = add(a, b);
    printf("sum is %f\n", c);

    return 0;
}

float add(float x, float y){//add函数体的实现
    float z;//函数体
    z = x + y;
    return (z);
}

例题3：对被调用的函数作声明2

#include "stdio.h"
float add(float x, float y){//add函数的实现
    float z;
    z = x + y;
    return (z);
}

int main(){
    float a, b, c;
    scanf("%f, %f", &a, &b);
    c = add(a, b);
    printf("sum is %f\n", c);

    return 0;
}

函数的嵌套调用

函数嵌套调用的含义

长套调用就是在定义一个西数时，其函数体方又包含另一个函数的完整定义。

利用函数进行模块化程序设计

模块化程序设计结构图

一个C 程序可由一个主函数和若干个其他函数构成。一个较犬的程序可分为若干个程序模块，每一个模块用来实现一个特定的功能。

局部变量和全局变量

局部变量

局部变量也称为内部变量
通常有两种局部变量在一个函数内部定义的局部变量，它只在本函数范围内有效在复合语句内定义的局部变量，它只在本复合语句范围内有效

全局变量

全局变量也称外部变量。是在函数之外定义的变量。
外部变量可以本文件中其他函数所共用。
它的有效范围从定义变量的位置开始到本源文件结東。

建议：尽量不要使用全局变量,原因如下：
1. 全局变量在程序的全部执行过程中都占用存储单元，而不是仅在需要时才开辟单元。
2. 使用全局变量过多,会降低程序的清晰性。在各个函数执行时都可能改变外部变量的值，程序容易出错。
3. 降低函数的通用性。因为函数在执行时要依赖于其所在的外部变量。如果将一个函数移到另一个文件中还要将有关的外部变量及其值一起移过去。但若该外部变量与其他文件的变量同名时，就会出现间题，降低了程序的可靠性和通用性。

例题6：全局变量与局部变量同名

#include "stdio.h"


int a = 3, b = 5;
int main(){
    int a = 8;

    printf("%d\n", max(a, b));


    return 0;
}

int max(int a, int b){
    int c;
    c = a>b?a:b;
    return (c);
}

当局部变量与全局变量同名，则在子程序内部，全局变量会被隐藏。 这段程序是不好的范例，应该尽量回避！！！

变量的存储类别

动态存储方式与静态存储方式

从变量值存在的时间角度来分，又可以分为静态存储方式和动态存储方式
1. 静态存储方式：指在程序运行期间由系统分配固定的存储空间方式
2. 动态存储方式:则是在程序运行期间根据需要进行动态的分配存储空间的方式。这个存储空间可以分为三部分：1.程序区2.静态存储区3.动态存储区

存储类型

变量定义的一般格式为：存储类型数据类型变量名我们平时定义的变量都省略了存储类型这一项
存储类型有以下几种：自动的（auto）静态的（static）寄存器的（register）外部的（extern）
根据变量的存储类别，可以知道变量的作用域和生存期

例7：输出1到5的阶乘值（考查静态变量的值）

#include "stdio.h"

int main(){
    int fac(int n);
    int i;
    for(i = 1;i<=5;i++){
        printf("%d != %d\n", i, fac(i));
    }


    return 0;
}

int fac(int n){
    static int f = 1;
    f = f * n;

    return (f);
}

递归函数

递归的定义

递归的定义若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。
在以下三种情况下，常常用到递归方法。定义是递归的数据结构是递归的问题的解法是递归的

递归的特点

递归的基本思想是“自己调用自己” 例：数学上最常见、最简单的递归问题就是自然数的阶乘
- n = 0 n ！= 1；
- n > 0 n! = n * (n-1);
适合用递归方法求解的问题有一个初始状态有后续情况可由前面的状态退出例：Fbonacci数列 F1 = F2 = 1 Fn = Fn-1 + Fn - 2(n >= 3)

例1：求解阶乘n1

#include "stdio.h"

unsigned fac(unsigned n){
    unsigned f;
    if (n == 0)
        f = 1; //递归的出口
    else
        f = n * fac(n-1); //递归的出口

    return f;
}

int main(){

    unsigned n;
    printf("输入要求的阶乘的数：");

    scanf("%d", &n);

    printf("%d的阶乘是%d\n", n, fac(n));



    return 0;
}

例2：计算斐波那契数列

 #include "stdio.h"

int f(int n){
    if (n == 1 || n == 2) return 1;
    else return f(n - 1)+ f(n - 2);

}
int main(){

    int n;
    printf("请输入Fibonacci数列的项数:");
    scanf("%d", &n);

    printf("Fibonacci数列的第%d项是%d\n", n, f(n));


    return 0;
}

递归过程与递归工作栈

递归过程在实现时，需要自己调用自己。
每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。
层层同下递归，退出时的次序正好相反：
因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。

递归概念小结

递归程序的特点编程精练，逻辑清楚，逼近数学递推公式。实现效率低。对函数的调用，都委进行参数替換、环境保护。
递归程序的要素递归语句递归次数递归出口

汉诺塔问题

问题描述：
1. 有三根杆子X，Y，Z。X杆上有n只碟子
2. 每次移动一块碟手，小的只能叠在大的上面
3. 把所有碟子从X杆经Y杆全部移到Z杆上，
递归求解:
1. 若只有一只碟子，直接將它从X杆移到Z杆；
2. 把n-1只碟子按大小递减的次序步X杆经Z杆移动到Y杆；将X杆上第n只碟子移到2杆；然后再将n-1只碟子按大小递减的次序从Y杆经X杆移到Z杆。

讨论这个程序中自相似的部分是什么？这个程序递归出口是什么？
递归体——程序中自相似的部分移动N-1只碟子和移动N只碟子的过程是相似的到那时这个过程不是完全一样的，因为盘子插入的竿子变了
递归的出口——递归终止的语句 N=1时只剩下一个碟子，直接移动到Z杆就好了
程序hanoi(N, X, Y, Z) 要将X杆上的N个盘子通过Y杆，放到Z杆上来。
这个问题可以划分为两个自相似的问题，和一次移动

将X杆上的N-1个盘子经过Z杆移动到Y杆 hanoi(N-1, X, Z, Y);

将第N个盘子从X杆移动到Z杆 move(X, Z)

将Y杆上的N-1个盘子经过X杆移动到Z杆

hanoi(N-1, Y, X, Z);
用函数描述移动
```
void hannio(int n, char X, char Y, char Z);
```
N个盘子，从X移动到Z，用Y作临时存放，可以用三次调用过程完成
```
hannoi(N-1, X, Z, Y);
move(X, Z);
hannoi(N-1, Y, X, Z);
```
递归的出口为N<=1

#include "stdio.h"

void hanoi(int n, char x, char y, char z);
void move(char c1, char c2);
int main(){

    int n;
    printf("Please input n:");

    scanf("%d", &n);
    hanoi(n, 'a', 'b', 'c');    


    return 0;
}

void hanoi(int n, char x, char y, char z){
    if (n == 1)
        move(x, z);
    else{
        hanoi(n - 1, x, z, y);
        move(x, z);
        hanoi(n - 1, y, x, z);
    }
}

void move(char c1, char c2){
    printf("%c -> %c\n", c1, c2);
}

递归程序总结

递归设计的实质：把一个复杂的问题可以分解成若干子问题来处理时其中某些子问题与原问题有相同的特征属性，则可以利用和原问题相同的分析处理方法。
在设计递归函数时，应注意：

首先应书写菌数的首部和规格说明，严格定义函数的功能和接口（递归调用的界面），对求精函数中所得的和原问题性质相同的子问题，只要接口一致便可进行递归调用；对函数中的每一个递归调用都看成只是一个简单的操作，只要接口一致，必能实现规格说明中定义的功能，切忌想得太深太远。

八皇后问题

程序结构

初始化（清楚棋盘）
循环八次：放置一个皇后；检查是否满足条件，如满足，登记皇后的位置如不满足，则退回，增加一步后再放皇后
直至放到最后一个皇后

自相似的关系提取

过程Generate；找到N个皇后适合的位置
这个问题可以划分成一个自相似的问题找到第N-1个皇后适合的位置找到第N个皇后适合的位置
递归终止条件找到了最后一个皇后的位置。

算法流程

Step 1
    数据初始化。
Step 2
    从col列开始接放第n个皇后（因为这样使可以符合每一竖列一个皇后的要求），挨个测试列是否可行，先测试当前位置(n，col)是否安全；
        如果是，摆放第n个皇后，并宣布占领(记得要横行竖列斜列一起来）
        如果没有测完所有的行
            -递归测试下一行 Generate(N+1)
            -n=7时，便打印出结果。
        如果当n＞=7时，发现此时已经无法摆放或摆放完毕时，便要进行回溯。
Step 3:
    输出结果

数据结构

place:int 数组[0..7];
    第n行皇后所占位置的列号
    主要用于输出结果
flag:bool 数组[0..7];
    表示col列上是否可以放皇后
d1:bool 数组[0..14]
    (n，col ）所在上对角线上是否可以放皇后
d2:bool 数组[0..14]
    ( n，col ） 所在下对角线上是否可以放皇后

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"
#include "string.h"

int place[8] = {0};
bool flag[8];
bool d1[15];
bool d2[15];
int number = 0;

void print();
void generate(int n);

int main(){

    memset(flag, 1, sizeof(flag));
    memset(d1, 1, sizeof(d1));
    memset(d2, 1, sizeof(d2));

    generate(0);
    
    // print();
    return 0;
}

void generate(int n){
    int col;
    for(col = 0;col<8;col++){
        if (flag[col] && d1[n - col + 7] &&d2[n+col]){
            place[n] = col;
            flag[col] = false;
            d1[n - col + 7] = false;
            d2[n + col] = false;
            if (n < 7)
                generate(n + 1);
            else
                print();
            
            flag[col] = true;
            d1[n - col + 7] = true;
            d2[n+col] = true;
        }
    }
}

void print(){
    int col, i, j;
    number++;
    printf("No.%d\n", number);
    int table[8][8] = {0};
    for(col = 0; col < 8;col++)
        table[col][place[col]] = 1;

    for(i = 0;i < 8;i++){
        for (j=0;j<8;j++){
            printf("%d ", table[j][i]);
        }
        printf("\n");
    }
}