信息学竞赛七年级培训课程课件C++

信息学竞赛培训课程第一期：走进信息竞赛与C++关于课程ABOUTI.上课时间：每周四下午16:05-17:35每周一~周四晚18:10-18:50II.预期进度：七年级上学期：语法基础七年级下学期：算法01、关于时间02、检测方式

①期末测验②编程技能大赛③NOIP全国赛④CSP-J/S全国赛课程内容CONENTS01、第一个C++程序02、简单程序设计03、选择结构04、循环结构赋值语句运算符与表达式常量与变量标准数据类型数据输入输出顺序结构实例if-else语句switch语句for语句while语句do-while语句循环嵌套if语句课程内容CONENTS05、数组06、函数07、结构体递推函数二维数组字符串一维数组递归08、基础算法数据排序高精度算法贪心算法信息学竞赛，梦开始的地方学生可以参加的竞赛多，大大小小的竞赛令人眼花瞭乱，但大多都是没用的。只有数学、物理学、化学、信息学、生物学的全国奥林匹克分区联赛、全国奥林匹克竞赛是由国家教育部主办的。一般来说，在奥赛中获奖的同学才能得到国家教育部的表彰，才能得到著名大学的青睐。青少年信息学奥林匹克联赛省级赛区中获得全国一等奖或全国青少年信息学奥林匹克竞赛获得一、二、三等奖的初中生都有保送一级达标校的资格。走进信息学竞赛与c++00信息学竞赛简介信息学竞赛就是计算机竞赛，考的是学生用计算机高级语言，利用各种算法解决问题的能力。其中的联赛是由中国国家教育部、中国信息学奥林匹克竞赛委员会、中国科协、中国计算机协会联合主办，面向所有学生的，是普及性的。它分初赛及复赛两个形式。初赛每年10月举行，形式为笔试，主要考计算机基础知识、数学知识、算法描述、程序阅读能力等。复赛在11月举行，形式为上机试，一般4个题目，只有在初赛中取得较好成绩的选手才能进入复赛。走进信息学竞赛与c++00信息学竞赛简介参与信息学竞赛的好处参与信息学奥赛就是为了拿奖，为了保送上高中吗？绝对不是的，学习的过程才是最重要的。接受这个培训的收获往往是终生受用的。走进信息学竞赛与c++001、开发智力，提高思维。

2、学到一门对日后发展有极大好处的基础本领。

3、培养沉稳坚韧的性格，严密谨慎的处世方式。

4、培养积极进取,勇于拼博的精神。

几个常见问题的解答走进信息学竞赛与c++001、参加奥赛跟学习有冲突吗？2、需要很高的智商吗？3、会很累很大压力吗？强调走进信息学竞赛与c++001、信息学是竞赛，不是社团。2、参加信息学不是不完成其他科目作业的借口。3、要求每个同学带一个笔记本，一个u盘。第一个C++程序01编译工具：DEV-c++打开界面：文件——新建——源代码（快捷键：ctrl+n）编译运行：下图箭头处（快捷键：F11）保存：文件——另存为cpp文件（快捷键：ctrl+s）第一个C++程序01默写“第一个c++程序”代码，要求输出“HelloWorld!”简单程序设计顺序结构实例02刚才的简单程序已体现出处理问题的步骤的顺序关系，每条语句按自上而下的顺序依次执行一次，这种自上而下依次执行的程序称为顺序结构程序。例2-1已知一位小朋友的电影票价是10元，计算x位小朋友的总票价是多少？简单程序设计赋值语句02在C++语言中，“=”作为赋值运算符，而不表示“等于”判断。变量=表达式；注意：I.变量=变量=…=表达式是成立的例如，“a=b=c=d=e=5;”，它实际上等价于：e=5;d=e;c=d;b=c;a=b;II.如果赋值运算符两边的数据类型不同，系统将会自动进行类型转换，即将赋值运算符右边的数据类型转换成左边的变量类型。例2-2输入两个正整数A和B，试交换A、B的值（使A的值等于B，B的值等于A）。简单程序设计运算符和表达式021.算术运算符

用于各类数值运算。包括加(+)、减(-)、乘(*)、除(/)、求余(或称模运算，%)、自增(++)、自减(--)共七种。2.关系运算符

用于比较运算。包括大于(>)、小于(<)、等于(==)、大于等于(>=)、小于等于(<=)和不等于(!=)六种。3.逻辑运算符

