函数可以直接或间接地调用自身,称为递归调用。所谓直接调用自身,就是指在一个函数的函数体中出现了对自身的调用表达式,例如:
函数间接调用自身,就是通过调用其它函数的同时在其它函数中有调用了自己,例如:
递归算法的实质是将原有的问题分解为新的问题,而解决新问题时又用到了原有问题的解法。按照这一原则分解下去,每次出现的新问题都是原有问题的简化的子集,而最终分解出来的问题,是一个已知解的问题。
递归的过程有两个阶段:
第一个阶段:递推。 讲原问题不断分解为新的子问题,逐渐从未知向已知推进,最终达到已知的条件,即递归结束的条件,这时递推阶段结束。例如,求5!,可以这样分解:
第二阶段:回归。从已知条件出发,按照递推的逆过程,逐一求值回归,最后达到递推的开始处,结束回归阶段,完成递归调用。例如,求5!的回归阶段如下:
分析:计算n!的公式如下:
这是一个递归形式的公式,在描述"阶乘"算法时又用到了"阶乘"。递归的结束条件是 n = 0.
2.用递归法计算从n个人中选择k个人组成一个委员会的不同组合数。
分析:由n个人里选k个人的组合数 = 由(n-1)个人里选k个人的组合数 + 由(n-1)个人里选(k-1)个人的组合数。递推的结束条件是n == k || k == 0 , 这时的组合数为1。
有三根针A、B、C。A针上有n个盘子,盘子大小不等,大的在下,小的在上,如下图所示。要求把这n个盘子从A针移动到C针,在移动过程中可以借助B针,每次只充许移动一个盘子,且在移动过程中在三根针上都保持大盘在下,小盘在上。
将n个盘子从A针移动到C针可以分解为下面3个步骤:
1.将A上n-1个盘子移动到B针上(借助C针);
2.把A针上剩下的一个盘子移动到C针上;
3.将n-1个盘子从B针移动到C针上(借助A针)
事实上,上面3个步骤包含两种操作:
1.将多个盘子从一个针移动到另一个针上,这是一个递归的过程。
2.将1个盘子从一个针上移动到另一个针上。
那么就可以用两个函数分别实现上面的两种操作,用hanoi函数实现第一种操作,用move函数实现第二种操作。
在函数为被调用时,函数的形参并不占有实际的内存空间,也没有实际的值。只有在函数被调用时才为形参分配存储单元,并将实参与形参结合。结合过程叫做参数传递,有值传递和引用传递两种方式。
值传递是指当发生函数调用时,给形参分配内存空间,并用实参来初始化形参(直接将实参的值传递给形参)。这一过程是参数值的单向传递过程,一旦形参获得了值便与实参脱离关系,此后无论形参发生了怎样的改变,都不会影响到实参。
上例中,swap之前x,y分别初始化为5和10,调用swap时, 实参x,y把值传递给形参a,b 由于这里是值传递,是单向的,所以实参x,y把值5,10传递给a,b之后就跟a,b没有关系了, 在swap里面a,b借助临时变量t交换了值,但是这是a,b之间交换了值不影响x,y的值。
引用是一种特殊类型的变量,可以被认为是另一个变量的别名。通过引用名与通过被引用的变量名访问变量的效果是一样的,例如:
使用引用时需要注意两个问题:
1.声明一个引用时,必须同时对它进行初始化,使它指向一个已存在的对象。
2.一旦一个引用被初始化后,就不能改为指向其它对象。也就是说,一个引用,从它诞生之时起,就必须确定是哪个变量的别名,而且始终只能作为这个变量的别名,不能另作它用。
&放在变量前面就是引用符号
上面的例子就是引用传递可以实现x,y的值交换操作。
引用传递与值传递的区别只是函数的形参写法不同,主调函数中的调用表达式完全一样。
函数调用时,需要保存现场和返回地址,然后转到子函数的代码起始地址去执行。子函数执行完后,又要取出先前保存的返回地址和现场状态,再继续执行。这一切都需要时间和空间方面的开销,所以频繁调用函数会降低程序的执行效率。对于一些功能简单、规模较小又使用频繁的函数,可以设计为内联函数。内联函数不是在调用时发生控制转移,而是在编译时将函数体嵌入在每个调用处。这样就节省了参数传递、控制转移等开销。
内联函数在定义时使用关键字inline, 语法形式如下:
inline 类型说明符 被调函数名(含类型说明的形参表){函数体语句;}
使用内联函数时应注意:
1.内联函数体内一般不能有循环语句和switch语句;
2.内联函数的定义必须出现在第一次被调用之前;
3.对内联函数不能进行异常接口声明
通常内联函数应该是比较简单的函数,结构简单、语句少。如果将一个复杂的函数定义为内联函数,反而会造成代码膨胀,增大开销。这种情况下,多数编译器都会自动将其转换为普通函数来处理。
因此,inline关键字只是表示一个要求,编译器并不承诺将inline修饰的函数作为内联。而没有用inline修饰的函数也可能编译为内联函数。
C++中充许给函数设置默认的形参值
函数在定义时可以预先声明默认的形参值。调用时如果给出实参,则用实参初始化形参;如果没有给出实参,则采用预先声明的默认形参值。例如:
默认形参值必须按从右向左的顺序声明。在有默认值的形参值右面,不能出现无默认值的形参。因为在调用时,实参初始化形参是按从左向右的顺序。例如:
默认形参值应该在函数原型中给出,例如:
注意:在相同的作用域内,默认形参值的说明应保持唯一,但如果在不同的作用域内,充许说明不同的默认形参,例如:
C++的函数重载,就是通过调用相同的函数名来响应不同的操作。在两个以上的函数中,具有相同的函数名,但是形参的个数或类型不同,编译器根据实参和形参的类型及个数的最佳匹配,自动确定调用哪个函数,这就是函数的重载。
1.判断一个数是否为质数(质数又称为素数)
质数又称之为素数。指在一个大于1的自然数中,除了1和此整数自身外,没法被其它自然数整除的数。即只有两个正因数(1和自己)的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。合数是由若干个质数相乘而得到的。
取模运算:a % p(或a mod p),表示a除以p的余数。
2.求两个整数的最大公约数和最小公倍数。
最大公约数,也称为最大公因数,最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。记号(a)表示a的约束中最大的那个数。与最大公约数相对应的概念是最小公倍数,a,b的最小公倍数记为[a,b]。
如果数a能被数b整除,a就叫做b的倍数,b就叫做a的约数。约数和倍数都表示一个数与另一个数的关系,不能单独存在。
几个自然数,公有的约数,叫做这几个数的公约数;其中最大的一个,叫做这几个数的最大公约数。例如:12,16的公约数有1,2,4,其中最大的一个是4,4是12与16的最大公约数,一般记为(12,16) = 4.
几个自然数公有的倍数,叫做这几个数的公倍数,其中最小的一个,叫做这几个数的最小公倍数。例如:4的倍数有4,8,12,……,6的倍数有6,12,……,4和6的公倍数有12,24,……,其中最小的是12,所以[4,6] = 12.两数互质最小公倍数为两数乘积。
互质又叫互素。若N个整数的最大公因数是1,则称这N个整数互质。例如8,10的最大公因数是2,不是1,因此不是整数互质。7,10,13的最大公因数是1,因此这是整数互质。下面分析两种求最大公约数的方法:
如果两个数相差不大,可以用大数减去小数,所得的差与小数的最大公约数就是原来两个数的最大公约数.例如:求78和60的最大公约数.78-60=18,18和60的最大公约数是6,所以78和60的最大公约数是6.
如果两个数相差较大,可以用大数减去小数的若干倍,一直减到差比小数小为止,差和小数的最大公约数就是原来两数的最大公约数.例如:求92和16的最大公约数.92-16=76,76-16=60,60-16=44,44-16=28,28-16=12,12和16的最大公约数是4,所以92和16的最大公约数就是4.
当两个数都较大时,采用辗转相除法比较方便.其方法是:
以小数除大数,如果能整除,那么小数就是所求的最大公约数.否则就用余数来除刚才的除数;再用这新除法的余数去除刚才的余数.依此类推,直到一个除法能够整除,这时作为除数的数就是所求的最大公约数.
例如:求4453和5767的最大公约数时,可作如下除法.
于是得知,5767和4453的最大公约数是73.
辗转相除法适用比较广,比短除法要好得多,它能保证求出任意两个数的最大公约数.
而最小公倍数可以借助最大公约数来求,分两步:
1.利用辗除法或其它方法求得最大公约数
2.最小公倍数等于两数之积除以最大公约数
cout<<"输入两个整数,用空格分隔,按回车结束:";
cout<<"输入两个整数,用空格分隔,按回车结束:";
输入两个整数,用空格分隔,按回车结束:12 8
这两个整数的最大公约数是:4
这两个整数的最小公倍数是:24
这样写是不行的,如输入5,3 则输出结果为625,为什么呢?
因为sum = sum*sum*func(5,1);这里func(5,1)返回的sum会改变前面的sum值,此外这里的运算是自右向左运算的,也就是说返回的sum = 5 ,然后最右边两个sum 运算之后sum值25,然后再于剩下的sum运算,此时是25*25 所以输入5,3之后输出的结果是625.
设A为自定义类,现有普通函数int fun(A& x)。则在该函数被调用]时: @[C](2)
A. 将执行复制构造函数来初始化形参x
B. 仅在实参为常量时,才会执行复制构造函数以初始化形参x
C. 无需初始化形参x
D. 仅在该函数为A类的友元函数时,无需初始化形参x
A.将执行复制构造函数来初始化形参x
B.仅在实参为常量时,才会执行复制构造函数以初始化形参x
D.仅在该函数为A类的友元函数时,无需初始化形参x
编译器/C语言中的指令-机器指令
3.生成项目(编译):*.exe
F7(出现00error为程序已经创建成功)
debug版本(调试版本)
release版本(发布版本) 编译器会优化掉一部分无用代码
内存的单位是字节(Byte) 每个字节占8个位(bit)
每个运行中的程序(进程)都有4G内存
内存不是内存条,是空头支票
变量类型就是告诉系统(编译器)我需要的内存有多大
变量名告诉系统(编译器)我需要的内存在哪里,变量名是地址的别名
变量类型 变量名称 = 值;
每种类型的变量,存储的数据都是有范围,超过这个范围的数据,将会被计算机丢弃,如:
变量宽度(字节byte)16进制 |
---|
内存编号就是内存地址,别名就是变量名
使用&地址符号,获得当前地址的内存
内存太多,使用编号代替,一个内存的编号就是地址,一个地址里面代表一个字节,一个字节就是八个0或者1
放到函数里面必须有一个明确的初始值
放到函数外面称为全局变量
变量的本质是容器,里面可以存储任意类型的数据
可以根据用户输入圆的半径,计算出圆的面积。
常量是一个数,不会变化
用变量是为了临时储存数据
大端小端针对的是数据超过1个字节的存储
小端模式:数据低位在内存地址编号低位,数据高位在高位
大端模式:数据高位在内存地址编号低位,数据高位在低位
程序在断点才可以看memory
float使用二进制规范存储,将小数点变为二进制IEEE规则
getchar()因为程序一直在运行,所以无法进行调试,需要删除掉
选择断点-把要看的变量名输入到address输入框中-查看存储的内存地址
如何让程序运行到某阶段的存储下来
浮点型有自己的存储规范,课堂上不涉及
当存储的12时是12,负数的时候存储的是EE
原码:最高位为符号位,其余各位为数据本身的绝对值
0X12 = ;//正数,最高位0正,最高位1为负
负数:符号位为1,其余位取反
负数:符号位为1,其余位对原码取反加1
原码://符号位为1,负数
反码://符号位为1,取反
计算机存储整数的时候存储补码
谁能告诉我下面的1代码表示什么?
%u:无符号数的输出标记
%d:有符号数的输出标记
有符号数与无符号数在存入内存的时候是相同的,比如
%x:十六进制输出标记
%p:类似于地址,全部位输出标记
fffff ff//有符号数,使用符号位进行补位
只有整数才有有符号与无符号之分
单引号==’ '==只是单个字符
putchar()
只能打印一个字符,给他任何数字都会进行查表,然后输出表的对应值
结果:因为没有0结束,会出现一些别的打印结果
所谓字符串是以数组的形式来表示的
输出打印字符串需要见到0才能停止,当数组扩大,会自动补0
一般情况下不用指明长度,编译器会计算长度,自动补0。
英文字符查表,中文如何操作的呢?
中文也有值,每个中文字有两个字节的占格
计算机发明之后及后面的很长一段时间,只用应用于美国及一些西方国家
我们专家把那些127之后的奇异符号们(EASCII)取消掉
规定两个大于127的数定义为汉字,字符等,全角
数组是连续申请一些内存供应使用
数组的地址是第一个数组的地址
如果我们要存储多人的年龄
能否让编译器分配多一点的int
越界/当你取数组中的数值时,假设数组中有10个值,age[10],值已经越界。
查看-调试-watch-右边输入名称
直接告诉编译器几人几科
二维数组与数组在存储方式上是相同的,不同工作主要是由编译器运作,二维数组就是一维数组
修改的情况下直接修改可以
没有二维数组或者多维数组,本质都是一维数组
表达式是运算符与运算与常量的之间的关系
==%%==使用两个才能显示
加密解密 安全 反病毒 反外挂
位运算能够精确的对某一个位进行操作
无符号数补0,有符号数补符号位 |
如何将二进制数中的某一个位置修改为1? //3位
如何将二进制数中的某一位置修改为0; //3位
//相同为奇数,不同为偶数
赋值是一个动作,表达式是一个数
关系运算符用于比较两者的关系
关系运算符也是双目运算符
表达式1 ? 表达式2 :表达式3
当表达式1为真时 整个表达式的结果为表达式2
当表达式2为真时 整个表达式的结果为表达式3
加在任何表达式的前面,改变表达式的值
人生选择坚持的人,虽然不一定会成功,但是一定无限接近于成功
循环语句的本质是重复执行(重点是终止条件)
有1,2,3,4四个数字,能组成多少互不相同且无重复的三位数?都是多少?
分支语句/无论条件如何,只有一个分支运行,只走一条线
5.不运行程序,说出下面程序执行的结果
表达式x必须是整数类型
如果分支多,效率高//4
if…else语句适合判断区间,而switch不适合
0 | 0 | 0 | 0 |
0 | 0 | 0 |
设置断点F9,取消断点F9
断点只能写在有语句的地方
至少会执行一次,所以,通常用来实现
从键盘上输入字符,并显示,直到输入TAB为止
4.编程将所有“水仙花数”打印出来,并打印其总个数。 “水仙花数”是一个 各个位立方之和等于该整数的三位数
5.验证“角谷猜想”, 判断给定的一个自然数,若为偶数除以 2,若为奇数则乘 3 加 1,得到一个新的自然数后按照上面的法则继续演算,一直到结果变为 1,并且将每一步的运算过程和得到的新的自然数显示出来。
6.百鸡问题:一只公鸡值 5 元,一只母鸡值 3 元,而 1 元可买 3 只小鸡。现有 100 元钱,想买 100 只鸡。问可买公鸡、母鸡、小鸡各几只?
7.编程实现:某人想将手中一张面值 100 元的人民币换成 5 元(可单换 20 张)、1 元(可单
换 100 张)和 0.5 元(可单换 200 张)面值的票子,但要求 100 元换以上的零钱共 100 张,
且要求每种不少于 1 张,共有多少种兑换方法。
8.韩信点兵:韩信才智过人,从不直接清点自己军队的人数,只要让士兵先后以三人一排、
五人一排、七人一排地变换队形,而他每次只掠一眼队伍的排尾就知道总人数了。输入 3
个非负整数 a,b,c,表示每种队形排尾的人数(a
(或报告无解)。已知总人数不小于 10,不超过 100。
9.一辆卡车违反交通规则,撞人后逃逸。现场有三位目击证人,但都没有记住车号,只记下
车号的一些特征。甲说:牌照的前两位数字是相同的。乙说:牌照的后两位数字是相同的,
但是和前两位不同。丙说;四位的车号刚好是一个整数的平方(四位车牌号>999)。请用以上
\10. 有一对兔子,从出生后的第三个月起每个月都生一对兔子。小兔子长到三个月以后每个
月都生一对兔子。小兔子长到第三个月以后每个月又生一对兔子。假设所有的兔子都不死,
问 30 个月内每个月的兔子总数是多少。
11.如果整数 A 的全部因子(包括 1,不包括 A 本身)之和等于 B,且整数 B 的全部因子(包
括 1,不包括 B 本身)之和等于 A。则将 A 和 B 称为亲密数。求 3000 以内的全部亲密数。
函数就是一系列指令的集合,可以完成某一些特定的功能
返回类型 函数名(参数列表)
编写一个函数,能够对任意两个整数实现加法操作,并且返回结果
1.编写一个函数,求两个数的最大公约数并返回。
2.编写一个函数,求一个 int 类型数组所有成员的平均值,并输出数组中最接近平均值的成
3.实现一个函数判断 year 是不是润年,是返回 1,不是返回 0。
4.实现一个函数,判断参数是不是素数,是返回 1,不是返回 0。
5.编写一个函数,可以将字符串 2 合并到字符串 1 中。
6.编写一个函数,打印 x*x 乘法表 x 为参数。
8.编写一个函数,输出 x 以内所有的素数,x 为参数
9.一函数,输入一行字符,将此字符串中最长的单词输出,单词间以空格分隔。
10.定义一个函数,使给定的二维数组(3×3)转置,即行列转换,并输出转换前和转换后的数据。
函数声明有返回类型,必须使return进行返回
函数有返回值,就是一个值
一个函数只能执行一次return
return 可以写多个,但只能执行一次
建议大家定义一个变量r
定义返回结果
数组作为参数传值的时候,是把当前数组的地址,是通过地址进行传递
int类型作为参数传递的时候传递的是值
函数运行时所使用的内存称为栈 |
当程序用完之后依然没有使用栈内存,会报错 |
尽量不要使用,递归非常浪费内存
当你需要一个容器能够存储1个字节,怎么做?//char
当你需要一个容器能够存储4个字节,你会怎么做?//int arr[10]
数组解决不了 成员之间类型不一样的问题
结构体在定义时要字节对齐
比如都是char,会自动扩充至int
结构体的大小未必是整体大小
当数组内的类型不一样时,定义结构体类型
可以,但是要赋值,否则会出现乱码
6.定义一个结构体表示点的 x,y 坐标,依次读入三个正整形坐标值,输出三个点构成的三角形面积
7.在全局定义的结构体和在局部定义的结构体有什么区别?
编写一函数,计算两个日期之间的时间差,并将其值返回。
日期以年、月、日表示。“时间差”以天数表示。注意考虑日期之间的闰年。
函数的输入参数为日期 1 和日期 2,函数的返回值为时间差,单位为天数。
编写一程序,在主函数中输入两个日期,调用上述函数计算两个日期之间的时间差,并将结果输出。
结构体参数为int/char/float/double等基本类型时,传递的是值,是在复制内容
参数为数组类型时,传递的是地址
允许p=p2,结构类型相同
定义结构体包含如下信息:学生姓名,性别,语文数学英语成绩。
设某班有20个学生,请实现以下功能:
1.可以录入学生信息。
2.可以删除学生信息。
3.可以查找学生信息。
1.带有*变量类型的标准写法:变量类型 * 变量名
2.任何类型都可以带 * 加上以后就是新的类型,统称为“指针类型”
指针本质类型的4个字节
运算幅度是类型砍掉一个类型之后的类型宽度
1.不带 * 类型的变量,++ 或者 – 都是加 1或者减1
2.带类型的变量,++或者–新增(减少)的数量是去掉一个后变量的宽度
指针类型的变量宽度永远是4字节
任何一个变量都加 * 变为新的类型
0 |
1(当前内存的编号,代号不需要存储) |
指针: 间接引用运算符 *
变量也有两个属性:地址和值。地址就是变量在计算机内部的名称
许多程序中,地址都归计算机管,对程序员隐藏。然而在C中,可以通过&运算符访问地址,通过*运算符获得地址上的值。
简而言之,普通变量把值作为基本量,把地址作为通过&运算符获得的派生量,而指针变量把地址作为基本量,把值作为通过*运算符获得的派生量。
有时需要把数组设置为只读,这样程序只能从数组中检索值。不能把新值写入数组,要创建只读数组,应该用const声明数组
如果我在程序编译的时候,我并不知道存多少
导致出现一个空白的内存
整个堆空间有一部分用了,有一部分没用,整个内存没有连续,当你申请一个较大内存的时候
4.文件属性:只读、可读可写,隐藏
预处理一般是指在程序源代码被转换为二进制代码之前,由预处理器对程序源代码文本进行处理,处理后的结果再由编译器进一步编译。
预处理功能主要包括宏定义,文件包含,条件编译三部分