C语言第入门——第十六课
目录
一、分治策略与递归
二、递归
1.求解n的阶乘
2.输入整数、倒序输出
3.输入整数、正序输出
4.计算第n位Fibonacci数列
编辑5.无序整数数组打印
6.找到对应数组下标
一、分治策略与递归
在我们遇到大问题的时候,我们的正确做法是将它分解成小问题,然后一个小问题一个小问题解决,这样的策略就是分治策略。
递归是分治策略的一种方式,可以不断地通过自己调用自己来将问题规模逐渐缩小,从而解决问题。
分治策略的特征:
①大规模问题化成小规模问题容易被解决掉
②大规模问题能够被划分为多个相同的小规模问题
③这些小规模问题的解组合起来是大问题的解
④小规模问题是相互独立的
举个例子:
皇帝让你数10个谷仓的米粒,问题规模太大,你可以找100个工人,每人分上相同重量的米进行数,每个人的数量相加就是最终米粒的数量。
这就是一个典型的分治策略问题,将大规模转化为小规模问题,而且是满足上面分治策略的四条特征的。
分治策略不光在我们算法中需要使用,我希望转化成我们的思维模式,帮助我们更好的解决生活中的问题。
二、递归
递归包含两个过程:递推和回归,递推逐层调用,直到递推终止条件满足,再逐层回归。
递归和普通函数调用类似,需要开辟栈帧空间,它只有满足中止条件逐层回归的时候,上一层的函数的栈帧空间才会被释放。注意,不存在无限递归的函数,因为栈帧空间是有限的,所以不能无限调用函数,开辟空间。
递归分为直接递归和间接递归。
直接递归:在函数执行的时候调用函数自身。
间接递归:在函数执行过程中调用其他函数,再调用函数自身。
一般不推荐使用间接递归,因为很容易递推错误。
1.求解n的阶乘
代码如下:
int fabi(int n)
{if (n == 1) return 1;int sum = fabi(n-1)*n;return sum;
}int main()
{int n = 0;scanf("%d", &n);int sum =fabi(n);printf("%d", sum);
}
分析:我们将代码复制多份便于观看,但其实只有一个代码哦。
我们这里取n=4,第一次进入到fabi()函数中,n!=1,执行下一条语句fabi(n-1)*n,也就是fabi(3)*4。
然后我们再次调用函数fabi(),此时n=3,我们进入到函数体中n!=1,执行下一条语句fabi(2)*3。
此时我们再次调用fabi()函数,此时n=2,n!=1,执行fabi(1)*2。
这里再次调用fabi()函数,此时n==1,所以我们return 1。
返回到上一层,我们继续执行,此时这条语句为sum = 1*2,我们返回1*2,然后我们继续回归上一层函数,sum = 3*2*1,然后我们再回归,最后得到sum =4*3*2*1,回归结束。
下面第一张是我画的示意图,如果看不清楚再看下面第二张老师画的图,老师画的比较清晰。
红色的线代表递推过程,绿色的线代表回归过程。
下面解释一下栈帧的动态变化情况。
在每次递推调用函数的时候,程序开辟栈帧空间,在回归的时候再一层层释放掉。
2.输入整数、倒序输出
输入一个整数(无符号整型),使用递归算法将整数倒序输出。
void Show(unsigned int n)
{if (n == 0) return ;else{printf("%d", n % 10);Show(n / 10);}
}
int main()
{unsigned int n = 0;scanf("%d", &n);Show(n);
}
逻辑图如下,变量和函数定义不太一样,但是逻辑一致。
3.输入整数、正序输出
法一:数组法
void Show(unsigned int n)
{ int ar[10] = {0};int i = 0;while (n!=0){ar[i] = n % 10;n = n / 10;i++;}i--;while (i>=0){printf("%d ", ar[i]);i--;}
}
int main()
{unsigned int n = 0;scanf("%d", &n);Show(n);
}
法二:递归法
void Show(unsigned int n)
{if (n == 0) return;else{Show(n / 10);printf("%d", n % 10);}
}
int main()
{unsigned int n = 0;scanf("%d", &n);Show(n);
}
4.计算第n位Fibonacci数列
法一:循环输出
int Fibonna(int n)
{int a = 1;int b = 1;if (n==0) return 0;if (n == 1 || n == 2){return 1;}else{int i = 0;int temp = 0;int result = 0;while (i<n-2){result = a + b;temp = b;b = result;a = temp;i++;}return result;}}
int main()
{int n = 0;scanf("%d", &n);int result = Fibonna(n);printf("%d", result);
}
法二:递归输出
int Fibonna(int n)
{if (n == 0) return 0;if (n == 1|| n == 2){return 1;}else{return (Fibonna(n - 1) + Fibonna(n - 2));}
}
int main()
{int n = 0;scanf("%d", &n);int result =Fibonna(n);printf("%d",result);
}
Q: 使用递归进行输出的时候空间复杂度是2^n,很大,怎么样降低时间复杂度?
A: 想要降低复杂度,主要就是要减少一个递归函数,将递归过程中的值存储下来就能减少相应的复杂程度。
写法一:一定要注意a,b,temp不能每次被调用的时候都初始化,要不然输出的值不正确。
int fac(int n)
{static int a = 1;static int b = 1;static int temp = 1;if (n <= 2) return temp;temp = a + b;b = a;a = temp;fac(n - 1);
}
int main()
{int n = 0;scanf("%d", &n);int result = fac(n);printf("%d", result);
}
写法二:思路一致,只不过老师写的更清楚明了。
int fanc(int n, int a, int b)
{if (n <= 2) return a;else return fanc(n - 1, a + b, a);
}
int fac(int n)
{int a = 1;int b = 1;return fanc(n, a, b);
}
int main()
{int n = 0;scanf("%d", &n);int result = fac(n);printf("%d", result);
}
5.无序整数数组打印
有一个整型数组,数值无序,使用循环和递归打印和查询。
法一:循环打印
void Show_Arr(const int* ar, const int n)
{if (n < 1 || ar == NULL) return;for (int i = 0; i < n; i++){printf("%d ", ar[i]);}
}
int main()
{const int n = 3;int ar[n] = { 12,23,34 };Show_Arr(ar,n);
}
法二:使用递归打印数组
void Show_Arr(const int* ar, const int n)
{if (n < 1 || ar == NULL) return;Show_Arr(ar, n - 1);printf("%d ", ar[n - 1]);}
int main()
{const int n = 3;int ar[n] = { 12,23,34 };Show_Arr(ar, n);
}
Q:上述递归代码我可可以将n-1修改成n--吗?请详细说明。
A:不可以修改,后置--是先取值后--,在下面示例中,n=3,n>0,调用函数,调用的新的函数还是n=3的函数,进入到一个循环,直到栈帧空间被填满。
Q:上述递归代码我可可以将n-1修改成--n吗?请详细说明。
A:也不可以修改,前置--是先--再取值,的确可以满足递归调用的逻辑,但是当他进行回归的时候会n的值被更改了,输出的是更改后的n-1,造成数据溢出问题。
6.找到对应数组下标
法一:循环找数组下标
int FindValue(const int* arr, int n, int value)
{if (n < 1 || arr == NULL) return 0;int pos = -1;for (int i = 0; i < n; i++){if (arr[i] == value){pos = i;break;}}return pos;
}
int main()
{const int n = 5;int arr[n] = { 10,11,12,13,14 };int val = 0;scanf("%d", &val);int m = FindValue(arr, n, val);printf("%d", m);
}
法二:递归找数组下标
这面这个代码输出的数组下标有问题,一直是-1
int FindValue(const int* br, int n, int val)
{int pos = -1;if (NULL == br || n < 1) return pos;if (br[n-1] == val){pos = n - 1;}else{FindValue(br, n - 1, val);}return pos;
}
int main()
{const int n = 5;int arr[n] = { 10,11,12,13,14 };int val = 0;scanf("%d", &val);int m=FindValue(arr,n,val);printf("%d", m);
}
正确代码
int FindValue(const int* br, int n, int val)
{int pos = -1;if (NULL == br || n < 1) return pos;if (br[n-1] == val){pos = n - 1;}else{pos =FindValue(br, n - 1, val);}return pos;
}
int main()
{const int n = 5;int arr[n] = { 10,11,12,13,14 };int val = 0;scanf("%d", &val);int m=FindValue(arr,n,val);printf("%d", m);
}
相关文章:
C语言第入门——第十六课
目录 一、分治策略与递归 二、递归 1.求解n的阶乘 2.输入整数、倒序输出 3.输入整数、正序输出 4.计算第n位Fibonacci数列 编辑5.无序整数数组打印 6.找到对应数组下标 一、分治策略与递归 在我们遇到大问题的时候,我们的正确做法是将它分解成小问题&a…...
IntelliJ IDEA 快捷键 Windows 版本
前言:常用快捷键 IntelliJ IDEA编辑器大受欢迎的原因之一是它的智能提示和丰富的快捷键,在日常开发中熟练的使用快捷键会大大提升开发的效率,本篇文章就笔者日常开发中的总结,把常用的、好用的快捷键做一个列表,方便…...
重生之我必去大厂java开发
JavaDreamer 重生之我必去大厂java开发。主线任务进入大厂java开发。 author :developer_zxh GitHub | Gitee 本项目记录了本人从中国科学院大学硕士研究生开始,如何进入大工 java 开发岗位的学习记录(目前在校未求职,加入后此状…...
2023年中职“网络安全“—Web 渗透测试②
2023年中职“网络安全“—Web 渗透测试② Web 渗透测试任务环境说明:1.访问http://靶机IP/web1/,获取flag值,Flag格式为flag{xxx};2.访问http://靶机IP/web2/,获取flag值,Flag格式为flag{xxx};3.访问http://靶机IP/web…...
【整顿C盘】pycharm、chrome等软件,缓存移动
C盘爆了,特来找一下巨大的软件缓存,特此记录,跟随的各大教程,和自己的体会 一、爆炸家族JetBrains 这个适用于pycharm、idea、webstorm等等,只要是JetBrains家的,2020版本以上,都是一样的方法 p…...
C# using语句使用介绍
在C#中,using语句有两种主要用途:一是引入命名空间,二是提供一种简便的方式来处理资源的清理(主要用于实现了 IDisposable 接口的对象)。 引入命名空间:using 语句用于引入命名空间,从而可以在代…...
leetcode (力扣) 201. 数字范围按位与 (位运算)
文章目录 题目描述思路分析完整代码 题目描述 给你两个整数 left 和 right ,表示区间 [left, right] ,返回此区间内所有数字 按位与 的结果(包含 left 、right 端点)。 示例 1: 输入:left 5, right 7 输出…...
Flutter笔记: 在Flutter应用中使用SQLite数据库
Flutter笔记 在Flutter应用中使用SQLite数据库(基于sqflite) 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/q…...
OpenAI GPT5计划泄露
OpenAI的首席执行官萨姆奥特曼在最近接受《金融时报》的专访时,分享了OpenAI未来发展的一些新动向。此外,他还透露了关于即将到来的GPT-5模型以及公司对AGI的长期目标的一些细节。 奥特曼指出: 1.OpenAI正在开发GPT-5,一种更先进的…...
【面试经典150 | 数学】Pow(x, n)
文章目录 写在前面Tag题目来源题目解读解题思路方法一:快速幂-递归方法二:快速幂-迭代 其他语言python3 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主…...
封装比较好的登录页面
封装比较好的登录页面 只在setup()函数中写流程,将逻辑代码抽离出来 <template><div class"wrapper"><img class"wrapper__img" srchttp://www.dell-lee.com/imgs/vue3/user.png /><div class"wrapper__input"&…...
如何使用Flask request对象处理请求
在 Flask 中,request 对象是处理 HTTP 请求的重要工具之一。它提供了许多属性和方法,可以帮助我们获取请求的相关信息和数据。本文将向你介绍 request 对象的常用方法以及如何在 Flask 应用程序中使用它。 1. 获取请求方法 首先,让我们看一…...
快速搜索多个word、excel等文件中内容
如何快速搜索多个word、excel等文件中内容 操作方法 以win11系统为介绍对象。 首先我们打开“我的电脑”-->“文件夹选项”-->“搜索”标签页,在“搜索内容”下方选择:"始终搜索文件名和内容(此过程可能需要几分钟)"。然后…...
Minio安装
环境 centos8,关闭防火墙 minio-20231101183725版本 参考官网:部署 MinIO:单节点单硬盘 — 适用于 Linux 的 MinIO 对象存储 单例 下载rpm,用中国镜像 wget https://dl.minio.org.cn/server/minio/release/linux-amd64/arch…...
Spring初识
未来的几周时间,大概率我会更新一下Spring家族的一些简单知识。而什么是Spring家族,好多同学还不是很清楚,我先来简单介绍一下吧: 所谓Spring家族,它其实就是一个框架,是基于Servlet再次进行封装的内容。为…...
2023全新付费进群系统源码 带定位完整版 附教程
这源码是我付费花钱买的分享给大家,功能完整。 搭建教程 Nginx1.2 PHP5.6-7.2均可 最好是7.2 第一步上传文件程序到网站根目录解压 第二步导入数据库(58soho.cn.sql) 第三步修改/config/database.php里面的数据库地址 第四步修改/conf…...
C# LINQ使用介绍
LINQ(Language-Integrated Query)是C#语言的一个强大特性,它允许开发者用声明性的方式查询和操作数据。LINQ提供了一致的查询体验,无论是操作内存中的对象(如数组或集合),还是操作外部数据源&am…...
【c++】——类和对象(中)——实现完整的日期类(优化)万字详细解疑答惑
作者:chlorine 专栏:c专栏 赋值运算符重载()()():实现完整的日期类(上) 我走的很慢,但我从不后退。 【学习目标】 日期(- - --)天数重载运算符 日期-日期 返回天数 对日期类函数进行优化(不符合常理的日期,负数,const成员)c中重载输入cin和输…...
开源与闭源:大模型时代的技术交融与商业平衡
一、开源和闭源的优劣势比较 1.1 开源 优势: 1.技术共享与吸引人才: 开源促进了技术共享,吸引了全球范围内的人才参与大模型的发展,形成了庞大的开发者社区。 2.推动创新: 开源模式鼓励开发者共同参与,推动…...
C#开发的OpenRA游戏之属性BodyOrientation(6)
C#开发的OpenRA游戏之属性BodyOrientation(6) 在顶层定义里会发现这个属性: ^SpriteActor: BodyOrientation: QuantizeFacingsFromSequence: RenderSprites: SpriteActor是用来定义角色的基本属性,它的第一个属性就是BodyOrientation,这个属性主要用来描述角色的身体的…...
Linux shell编程学习笔记27:tputs
除了stty命令,我们还可以使用tput命令来更改终端的参数和功能。 1 tput 命令的功能 tput 命令的主要功能有:移动更改光标、更改文本显示属性(如颜色、下划线、粗体),清除屏幕特定区域等。 2 tput 命令格式 tput [选…...
【计算机网络笔记】IPv6简介
系列文章目录 什么是计算机网络? 什么是网络协议? 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能(1)——速率、带宽、延迟 计算机网络性能(2)…...
c语言-数据结构-堆
目录 一、二叉树 1、二叉树的概念 2、完全二叉树和满二叉树 3、完全二叉树的顺序存储 二、堆 2、堆的概念与结构 3、堆的创建及初始化 4、堆的插入(小堆) 5、堆的删除 6、显示堆顶元素 7、显示堆里的元素个数 8、测试堆的各个功能 9、 实现堆…...
ROS基础—关于参数服务器的操作
1、rosparam list 获取参数服务器的所有参数。 2、rosparam get /run_id 获取参数的值...
Sql Server 2017主从配置之:事务日志传送
使用事务日志传送模式搭建Sql Server 2017主从同步,该模式有一定的延迟,是通过3个不同的定时任务,将主库的日志同步到从库进行恢复来实现数据库同步操作。 环境准备 两台服务器,配置都是8g2核,50g硬盘,操…...
每日OJ题_算法_双指针_力扣283. 移动零+力扣1089. 复写零
力扣283. 移动零 283. 移动零 - 力扣(LeetCode) 难度 简单 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 请注意 ,必须在不复制数组的情况下原地对数组进行操作。 示例…...
WebGl-Blender:建模 / 想象成形 / Blender概念词汇表 / 快捷键
一、理解Blender 欢迎来到Blender!Blender是一款免费开源的3D创作套件。 使用Blender,您可以创建3D可视化效果,例如建模、静态图像,3D动画,VFX(视觉特效)快照和视频编辑。它非常适合那些受益于…...
【C++】【Opencv】cv::warpAffine()仿射变换函数详解,实现平移、缩放和旋转等功能
仿射变换是一种二维变换,它可以将一个二维图形映射到另一个二维图形上,保持了图形的“形状”和“大小”不变,但可能会改变图形的方向和位置。仿射变换可以用一个线性变换矩阵来表示,该矩阵包含了六个参数,可以进行平移…...
WPF实现右键菜单
在WPF中,创建上下文菜单(通常称为“右键菜单”)是通过使用ContextMenu控件来实现的。你可以在XAML中声明上下文菜单,并将其关联到任何FrameworkElement。以下是如何在WPF中实现上下文菜单的基本步骤: 1. 在XAML中定义…...
Java智慧工地SaaS管理平台源码:AI/云计算/物联网
智慧工地是指运用信息化手段,围绕施工过程管理,建立互联协同、智能生产、科学管理的施工项目信息化生态圈,并将此数据在虚拟现实环境下与物联网采集到的工程信息进行数据挖掘分析,提供过程趋势预测及专家预案,实现工程…...
【漏洞复现】通达oa 前台sql注入
漏洞描述 通达OA(Office Automation)是一款企业级协同办公软件,旨在为企业提供高效、便捷、安全、可控的办公环境。它涵盖了企业日常办公所需的各项功能,包括人事管理、财务管理、采购管理、销售管理、库存管理、生产管理、办公自动化等。通达OA支持PC端和移动端使用,可以…...
机器学习笔记 - Ocr识别中的文本检测EAST网络概述
一、文本检测 文本检测简单来说就是找到图像中可以出现文本的区域。例如,请参见下图,其中在检测到的文本周围绘制了绿色边框。 在进行文本检测时,你可能会遇到两种情况 具有结构化文本的图像:这是指具有干净/均匀背景和常规字体的图像。文本大多密集,行结构正确,…...
【SQL server】数据库、数据表的创建
创建数据库 --如果存在就删除 --所有的数据库都存在sys.databases当中 if exists(select * from sys.databases where name DBTEST)drop database DBTEST--创建数据库 else create database DBTEST on --数据文件 (nameDBTEST,--逻辑名称 字符串用单引号filenameD:\DATA\DBT…...
vue的生命周期分别是什么?
Vue的生命周期分为8个阶段,分别是: beforeCreate:实例初始化之后,数据观测 (data observer) 和 event/watcher 事件配置之前被调用。 created:实例已经创建完成后被调用,这时候实例已完成以下的配置&#…...
Java拼图游戏
运行出的游戏界面如下: 按住A不松开,显示完整图片;松开A显示随机打乱的图片。 User类 package domain;/*** ClassName: User* Author: Kox* Data: 2023/2/2* Sketch:*/ public class User {private String username;private String password…...
Vue框架的element组件table文字居中
1.直接上代码 <el-table max-height"500px" :data"datas.roles" style"width: 100%" border :header-cell-style"{textAlign: center}" :cell-style"{ textAlign: center }"><el-table-column prop"id" …...
科技创新 共铸典范 | 江西卫健办邓敏、飞图影像董事长洪诗诗一行到访拓世科技集团,提振公共卫生事业发展
2023年11月15日,拓世科技集团总部迎来了江西省卫健项目办项目负责人邓敏、江西飞图影像科技有限公司董事长洪诗诗一行的考察参观,集团董事长李火亮、集团高级副总裁方高强进行热情接待。此次多方交流,旨在共同探讨携手合作,激发科…...
Linux安装OpenCV并配置VSCode环境
Linux安装OpenCV并配置VSCode环境 安装OpenCV环境安装必需工具下载并解压OpenCV库(Opencv Core Modules和opencv_contrib)创建构建目录,进行构建验证构建结果安装验证安装结果 配置VSCode环境创建项目文件修改配置信息执行程序 安装环境 Ubun…...
Django(ORM事务操作|ORM常见字段类型|ORM常见字段参数|关系字段|Meta元信息)
文章目录 ORM事务操作什么是事务?事务的产生事务的四大特征ORM中如何使用事务 ORM字段类型常用字段与不常用字段类型ORM还支持用户自定义字段类型 ORM字段参数关系字段ForeignKey外键on_delete参数设置的值 OneToOneField与ForeignKey的区别多对多关系建立的方式ORM…...
【mujoco】Ubuntu20.04配置mujoco210
【mujoco】Ubuntu20.04配置mujoco210 文章目录 【mujoco】Ubuntu20.04配置mujoco2101. 安装mujoco2102. 安装mujoco-py3.使用render时报错Reference 本文简要介绍一下如何在ubuntu20.04系统中配置mujoco210,用于强化学习。 1. 安装mujoco210 在官方资源里找到http…...
【洛谷 P3853】[TJOI2007] 路标设置 题解(二分答案+循环)
[TJOI2007] 路标设置 题目背景 B 市和 T 市之间有一条长长的高速公路,这条公路的某些地方设有路标,但是大家都感觉路标设得太少了,相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题,我们把公路上相邻路标的最大…...
蓝桥杯 vector
vector的定义和特性 注意:vector需要开C11标准 vector的常用函数 push_back():将元素添加到vector末尾 pop_back():删除vector末尾的元素 begin()和end():返回指向vector第一个元素和最后一个元素之后一个位置的迭代器。 示例 vector<int> vec{10,20,30};f…...
ai绘画部署教程
在部署AI绘画Web环境的过程中,你提供了一些关键步骤。以下是一些详细说明: 1. 克隆webui 首先,通过以下命令从GitHub上克隆webui的代码: git clone https://github.com/AUTOMATIC1111/stable-diffusion-webui 这将下载webui的源…...
策略模式的应用——应对频繁的需求变更
秋招结束后,间接性堕落了一段时间,学习几乎停止下来了。内心甚是焦灼,感觉生活很无趣!为了在参加工作后能够快速上手和成为一名优秀的中级开发者,从这篇文章开始将不断学习优秀的编码经验,学习是永无止境的…...
qt-C++笔记之treeWidget初次使用
qt-C笔记之treeWidget初次使用 code review! 文章目录 qt-C笔记之treeWidget初次使用1.运行2.文件结构3.main.cpp4.widget.h5.widget.cpp6.widget.ui7.main.qrc8.qt_widget_test.pro9.options.png 1.运行 2.文件结构 3.main.cpp 代码 #include "widget.h"#include…...
SQL零基础入门教程,贼拉详细!贼拉简单! 速通数据库期末考!(八)
FULL OUTER JOIN 除了前面讲到的 INNER JOIN(内连接)、LEFT JOIN(左连接)、RIGHT JOIN(右连接),还有另外一种关联方式,即 FULL OUTER JOIN(全外连接) FULL O…...
C语言编程陷阱(八)
陷阱36:不要使用指针作为函数的返回值 有时候,我们可能想要用一个函数来返回一个指针,比如返回一个动态分配的内存,或者返回一个数组的某个元素的地址。但是,如果我们不小心,我们可能会犯一个很常见的错误,就是返回一个局部变量的地址。例如,看看下面的代码: #inclu…...
客户端性能优化实践
背景 双十一大促时,客户客服那边反馈商品信息加载卡顿,在不断有订单咨询时,甚至出现了商品信息一直处于加载状态的情况,显然,在这种高峰期接待客户时,是没法进行正常的接待工作的。 起初,页面一…...
mysql使用--表达式和函数
1.表达式 如:11,一般包含操作数,运算符。 _1.操作数 MYSQL中最常用的操作数有以下几种 (1).常数 (2).列名,针对某个具体的表,它的列名可被当作表达式的一部分 (3).函数调用 一个函数用于完成某个特定的功能。比如NOW()…...
<蓝桥杯软件赛>零基础备赛20周--第6周--数组和队列
报名明年4月蓝桥杯软件赛的同学们,如果你是大一零基础,目前懵懂中,不知该怎么办,可以看看本博客系列:备赛20周合集 20周的完整安排请点击:20周计划 每周发1个博客,共20周(读者可以按…...