一、函数介绍
1.1 函数是什么
在计算机科学中 子程序(函数 function) 是一个大型程序中的某部分代码 由一个或多个语句块组成
它负责完成某项特定任务 而且相较于其他代码 具备相对的独立性
一般会有输入参数并有返回值 并封装了函数的过程 隐藏了实现细节
这些代码通常被集成为软件库(库函数)
1.2 C语言中函数的分类
- 分为库函数 和 自定义函数
库函数的好处
常见的库函数
1.3 函数原型
- 函数名 参数 返回值
1.4 高内聚 低耦合
- 让函数的功能 尽量独立 解耦
- 各模块之间尽量相互独立
1.5 C语言main函数的位置
- 第一章说了
main函数必须要有 有且仅有1个 - 对于位置是没有要求的
二、函数的参数
2.1 实参和形参
- 不管什么形式的形参 函数调用时
都要有确定的值函数调用过程中才会给形参分配内存空间不调用函数的时候 他们就是一段代码- 形参是
在函数调用的时候才会实例化才开辟内存空间出函数的时候 形参就自动销毁了形参只在函数中有效 和局部变量类似 所以他们都在栈区- 形参
实例化之后相当于是实参的一份临时拷贝
实际参数(实参)
形式参数(形参)
2.2 函数的参数(实参)可以是表达式
函数的参数可以是表达式 也就是()括起来的 所以下面只有四个参数
前面两个是逗号表达式 表达式的值才作为参数
2.3 传值与传址(swap函数)
- 其实我可以说:
都是传值 都是临时拷贝 只不过一种值是数值 一种值是地址
值传递:
a b是实际参数 x y是形式参数
形参会申请自己的内存空间实参ab和形参xy使用的不是同一空间
本代码仅仅交换了形参x y
址传递:
其实形参仍然是实参的临时拷贝pa就是&a的一份临时拷贝 只不过pa和&a 都指向同一块内存空间 所以会影响到a的值
2.4 明确形参是实参的临时拷贝
2.3的图解 x y的确是形参的临时拷贝
下图 传参传的是&a 也就是a的地址
形参pa 照样是实参的一份临时拷贝如下图 pa里放的是一个地址
只不过因为pa是地址 所以通过pa 可以找到a
但是再怎么折腾形参pa 也不会影响到实参&a
解引用*pa其实是远程影响到了a
再来看这个案例 我图片上说的有些复杂了 别看
其实本质就在于:形参一直都是实参的临时拷贝 这里是把a和b的地址临时拷贝给pa和pb了
然后我只是交换了形参pa和形参pb的值所以*pa找到b *pb找到a函数里看上去是交换了 倒不如说我先打印的b 再打印的a
只要能理解"临时拷贝" 这里就很好理解 总感觉语言难以描述 但是想很容易想清楚
2.5 void(如果不写函数返回值 默认是int)
- 写了void 就表示
不需要参数 不要传参;没有返回值 不需要返回!! - 不要去钻没有意义的牛角尖!!
- 作为写函数的人 如果你希望函数没有返回值或者不需要传参 就写上void
- 作为函数调用者 你看到了void 就遵守这个规则 不要钻牛角尖!!
- 函数的返回类型不写的话 默认是int类型 如果不需要返回值请写上void
下面我钻一下牛角尖:
下面的研究没啥意义 但凡规范一点 啥事没有 函数切忌写的模棱两可
如果函数没有规定形参的类型
不管传递什么 反正都不要可以执行下去
如果函数规定形参是void 但还是传了个参数 不会报错 但是会报警告 无论如何 就算不报错 既然写了void 就不要传参给void
不规定函数的返回类型 不代表不返回任何东西
而默认返回int
当你不需要返回任何东西的时候请明确定义为void test() 规范!!!
2.6 有返回值的函数一定要都return
- 下面这个代码 假如我输入1 会打印yes 显然错误
- 错误的原因就在于 如果是闰年 返回1
如果不是闰年呢? 没写返回值!(未定义行为!不一定会返回什么)
int is_leap_year(int year)
{
if ((year % 400 == 0) || ((year % 4 == 0) && (year % 100 != 0)))
return 1;
}
int main()
{
int i = 0;
scanf("%d", &i);
int test = is_leap_year(i);
if (is_leap_year(i) == 1)
printf("yes\n");
else
printf("no\n");
return 0;
}
所以也要学会看警告
具体错误可能在于 编译器借用了是闰年的return 1 因为我没有定义不是闰年返回什么 所以他也给我返回1
反正编译器报警告了 也要学会看警告
2.7 一道关于不写返回值的例题
下面这个代码
不写返回值 默认返回的int但是代码里并没有return(未定义行为)
这时候返回的值取决于编译器的实现 大多数时候返回的是该函数执行完最后一条指令产生的结果
最终test()返回的其实就是printf的返回值—>也就是打印的字符的个数(这是VS2022的测试结果)
2.8 在函数中 尽量少使用全局变量
- 假如前面的2.3 把a b定义成全局变量 确实怎么都可以交换a b
- 但是 全局变量本身很危险 谁都可以用 跨文件只要声明了 也能用 很危险
- 其次 我们说函数有一个特点就是"模块化" 他仿佛是一个独立的模板 实现某个特点的功能 如果函数依赖全局变量 仿佛就失去了"独立性" 而依赖全局变量了
2.9 当参数是数组名的时候 不能在函数内部计算元素个数
如果在函数内部用sizeof(arr)/sizeof(char) 结果恒为4/8
因为不论传参的形式是下面哪一种 本质是就是一个指针
既然在函数里 ch一定是一个指针 那么sizeof(指针) 就一定是4或者8
在指针那一章节已经详细论述过
三、函数的调用与练习
3.1 传值调用和传址调用
传值调用
传址调用
说明:
下面的练习的主要思路在考研C语言程序设计_编程题相关(持续更新)一文写过 本文主要是练习函数的写法
3.2 判断一个数是不是素数
- 一开始忘记#include<math.h>了 一直不打印 找了半天的错…
- return比break更彻底
#include<math.h>
#include<stdio.h>
#include<string.h>
int isPrime(int num)
{
//num是素数就返回1 否则返回0
int j = 0;
for (j = 2; j <= sqrt(num); j++)
{
if (num % j == 0)
return 0;
}
//因为这是return 所以能return1 肯定没有return0过
return 1;
}
int main()
{
int i = 0;
for (i = 100; i <= 200; i++)
{
if (isPrime(i))
printf("%d ", i);
}
return 0;
}
3.3 判断一年是不是闰年
int isLeapYear(int year)
{
return (year % 400 == 0) || ((year % 4 == 0) && (year % 100 != 0));
}
int main()
{
int i = 0;
for (i = 1000; i <= 2000; i++)
{
if (isLeapYear(i))
printf("%d ", i);
}
return 0;
}
3.4 实现一个整形有序数组的二分查找
这里犯了如下错误:
- mid = (left + right) / 2; 没有写在循环里!! 所以说
以后写while 别一上来就while 先把逻辑写好 再cv到while里!!!return下标mid 不是return kk要你return了干嘛的?不能在函数里用sizeof(arr)/sizeof(int)求len经典的错误这个结果永远都是1或者2(取决于几位机器)在函数里sizeof(arr)求的是一个指针变量的大小
- 我的思路是 找到了返回下标
找不到就返回0 这个设计就是错的 假如我要找的下标正好是0呢?
更正:既然找到了是返回下标 下标肯定是≥0 那找不到就返回-1- 还有
前提一定是有序数组啊 我一开始又给了无序的测试数组....- 数组传参也可以写成int arr[ ]
但是本质还是int* arr 而且arr[1]本质上是*(arr+1)
//把找到的下标返回 找不到就返回-1
//也可以写成int arr[] 但是本质上是int* arr
int BinarySearch(int* arr, int k, int len)
{
int left = 0;
int right = len - 1;
int mid = 0;
//能不能= 想不通 举个例子不就想通了
//都指向同一个元素的时候 肯定还要再求一个mid去判断一下的 肯定要写=
while (left <= right)
{
mid = (left + right) / 2;
if (arr[mid] < k)
left = mid + 1;
else if (arr[mid] > k)
right = mid - 1;
else
return mid;//返回的是下标 不是k
}
return -1;
}
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int len = sizeof(arr) / sizeof(arr[0]);
int k = 10;
int index = BinarySearch(arr, k, len);
if (index != -1)
printf("找到了 下标是:%d\n", index);
else
printf("查无此人\n");
return 0;
}
3.5 写一个函数 每调用一次这个函数 就会将num的值增加1
本解法主要就是要知道传址调用的意义 此外还要注意一下优先级的问题
- *pnum = *pnum + 1; ok
- *(pnum)++; ok
*pnum++;no no no- *pnum++ 等价于 *(pnum++) 因为++的优先级高 先应用于pnum 而且是后置++ 这么写相当于每次进去函数就解引用pnum 拿到num 然后啥也不干 再对pnum自增 让他成为野指针
- 关于优先级的问题 在第5章操作符会详细讨论
void func(int * pnum)
{
//*pnum++ err
(*pnum)++;
}
int main()
{
int num = 10;
func(&num);
printf("%d\n", num);
func(&num);
printf("%d\n", num);
func(&num);
printf("%d\n", num);
return 0;
}
还有一种思路 可以不用指针
四、函数的嵌套调用和链式访问
4.1 函数可以嵌套调用 但不能嵌套定义
- 下面就是嵌套调用
#include <stdio.h>
void new_line()
{
printf("hehe\n");
}
void three_line()
{
int i = 0;
for(i=0; i<3; i++)
{
new_line();
}
}
int main()
{
three_line();
return 0;
}
函数可以嵌套调用 但是不能嵌套定义
main函数也是个函数
4.2 链式访问
- 链式访问:把一个函数的返回值作为另外一个函数的参数
- 这就是一种链式访问 把strlen的返回值 作为printf的参数
- 这里要注意 先执行里面一层的函数(strlen) 再执行外面的
4.3 printf()函数的返回值
printf的返回值是
打印的字符的个数比如用%d打印34 34有俩字符 3和4 返回值就是2
4.2说到了 先执行里面一层的函数 再执行外面的
所以打印顺序是:图上面写错了写错了 是打印4321
五、函数的声明和定义
5.1 函数声明和定义
- 声明可以告诉编译器
有一个函数叫什么 参数是什么 返回类型是什么但是具体是不是真的存在这个函数 函数声明决定不了 - 函数的声明一般出现在函数的使用之前 要满足
先声明后使用 - 函数的声明一般要放在
头文件中 - 函数的定义是指函数的具体实现 交待函数的功能实现
5.2 保证先声明(定义)后使用
编译的时候 是从前往后扫描代码的
先用后定义 会报一个警告
声明一下 就不会报警告了
满足先声明后使用函数声明里的x y 可以省略
其实
函数的定义也算是一种特殊的声明既然说要先声明后使用 那建议定义的时候直接定义在使用之前
变量的声明和定义 在第一章已经提到了 也是类似的规则
虽然规则允许 但是为什么要这样写代码??? 这不是**吗 直接定义在前面不就行了
5.3 实际场景下的函数的声明和定义
● add.h:函数的声明
● add.c:函数的实现(定义)
● test.c:测试
5.4 模块化编程的优势
- 每个程序员分别去写自己的模块
模块之间相互独立需要用到的时候调用一下即可 - 其实 之前已经提到过
我在test.c里extern int Add(int x,int y); 就可以跨文件使用add.c里的Add()了为什么非要写一个add.h 然后include<“add.h”>呢?->这样写可以做到代码的隐藏
假设我希望把我写的程序卖给别人用 但是不希望别人知道我的源码
以add这个功能为例 我就可以写add.h+add.c 两个文件 然后编译生成一个静态库add.lib
这个文件就是.h和.c编译所生成的 是无法通过.lib看到源码的
然后就把add.lib和add.h卖给别人 别人只知道函数长什么样 怎么用 但是不知道函数的具体实现
买家导入静态库 就可以使用这个函数的功能了 但是不知道源代码
六、 函数递归与经典习题
补充:int的取值范围
- 这个知识点会在
后续第九章:数据的存储详细介绍 - 这里就暂时记住如果
是有符号int最大是21亿多 如果是无符号int最大是42亿多 - 下面的题目暂时不考虑计算结果超过了42亿这种情况 而是学习递归的思想
6.1 什么是递归
程序或函数直接或间接调用自身的编程技巧称为递归(recursion)- 递归通常把一个大型复杂的问题
层层转化为一个与原问题相似的规模较小的问题来求解 - 递归策略只需
少量的程序就可描述出解题过程所需要的多次重复计算 大大地减少了程序的代码量 - 递归的主要思考方式在于:大事化小 找到子问题+递归函数的出口
这就是一个递归 但是
是死递归
6.2 递归的两个必要条件
- 存在限制条件 当满足这个限制条件的时候 递归便不再继续
即递归要有出口 - 每次递归调用之后
越来越接近这个限制条件 - 我个人理解的递归是:
-
- 能判断出
一个问题确实是有N个类似的子问题组成明确子问题是怎么样的
- 能判断出
-
假设出递归函数实现的功能并顺着思路利用这个函数 写出代码
-
- 能确定递归出口
(明确在什么条件下才继续"递" 否则就开始"归")
- 能确定递归出口
-
每次函数调用都会更接近出口在这种条件下 就可以用递归求解
6.3 死递归导致栈溢出(StackOverFlow)
6.4 按顺序打印一个无符号整型值的每一位
接收一个无符号整型值
按照顺序打印它的每一位
例如:
输入:1234
输出:1 2 3 4
确定子问题 假设PrintfNum()的功能是打印参数的每一位- PrintfNum(1234) =
PrintfNum(123) + 打印4 =
PrintfNum(12) + 打印3 + 打印4 =
PrintfNum(1) + 打印2 + 打印3 + 打印4(达到递归出口)=
打印1 + 打印2 + 打印3 + 打印4确定递归结束条件:要打印的数字只剩下个位了 也就是参数<10
也就是说参数>=10(或者>9)的时候 继续递归
void PrintNum(int num)
{
//printf("%d ", num % 10); 写在前面就是倒序打印
if (num > 9)//or if(num / 10 > 0)
PrintNum(num / 10);//子问题
//写在这里才是顺序打印
printf("%d ", num % 10);
}
int main()
{
int num = 2311516;
PrintNum(num);
return 0;
}
如果尝试迭代法的话 发现:只能倒序打印
看一下这道题一个错误的写法 多写了else:
6.5 不允许创建临时变量 求字符串的长度
解法1:迭代法
遗憾的是 用到了临时变量count
int MyStrlen(char* str)
{
int count = 0;
while (*str != '\0')
{
count++;
str++;
}
return count;
}
解法2:递归法 但是还是创建了临时变量
这是我一开始想到的思路 但是没注意到不创建临时变量
其次 我一开我把int len = 0;定义在了下面注释的地方导致每次长度都会被清零 最终结果永远是1
int len = 0;
int StrLen(char* str)
{
//int len = 0;
if (*str != '\0')
{
StrLen(++str);
len++;
}
return len;
}
解法3:递归法 而且不创建临时变量
注意
不要忘记return 0
如果没有这个return 0 当最后一次计算MyStrLen(‘\0’)的时候发现根本无路可走 成了未定义行为了
而且不写return 0不仅是语法上的错误 更是逻辑上的错误
本身本题的递归出口就是:遇到\0 就要返回0了
也就说每次传参都离\0越来越近直到真的传了\0的地址进去 解引用发现是\0 就返回0并从此刻开始"归"
参考代码:
int MyStrlen(char* ch)
{
//hello 1+ello 1+1+llo 1+1+1+lo 1+1+1+1+o 1+1+1+1+1+0
if (*ch == '\0')
//递归出口
return 0;
else
return 1 + MyStrlen(++ch);
}
int main()
{
char ch[] = "hello";
printf("%d ", MyStrlen(ch));
return 0;
}
或者这么写:
只要每次都让str+1 离递归出来越来越近就ok
千万不可以写成后置++了 不然每次传递的都是首地址 死递归了
int MyStrLen(char* str)
{
if (*str != '\0')
return 1 + MyStrLen(str+1);
else
return 0;
}
- 写成后置++ 如下图 就死递归了(看下面的
函数栈帧) - 第一次调用MyStrlen(ch++)
后置++ 先使用 再++ 但是+的是这个函数栈帧的ch - 第二次调用MyStrlen(ch++)
这个ch接收的是第一次先使用传进来的地址虽然参数的名字是一样的 但是各自在不同的函数栈帧 也是后置++也是先使用 本质上都是同一个地址 - 每次递归调用的时候
虽然形参名字都叫ch 但其实是不同的ch都是一份临时拷贝 所以每次都是首地址 永远不会接近递归出口 导致死递归
6.6 怎么找递归出口
我认为这个思想很重要 所以写了一小节
如果用递归
那么我每次都会把原问题 转换成一个相同逻辑的子问题+其他操作
我必须要思考 什么时候这个子问题就成最小的 无法再分裂出子问题了?
6.4:当只剩下个位数的时候 无法再分裂了 所以递归出口就是参数是个位数
6.5:当成空字符串了 就无法再分裂了 所以递归出口就是*str指向\0 这个时候要返回0 并开始"归"
七、迭代与递归
7.1 求n的阶乘 注意0!=1
一个注意点:0!=1
- 函数从哪里调用
return就回到那里去继续往下执行- 理解代码执行流程:
函数A里在SP处调用函数B 从SP处开始函数A就"暂停"了 直到函数B执行完 再回到SP处继续执行A- 假如求factorial(10000)
递归会栈溢出迭代算的不对(超过int范围)- 假如
递归的重复计算太多了 导致栈溢出可以考虑用迭代 迭代最多算的不对 栈溢出可是程序崩溃了
int factorial_rec(int num)//递归
{
//5!=5*4!=5*4*3!....
//分裂到1! 不可以再分出子问题 就可以归了
if (num == 1 || num == 0)//or if(num<=1)
return 1;
else
return num * factorial_rec(num - 1);
}
int factorial_ite(int num)//迭代
{
int i = 0;
int ret = 1;
for (i = 1; i <= num; i++)
{
ret *= i;
}
return ret;
}
int main()
{
//递归求n的阶乘
int num = 0;
printf("%d ", factorial_rec(num));
return 0;
}
7.2 求第n个斐波那契数
递归法(容易栈溢出)
有了前面的铺垫 可以轻易写出这个的递归算法 但是代码简单就一定好吗?
NO!! 递归的写法 假如算fib(50)算的特别慢 但并没有栈溢出 一直在算因为发生了大量的重复计算
如下图递归求第四十个fib数 第三个fib数被重复计算了快四千万次!!
int fib_rec(int index)
{
if (index == 1 || index == 2)
return 1;
else //也就是求第3+个fib
return fib_rec(index - 1) + fib_rec(index - 2);
}
迭代法
迭代法的思路:
要自己画图 找到关键步骤:
1 1 2 3 5 8 13 假设我要求第6个fib 也就是8
想象一下一开始的时候有两个指针指向1和1 然后每次循环都让他们往前移动一位数
这两个指针指向的内容变化过程是:
1 1->1 2->2 3->3 5->5 8 这个时候 8就出现了(假如是一个人口算 那他肯定也是这么算的 逐渐往后加)
也就是第二个指针所指向的内容 那么直接把他返回即可
迭代法 求fib(10000)
虽然结果不对 因为结果用int接收的但是算的很快
下面提供三种不同的写法 思路都是一样的 就是实现过程不一样
- 写法1 for循环:
- 这是我的写法 自己
画图找规律发现 求第3个 要循环1次 求第index个 要循环index-2次 - 能确定循环次数 于是决定用for循环
int fib_ite1(int index)
{
//前两个直接定义出
int first = 1;
int second = 1;
//计算得出第index个fib数 index>=3
int index_num = 0;
//循环结束条件是画图找规律得出
for (int i = 1; i <= index - 2; i++)
{
index_num = first + second;
first = second;
second = index_num;
//second放的就是第index个fib
}
//直接返回就行了 如果index<3 返回的是我定义好的1和1
//否则循环计算出来的
return second;
}
写法2 while循环:
好像突然感觉到while和for的适用场景了
确定循环次数 用for; 当…时需要循环 用while因为while不是还可以翻译成当....时候
这里就顺着我的思路写代码:前两个都初始化成1当(while)要求第三个开始的fib数的时候 就进入循环计算得出同时确定一下出循环的条件 就ok了
注意这里返回的是c 所以c必须初始化成1
返回b也一样 毕竟最后一次总会把b=c但是如果返回b的话 c就不一定要初始化成1了
7.3 如何选择递归与迭代
- 在调试factorial函数的时候 如果你的参数比较大 那就会报错:stack overflow（栈溢出）
- 系统
分配给程序的栈空间是有限的但是如果出现了死循环 或者死递归 这样有可能导致一直开辟栈空间 最终产生栈空间耗尽的情况 这样的现象我们称为栈溢出
那如何解决上述的问题：
- 将递归改写成非递归(迭代)
- 使用static对象替代nonstatic局部对象 在递归函数设计中 可以使用static对象替代nonstatic局部对象(即栈对象) 就是把本来占用栈空间的数据放到静态区
一定程度上可以缓解栈区的压力 但是这种操作的帮助是微乎其微的(而且static对象还可以保存递归调用的中间状态)
- 递归用
栈区开销换简洁性和可读性
7.4 函数栈帧简介
- 配合着本文的6.5思考:
为什么MyStrlen(ch++)会导致死递归? - 函数栈帧的底层细节十分复杂 本文暂时不做详细论述 只需要知道一些基本的原理 帮助理解递归即可
问题描述:
也许会疑问:当n=2 最后一次调用Fac(n-1) 去执行Fac(1)
然后1返回给Fac(n-1) 继续执行return n*Fac(n-1)的时候 n为什么还是2?
因为每次函数调用
都会在栈区开辟各自的函数栈帧 他们都有各自的独立形参互不影响
当Fac(1)调用结束(就是return了) 它的栈帧就销毁了
然后返回到Fac(2)的栈帧继续执行它的栈帧里的n自然还是2当Fac(2)调用结束 它的栈帧也销毁了
以此类推 栈帧会依次销毁
main函数执行完 也会销毁
所以说死递归的时候 一直在向内存的栈区申请函数栈帧 就栈溢出了
如下图 最终会开辟这么多函数栈帧然后"归"的时候开始销毁
八、两个经典例题
8.1 青蛙跳台阶(动态规划的基本认识)
问题描述
一只青蛙
他可以一次跳一级台阶
或者一次跳两级台阶
假设青蛙要跳上n级台阶
请问一共有多少种跳法?
递归
- 这道题和斐波那契数列十分类似 只不过斐波那契数列我们直接知道 第三个数开始 每个数就是前两个数之和
- 而这道题 青蛙跳上一级台阶 只有1种跳法 ;跳上二级台阶 有2种跳法
- 思考:跳上第n级(n>=3)呢?
- 假设我给定一个函数 frogJumps(int steps)
假设它的功能就是:可以计算出青蛙跳到steps级台阶有多少种跳法 - 假设青蛙第一次跳了1级 那么剩下的跳法就是frogJumps(n-1)
- 假设青蛙第一次跳了2级 那么剩下的跳法就是frogJumps(n-2)
- 所以所有的跳法就是frogJumps(n-1) + frogJumps(n-2) 当n>=3
- 只要有了递推公式 递归的代码其实很容易写出来
int frogJumps(int steps)
{
if (steps <= 2)
return steps;
else
return frogJumps(steps - 1) + frogJumps(steps - 2);
}
int main()
{
printf("%d ", frogJumps(1));
printf("%d ", frogJumps(2));
printf("%d ", frogJumps(3));
printf("%d ", frogJumps(4));
printf("%d ", frogJumps(5));
return 0;
}
动态规划
利用本题正好可以介绍一下动态规划的基本思想 博主在后续的C语言专栏 会持续更新八大算法的思想和最基本的例题 希望对大家有所帮助~
本文在前面多次提到:
不管是用递归计算n!还是递归求第n个斐波那契数量
递归代码虽十分简洁 但是有一个很严重的问题:递归很容易产生大量的重复计算
但是实际上:
- 在计算10!的时候就已经产生9! 8! 7!..了
- 在计算第40个斐波那契数的时候 前面的斐波那契数其实也都已经计算过了
- 那么 该怎么把这些已经计算过的子问题 给利用起来 帮助计算下一个子问题呢?
这就引出了动态规划的一个典型的思想:利用上一次的计算结果 快速计算出下一步的结果
下面可以看看动态规划会怎么计算这道题:
- 台阶的级数n和几种跳法 其实是一 一对应的 --> 数组
#define N 10
int main()
{
int arr[N] = { 0 };
arr[0] = 1;
arr[1] = 2;
//前两个子问题的解直接给出
//从第三个子问题开始(i=2) 计算得出
for (int i = 2; i < N; i++)
arr[i] = arr[i - 1] + arr[i - 2];
//当循环结束 其实数组里已经放好了1~N级台阶对应的跳法
for (int i = 0; i < N; i++)
printf("青蛙跳上%d级台阶有%d种跳法\n", i + 1, arr[i]);
return 0;
}
补充:迭代法
- 和
本文7.2类似 - 只不过前两个数是1 2 所以无法直接return tmp 需要再加一个if判断
参考代码:
int Fib(int index)
{
//如果index 1 2 直接返回即可
if (index <= 2)
return index;
//如果能走到这里 就说明index>=3了 那就计算求出第index个数(也就是index级台阶有几种跳法)
int a = 1;
int b = 2;
int tmp = 0;
while (index >= 3)//3级 循环1次 把tmp返回;4级 循环2次 把tmp返回....
{
tmp = a + b;
a = b;
b = tmp;
index--;
}
return tmp;
}
int main()
{
printf("%d\n", Fib(1));
printf("%d\n", Fib(2));
printf("%d\n", Fib(3));
printf("%d\n", Fib(4));
printf("%d\n", Fib(5));
printf("%d\n", Fib(6));
printf("%d\n", Fib(7));
printf("%d\n", Fib(8));
printf("%d\n", Fib(9));
printf("%d\n", Fib(10));
return 0;
}
8.2 汉诺塔
问题描述
将塔A的柱子移动到塔C
要求:
- 大的柱子只能在小的柱子下面
- 一次只能移动一个柱子
思路
这里的思路和本文6.2我个人理解的递归非常类似 首先核心思路是:
想把A上的n个柱子移动到C
S1:先把A上面n-1个柱子移动到B
S2:再把A剩下的1个柱子移动到C
S3:最后把B上的n-1个柱子移动到C
- 本题显然可以分裂出子问题
移动n个柱子从A到C和移动n-1个柱子从B到C是类似的问题
- 假设 void Hanoi(int n, char source, char auxiliary, char target)的功能是:
把在source(源头塔)上的n个长方体 利用auxiliary(辅助塔) 移动到target(目标塔)
下面看代码的时候 不要受参数名影响(B有时候作为目标塔 有时候作为辅助塔 这取决于传参的顺序)
就这么理解:Hanoi()的功能是把第二个参数上的n个柱子 利用第三个参数 移动到第四个参数上去- 递归的出口:只有一个柱子的时候 一个柱子直接移动就行了
- 每次调用都是一层一层往上 越来越接近1个柱子的情况
- move函数只是模拟了移动这个行为 move(‘A’,‘C’)就表示把A塔上第一个柱子移动到C塔上去
代码实现
当假设出函数的功能 同时有了子问题如何分裂的思路之后
直接顺着这个思路写下去 那就对了!! 正如我6.2所说的!!
void move(char ch1, char ch2)
{
printf("%c----->%c\n", ch1, ch2);
}
void Hanoi(int n, char source, char auxiliary, char target)
{
//如果只有1个柱子 直接移动到目标塔就行
if (n == 1)
{
move(source, target);
}
//不止1个柱子 接收到的参数是A B C
else//n>=2
{
//S1:先把A上面n-1个柱子移动到B
Hanoi(n - 1, source, target, auxiliary);
//S2:再把A剩下的1个柱子移动到C
move(source, target);
//S3:最后把B上的n-1个柱子移动到C
Hanoi(n - 1, auxiliary, source, target);
}
}
int main()
{
Hanoi(3, 'A', 'B', 'C');
return 0;
}
思考:怎么判断一共要移动几次?(时间复杂度?)
- 根据子问题的递推规则发现:
n个柱子移动次数是1+2*(n-1个柱子的移动次数) - 进一步找规律发现:
n个柱子需要移动2^n-1次 - 也就是说
时间复杂度是O(2^n)其中n是盘子的数量
