第6章过程封装函数.ppt

第6章 过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模版变量的作用域变量的存储类别递归函数基于递归的算法,函数的用途,函数是程序设计语言中最重要的部分，是模块化设计的主要工具。每一个C+程序都要用到函数。即使你自己不定义新的函数,在每一个完整的C+程序中都必须有一个main()函数。在C+语言中，字符处理、字符串处理和数学计算都是用函数的方式提供的。,第6章 过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模版变量的作用域变量的存储类别递归函数基于递归的算法,如何写一个函数,函数定义函数的返回值：返回值类型应与定义中的类型标识符一致。C+的函数只能有一个返回值。表示一个函数没有返回值，类型标识符用void。没有返回值的函数也称为过程,类型标识符 函数名（形式参数表）变量定义部分 语句部分,return 返回值；或 return（返回值）；,eg.int max(int a,int b)if(ab)return(a)else return(b);,函数体,函数的命名,函数名是一个标识符，符合标识符命名规范函数名要有意义函数名一般是一个动词短语，表示函数的行为,函数举例无参数、无返回值的函数,打印一个由五行组成的三角形,*,void printstar()cout“*n”;cout“*n”;cout“*n”;cout“*n”;cout“*n”;,函数举例有参数、无返回值的函数,打印一个由n行组成的三角形,void printstar(int numOfLine)int i,j;for(i=1;i=numOfLine;+i)cout endl;for(j=1;j=numOfLine-i;+j)cout;for(j=1;j=2*i-1;+j)cout“*”;,函数举例无参数、有返回值的函数,从终端获取一个1 10之间的整型数int getInput()int num;while(true)cin num;if(num=1,函数举例有参数、有返回值的函数,计算n!,int p(int n)int s=1,i;if(n 0)return(0);for(i=1;i=n;+i)s*=i;return(s);,函数举例返回布尔量的函数,判断某一年是否为润年的函数,bool IsLeapYear(int year)bool leapyear;leapyear=(year%4=0),第6章 过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模版变量的作用域变量的存储类别递归函数基于递归的算法,函数的声明,所有函数在使用前必须被声明，以便让编译器知道用户的用法是否正确。函数声明包括下列内容：函数名函数的参数类型函数的返回类型函数的声明被称为函数的原型，它的形式为：返回类型 函数名（参数表）；参数表中的每个参数说明可以是类型，也可以是类型后面再接一个参数名。如：int max(int,int);int max(int a,int b);,函数说明规则,库函数在调用前需要include相应的头文件。自定义的函数在调用时需要进行函数原型说明。函数原型说明与函数首部写法上需要保持一致，即函数类型、函数名、参数个数和参数顺序必须相同。如果被调函数的定义在主调函数之前，可以不必加声明。如果在所有函数定义之前，在函数外部已经做了函数声明，则在主调函数中无须再作声明。,函数调用,#include int max(int a,int b);main()int x,y;cin x y;cout b)return(a);else return(b);,函数原型说明,函数调用,函数实现,函数调用,#include int max(int a,int b)if(a b)return(a);else return(b);main()int x,y;cin x y;cout max(x+5,y-3);,函数调用,函数实现，无须函数声明,建议用前一种方式！,函数调用,函数调用形式 函数名（实际参数表）eg.max(x,y)；注意：形式参数和实际参数的个数、排列次序、类型要完全相同。实际参数可以是常量、变量、表达式，甚至是另一个函数调用传递方式：值传递 值传递：函数获得了主调程序参数变量值的拷贝。被调程序可以改变这些拷贝，但这对主调程序的环境没有影响。,函数调用,调用方式,1.作为语句：printstar();,2.作为表达式的一部分,如要计算 5!+4!+7!,x=p(5)+p(4)+p(7),3.作为函数的参数,Printstar(p(5)+p(4)+p(7);,函数执行过程,在主程序中计算每个实际参数值用实际参数值初始化形式参数依次执行函数体的每个语句，直到遇见return语句或函数体结束计算return后面的表达式的值，用表达式的值构造一个临时变量回到调用函数，用临时变量置换函数调用，继续主程序的执行,函数执行过程,int p(int);int max(int a,int b)main()int x,y;cin x y;cout n2?n1:n2);,第6章 过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模板变量的作用域变量的存储类别递归函数基于递归的算法,数组作为函数的参数,设计一函数，统计10位同学的平均成绩设计考虑：如何传递参数参数是10位同学的考试成绩，可以用10个整型数来表示。所以有10个整型的形式参数一组同类数据可以用一个数组来描述，所以参数也可以是一个10个元素的整型数组第二种方法更加简练返回值是平均成绩,统计函数的实现,int average(int array10)int i,sum=0;for(i=0;i 10;+i)sum+=arrayi;return sum/10;,average函数的使用,int main()int i,score10;cout scorei;cout 平均成绩是：average(score)endl;return 0;,注意：形式参数是数组，实际参数也是一个数组,一个有趣的现象,在函数average的return语句前增加一个对array3赋值的语句，如array3=90。在main函数的average函数调用后，即return语句前增加一个输出score3的语句结果是什么？你会发现输出的值90而不是80。,数组参数的传递机制,C+语言规定，数组名是数组的起始地址参数传递时，实际参数是数组名，形式参数也是数组名按照值传递，当用实际参数score调用函数 average时，是用score 初始化形式参数数组array。如 score 的首地址为1000，在函数中形参数组array的首地址也为1000。形式参数和实际参数是同一数组！,数组作为函数的参数,在函数中并没有定义新的数组对形式参数数组指定规模是没有意义的形式参数数组不需要指定大小，所以方括号中为空函数如何知道数组的规模？用另一个整型参数表示总结：数组传递需要两个参数，数组名和数组规模,第6章 过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模版变量的作用域变量的存储类别递归函数基于递归的算法,默认参数,对于某些函数，程序往往会用一些固定的值去调用它.例如对于以某种数制输出整型数的函数print：void print(int value,int base);在大多数情况下都是以十进制输出，因此base的值总是为10。C+在定义或声明函数时可以为函数的某个参数指定默认值。当调用函数时没有为它指定实际参数时，系统自动将默认值赋给形式参数。例如，可以将print函数声明为 void print(int value,int base=10);调用print(20)等价于 print(20,10),带有默认参数的函数的使用,C+在说明函数原型时，可以为一个或多个参数指定缺省值。调用此函数时，若缺省某一参数，C+自动以缺省值作为此参数的值。如：int special(int x=2,float y=1.5)调用时可用：special(5,3.2)/x=5;y=3.2 special(6)/x=6;y=1.5 special()/x=2;y=1.5,带有默认参数的函数注意事项,缺省参数无论有几个，都必须放在参数序列的最后，例如：Int SaveName(char*first,char second=“”,char*third=“”,char*fouth=“”);在函数调用时，若某个参数省略，则其后的参数皆应省略而取其缺省值,带有默认参数的函数注意事项,对参数默认值的指定只有在函数声明处有意义。因为函数的默认值是提供给调用者使用的。在不同的源文件中，可以对函数的参数指定不同的默认值。例如对于上面的print函数，如果在某一个功能模块中输出的大多是十进制数，那么在此功能对应的源文件中可以指定base的默认值为10。如果在另一个功能最模块中经常要以二进制输出，那么在此功能模块对应的源文件中可以指定默认值是2。,第6章 过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模版变量的作用域变量的存储类别递归函数基于递归的算法,内联函数,目的是为了提高执行效率。对于任何内联函数，编译器在符号表里放入函数的声明（包括名字、参数类型、返回值类型）。如果编译器没有发现内联函数存在错误，那么该函数的代码也被放入符号表里。在调用内联函数时，编译器直接用内联函数的代码替换函数调用，于是省去了函数调用的开销。,内联函数,内联函数的定义：在函数头部前加保留词inline,#includeinline float cube(float s)return s*s*s;int main()float side;cin side;cout cube(side)endls;return 0;,慎用内联函数,内联以代码复制(膨胀)为代价，省去了函数调用的开销，提高函数的执行效率。如果相比于执行函数体内代码的时间，函数调用的开销可以忽略不计，那么效率的收获会很小。以下情况不宜用内联:如果函数体内的代码比较长，使用内联将导致内存消耗代价较高。如果函数体内出现循环，那么执行函数体内代码的时间要比函数调用的开销大。,第6章 过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模版变量的作用域变量的存储类别递归函数基于递归的算法,重载函数,在传统的C语言中，不允许出现同名函数。当要求写一组功能类似、参数类型或参数个数不同的函数时，必须给它们取不同的函数名 例如某个程序要求找出一组数据中的最大值，这组数据最多有5个数据。我们必须写四个函数：求两个值中的最大值、求三个值中的最大值、求四个值中的最大值和求五个值中的最大值。我们必须为这四个函数取四个不同的函数名，例如：max2,max3,max4和max5。,函数重载,使参数个数不同、参数类型不同或两者兼而有之的两个以上的函数取相同的函数名 如int max(int a1,int a2);int max(int a1,int a2,int a3);int max(int a1,int a2,int a3,int a4);int max(int a1,int a2,int a3,int a4,int a5);,函数重载的实现,由编译器确定某一次函数调用到底是调用了哪一个具体的函数。这个过程称之为绑定（binding，又称为联编或捆绑）。编译器首先会为这一组重载函数中的每个函数取一个不同的内部名字。当发生函数调用时，编译器根据实际参数和形式参数的匹配情况确定具体调用的是那个函数，将这个函数的内部函数名取代重载的函数名。,第6章 过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模版变量的作用域变量的存储类别递归函数基于递归的算法,函数模板,如果一组重载函数仅仅是参数的类型不一样，程序的逻辑完全一样，那么这一组重载函数可以写成一个函数模板。所谓的函数模板就是实现类型的参数化（泛型化），即把函数中某些形式参数的类型定义成参数，称为模板参数 在函数调用时，编译器根据实际参数的类型确定模板参数的值，生成不同的模板函数。,函数模板的定义,一 般的定义形式 template 返回类型 FunctionName(形式参数表)/函数定义体 模板形式参数表可以包含基本数据类型，也可以包含类类型（需加前缀class）template T max(T a,T b)return ab?a:b；,函数模板的使用,maxNum=max(3,7);maxChar=max(z,a);maxDouble=max(3.5,4.6);函数模板的实例化：根据实际参数确定模板参数的值将模板参数的值代入函数模板，形成一个真正的函数,第6章 过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模版变量的作用域变量的存储类别递归函数基于递归的算法,标识符的作用域,一个标识符能被存取的程序部分，称为标识符的作用域标识符的作用域与程序块有关。所谓的程序块是带有声明的复合语句如右框中有两块,Int main(void)int a=2,b=3;cout a b;int a=4;cout a b;cout a b;,标识符的作用域续,在块中说明的标识符是局部的，仅能在本块中和内部的块中存取。当内部块与外部块有同名标识符时，在内部块中屏蔽外部块的同名标识符。在一个函数中，我们不能存取主调程序的变量，即使知道该变量的名字。函数参数对该函数也是局部的，可以将它看成在块内，即函数体内说明的说明的变量。,局部变量和全局变量,局部变量：在块内定义的变量称为局部变量，即使是main函数中定义的变量也是局部的。全局变量：在所有的函数外面定义的变量称为全局变量作用范围：从定义位置到文件结束。如在作用范围外的函数要使用此变量，用关键词extern在函数内说明此全局变量。作用：方便函数间的数据传递请写出下列程序的执行结果：,int p=1,q=5，r=3;int f1()int p=3,r=2;q=p+q+r;cout“f1:p,q,r=“p q r;int f2()p=p+q+r;cout“f2:p,q,r=“p q r;int f3()int q;r=2*r;q=r+p;cout“f3:p,q,r=“p q r;main()f3();cout“after f3:p,q,r=”p q r;f1();cout“after f1:p,q,r=“p q r;f2();cout“after f2:p,q,r=”p q r;,结果：,f3:p,q,r=1 7 6,after f3:p,q,r=1 5 6,f1:p,q,r=3 10 2,after f1:p,q,r=1 10 6,f2:p,q,r=17 10 6,after f2:p,q,r=17 10 6,全局变量的使用说明,全局变量破坏了模块化，建议尽量少使用当全局变量和局部变量同名时，在局部变量的作用范围中全局变量被屏蔽。全局变量的使用将在模块化设计中详细介绍,第6章 过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模版变量的作用域变量的存储类别递归函数基于递归的算法,存储类型,在C+语言中，每个变量有两个属性：类型：变量所存储的数据类型存储类型：变量所存储的区域：标准的变量定义：存储类型 数据类型 变量名；存储类型：自动变量：auto寄存器变量：register外部变量：extern静态变量：static,auto,在函数内或块内定义的变量缺省时是auto。如auto int i；当进入块时，系统为自动变量分配空间。当退出块时，系统释放分配给自动变量的值。因此自动变量的值就消失了。当再次进入该块时，系统重新分配空间。,register,存储在寄存器中，代替自动变量或形参，可以提高变量的访问速度。如无合适的寄存器可用，则编译器把它设为自动变量。,extern,声明一个不在本模块作用范围内的全局变量。如：extern int num;num为一个的全局变量。用途：在某函数中引用了一个声明在本函数后的全局变量时，需要在函数内用extern声明此全局变量。当一个程序有多个源文件组成时，用extern可引用另一文件中的全局变量。,/file1.cpp#include using namespace std;void f();extern int x;/外部变量的声明int main()f();cout in main():x=“x endl;return 0;,/file2.cpp#include using namespace std;int x;/全局变量的定义void f()cout in f():x=“x endl;,static,为在整个程序的运行期间都存在的变量限定访问范围。两类静态变量：静态的局部变量静态的外部变量,静态的局部变量,允许局部变量保存它的原有值，以便在次进入块时还可以使用此值。,eg.int f(int a)int b=0;static int c=3;b=b+1;c=c+1;return(a+b+c);void main()int a=2,i;for(i=0;i3;+i)cout f(a);,运行结果为：7 8 9,静态的外部变量,用static说明的全局变量其他源文件不能用extern引用它用extern还可以用在函数定义或说明中。该函数只能被用于本源文件中，其他源文件不能调用此函数。,静态变量的使用,未被程序员初始化的静态变量都由系统初始化为0。局部静态变量的初值是编译时赋的。当运行时重复调用此函数时，不重复赋初值。虽然局部静态变量在函数调用结束后仍然存在，但其他函数不能引用它。,void a();void b();void c();void d();main()int x=6;cout“x in main is“x endl;a();b();c();d(x);x+;a();b();c();d(x);cout“x in main is”x endl;void a()int x=25;cout“x in a is”x endl;void b()static int x=50;cout“x in b is”x+endl;void c()extern int x;x*=10;cout“x in c is”x endl;int x=2;void d(int x)cout“x in d is”+x endl;,结果：,x in main is 6,x in a is 25,x in b is 50,x in c is 20,x in d is 7,x in a is 25,x in b is 51,x in c 200,x in d is 8,x in main is 7,第6章 过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模版变量的作用域变量的存储类别递归函数基于递归的算法,递归用途,递归程序设计：将一个大问题简化为同样形式的较小问题。在一个递归求解中，分解的子问题与最初的问题具有一样的形式 作为处理问题的工具，递归技术是一种非常有力的工具。利用递归不但可以使得书写复杂度降低，而且使程序看上去更加美观递归调用：在一个函数中直接或间接地调用函数本身,递归条件,必须有递归终止的条件 函数有与递归终止条件相关的参数在递归过程中，决定终止条件的参数有规略地递增或递减,递归的标准模式,有可对函数的入口进行测试的基本情况 if(条件)return(不需要递归的简单答案);else return(递归调用同一函数)；,基本情况,典型的递归函数阶乘函数,递归形式：,递归终止条件,long p(int n)if(n=0)return 1;else return n*p(n-1);,简单应用求n的k次幂,int RaiseIntToPower(int n,int k)if(k=0)return(1);else return(n*RaiseIntToPower(n,k-1);,Fibonacci函数,int f(int n)if(n=0)return 0;elseif(n=1)return 1;else return(f(n-1)+f(n-2);,理解递归,问题：求解n!可以用循环的方法，即从1开始，乘2，再乘3.一直乘到n。这种方法容易理解，也容易实现由于n!=n(n-1)!数学里定义0！1，从而n!可以用下面的递归公式表示：,递归函数设计,int p(int n)if(n=0)return(1);else return(n*p(n-1);,递归执行的过程,求p(4),递归过程,回溯,递归与迭代的选择,对于大多数常用的递归都有简单、等价的迭代程序。究竟使用哪一种，凭你的经验选择。迭代程序复杂，但效率高。递归程序逻辑清晰，但往往效率较低。,Fibonacci函数的递归实现,int f(int n)if(n=0)return 0;elseif(n=1)return 1;else return(f(n-1)+f(n-2);实现效率分析：消费的时间是灾难性的！,Fibonacci函数的迭代实现,int f(int n)int i,fn,fn_1=0,fn_2=1;if(n=0)return 0;if(n=1)return 1;for(i=2;i=n;+i)fn=fn_1+fn_2;fn_2=fn_1;fn_1=fn;return fn;,消耗的时间：执行n次加法和3n次赋值！,系统考虑,对递归函数的每次调用都需要内存空间。由于很多调用的活动都是同时进行的，操作系统可能会耗尽可用的内存,避免在处理过大的n时产生溢出问题。,递归过程-数字旋转方阵（蛇阵）,数字旋转方阵如右图所示。编程输出任意N*N的蛇阵。,用递归的观点看问题,先填最外圈，然后再填内部内部的填法同上。也是先填最外圈，再填内部。根据上述思想，可以设计一个递归函数fill。该函数先填外圈，然后递归调用自己填内部。函数原型：void fill(int number,int begin,int size)number：表示要填入的起始数据 begin：表示要填的起始位置 size：蛇阵的规模要生成一个6*6的蛇阵只要调用：fill(1,0,6),Main函数,int p2020;void fill(int,int,int);int main()int row,col,size;cout size;fill(1,0,size);for(row=0;row size;+row)cout endl;for(col=0;col size;+col)cout prowcol t;return 0;,Fill函数的设计,自上而下填最左列自左而右填最下行自下而上填最右列自右而左填最上行递归调用fill，规模减2，起始位置为原来的下一行下一列，填入的起始数字为填入一圈后的第一个数字。,Void fill(int number,int begin,int size)int i,row=begin,col=begin;if(size=0)return;if(size=1)pbeginbegin=number;return;prowcol=number;+number;for(i=0;isize-1;+i)+row;prowcol=number;+number;for(i=0;isize-1;+i)+col;prowcol=number;+number;for(i=0;isize-1;+i)-row;prowcol=number;+number;for(i=0;isize-2;+i)-col;prowcol=number;+number;fill(number,begin+1,size-2);,递归过程Hanoi塔问题,目标：将A上的盘子全部移到B上规则：每次只能移动一个盘子不允许大盘子放在小盘子上,Hannoi塔,n4（最开始的情况）n4（完成情况）,Hannoi塔,第1步：从开始的杆到辅助杆（src到aux）第2步：从开始杆到目的杆（src到dst）,Hannoi塔,第3步：从辅助杆到目的杆（aux到dst）第4步：从开始的杆到辅助杆（src到aux）,Hannoi塔,第5步：从目的杆到开始杆（dst 到src）第6步：从目的杆到辅助杆（dst到aux）,Hannoi塔,第7步：从开始杆到目的杆（src 到dst）第8步：从开始杆到目的杆（src到dst）,Hannoi塔,第9步：从辅助杆到目的杆（aux 到dst）第10步：从辅助杆到开始的杆（aux到src）,Hannoi塔,第11步：从目的杆到开始杆（dst 到src）第12步：从辅助杆到目的杆（aux 到dst）,Hannoi塔,第13步：从开始的杆到辅助杆（src到aux）第14步：从开始杆到目的杆（src到dst）,Hannoi塔,第15步：从辅助杆到目的杆（aux 到dst）,解题思路,最简单的情况，只有一个盘子：将盘子直接从A移到B大于一个盘子的情况：将除了最下面一个盘子外的所有盘子从A移到C将最下面的盘子从A移到B将C上的盘子移回B,Hanoi 塔函数,void Hanoi(int n,char start,char finish,char temp)if(n=1)cout finish t;Hanoi(n-1,temp,finish,start);,汉诺塔问题的意义,只能用递归解决的问题引出了可计算性问题：有解决方案的问题不一定是可解的,全排列问题,如给定三个字母“ABC”，那么可形成的全排列为：ABC,ACB,BAC,BCA,CAB,CBA。试设计一个函数，输入一个字符串，输出该字符串中所有字母的全排列,用递归的思想分析问题,如排列“ABCDE”，用递归的思想可以看成：第一个字母为A，后面是“BCDE”的全排列第一个字母为B，后面是“CDE”的全排列第一个字母为C，后面是“BDE”的全排列第一个字母为D，后面是“BCE”的全排列第一个字母为E，后面是“BCD”的全排列第一个字母为B，后面是“ACDE”的全排列第一个字母为C，后面是“BADE”的全排列第一个字母为D，后面是“BCAE”的全排列第一个字母为E，后面是“BCDA”的全排列,选择存储结构,用一个字符串存储排列。对n个字符的排列来讲，第一个元素有n 种选择，对每种选择，排列后面n-1个元素。n-1个元素的排列：固定第二个元素(n-1种选择），排列后面n-2个元素。依此类推。函数原型可选为：void permu(char str,int k)表示排列字符串str中从 k 开始的元素函数的调用：排列字符串中的所有元素可调用 permu(char str,0);,排列函数,Void PermuteWithFixedPrefix(char str,int k)int i;if(k=strlen(str)cout str endl;else for(i=k;istrlen(str);+i)swap(str,k,i);PermuteWithFixedPrefix(str,k+1);swap(str,k,i);,包裹函数,void ListPermutations(char str)PermuteWithFixedPrefix(str,0);,第6章 过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模版变量的作用域变量的存储类别递归函数基于递归的算法,基于递归的算法,回溯法 分治法 动态规划,回溯法,首先暂时放弃问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现候选解不可能是解时，就选择下一候选解。如果当前候选解除了不满足规模要求外，满足其他所有要求时，继续扩大当前候选解的规模，并继续试探。如果当前的候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。寻找下一候选解的过程成为回朔。扩大当前候选解的规模，并继续试探的过程称为向前试探。分书问题和八皇后都是典型的回溯法问题,八皇后问题,在一个8*8的棋盘上放8个皇后，使8个皇后中没有两个以上的皇后会在同一行、同一列或同一对角线上,八皇后问题的求解过程,求解过程从空配置开始，在第一列到第m列为合理配置的基础上再配置m+1列，直到第n列的配置也时合理时，就找到了一个解。另外在一列上也有n种配置。开始时配置在第一行，以后改变时，顺序选择第二行、第三行、。、第n行。当配置到第n行时还找不到一个合理的配置时，就要回朔，去改变前一列的配置。,算法,queen_all(k)for(i=1;i=8;+i)if(皇后放在第i行是可行的)在第i行放入皇后；if（k=8）输出解；else queen_all(k+1);,棋盘的数据结构的设计,比较直观的方法是采用一个二维数组，但仔细考察，就会发现，这种表示方法给调整候选解及检查其合理性会带来困难。对于本题来说，我们关心的并不是皇后的具体位置，而是“一个皇后是否已经在某行和某条斜线合理地安置好了”。因为在每一列上恰好放一个皇后，所以引入一个一维数组(设为col（9）)，值colj表示在棋盘第j列上的皇后位置。如col3的值为4，就表示第三列的皇后在第四行。另外，为了使程序在找完了全部解后回溯到最初位置，设定col0的初值为0。当回溯到第0列时，说明程序已求得全部解(或无解)，结束程序执行。,候选解的合理性检查,引入以下三个工作数组 数组a9，aA=true表示第A行上还没有皇后；数组b16，bA=true表示第A条右高左低斜线上没有皇后；从左上角依次编到右下角(1-15)。数组c16，cA=true表示第A条左高右低斜线上没有皇后。从左下角依次编到右上角(1-15)。,void queen_a11(int k)/在8x8棋盘的第k列上找合理的配置int i,j;char awn;for(i=1;i awn;if(awn=Q|awn=q)exit(0);else queen_a11(k+1);/递归至第k十1列 ai=bk+i-1=c8+k-i=true;/恢复对应位置无皇后,主程序,int col9;bool a9,b17,c17;int main()int j;for(j=0;j=8;j+)aj=true;for(j=0;j=16;j+)bj=cj=true;queen_a11(1);return 0;,基于递归的算法,回溯法 分治法 动态规划,递归与分而治之法,分而治之法分：分成较小的可以递归解决的问题治：从子问题的解形成原始问题的解分而治之算法通常都是高效的递归算法在分而治之法中，递归是“分”，额外的开销是“治”,最大连续子序列问题,给定(可能是负的)整数序列，寻找(并标识)的值为最大的序列。如果所有的整数都是负的，那么最大连续子序列的和是零。例如，假设输入是-2,11,-4,13,-5,2，那么答案是20，它表示连续子序列包含了第2项到第4项（如粗体字部分）。又如第二个例子，对于输入1,-3,4,-2,-1,6,答案是7，这个子序列包含最后四项。,分而治之法的解题思路,假设输入是4，3，5，2，1，2，6，2。我们把这个输入划分成两部分，前四个和后四个。这样最大连续子序列的和可能出现在下面三种情况中。情况1：整个位于前半部，可递归计算。情况2：整个位于后半部，可递归计算。情况3：从前半部开始但在后半部结束。,情况3的解决方法,从两半部分的边界开始，通过从右到左的扫描来找到左半段的最长序列。类似地，从左到右的扫描找到右半段的最长序列。把这两个子序列组合起来，形成跨越分割边界的最大连续子序列。在这个实例中，结果序列是从第一部分的第一个元素到第二部分的其余元素。总和是两个子序列的和，即4+7=11.,算法总结,递归地计算整个位于前半部的最大连续子序列。递归地计算整个位于后半部的最大连续子序列。通过两个连续循环，计算从前半部开始但在后半部结束的最大连续子序列的和。选择三个和中的最大值。,Int maxSum(int a,int left,int right)int maxLeft,maxRight,center;int leftSum=0,rightSum=0;int maxLeftTmp=NEGMAX,maxRightTmp=NEGMAX;center=(left+right)/2;if(left=right)return aleft 0?aleft:0;maxLeft=maxSum(a,left,center);maxRight=maxSum(a,center+1,right);,for(int i=center;i=left;-i)leftSum+=ai;if(leftSum maxLeftTmp)maxLeftTmp=leftSum;for(int i=center+1;i maxRightTmp)maxRightTmp=rightSum;return max3(maxLeft,maxRight,maxLeftTmp+maxRightTmp);,快速排序,思路：将待排序的数据放入数组a中，数据为alow,ahigh从待排序的数据中任意选择一个，如alow，将它放入变量k将待排序的数据分成两组，一组比k小，放入数组的前一半；一组比k大，放入数组的后一半；将k放入中间位置。对前一半和后一半分别重复上述方法。最好时间效率：O(nlogn),low,high,快速排序要解决的问题,如何选择作为分段基准的元素？采用第一个元素选取第一个、中间一个和最后一个中的中间元素如何分段？考虑空间问题,快速排序函数,Void quicksort(int a,int low,int high)int mid;if(low=high)return;mid=divide(a,low,high);quicksort(a,low,mid-1);quicksort(a,mid+1,high);,划分过程,从右向左开始检查。如果high的值大于k，high减1，继续往前检查，直到遇到一个小于k的值。将大于k的这个值放入low的位置。然后从low位置开始从左向右检查，直到遇到一个大于k的值。将low位置的值放入high位置，重复第一步，直到low和high重叠。将k放入此位置。,low,high,K=5,low,high,K=5,low,high,low,high,low,high,low,high,Divide函数,Int divide(int a,int low,int high)int k=alow;do while(low=k)-high;if(low high)alow=ahigh;+low;while(low high,基于递归的算法,回溯法 分治法 动态规划,动态规划的思想,在实际中经常会遇到一个复杂的问题不能简单地分成几个子问题，而是会分解出一系列的子问题。如果用分治法的话会使得递归调用的次数呈指数增长。如Finonacci数列的计算，第i个Fibonacci数是前两个Fibonacci数之和。它是基于分而治之算法。在每一阶段都将当前问题分解为多个已解决的子问题为解决递归爆炸问题，通常先找出小问题的解，记录在一个表中，在解决大问题时不需要递归，只需要从表中取出小问题的解。,找零问题,对于一种货币，有面值为C1,C2,CN(分)的硬币，最少需要多少个硬币来找出K分钱的零钱。,贪婪法解法,我们不断使用可能的最大面值的硬币 如：美元的硬币有1、5、10和25分的面值(忽略流通频率很低的50分硬币)。我们可以通过使用2个25分、一个10分的硬币以及三个1分来找出63分钱，一共是6个硬币。如果美元中包含一个21分硬币时，贪心算法仍然给出一个用六个硬币的解，但是最佳的解是用三个硬币(三个都是21分的硬币。),解法1分治法,如果我们可以用一个硬币找零，这就是最小的。否则，对于每个可能的值i，我们可以独立计算找i分钱零钱和K-i分钱需要的最小硬币数