用于逻辑运算。包括与(&&)、或(||)、非(!)三种。例2-3输入两个正整数a和b，试求a与b之间的和、差、积、商以及余数（a在前）。mouth_age√s2√m.k.jack×a<=9b×9y×简单程序设计常量和变量02常量是指在程序中使用的一些具体的数、字符。在程序运行过程中，其值不能被更改。常量的定义：const符号常量=常量字串;例如：constintPI=3;变量代表了一个存储单元，其中的值是可以改变的，因此称为变量。变量的定义：数据类型变量名注意：变量名只能由数字、字母及下划线（_)组成，且数字不能放在开头。例2-4下列变量名中，不符合命名规范的有哪些？mouth_ages2m.k.jacka<=9b9y√√×××简单程序设计标准数据类型02整型[long]int-231～231-14(32位)单精度实型float-3.4E-38～3.4E+384(32位)6～7位双精度实型double-1.7E+308～1.7E+3088(64位)15～16位布尔变量bool真true或假false之一1(8位)字符变量char1(8位)数据类型定义标识符数值范围占字节数有效位数暂时要求掌握C++语言提供了丰富的数据类型,现在介绍几种基本的数据类型：整型、实型、字符型。它们都是系统定义的简单数据类型，称为标准数据类型。简单程序设计标准数据类型02在C++语言中，整型类型标识符为int。根据整型变量的取值范围又可将整型变量定义为以下8种整型类型：数据类型定义标识符占字节数数值范围数值范围短整型short[int]2(16位)-32768～32767-215～215-1整型[long]int4(32位)-2147483648～2147483647-231～231-1长整型long[int]4(32位)-2147483648～2147483647-231～231-1超长整型longlong[int]8(64位)-9223372036854775808～9223372036854775807-263～263-1无符号整型

unsigned[int]2(16位)0～655350～216-1无符号短整型unsignedshort[int]2(16位)0～655350～216-1无符号长整型unsignedlong[int]4(32位)0～42949672950～232-1无符号超长整型unsignedlonglong8(64位)0～184467440737095516150～264-1简单程序设计数据输入输出02cin/cout流cin>>a;cout<<a;格式化输入输出scanf(“%d”,&a);printf(“%d”,a);例2-5输出保留3位小数的浮点数读入一个单精度浮点数，保留3位小数输出这个浮点数。输入:只有一行，一个单精度浮点数。输出:也只有一行，读入的单精度浮点数。样例输入:12.34521样例输出:12.345简单程序设计练习02练习1温度表达转化利用公式C=5*(F-32)/9(其中C表示摄氏温度，F表示华氏温度)进行计算转化,输入华氏温度f，输出摄氏温度c，要求精确到小数点后5位。输入:输入一行，包含一个实数f，表示华氏温度。（f>=-459.67）输出:输出一行，包含一个实数，表示对用的摄氏温度，要求精确到小数点后5位。样例输入:41样例输出:5.00000简单程序设计练习02练习2输入一个三位数，要求把这个数的百位数与个位数对调，输出对调后的数。样例输入:

234样例输出:

432

简单程序设计练习02练习3等差数列末项计算给出一个等差数列的前两项a1，a2，求第n项是多少。输入:输入仅一行，包括a1,a2,n(-100<=a1,a2<=100,0<=n<=1000)。输出:

一个整数，即n的值。样例输入:14100样例输出:298选择结构概述03程序由若干条语句组成，各语句按照顺序一条一条地执行，这种顺序结构是简洁的。但在现实世界中，在解决问题的过程中，不可避免地遇到需要进行选择、或需要循环工作的情况。这时，程序执行的顺序需要发生变化，而非从前向后逐一执行。因此，程序中除了顺序结构以外，通常还有选择结构、循环结构以及转移机制。C++提供三种选择结构，即if选择结构、if-else选择结构和switch选择结构。选择结构if语句03if语句格式：if(条件表达式)语句1；条件表达式语句1falsetrue例3-1读入一个整数a，如果a为偶数在屏幕上输出yes。选择结构if-else语句03if-else语句格式：if(条件表达式)

