C学习笔记(2)

C学习笔记(2)

C C学习笔记 算法


函数的递归调用

  • 必须定义第一项甚至第二项,作为递归的开始 有点像数学归纳法的原理
  • 定义有限次数的、有终止的递归调用

    一般形式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    #include <stdio.h>
    //定义递归函数
    int recursion(int n){//recursion:递归
    int c;
    if(n==1){
    c;//定义n=1时的返回值
    }else{
    c = recursion(n-1);//定义递归调用自己的方法
    }
    return c;
    }
    //main函数中调用
    void main(){
    int n;
    scanf("%d",&n);
    int re = recursion(n);//re的值即为该递归的返回值
    ...
    }
  • 例子:汉诺塔

汉诺塔是一个很典型的递归的例子。其问题是这样的:古代有一个梵塔,塔内有3个座A,B,C,开始时A座上有64个盘子,盘子大小不等,大的在下,小的在上(如图)。有一个老和尚想把这64个盘子从A座移到C座,但规定每次只允许移动一个盘子,且在移动的过程中3个座上都始终保持大盘在下,小盘在上。在移动过程中可以利用B座。

汉诺塔图片

问题解决:简化模型,A->C移动64个盘子可以简化问题为:

1.63个盘子:A->B
2.一个盘子:A->C
3.63个盘子:B->C

想实现以上过程,需要实现:

1.62个盘子:A->C
2.一个盘子:A->B
3.62个盘子:B->C
...
由此可以抽象化为:

1.n-1个盘子:起始柱->辅助柱
2.一个盘子:起始柱->目标柱
3.n-1个盘子:辅助柱->目标柱

注:
1.由于过程的复杂性,并不是每一步的起始柱和目标柱都是A和C,所以需要灵活定义。
2.定义函数 hanni(盘子总数,起始柱,辅助柱,目标柱),这三个柱子的顺序并没有固定,但是需要在自己的函数中一致
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
输入:盘子总数
输出:移动盘子的步骤
**/
#include<stdio.h>
int main(){
void hanni(int n,char,char,char);
int m; //盘子总数
printf("input the number of disks:");
scanf("%d",&m);
printf("the step to move %d disks:\n",m);
hanni(m, 'A', 'B', 'C'); //调用递归函数,传递总数m
}
void hanni(int n,char one,char two,char three){
void m_ove(char,char);
if(n==1){ //定义递归的开始
m_ove(one, three);
}else{ //定义递归的具体步骤
hanni(n-1, one, three, two);//将n-1个盘子从A移到B;
m_ove(one, three);//将A的盘子移到C;
hanni(n-1, two, one, three);//将B的n-1个盘子移到C;
}
}
void m_ove(char x,char y){
printf("%c --> %c\n",x,y);
}
输出结果:
input the number of disks:3
the step to move 3 disks:
A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C
Program ended with exit code: 0


C语言的变量和函数的储存方式

C语言的关键字staticextern

  • 变量

    C语言的变量分为局部变量全局变量

局部变量:用完即释放空间,需定义清楚数据类型以分配空间

  1. auto默认值,在动态储存区中分配储存空间,函数调用结束时就释放这些储存空间
  2. static:在静态储存区内分配储存单元,在程序整个调用期间都不释放。 可重复调用上次结果的值
  3. *register:储存于CPU寄存器,由于硬件的发展,现已淘汰

全局变量:分配静态储存空间,无需定义清楚数据类型,但是需要申明作用类型

  1. 直接定义,全局可用,在其他文件中使用时可用extern关键字申明
  2. static申明,将变量的作用域限制在本文件中,其他文件不可引用 由于该方法提高了安全性,推荐使用

  • 函数
    C语言的函数分为内部函数外部函数

内部函数:只能被本文件中的其他函数调用。在申明时加static关键字

例:static int fun(int a,int b);

外部函数默认值,可供其他文件调用.在申明时加extern关键字

例:extern int fun(int a,int b);

一般来说,在文件首定义static的变量和函数,提高工程的可靠性和通用性