语句1；else语句2；例3-2输入温度t的值，判断是否适合晨练。(25<=t<=30，则适合晨练yes，否则不适合no)条件表达式语句块2flasetrue语句块1选择结构switch语句03语句格式：switch（表达式）{case常量表达式1：语句序列1；break;case常量表达式2：语句序列2；break;……case常量表达式n：语句序列n；break;default:语句序列n+1；}在使用switch语句时，还应注意以下几点：1.case语句后的各常量表达式的值不能相同，否则会出现错误码。2.每个case或default后，可以包含多条语句，不需要使用“{”和“}”括起来。3.各case和default子句的先后顺序可以变动，这不会影响程序执行结果。4.default子句可以省略，default后面的语句末尾可以不必写break。程序设计风格提示：写switch语句时，switch（表达式）单独一行，各case分支和default分支要缩进两格并对齐，分支处理语句要相对再缩进两格，以体现不同层次的结构。应用条件语句可以很方便地使程序实现分支，但是出现分支比较多的时候，虽然可以用嵌套的if语句来解决，但是程序结构会显得复杂，其至凌乱。为方便实现多情况选择，C++提供了一种switch开关语句。例3-3根据从键盘上输入的表示星期几的数字，对应输出它的英文名称。选择结构练习03练习4晶晶赴约会

晶晶的朋友贝贝约晶晶下周一起去看展览，但晶晶每周的1、3、5有课必须上课，请帮晶晶判断她能否接受贝贝的邀请，如果能输出YES；如果不能则输出NO。注意YES和NO都是大写字母！输入:输入有一行，贝贝邀请晶晶去看展览的日期，用数字1到7表示从星期一到星期日。输出:输出有一行，如果晶晶可以接受贝贝的邀请，输出YES，否则，输出NO。注意YES和NO都是大写字母！样例输入:2样例输出:YES选择结构练习03练习4晶晶赴约会

晶晶的朋友贝贝约晶晶下周一起去看展览，但晶晶每周的1、3、5有课必须上课，请帮晶晶判断她能否接受贝贝的邀请，如果能输出YES；如果不能则输出NO。注意YES和NO都是大写字母！输入:输入有一行，贝贝邀请晶晶去看展览的日期，用数字1到7表示从星期一到星期日。输出:输出有一行，如果晶晶可以接受贝贝的邀请，输出YES，否则，输出NO。注意YES和NO都是大写字母！样例输入:2样例输出:YES选择结构练习03练习5骑车与走路在长郡校园里，没有自行车，上课办事会很不方便。但实际上。并非去办任何事情都是骑车快,因为骑车总要找车、开锁、停车、锁车等,这要耽误一些时间。假设找到自行车，开锁并车上自行车的时间为27秒；停车锁车的时间为23秒；步行每秒行走1.2米，骑车每秒行走3.0米。请判断走不同的距离去办事,是骑车快还是走路快。如果骑车快，输出一行"Bike"；如果走路快，输出一行"Walk"；如果一样快，输出一行"All"。输入:输入一行，包含一个整数，表示一次办事要行走的距离,单位为米。输出:输出一行,如果骑车快,输出一行"Bike";如果走路快,输出一行"Walk";如果一样快,输出一行"All"。样例输入:120样例输出:Bike选择结构练习03练习6最大数输出输入三个整数，数与数之间以一个空格分开。输出一个整数，即最大的整数。输入:输入为一行，包含三个整数（大小不同），数与数之间以一个空格分开。输出:输出一行，包含一个整数，即最大的整数。样例输入:102056样例输出:56循环结构概述04在解决问题的过程中，有时候我们需要将同一语句重复执行，这个时候我们可以用到循环结构。C++提供三种选择结构，即for语句，while语句，do-while语句。循环结构for语句04for语句格式：for（控制变量初始化表达式；条件表达式；增量表达式）{语句块（循环体）}例：将控制变量从1变到100，增量为1

for(inti=1;i<=100;i++)例4-1计算1+2+3+...+100的和。循环结构while/do-while语句04while语句格式：while（条件表达式）{语句块（循环体）}例4-2求1+2+3+...+n的和大于100时，n的最小值。do-while语句格式：do{语句块（循环体）}while（条件表达式）思考？循环结构循环嵌套04例4-3对于给定的自然数n(n<20)，在屏幕上输出仅由“*”构成的n行的直角三角形。例如：当n=5时，输出：

* ** *** **** *****循环结构练习04练习7求平均年龄

班上有学生若干名，给出每名学生的年龄（整数），求班上所有学生的平均年龄，保留到小数点后两位。输入:

第一行有一个整数n（1<=n<=100），表示学生的人数。其后n行每行有1个整数，表示每个学生的年龄，取值为15到25。输出:

输出一行，该行包含一个浮点数，为要求的平均年龄，保留到小数点后两位。样例输入:21817样例输出:17.50循环结构练习04练习8满足条件的数将正整数m和n之间(包括m和n)能被17整除的数累加，其中0<m<n<1000。输入:一行，包含两个整数m和n，其间，以一个空格间隔。输出:输出一行，包行一个整数，表示累加的结果。样例输入:5085样例输出:204循环结构练习04练习9求100－999中的水仙花数。若三位数ABC，ABC=A^3+B^3+C^3，则称ABC为水仙花数。例如153，1^3+5^3+3^3=1+125+27=153，则153是水仙花数。输入：无输出：水仙花数，中间用空格隔开。样例：153370371407数组05例5-1输入50个学生的某门课程的成绩，打印出低于平均分的学生序号与成绩。如果，用简单变量a1，a2,…，a50存储这些数据，要用50个变量保存输入的数据，程序片断如下：cin>>a1>>a2>>…>>a10;…cin>>a41>>a42>>…>>a50;我们需要把一大批具有相同性质的数据组合成一个新类型的变量，可以用简单的程序（比如循环50次）对这个新变量的各个分量进行相同的处理，每个分量仍然保留单个变量的所有性质（在上面的例子中，各分量是整型变量或实型变量的性质）。数组一维数组05一维数组的定义当数组中每个元素只带有一个下标时，我们称这样的数组为一维数组。数组的定义格式如下：

类型标识符数组名[常量表达式]说明：①数组名的命名规则与变量名的命名规则一致。②常量表达式表示数组元素的个数。可以是常量和符号常量，但不能是变量。例如：

inta[10];//数组a定义是合法的

intb[n];

//数组b定义是非法的a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]数组一维数组05一维数组的初始化可以在定义时完成：

类型标识符数组名[常量表达式]={值1，值2，…}inta[5]={1,2,3,4,5}//写出全部inta[5]={1,2,3}//写出部分inta[5]={};//初始化为0例5-2输入10个数,要求程序按输入时的逆序把这10个数打印出来。一维数组的输入输出一般用循环输入输出：

for(inti=1;i<=n;i++)cin>>a[i];数组一维数组05例5-1输入50个学生的某门课程的成绩，打印出低于平均分的学生序号与成绩。数组一维数组05例5-3输入n个学生的某门课程的成绩，打印出低于平均分的学生序号与成绩。(n<=100)数组一维数组05例5-4陶陶摘苹果【Noip2005普及组第1题】陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。输入:包括两行数据。第一行包含10个100到200之间(包括100和200)的整数(以厘米为单位)分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间(包含100和120)的整数(以厘米为单位)，表示陶陶把手伸直的时候能够达到的最大高度。输出:包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。样例输入:100200150140129134167198200111110样例输出:5数组二维数组05二维数组的定义数据类型数组名[常量表达式1][常量表达式2]；inta[3][5];二维数组的输入输出for(inti=0;i<=2;i++){for(intj=0;j<=4;j++){cin>>a[i][j];}}表示a是二维数组（相当于一个3*5的表格），共有3*5=15个元素，它们是：a[0][0]a[0][1]a[0][2]a[0][3]a[0][4]a[1][0]a[1][1]a[1][2]a[1][3]a[1][4]a[2][0]a[2][1]a[2][2]a[2][3]a[2][4]二维数组的初始化inta[3][5]={{0,0,0,0,0},{1,1,1,1,1},{2,2,2,2,2}}数组二维数组05例5-5输入一个6*6的矩阵（方阵），把矩阵二条对角线上的元素值加上10，然后输出这个新矩阵。数组二维数组05例5-6矩阵交换行给定一个5*5的矩阵(数学上，一个r×c的矩阵是一个由r行c列元素排列成的矩形阵列)，将第n行和第m行交换，输出交换后的结果。输入:输入共6行，前5行为矩阵的每一行元素,元素与元素之间以一个空格分开。第6行包含两个整数m、n，以一个空格分开（1<=m,n<=5）。输出:输出交换之后的矩阵，矩阵的每一行元素占一行，元素之间以一个空格分开。样例输出:3082456783930537214612212样例输入:122125678393053721463082415数组字符串05

一、字符类型

字符类型为由一个字符组成的字符常量或字符变量。

字符常量定义:

const字符常量=‘字符’

字符变量定义:

char字符变量;

字符类型是一个有序类型,字符的大小顺序按其ASCⅡ代码的大小而定。

数组字符串05

二、字符数组

字符数组是指元素为字符的数组。字符数组是用来存放字符序列或字符串的。字符数组也有一维、二维和三维之分。

1、字符数组的定义格式

字符数组定义格式同于一般数组，所不同的是数组类型是字符型，第一个元素同样是从ch1[0]开始，而不是ch1[1]。具体格式如下：

[存储类型]char数组名[常量表达式1]…

例如：

charch1[5];

//数组ch1是一个具有5个字符元素的一维字符数组

charch2[3][5];//数组ch2是一个具有15个字符元素的二维字符数组

2.字符数组的赋值字符数组赋值类似于一维数组，赋值分为数组的初始化和数组元素的赋值。初始化的方式有用字符初始化和用字符串初始化两种，也有用初始值表进行初始化的。(1).用字符初始化数组例如：charchr1[5]={‘a’,‘b’,‘c’,‘d’,‘e’};初始值表中的每个数据项是一个字符，用字符给数组chr1的各个元素初始化。当初始值个数少于元素个数时，从首元素开始赋值，剩余元素默认为空字符。

字符数组中也可以存放若干个字符，也可以来存放字符串。两者的区别是字符串有一结束符(‘\0’)。反过来说，在一维字符数组中存放着带有结束符的若干个字符称为字符串。字符串是一维数组，但是一维字符数组不等于字符串。例如：charchr2[5]={‘a’,‘b’,‘c’,‘d’,‘\0’};即在数组chr2中存放着一个字符串“abcd”。数组字符串05(3).数组元素赋值字符数组的赋值是给该字符数组的各个元素赋一个字符值。例如：charchr[3];

chr[0]=‘a’;chr[1]=‘b’;chr[2]=‘c’;(4).字符常量和字符串常量的区别①两者的定界符不同，字符常量由单引号括起来，字符串常量由双引号括起来。②字符常量只能是单个字符，字符串常量则可以是多个字符。③可以把一个字符常量赋给一个字符变量，但不能把一个字符串常量赋给一个字符变量。④字符常量占一个字节，而字符串常量占用字节数等于字符串的字节数加1。增加的一个字节中存放字符串结束标志‘\0’。例如：字符常量‘a’占一个字节，字符串常量“a”占二个字节。数组字符串05三、字符串的输入与输出字符串可以作为一维字符数组来处理，那么字符串的输入和输出也可以按照数组元素来处理。本节仅介绍将字符串作为一个整体进行输入和输出的语句。1、输入从键盘输入一个字符数组可以使用scanf语句或gets语句。(1)scanf语句格式：scanf(“%s”,字符串名称);说明：①这里的字符串名称之前不加&这个取地址符。例如：scanf(“%s”,&s1)是错误的。②系统会自动在输入的字符串常量后添加‘\0’标志，因此输入时，仅输入字符串的内容即可。

③输入多个字符串时，以空格分隔。例如：scanf(“%s%s%s”,s1,s2,s3)；从键盘分别输入Letusgo，则三个字符串分别获取了三个单词。反过来可以想到，如果仅有一个输入字符串名称的情况下，字符串变量仅获取空格前的内容。例如：scanf(“%s”,s1)；从键盘分别输入Letusgo，则仅有第一个单词被获取，即s1变量仅获取第一个单词Let。(2)gets语句格式：gets(字符串名称)；说明：使用gets只能输入一个字符串。例如：gets(s1,s2)；是错误的。使用gets，是从光标开始的地方读到换行符也就是说读入的是一整行，而使用scanf是从光标开始的地方到空格，如果这一行没有空格，才读到行尾。例如：scanf(“%s”,s1)；gets(s2)；对于相同的输入HelloWorld!。s1获取的结果仅仅是Hello，s2获取的结果则是HelloWorld!数组字符串05(2)gets语句格式：gets(字符串名称)；说明：使用gets只能输入一个字符串。例如：gets(s1,s2)；是错误的。使用gets，是从光标开始的地方读到换行符也就是说读入的是一整行，而使用scanf是从光标开始的地方到空格，如果这一行没有空格，才读到行尾。例如：scanf(“%s”,s1)；gets(s2)；对于相同的输入HelloWorld!。s1获取的结果仅仅是Hello，s2获取的结果则是HelloWorld!数组字符串052、输出向屏幕输出一个字符串可以使用printf语句或puts语句。(1)printf语句格式：printf(“%s”,字符串名称);说明：①用%s格式输出时，printf的输出项只能是字符串(字符数组)名称，而不能是数组元素。例如：printf(“%s”,a[5]);是错误的。②输出字符串不包括字符串结束标志符‘\0’。(2)puts语句格式：puts(字符串名称);说明：puts语句输出一个字符串和一个换行符。对于已经声明过的字符串a，printf(“%s\n”,a)和puts(a)是等价的。例5-7在应用计算机编辑文档的时候，我们经常遇到替换任务。如把文档中的“电脑”都替换成“计算机”。现在请你编程模拟一下这个操作。输入两行内容，第1行是原文(长度不超过200个字符)，第2行包含以空格分隔的两个字符A和B，要求将原文中所有的字符A都替换成字符B，注意：区分大小写字母。输入样例：IloveChina.IloveBeijing.IU输出样例：UloveChina.UloveBeijing.数组字符串05例5-8凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。输入输出格式输入格式：输入文件只有一行，一个字符串s。输出格式：输出文件只有一行，包含一个整数，即作文标题的字符数（不含空格和换行符）。输入输出样例输入样例Ca23输出样例4注：2018年noip普及组第一题数组字符串05函数与递归函数06通常，在程序设计中，我们会发现一些程序段在程序的不同地方反复出现，此时可以将这些程序段作为相对独立的整体，用一个标识符给它起一个名字，凡是程序中出现该程序段的地方，只要简单地写上其标识符即可。这样的程序段，我们称之为子程序。

在一个程序中可以只有主程序而没有子程序(本章以前都是如此)，但不能没有主程序，也就是说不能单独执行子程序。

在此之前，我们曾经介绍并使用了C++提供的各种标准函数，如abs(),sqrt()，swap()等等，这些系统提供的函数为我们编写程序提供了很大的方便。函数与递归函数06例6-1求：1!+2!+3!+……+n！#include<iostream>usingnamespacestd;intmain(){ intsum=0; intn; cin>>n; for(inti=1;i<=n;i++){ intjs=1; for(intj=1;j<=i;j++){ js*=j; } sum+=js; } cout<<sum; return0;}每次重复，单独拿出来函数与递归函数06例6-1求：1!+2!+3!+……+n！intmain(){ intsum=0; intn; cin>>n; for(inti=1;i<=n;i++){ sum+=js; } cout<<sum; return0;}#include<iostream>usingnamespacestd;现在的问题是：C++不提供js(x)这样一个标准函数，这个程序是通不过的，没关系，我们编写自己的函数。intjs(intn){ intk=1; for(inti=1;i<=n;i++){ k*=i; } returnk;}sum+=js(i);函数与递归函数061.函数的定义

1.函数定义的语法形式

数据类型函数名（形式参数表） { 函数体//执行语句 }

intjs(intn){

intk=1;

for(inti=1;i<=n;i++){

k*=i;

}

returnk;

}

注：函数的数据类型是函数的返回值类型（若数据类型为void,则无返回值）函数与递归函数062.函数的声明和调用

#include<iostream>

usingnamespacestd;

intjs(int);//函数的声明

intmain()

{

intsum=0;

for(inti=1;i<=10;++i)

sum+=js(i);//函数的调用

cout<<"sum="<<sum<<endl;

return0;

}

intjs(intn)//定义的函数体

{

ints=1;

for(inti=1;i<=n;++i)

s*=i;

returns;//函数的返回值

}函数与递归函数06例6-2用函数的方法，计算如图多边形的面积s，保留三位小数。三角形a,b,c面积s求法：p=(a+b+c)/2；s=sqrt(p*(p-a)*(p-b)*(p-c));输入样例：1111111输出样例：1.299函数与递归函数06例6-3计算组合数C(m,n)的值(n<=m<=10)。组合数C(m,n)可以理解为从m个数中任意取出n个数的所有情况数。求这个数值，有一个经典的计算方法：C(m,n)=m!/((m-n)!n!)。输入两个数m,n。输出组合数C(m,n).输入样例：52输出样例：10函数与递归函数06例6-4定义一个函数check(n,d)，让它返回一个布尔值。

如果数字d在正整数n的某位中出现则送回true，否则送回false。

例如：check(325719,3)==true；check(77829,1)==false；

输入两个数n，d。输出true或者false。输入样例：3257193输出样例：true对所有数据，0<=n<=100,0<=d<=9.函数与递归递推06

递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。

递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。#D函数与递归递推06例6-5现有斐波那契数列（Fibonacci），它的前若干项是1，1，2，3，5，8，13，21，34……求此数列第n项（3<=n<=100）。#D函数与递归递推06例6-6楼梯有n个台阶，上楼可以一步上一阶，也可以一步上两阶。一共有多少种上楼的方法？这是一道计数问题。在没有思路时，不妨试着找规律。n=5时，一共有8种方法：

5=1+1+1+1+1

5=2+1+1+1

5=1+2+1+1

5=1+1+2+1

5=1+1+1+2

5=2+2+1

5=2+1+2

5=1+2+2函数与递归递归06递归程序设计是C++语言程序设计中的一种重要的方法，它使许多复杂的问题变得简单，容易解决了。

递归特点是：函数或过程调用它自己本身。

其中直接调用自己称为直接递归；

而将A调用B，B以调用A的递归叫做间接递归。

函数与递归递归06例6-7给定n（1<=n<=10000）,用递归的方法计算1+2+3...+n。本题可以用递归方法求解，其原因在于它符合递归的三个条件：

(1)本题是累加问题：当前和=前一次和+当前项，而前一次和的计算方法与其相同，只是数据不同s(n)=s(n-1)+n;【递归公式】(2)给定n,所以是有限次的递归调用；【有限次数】

(3)结束条件是当n=1，则s=1。【边界条件】函数与递归递归06例6-8输入n（n<=10000）个数，再输入x，用二分法判断它是否在这n个数中，如果存在则输出：“YES”否则输出“NO”。二分查找算法：

（1）设有N个数，存放在A数组中，待查找数为X，用L指向数据的低端，用R指向数据的高端，MID指向中间：

（2）若X=A[MID]输出“YES”；

（3）若X<A[MID]则到数据前半段查找：R不变，L=MID+1，计算新的MID值，并进行新的一段查找；

（4）若X>A[MID]则到数据后半段查找：L不变，R=MID-1，计算新的MID值，并进行新的一段查找；

（5）若L>R都没有查找到，则输出“NO”。函数与递归递归06例6-9用递归算法求x^n。

【分析】把Xn分解成：x^0=1(n=0)x^1=x*x0(n=1)x^2=x*x1(n>1)x^3=x*x2(n>1)……(n>1)因此将x^n转化为：x*xn-1，，其中求xn-1又用求xn的方法进行求解。 ①定义子程序x^n(intn)求X^n;如果n>=1则递归调用x^n(n-1)求x^n—1; ②当递归调用到达n=0时终止调用,然后执行本“层”的后继语句; ③遇到子程序运行完，就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后继语句; ④继续执行步骤③，从调用中逐“层”返回，最后返回到主程序。结构体07在实际问题中，一组数据往往具有不同的数据类型。例如，人口大普查时，我们需要记录每一位公民的姓名，年龄，性别，住址，身份证号码。这些信息分别要用整型，字符型，字符串型来记录。为了解决问题，C++语言给出了另一种构造数据类型——“结构体”，它在数据存储方面相当于其他高级语言中的记录，但它有着面向对象的优势。结构体07结构体(struct)定义和操作1.定义结构体及结构体变量结构体变量的定义有两种形式：(1)定义结构体类型的时候同时定义变量struct结构体类型名{//其中struct是关键字成员表;//可以有多个成员成员函数;//可以有多个成员函数，也可以没有}结构体变量表;//可以同时定义多个结构体变量，用“，”隔开例如：structstudent{//定义类型名叫student的struct类型 stringname; intchinese,math; inttotal;}a[110];//同时定义了a数组变量(2)先定义结构体再定义结构体变量struct结构体类型名{成员表;成员函数;};结构体名结构体变量表//同样可以同时定义多个结构体变量例如：structstudent{ stringname; intchinese,math; inttotal;};studenta[110];在定义结构体变量时注意，结构体变量名和结构体名不能相同。在定义结构体时，系统对其不分配实际内存。只有定义结构体变量时，系统才为其分配内存。结构体072.结构体变量的特点（1）结构体变量可以整体操作，例如：swap(a[j],a[j+1]);（2）结构体变量的成员访问也很方便、清晰，例如：cin>>a[i].name;（3）结构体变量的初始化和数组的初始化类似，例如：studentop={"gaoxiang",89,90,179};3.成员调用结构体变量与各个成员之间引用的一般形式为：

结构体变量名.成员名对于上面定义的结构体变量，我们可以这样操作：cin>>a[i].name;//一般情况下不能写cin>>a[i]; a[i].total=a[i].chinese+a[i].math;//就像用整型变量一样实际上结构体成员的操作与该成员类型所具有的操作是一致的。成员运算符“.”在存取成员数值时使用，其优先级最高，并具有左结合性。在处理包含结构体的结构体时，可记作：strua.strub.membb这说明结构体变量strua有结构体成员strub；结构体变量strub有成员membb。4.成员函数调用结构体成员函数调用的一般形式为：结构体变量名.成员函数结构体成员函数默认将结构体变量作为引用参数。结构体07例7-1输入N(0<=N<=100)个学生的姓名和语文、数学的得分，按总分从高到低输出，分数相同的按输入先后输出。输入格式：第1行，有一个整数N，N的范围是[1…100]；下面有N行，每行一个姓名，2个整数。姓名由不超过10个的小写字母组成，整数范围是[0…100]。输出格式：总分排序后的名单，共N行，每行格式：姓名语文数学总分。输入样例：4gaoxiang7896wangxi7099liujia9087zhangjin7891输出样例：liujia9087177gaoxiang7896174wangxi7099169zhangjin7891169结构体07例7-1输入N(0<=N<=100)个学生的姓名和语文、数学的得分，按总分从高到低输出，分数相同的按输入先后输出。结构体07例7-2离散化基础。以后要学习使用的离散化方法编程中，通常要知道每个数排序后的编号（rank值）。输入格式：第1行，一个整数N，范围在[1…10000]；第2行，有N个不相同的整数，每个数都是int范围的。输出格式：依次输出每个数的排名。输入样例:582694输出样例:41352结构体07例7-2离散化基础。以后要学习使用的离散化方法编程中，通常要知道每个数排序后的编号（rank值）。练习05-07练习10校门外的树某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。输入:第一行有两个整数L（1<=L<=10000）和M（1<=M<=100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。对于20%的数据，区域之间没有重合的部分；对于其它的数据，区域之间有重合的情况。输出:包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。样例输入:样例输出:5003298150300100200470471练习05-07练习10校门外的树练习05-07练习11把雌雄各一的一对新兔子放入养殖场中。每只雌兔在出生两个月以后，每月产雌雄各一的一对新兔子。试问第n个月后养殖场中共有多少对兔子。练习05-07练习12计数问题试计算在区间1到n的所有整数中，数字x(0≤x≤9)共出现了多少次？例如，在1到11中，即在1,2,3,4,5,6,7,8,9,10,11中，数字1出现了4次。输入输出格式输入格式：2个整数n,x，之间用一个空格隔开。输出格式：1个整数，表示x出现的次数。输入样例111输出样例4对于100%的数据，1≤n≤1,000,000,0≤x≤9。练习05-07练习12计数问题练习05-07练习13汉诺塔问题①问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图所示。要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？练习05-07练习13汉诺塔问题①练习05-07练习14汉诺塔问题②问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图所示。要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。现要求设计将A柱子上N个盘子搬移到C柱去的方法。练习05-07练习14汉诺塔问题②基础算法高精度算法08高精度计算

利用计算机进行数值计算，有时会遇到这样的问题：有些计算要求精度高，希望计算的数的位数可达几十位甚至几百位，虽然计算机的计算精度也算较高了，但因受到硬件的限制，往往达不到实际问题所要求的精度。我们可以利用程序设计的方法去实现这样的高精度计算。介绍常用的几种高精度计算的方法。基础算法高精度算法08高精度计算中需要处理好以下几个问题：(1)数据的接收方法和存贮方法数据的接收和存贮：当输入的数很长时，可采用字符串方式输入，这样可输入数字很长的数，利用字符串函数和操作运算，将每一位数取出，存入数组中。

voidinit(inta[]){strings;cin>>s; a[0]=s.length(); for(i=1;i<=a[0];i++) a[i]=s[a[0]-i]-'0'; }另一种方法是直接用循环加数组方法输入数据。基础算法高精度算法08例8-1使用字符串输入数据，倒序输出。基础算法高精度算法08高精度计算中需要处理好以下几个问题：(2)高精度数位数的确定位数的确定：接收时往往是用字符串的，所以它的位数等于字符串的长度。(3)进位,借位处理

加法进位：c[i]=a[i]+b[i];if(c[i]>=10){c[i]%=10;++c[i+1];}减法借位：if(a[i]<b[i]){--a[i+1];a[i]+=10;}c[i]=a[i]-b[i];

乘法进位：c[i+j-1]=a[i]*b[j]+x+c[i+j-1];x=c[i+j-1]/10;c[i+j-1]%=10;(4)商和余数的求法商和余数处理：视被除数和除数的位数情况进行处理.基础算法高精度算法08例8-2-1高精度加法。输入两个正整数，求它们的和。856+2551111

A3A2A1+B3B2B1

C4C3C2C1

基础算法高精度算法08例8-2-2高精度减法（第二个可能比第一个大）。输入两个正整数，求它们的差。基础算法数据排序