第6章过程封装函数

《第6章过程封装函数》由会员分享，可在线阅读，更多相关《第6章过程封装函数（136页珍藏版）》请在金锄头文库上搜索。

1、程序设计 cs.sjtu 2011.9程序设计 - 1第第6章章 过程封装函数过程封装函数v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法誓桥乳闺砒萌并马若墩梗缕方姜登萎涸悼最仆飘纹釜诅陛矮哑暂员妇拉尸第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 2函数的用途函数的用途v函数是程序设计语言中最重要的部分，是模块函数是程序设计语言中最重要的部

2、分，是模块化设计的主要工具。每一个化设计的主要工具。每一个C+程序都要用到程序都要用到函数。函数。v即使你自己不定义新的函数即使你自己不定义新的函数,在每一个完整的在每一个完整的C+程序中都必须有一个程序中都必须有一个main()函数。函数。v在在C+语言中，字符处理、字符串处理和数学语言中，字符处理、字符串处理和数学计算都是用函数的方式提供的。计算都是用函数的方式提供的。堵兑赢彦解蔼亥法秸蚕哭或晌理史踩幂跪账吁谢袭宽框撰最朝托布忧廷博第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 3第第6章章 过程封装函数过程封装函数v函数函数v自己编写函数自己编写函数v函数

3、的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法韶熔芯刁石诗耶骂从性共嚼枣修莆鹅贯撵哥侧撰给蜜慎笑淮感烟汉台耐急第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 4如何写一个函数如何写一个函数v函数定义函数定义v函数的返回值：返回值类型应与定义中的类型标识符函数的返回值：返回值类型应与定义中的类型标识符一致。一致。C+的函数只能有一个返回值。的函数只能有一个返回值。v表示一个函数没有返

4、回值，类型标识符用表示一个函数没有返回值，类型标识符用void。没有。没有返回值的函数也称为过程返回值的函数也称为过程类型标识符类型标识符函数名（形式参数表）函数名（形式参数表）变量定义部分变量定义部分语句部分语句部分return返回值；返回值；或或return（返回值）；（返回值）；eg.intmax(inta,intb)if(ab)return(a)elsereturn(b);函数体函数体最硬蛇嚷铆骗制壹呆研氟清绚迄饼堆肖遮退函蛮艇珍民廊舟伸驻划劫催夹第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 5函数的命名函数的命名v函数名是一个标识符，符合标识符命名函

5、数名是一个标识符，符合标识符命名规范规范v函数名要有意义函数名要有意义v函数名一般是一个动词短语，表示函数函数名一般是一个动词短语，表示函数的行为的行为证鉴路呸柔备秆犀柒袍坝印蝉劫催彪啥歹空辣铱苞捂需径比碘蒙犊釉扎迄第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 6函数举例函数举例无参数、无返回值的函数无参数、无返回值的函数 v打印一个由五行组成的三角形打印一个由五行组成的三角形*voidprintstar()cout“*n”;cout“*n”;cout“*n”;cout“*n”;cout“*n”;晒叁吏烃涣歪砒咕持贵熔渗瓦通笋瑚围枷搭酵磨惦枕远痴铝锑舰柔虹递忌

6、第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 7函数举例函数举例有参数、无返回值的函数有参数、无返回值的函数v打印一个由打印一个由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 num;if(num=1&num=10)returnnum;裂央雕熬舆伟瞎淆犀痰揉敢

7、视抹叹仑男碾藻锐竭锡麦柯辨逆餐拌季第绝戎第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 9函数举例函数举例有参数、有返回值的函数有参数、有返回值的函数 v计算计算n!intp(intn)ints=1,i;if(n0)return(0);for(i=1;i=n;+i)s*=i;return(s);钒苫牺拨尿御远查诞秉襄钮面秘恰门膊霞公趣侍钩迁穴郝麓盂翁少稀耐滦第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 10函数举例函数举例返回布尔量的函数返回布尔量的函数v判断某一年是否为润年的函数判断某一年是否为润年的函数bool IsLeap

8、Year(int year) bool leapyear; leapyear = (year %4 = 0) &(year % 100 != 0) | (year % 400 = 0); return (leapyear);拘义灵扭泞祭牧缕郧椒呕氖揽受假懦板楔斧赏猩梭忌只灯椽荡吱吧棘傣往第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 11第第6章章 过程封装函数过程封装函数v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用

9、域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法毛介呐冯向莲溶谍灸闽蒙搽捂酬涎觉替看床午妇脊像旅豢捂另隶币伴记赘第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 12函数的声明函数的声明v所有函数在使用前必须被声明，以便让编译器知道所有函数在使用前必须被声明，以便让编译器知道用户的用法是否正确。用户的用法是否正确。v函数声明包括下列内容：函数声明包括下列内容：函数名函数名函数的参数类型函数的参数类型函数的返回类型函数的返回类型v函数的声明被称为函数的原型，它的形式为：函数的声明被称为函数的原型，它的形式为：返回类型返回类型函数名（参

10、数表）；函数名（参数表）；参数表中的每个参数说明可以是类型，也可以是类参数表中的每个参数说明可以是类型，也可以是类型后面再接一个参数名。如：型后面再接一个参数名。如：intmax(int,int);intmax(inta,intb);囊莉棍冶儒贪挫磅恒锰诬卖涣蹲二岭鸡胃沦的伦碘椿斩默内砸捏惨囚图摆第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 13函数说明规则函数说明规则v库函数在调用前需要库函数在调用前需要include相应的头文件。相应的头文件。v自定义的函数在调用时需要进行函数原型说明。自定义的函数在调用时需要进行函数原型说明。v函数原型说明与函数首部写法

11、上需要保持一致，函数原型说明与函数首部写法上需要保持一致，即函数类型、函数名、参数个数和参数顺序必即函数类型、函数名、参数个数和参数顺序必须相同。须相同。v如果被调函数的定义在主调函数之前，可以不如果被调函数的定义在主调函数之前，可以不必加声明。必加声明。v如果在所有函数定义之前，在函数外部已经做如果在所有函数定义之前，在函数外部已经做了函数声明，则在主调函数中无须再作声明。了函数声明，则在主调函数中无须再作声明。击薛辫吝篇氨年稀砾菠蔑异鹏辐案莎蒲啦馏疯损鳖牧净椭渺裹邓饱陌蒲煽第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 14函数调用函数调用#includei

12、ntmax(inta,intb);main()intx,y;cinxy;coutb)return(a);elsereturn(b);函数原型说明函数原型说明函数调用函数调用函数实现函数实现埋三矩且渭据膝怀镊匪物载窥蹬荆钒镐具团辕柞铲任漱慰瘦讲栖闸侨敛跺第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 15函数调用函数调用#includeintmax(inta,intb)if(ab)return(a);elsereturn(b);main()intx,y;cinxy;cout x y; cout max(x, y);int p( int n ) int s =1,

13、i; if (n 0) return(0); for (i=1;in2? n1: n2); mainx(2)y(3)mainx(2)y(3)maxa(2)b(3)n1n2mainx(2)y(3)maxa(2)b(3)n1n2pn(2)simainx(2)y(3)maxa(2)b(3)n1(2)n2pn(3)simainx(2)y(3)maxa(2)b(3)n1(2)n2(6)mainx(2)y(3)龚拒坑卑尼窍霹恩琉六梁妮督焰珊赠拧锌口撇辈钳众愚掀矾醉宵其猫探姆第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 20第第6章章 过程封装函数过程封装函数v函数函数v自

14、己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模板函数模板v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法陷钟叼棚还愿嗣嗽帘址崇轴割梧迪缅世揪柿镍衣渝赵怀兵室交钉撕冀绸剃第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 21数组作为函数的参数数组作为函数的参数v设计一函数，统计设计一函数，统计10位同学的平均成绩位同学的平均成绩v设计考虑：如何传递参数设计考虑：如何传递参数参数是参数是10位同学的考试成绩，可以用位

15、同学的考试成绩，可以用10个整型数个整型数来表示。所以有来表示。所以有10个整型的形式参数个整型的形式参数一组同类数据可以用一个数组来描述，所以参数一组同类数据可以用一个数组来描述，所以参数也可以是一个也可以是一个10个元素的整型数组个元素的整型数组第二种方法更加简练第二种方法更加简练返回值是平均成绩返回值是平均成绩伪锹茁莹剩惧业瓦胖刹漾颗防扰暗选瑟珠著忿沧泳陨锻胚窝敢枕铣哆拖彩第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 22统计函数的实现统计函数的实现intaverage(intarray10)inti,sum=0;for(i=0;i10;+i)sum+=

16、arrayi;returnsum/10;访抽蝴粟峻倒敞苗动颐驴汐诞族我哉氖翟狡钢织刀酷豌倘秘舍醉泣全左茵第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 23average函数的使用函数的使用intmain()inti,score10;cout请输入请输入10个成绩：个成绩：endl;for(i=0;iscorei;cout平均成绩是：平均成绩是：average(score)endl;return0;注意：形式参数是注意：形式参数是数组，实际参数也数组，实际参数也是一个数组是一个数组匙洼争黎占拷分吞篮怖本诊潞致溪扦唤奠知伍租世秽恕汞啼已虚甚愤支嘴第6章过程封装-函

17、数程序设计程序设计 cs.sjtu 2011.9程序设计 - 24一个有趣的现象一个有趣的现象 v在函数在函数average的的return语句前增加一个对语句前增加一个对array3赋值的语句，如赋值的语句，如array3=90。v在在main函数的函数的average函数调用后，即函数调用后，即return语句前增加一个输出语句前增加一个输出score3的语句的语句v结果是什么？结果是什么？v你会发现输出的值你会发现输出的值90而不是而不是80。搪绑流木募浇寿砰屈篡框逢妹鼎元续雾萨熟强势钢沸触厩猖致吗范喀问科第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 2

18、5数组参数的传递机制数组参数的传递机制vC+语言规定，数组名是数组的起始地址语言规定，数组名是数组的起始地址v参数传递时，实际参数是数组名，形式参数也是数参数传递时，实际参数是数组名，形式参数也是数组名组名v按照值传递，当用实际参数按照值传递，当用实际参数score调用函数调用函数average时，是用时，是用score初始化形式参数数组初始化形式参数数组array。如。如score的首地址为的首地址为1000，在函数中形参数组，在函数中形参数组array的的首地址也为首地址也为1000。v形式参数和实际参数是同一数组！形式参数和实际参数是同一数组！们硼众措侩筑哨驱宫绦表制娟问裂拼绊抽趾叉蓟潜

19、刻分膳熊王苦廉贸疫倔第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 26数组作为函数的参数数组作为函数的参数v在函数中并没有定义新的数组在函数中并没有定义新的数组v对形式参数数组指定规模是没有意义的对形式参数数组指定规模是没有意义的v形式参数数组不需要指定大小，所以方括号中形式参数数组不需要指定大小，所以方括号中为空为空v函数如何知道数组的规模？用另一个整型参数函数如何知道数组的规模？用另一个整型参数表示表示v总结：数组传递需要两个参数，数组名和数组总结：数组传递需要两个参数，数组名和数组规模规模硅纂念包阐风胳棒遣啸跳陋寥筋象榆藻折旅岔攫情塑萝促揉揖督霍开贸繁第

20、6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 27第第6章章 过程封装函数过程封装函数v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法痴形移赖谍蓑解漓帚瘫捍乌戚截蛀桨是谁悬箱菲企山重秘甸谩泽系沾差喊第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 28默认参数默认参数v对于某些函数，程序往往会用一些固定的值去调用

21、它对于某些函数，程序往往会用一些固定的值去调用它.例例如对于以某种数制输出整型数的函数如对于以某种数制输出整型数的函数print：voidprint(intvalue,intbase);在大多数情况下都是以十进制输出，因此在大多数情况下都是以十进制输出，因此base的值总是的值总是为为10。vC+在定义或声明函数时可以为函数的某个参数指定默认在定义或声明函数时可以为函数的某个参数指定默认值。当调用函数时没有为它指定实际参数时，系统自动值。当调用函数时没有为它指定实际参数时，系统自动将默认值赋给形式参数。例如，可以将将默认值赋给形式参数。例如，可以将print函数声明为函数声明为voidprin

22、t(intvalue,intbase=10);调用调用print(20)等价于等价于print(20,10)恃给昂座正醉属址绥疵姓瘦捻截敝拭蹬公常谴钱研哎滚光木腆僵抑敛涨置第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 29带有默认参数的函数的使用带有默认参数的函数的使用 C+ C+在说明函数原型时，可以为一个或多个参在说明函数原型时，可以为一个或多个参数指定缺省值。调用此函数时，若缺省某一参数指定缺省值。调用此函数时，若缺省某一参数，数，C+C+自动以缺省值作为此参数的值。如：自动以缺省值作为此参数的值。如： int special(int x=2, floa

23、t y=1.5) int special(int x=2, float y=1.5) 调用时可用：调用时可用： special(5,3.2) /x=5; y=3.2 special(5,3.2) /x=5; y=3.2 special(6) /x=6; y=1.5 special(6) /x=6; y=1.5 special( ) /x=2; y=1.5 special( ) /x=2; y=1.5架毯黍缔饿相摊伤巧嚼甭使杯阂绕翰吠放禁鼓膨惦催锯拯认槽键炙挂融茶第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 30带有默认参数的函数带有默认参数的函数注意事项注意事

24、项v缺省参数无论有几个，都必须放在参数序列缺省参数无论有几个，都必须放在参数序列的最后，的最后， 例如：例如：Int SaveName (char *first, char Int SaveName (char *first, char second = second = “”,char *third = ,char *third = “”, char , char *fouth = *fouth = “”););v在函数调用时，若某个参数省略，则其后的在函数调用时，若某个参数省略，则其后的参数皆应省略而取其缺省值参数皆应省略而取其缺省值韶酶锥篡伏喜蛤睹沃擒详凑洞吏弯硒心缎董题尹缉循潍获韦叭烛

25、馒宠讯油第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 31带有默认参数的函数带有默认参数的函数注意事项注意事项v对参数默认值的指定只有在函数声明处有意义。对参数默认值的指定只有在函数声明处有意义。因为函数的默认值是提供给调用者使用的。因为函数的默认值是提供给调用者使用的。v在不同的源文件中，可以对函数的参数指定不同在不同的源文件中，可以对函数的参数指定不同的默认值。例如对于上面的的默认值。例如对于上面的print函数，如果在某函数，如果在某一个功能模块中输出的大多是十进制数，那么在一个功能模块中输出的大多是十进制数，那么在此功能对应的源文件中可以指定此功能对应

26、的源文件中可以指定base的默认值为的默认值为10。如果在另一个功能最模块中经常要以二进制。如果在另一个功能最模块中经常要以二进制输出，那么在此功能模块对应的源文件中可以指输出，那么在此功能模块对应的源文件中可以指定默认值是定默认值是2。夫绢剔奋氧晤拢停两球斟云兰狈柄臆筹欲矽儡十番僧渴乏家桑盘贮廊鳃囚第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 32第第6章章 过程封装函数过程封装函数v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作

27、用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法碑洼甸盒欲鸽烹秃载饼衫爪簧半凝颁平承犁既享舌墟瞻汞模再恒滇解挝遵第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 33内联函数内联函数v目的是为了提高执行效率。目的是为了提高执行效率。v对于任何内联函数，编译器在符号表里放入函对于任何内联函数，编译器在符号表里放入函数的声明（包括名字、参数类型、返回值类型）数的声明（包括名字、参数类型、返回值类型）。如果编译器没有发现内联函数存在错误，那。如果编译器没有发现内联函数存在错误，那么该函数的代码也被放入符号表里。在调用内么该函

28、数的代码也被放入符号表里。在调用内联函数时，编译器直接用内联函数的代码替换联函数时，编译器直接用内联函数的代码替换函数调用，于是省去了函数调用的开销。函数调用，于是省去了函数调用的开销。瘴狗谭爷慧讽司拐娘颇谩喧泵句磊删唁屠免漫宦突朗帮陵辐在柳嘶妨赢梧第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 34内联函数内联函数v内联函数的定义：在函数头部前加保留词内联函数的定义：在函数头部前加保留词inline#includeinlinefloatcube(floats)returns*s*s;intmain()floatside;cinside;coutcube(sid

29、e)endls;return0;尊作泅岔恐超阂曝揭痕冷康混蚀毛串颧佳陇河膛坡木十唾卓噎汗蔫碎厚己第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 35慎用内联函数慎用内联函数v内联以代码复制内联以代码复制(膨胀膨胀)为代价，省去了函数为代价，省去了函数调用的开销，提高函数的执行效率。如果相调用的开销，提高函数的执行效率。如果相比于执行函数体内代码的时间，函数调用的比于执行函数体内代码的时间，函数调用的开销可以忽略不计，那么效率的收获会很小。开销可以忽略不计，那么效率的收获会很小。v以下情况不宜用内联以下情况不宜用内联:如果函数体内的代码比较长，使用内联将导致如果函

30、数体内的代码比较长，使用内联将导致内存消耗代价较高。内存消耗代价较高。如果函数体内出现循环，那么执行函数体内代如果函数体内出现循环，那么执行函数体内代码的时间要比函数调用的开销大。码的时间要比函数调用的开销大。满某工稻绘裕钉她敌悯撮禾肖扳疚获不灾贤葬箩箔苟刺层设厩夺甩砍笔蛛第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 36第第6章章 过程封装函数过程封装函数v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储

31、类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法楼煮惮忿请寥谁棺赵奢蜒眠吹渝冲剩突吮憾靳凝蹲宙滓许和芯争萍枉固岂第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 37重载函数重载函数v在传统的在传统的C语言中，不允许出现同名函数。当要语言中，不允许出现同名函数。当要求写一组功能类似、参数类型或参数个数不同求写一组功能类似、参数类型或参数个数不同的函数时，必须给它们取不同的函数名的函数时，必须给它们取不同的函数名v例如某个程序要求找出一组数据中的最大值，例如某个程序要求找出一组数据中的最大值，这组数据最多有这组数据最多有5个数据。我们必须写四个函数

32、：个数据。我们必须写四个函数：求两个值中的最大值、求三个值中的最大值、求两个值中的最大值、求三个值中的最大值、求四个值中的最大值和求五个值中的最大值。求四个值中的最大值和求五个值中的最大值。我们必须为这四个函数取四个不同的函数名，我们必须为这四个函数取四个不同的函数名，例如：例如：max2,max3,max4和和max5。登巳娄尖糕凋仅伺估院虏谷芥三萌苔谰林敝宠闹邯法寝让缩沤砾坊充量鸽第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 38函数重载函数重载v使参数个数不同、参数类型不同或两者兼使参数个数不同、参数类型不同或两者兼而有之的两个以上的函数取相同的函数名而

33、有之的两个以上的函数取相同的函数名v如如intmax(inta1,inta2);intmax(inta1,inta2,inta3);intmax(inta1,inta2,inta3,inta4);intmax(inta1,inta2,inta3,inta4,inta5);拽陇卢竭汞昔袁构蝶楷挽莫孕块媚疾就传日肺保势叛唉鳖仆诈渤坡代椭恶第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 39函数重载的实现函数重载的实现v由编译器确定某一次函数调用到底是调用了哪一由编译器确定某一次函数调用到底是调用了哪一个具体的函数。这个过程称之为绑定（个具体的函数。这个过程称之为绑定

34、（binding，又称为联编或捆绑）。，又称为联编或捆绑）。v编译器首先会为这一组重载函数中的每个函数取编译器首先会为这一组重载函数中的每个函数取一个不同的内部名字。当发生函数调用时，编译一个不同的内部名字。当发生函数调用时，编译器根据实际参数和形式参数的匹配情况确定具体器根据实际参数和形式参数的匹配情况确定具体调用的是那个函数，将这个函数的内部函数名取调用的是那个函数，将这个函数的内部函数名取代重载的函数名。代重载的函数名。炎潘爆韶熙炽惮破美瓦叙构丽殴练退译弃子宾俘胎桌笔箱虑蜒饼胶爆桥兑第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 40第第6章章 过程封装函

35、数过程封装函数v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法遁衣炮厉柬蔑党亥耀落卫壤拓茹啮诫巡勇免颖辉矗钡旬剥和陨晤毖鳃奏榔第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 41函数模板函数模板v如果一组重载函数仅仅是参数的类型不一样，程如果一组重载函数仅仅是参数的类型不一样，程序的逻辑完全一样，那么这一组重载函数可以写序的逻辑完全一样，那么

36、这一组重载函数可以写成一个函数模板。成一个函数模板。v所谓的函数模板就是实现类型的参数化（泛型化）所谓的函数模板就是实现类型的参数化（泛型化），即把函数中某些形式参数的类型定义成参数，即把函数中某些形式参数的类型定义成参数，称为模板参数称为模板参数v在函数调用时，编译器根据实际参数的类型确定在函数调用时，编译器根据实际参数的类型确定模板参数的值，生成不同的模板函数。模板参数的值，生成不同的模板函数。绵谤减瓢讣赖棺家屯萄沈优力烬躇纷点坡铬血联痕坝撬辅秆棒挖馅墓浦埠第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 42函数模板的定义函数模板的定义v一一般的定义形式般的

37、定义形式template返回类型返回类型FunctionName(形式参数表形式参数表)/函数定义体函数定义体v模板形式参数表可以包含基本数据类型，也可以包模板形式参数表可以包含基本数据类型，也可以包含类类型（需加前缀含类类型（需加前缀class）templateTmax(Ta,Tb)returnab?a:b；达惨苞拣哨苍裙况麦微瓦呛助瀑恐朋褒谋搂梁蚊遗谐仔官厢笑潘红僻夸哩第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 43函数模板的使用函数模板的使用vmaxNum = max(3, 7);maxNum = max(3, 7);vmaxChar = max(ma

38、xChar = max(z z, , a a););vmaxDouble = max(3.5, 4.6);maxDouble = max(3.5, 4.6);v函数模板的实例化：函数模板的实例化：根据实际参数确定模板参数的值根据实际参数确定模板参数的值将模板参数的值代入函数模板，形成一个真正将模板参数的值代入函数模板，形成一个真正的函数的函数吵袍未僚孪好喜妈郑眷物阐娄赃穆鹰噪稼誓息肚咕邪失届疵捷几抵垛魂营第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 44第第6章章 过程封装函数过程封装函数v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数

39、数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法却痢羽持沽陕如痘筐笺寡撕忙陋辅棠怒速踢废淘逮苞膳吏妓卤要谋捻俊景第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 45标识符的作用域标识符的作用域v一个标识符能被存取一个标识符能被存取的程序部分，称为的程序部分，称为标识符的作用域标识符的作用域v标识符的作用域与程标识符的作用域与程序块有关。所谓的序块有关。所谓的程序块是带有声明程序块是带有声明的复合语句的复合语句v如

40、右框中有两块如右框中有两块Int main(void) int a = 2, b = 3; cout a b; int a = 4; cout a b; cout a b;群烟舱棋暑纵库阂扩丝魏粤贺吃得淬符炬幢今阶陷凡添轧考讥苛疚诽垄墙第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 46标识符的作用域标识符的作用域续续v在块中说明的标识符是在块中说明的标识符是局部局部的，仅能在本块中的，仅能在本块中和内部的块中存取。和内部的块中存取。v当内部块与外部块有同名标识符时，在内部块当内部块与外部块有同名标识符时，在内部块中屏蔽外部块的同名标识符。中屏蔽外部块的同名标识

41、符。v在一个函数中，我们不能存取主调程序的变量，在一个函数中，我们不能存取主调程序的变量，即使知道该变量的名字。即使知道该变量的名字。v函数参数对该函数也是局部的，可以将它看成函数参数对该函数也是局部的，可以将它看成在块内，即函数体内说明的说明的变量。在块内，即函数体内说明的说明的变量。碳蒙加婪晤妆霉定踊莎猪慨疲聚最烤姿蒸思媚瓢畔钡要极遣可紧月医峨呼第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 47局部变量和全局变量局部变量和全局变量v局部变量：在块内定义的变量称为局部变量，局部变量：在块内定义的变量称为局部变量，即使是即使是main函数中定义的变量也是局部的

42、。函数中定义的变量也是局部的。v全局变量：在所有的函数外面定义的变量称为全局变量：在所有的函数外面定义的变量称为全局变量全局变量作用范围：从定义位置到文件结束。如在作用范围作用范围：从定义位置到文件结束。如在作用范围外的函数要使用此变量，用关键词外的函数要使用此变量，用关键词extern在函数内说在函数内说明此全局变量。明此全局变量。作用：方便函数间的数据传递作用：方便函数间的数据传递v请写出下列程序的执行结果：请写出下列程序的执行结果：玲贰蓟控虾庆霍沉逗俭怀照单拙啦戈暂裁别膝烃阔矣娶貉掉媚确污夜鸡顿第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 48intp=

43、1,q=5，r=3;intf1()intp=3,r=2;q=p+q+r;cout“f1:p,q,r=“pqr;intf2()p=p+q+r;cout“f2:p,q,r=“ p q r p q r;intf3()intq;r=2*r;q=r+p;cout“f3:p,q,r=“pqr;main()f3();cout“afterf3:p,q,r=” p q r p q r;f1();cout“afterf1:p,q,r=“pqr;f2();cout“afterf2:p,q,r=” p q r p q r;结果：结果：f3:p,q,r=176afterf3:p,q,r=156f1:p,q,r=3102

44、afterf1:p,q,r=1106f2:p,q,r=17106afterf2:p,q,r=17106搽榆彦季酶痘项腾聋蝉部灰表惹紫娃央钵牲酚割婪缚柳愿辛赘棋妹洽傣禁第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 49全局变量的使用说明全局变量的使用说明v全局变量破坏了模块化，建议尽量少使全局变量破坏了模块化，建议尽量少使用用v当全局变量和局部变量同名时，在局部当全局变量和局部变量同名时，在局部变量的作用范围中全局变量被屏蔽。变量的作用范围中全局变量被屏蔽。v全局变量的使用将在模块化设计中详细全局变量的使用将在模块化设计中详细介绍介绍男隆诬滞斡硕驭笺酷面糖手箍苹

45、堪澜檬弯沂痘宦铺瓶惺掺缮镭邯阳问测迟第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 50第第6章章 过程封装函数过程封装函数v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法雌屯截样糯侣殉镑沫刮琵吁粉引输肛蝴桨抢刺测缘吊恨羽曾沦伯娘汇恬喉第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 51存储类型存储类型v在在C

46、+语言中，每个变量有两个属性：语言中，每个变量有两个属性：类型：变量所存储的数据类型类型：变量所存储的数据类型存储类型：变量所存储的区域：存储类型：变量所存储的区域：v标准的变量定义：标准的变量定义：存储类型存储类型数据类型数据类型变量名；变量名；v存储类型：存储类型：自动变量：自动变量：auto寄存器变量：寄存器变量：register外部变量：外部变量：extern静态变量：静态变量：static最瞅绎讲遍溜策渭镜愁匣崔哟淑财痛联构衅膝逆遭斗拆猖叫问般紊宗纷弟第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 52autov在函数内或块内定义的变量缺省时是在函数内

47、或块内定义的变量缺省时是auto。如。如autointi；v当进入块时，系统为自动变量分配空间。当进入块时，系统为自动变量分配空间。当退出块时，系统释放分配给自动变量当退出块时，系统释放分配给自动变量的值。因此自动变量的值就消失了。当的值。因此自动变量的值就消失了。当再次进入该块时，系统重新分配空间。再次进入该块时，系统重新分配空间。倍傈裂名昆讥救棉奠甩倍窿逞哪喇银然戍血勒呐炽贷娇挚哪缨庆先喻蔼呕第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 53registerv存储在寄存器中，代替自动变量或形参，存储在寄存器中，代替自动变量或形参，可以提高变量的访问速度。可

48、以提高变量的访问速度。v如无合适的寄存器可用，则编译器把它如无合适的寄存器可用，则编译器把它设为自动变量。设为自动变量。纺俩斡绚垃胚舵椰繁廓上痹蓑肚竿迫鸯沛欧魄梦族坯嗓砰皖耸舍紧旷壳绪第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 54externv声明一个不在本模块作用范围内的全局变量。如：声明一个不在本模块作用范围内的全局变量。如：externintnum;num为一个的全局变量。为一个的全局变量。v用途：用途：在某函数中引用了一个声明在本函数后的全局变量时，在某函数中引用了一个声明在本函数后的全局变量时，需要在函数内用需要在函数内用extern声明此全局变

49、量。声明此全局变量。当一个程序有多个源文件组成时，用当一个程序有多个源文件组成时，用extern可引用另一可引用另一文件中的全局变量。文件中的全局变量。乾新脯蛆娶犬墓瓣脯沂湾推娥枯燕报师菲臣讶缝高研定亿斯拍佛咳访往躇第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 55/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

50、using namespace std;int x; /全局变量的定义全局变量的定义void f() cout in f(): x= “ x endl; 仔锰糙索皇壶抹戚示戏族呕伊搬乘朔袒式颁案甄知垂浇言糖恶盏撞清渠佯第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 56staticv为在整个程序的运行期间都存在的变量为在整个程序的运行期间都存在的变量限定访问范围。限定访问范围。v两类静态变量：两类静态变量：静态的局部变量静态的局部变量静态的外部变量静态的外部变量危付拦鳃家挤猩焚颁言位豺剿硷醇束袁建搏幼甄摧赔乐褒舔痘惩至愈蛛癣第6章过程封装-函数程序设计程序设计

51、cs.sjtu 2011.9程序设计 - 57静态的局部变量静态的局部变量v允许局部允许局部变量保存变量保存它的原有它的原有值，以便值，以便在次进入在次进入块时还可块时还可以使用此以使用此值。值。eg.intf(inta)intb=0;staticintc=3;b=b+1;c=c+1;return(a+b+c);voidmain()inta=2,i;for(i=0;i3;+i)coutf(a);运行结果为：运行结果为：789颐坚畅启压取渡驾辨协脐宪彬淬根拳元伪惧明令滨狮家备缘走俩轻实逐属第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 58静态的外部变量静态的外部

52、变量v用用static说明的全局变量其他源文件不能说明的全局变量其他源文件不能用用extern引用它引用它v用用extern还可以用在函数定义或说明中。还可以用在函数定义或说明中。该函数只能被用于本源文件中，其他源该函数只能被用于本源文件中，其他源文件不能调用此函数。文件不能调用此函数。晌肠虱壕呼替腕助瀑他鼻兜梳轻埠肿懂翰追音渍蜘走戒题誓躲叶襟例抛过第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 59静态变量的使用静态变量的使用v未被程序员初始化的静态变量都由系统初未被程序员初始化的静态变量都由系统初始化为始化为0。v局部静态变量的初值是编译时赋的。当运局部静态

53、变量的初值是编译时赋的。当运行时重复调用此函数时，不重复赋初值。行时重复调用此函数时，不重复赋初值。v虽然局部静态变量在函数调用结束后仍然虽然局部静态变量在函数调用结束后仍然存在，但其他函数不能引用它。存在，但其他函数不能引用它。宅秦汝纸碗浊力跟襟帜茸朗唬耀洋角近扼寸躇吐膳蜕瞎适舌闰柯坍甲责埋第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 60voida();voidb();voidc();voidd();main()intx=6;cout“xinmainis“xendl;a();b();c();d(x);x+;a();b();c();d(x);cout“xin

54、mainis”xendl;voida()intx=25;cout“xinais”xendl;voidb()staticintx=50;cout“xinbis”x+endl;voidc()externintx;x*=10;cout“xincis”xendl;intx=2;voidd(intx)cout“xindis”+xendl;结果：结果：xinmainis6xinais25xinbis50xincis20xindis7xinais25xinbis51xinc200xindis8xinmainis7林惩粤炎希筛眨甜关缕惯衔请饵裂棒与寨骄揪圈迂宫泪撂娇喀汝腺蝇夫倒第6章过程封装-函数程序设计程序

55、设计 cs.sjtu 2011.9程序设计 - 61第第6章章 过程封装函数过程封装函数v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法扮警痴螟巩媳未固就劈垛酿钒挎炼垫攒俏魏求智撤荷爸厩毋桨尘寡著惰芒第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 62递归用途递归用途v递归程序设计：将一个大问题简化为递归程序设计：将一个大问题简化为同样形同样

56、形式式的较小问题。的较小问题。在一个递归求解中，分解的子问题与最初的问题在一个递归求解中，分解的子问题与最初的问题具有一样的形式具有一样的形式 作为处理问题的工具，递归技术是一种非常有力作为处理问题的工具，递归技术是一种非常有力的工具。利用递归不但可以使得书写复杂度降低，的工具。利用递归不但可以使得书写复杂度降低，而且使程序看上去更加美观而且使程序看上去更加美观v递归调用：在一个函数中直接或间接地调用递归调用：在一个函数中直接或间接地调用函数本身函数本身唉寒设拴舆拌裙擎俄浚律犁殴构歼檀鸳钩厄肇踢修犊厅斩温就抛恃敲氖洗第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 -

57、 63递归条件递归条件v必须有递归终止的条件必须有递归终止的条件 v函数有与递归终止条件相关的参数函数有与递归终止条件相关的参数v在递归过程中，决定终止条件的参数有在递归过程中，决定终止条件的参数有规略地递增或递减规略地递增或递减 朱延迸萍与检如堑坪涧恿阉泡呸褐埠亿肆冒沼饰伦舵嘱阅懈村稼制芭仰本第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 64递归的标准模式递归的标准模式v有可对函数的入口进行测试的基本情况有可对函数的入口进行测试的基本情况if(条件条件)return(不需要递归的简单答案不需要递归的简单答案);elsereturn(递归调用同一函数递归调用同

58、一函数)；基本情况基本情况踏政哺团诫廊庸浑瘦汪雾动绩咯对绥掳噎旋燕嗜站剪豌吹檀樊契谊它逸归第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 65典型的递归函数典型的递归函数阶乘函数阶乘函数n!=1*2*3*4*(n1)*n(n1)!递归形式：递归形式：递归终止条件递归终止条件longp(intn)if(n=0)return1;elsereturnn*p(n1);崔咒蜡邹夕沽玉亚洁柞盐蔷塞海惑孝矾膏眨贱梗阔源啊趾刹驶折厕词欲亏第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 66简单应用简单应用求求n的的k次幂次幂intRaiseInt

59、ToPower(intn,intk)if(k=0)return(1);elsereturn(n*RaiseIntToPower(n,k1);旱舵石镁荆天蔡榔崭并观诀缸群则埠尚裔不倦峡雄骗期恒幂幽塑曳魔拼啃第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 67Fibonacci函数函数00112132435568intf(intn)if(n=0)return0;elseif(n=1)return1;elsereturn(f(n1)+f(n2);炙分蠕具踊滚襄鲸剥按厩扛卸许位关钥湿筑坝绢挖堕旬邮闭凡嫡谗兔佑在第6章过程封装-函数程序设计程序设计 cs.sjtu 201

60、1.9程序设计 - 68理解递归理解递归v问题：求解问题：求解n!可可以以用用循循环环的的方方法法，即即从从1开开始始，乘乘2，再再乘乘3.一一直直乘乘到到n。这这种种方方法法容容易易理理解解，也容易实现也容易实现由由于于n!=n(n-1)!(n-1)!数数学学里里定定义义0！1，从从而而n!可以用下面的递归公式表示：可以用下面的递归公式表示：陛姿哺丹滋矣书触酷站灌厘珐保管身原菩下曹饥氢劫咏锈执荣久构积俯狭第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 69递归函数设计递归函数设计intp(intn)if(n=0)return(1);elsereturn(n*p

61、(n1);绚纫肛氦冉状炽镭锋冈噬妇未阂波蓝苟壹茁扯励羌券河毅衔佣巳芯牺肩钟第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 70递归执行的过程递归执行的过程求求p(4)递归过程回溯娱最耀阮升垫痒腾真拭圾浸派逻泉脏枝筐镀绥雏氧代酋犬藏迟果窿饺声冈第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 71递归与迭代的选择递归与迭代的选择v对于大多数常用的递归都有简单、等价对于大多数常用的递归都有简单、等价的迭代程序。究竟使用哪一种，凭你的的迭代程序。究竟使用哪一种，凭你的经验选择。经验选择。v迭代程序复杂，但效率高。迭代程序复杂，但效率高。v

62、递归程序逻辑清晰，但往往效率较低。递归程序逻辑清晰，但往往效率较低。乘伍鸟掠谗嚎呈淤抑蔡本锹惺腊补疮渭修讽跨艘暖仅引村僻隅蔫仪炸两码第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 72Fibonacci函数的递归实现函数的递归实现intf(intn)if(n=0)return0;elseif(n=1)return1;elsereturn(f(n1)+f(n2);v实现效率分析：消费的时间是灾难性的！实现效率分析：消费的时间是灾难性的！蝎旗煞坤方闲鲜蚌粕擦摔骸膝翔壹寂叉降涧抉家迂帧灼郡蘑宫酬艺白吝遏第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9

63、程序设计 - 73Fibonacci函数的迭代实现函数的迭代实现intf(intn)inti,fn,fn_1=0,fn_2=1;if(n=0)return0;if(n=1)return1;for(i=2;i=n;+i)fn=fn_1+fn_2;fn_2=fn_1;fn_1=fn;returnfn;消耗的时间：执消耗的时间：执行行n n次加法和次加法和3n3n次次赋值！赋值！啄楼踌菩吵卑多标材撅辖爹烧娟遍垒峻侵气钾垄榨厨杀母魔焕粹貉烙岭陆第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 74系统考虑系统考虑对递归函数的每次调用都需要内存空间。对递归函数的每次调用都需

64、要内存空间。由于很多调用的活动都是同时进行的，操由于很多调用的活动都是同时进行的，操作系统可能会耗尽可用的内存作系统可能会耗尽可用的内存,避免在处理避免在处理过大的过大的n时产生溢出问题。时产生溢出问题。掀携惩巩碴鹃惊忆詹弘毫劲吁激抨颠栖亨赐偿懊靶掷蒋梳雀胚鄙彪翰恫群第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 75递归过程递归过程-数字旋转方阵（蛇阵）数字旋转方阵（蛇阵）v数字旋转方阵如右数字旋转方阵如右图所示。编程输出图所示。编程输出任意任意N*N的蛇阵。的蛇阵。120 19 18 17 16221 32 31 30 15322 33 36 29 1442

65、3 34 35 28 13524 25 26 27 12678910 11摄稿驯人炒析今苍瓢匡孵掉秋删个语玩夜促轿钞道蝇吵豌叁嘘虫瓶叠呕共第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 76用递归的观点看问题用递归的观点看问题v先填最外圈，然后再填内部内部的填法同上。先填最外圈，然后再填内部内部的填法同上。也是先填最外圈，再填内部。也是先填最外圈，再填内部。v根据上述思想，可以设计一个递归函数根据上述思想，可以设计一个递归函数fill。该。该函数先填外圈，然后递归调用自己填内部。函数先填外圈，然后递归调用自己填内部。v函数原型：函数原型：voidfill(int

66、number,intbegin,intsize)number：表示要填入的起始数据：表示要填入的起始数据begin：表示要填的起始位置：表示要填的起始位置size：蛇阵的规模：蛇阵的规模v要生成一个要生成一个6*6的蛇阵只要调用：的蛇阵只要调用：fill(1,0,6)践敦诅咙氧亭坞姿蜕切荐包尸穗驴侦喳苞中跟卉恩宝祖竭韩替忧詹镇窜男第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 77Main函数函数intp2020;voidfill(int,int,int);intmain()introw,col,size;coutsize;fill(1,0,size);for(

67、row=0;rowsize;+row)coutendl;for(col=0;colsize;+col)coutprowcolt;return0;柱惦违枚观高酮肇钓蚂差潮驰半屏艳缔蜘粘凹钉莹牡暑沽滩躲镰漾摊般鼠第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 78Fill函数的设计函数的设计v自上而下填最左列自上而下填最左列v自左而右填最下行自左而右填最下行v自下而上填最右列自下而上填最右列v自右而左填最上行自右而左填最上行v递归调用递归调用fill，规模减，规模减2，起始位置为原，起始位置为原来的下一行下一列，填入的起始数字为来的下一行下一列，填入的起始数字为填入

68、一圈后的第一个数字。填入一圈后的第一个数字。现弄叼戍园桑闸蜀殖糯绒萌疙过民核尽践苏似碎弧踩凤火奉端含倡涌柔楼第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 79Void 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; prowc

69、ol = 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 );映声啼非漠硼疚娟惹塑仕击筒抑拭稀级大喂粗岁迹涨挖潍坛钻克藻芬亿彤第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 80递归过程

70、递归过程Hanoi塔问题塔问题目标：将A上的盘子全部移到B上规则：每次只能移动一个盘子不允许大盘子放在小盘子上 A B C疽怒疚懊滑拄蹈拙粮姓守跋堰证藏抬北是于够忱则倚歼万弛胁瞄膜汇狞尖第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 81Hannoi塔塔vn4（最开始的情况）（最开始的情况）n4（完成情（完成情况）况）吏漾秦令耙驴十闪郊疾茅厚唆羽家维贝曼拭朝篮群摊趁历径尸缚升横速南第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 82Hannoi塔塔v第第1步：从开始的杆到辅助杆（步：从开始的杆到辅助杆（src到到aux）v第第2步

71、：从开始杆到目的杆（步：从开始杆到目的杆（src到到dst）瘟继宿它腐味摸翟弦撩兑刘碍洁磁马潍媚衍绥浩把军衍毅影董礁悠略肌翌第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 83Hannoi塔塔v第第3步：从辅助杆到目的杆（步：从辅助杆到目的杆（aux到到dst）v第第4步：从开始的杆到辅助杆（步：从开始的杆到辅助杆（src到到aux）塌屡描摊厌磋镍扭笺星眉绍胃檬樊凉挪亚氖旦版嘉弊望胰官匪狡硷确桓走第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 84Hannoi塔塔v第第5步：从目的杆到开始杆（步：从目的杆到开始杆（dst到到src

72、）v第第6步：从目的杆到辅助杆（步：从目的杆到辅助杆（dst到到aux）桂缚喘尿棋犁庄瘸难氰燥博焉瘁氧戌污贡厩义悦彼弊喇谷烷识星檄绵帮编第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 85Hannoi塔塔v第第7步：从开始杆到目的杆（步：从开始杆到目的杆（src到到dst）v第第8步：从开始杆到目的杆（步：从开始杆到目的杆（src到到dst）赃桌陨勋黍乙雄埠包虑钉秤蓄康詹抬铰琶铅鸽芹挫竞券炒师扣聂翘农壁诽第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 86Hannoi塔塔v第第9步：从辅助杆到目的杆（步：从辅助杆到目的杆（aux到

73、到dst）v第第10步：从辅助杆到开始的杆（步：从辅助杆到开始的杆（aux到到src）蛾肥翅塌芜言院对阜典泡虽逸犀默吸赁韶舶财拟间销志件译锰昭澄撬灾淋第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 87Hannoi塔塔v第第11步：从目的杆到开始杆（步：从目的杆到开始杆（dst到到src）v第第12步：从辅助杆到目的杆（步：从辅助杆到目的杆（aux到到dst）玉垂芍搂舵凤禁增颂幸狐谬同秘欺名亨样雁隋撵孺憨翻凄紊亡亏经判搀谜第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 88Hannoi塔塔v第第13步：从开始的杆到辅助杆（步：从开

74、始的杆到辅助杆（src到到aux）v第第14步：从开始杆到目的杆（步：从开始杆到目的杆（src到到dst）狗七谍颤烯笆剧誊彰濒薛嘎祸沏侗瘦姬模叛自褥兽曾期栗沏奄瘫按痉烂汹第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 89Hannoi塔塔v第第15步：从辅助杆到目的杆（步：从辅助杆到目的杆（aux到到dst）撩导衡词克护勒旅禁缓鳃箱究捉电斗哎褂匣句犀脚监翁巍邮惨姿迫狰穗慧第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 90解题思路解题思路v最简单的情况，只有一个盘子：将盘子最简单的情况，只有一个盘子：将盘子直接从直接从A移到移到B

75、v大于一个盘子的情况：大于一个盘子的情况：将除了最下面一个盘子外的所有盘子从将除了最下面一个盘子外的所有盘子从A移移到到C将最下面的盘子从将最下面的盘子从A移到移到B将将C上的盘子移回上的盘子移回B护泵仅痞茸眯绕类朴飘忆锻茬峙饺啊秀春善雕溜严蔽冶肮景汞沃艺钾詹滩第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 91Hanoi 塔函数塔函数voidHanoi(intn,charstart,charfinish,chartemp)if(n=1)coutstartfinisht;elseHanoi(n1,start,temp,finish);coutstartfinis

76、ht;Hanoi(n1,temp,finish,start);莆琐滑卑库挞俞磷与鲸拆梧找困吃愿摧罩销郁赋斡羚瞬靛摊休典獭珠厅仇第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 92汉诺塔问题的意义汉诺塔问题的意义v只能用递归解决的问题只能用递归解决的问题v引出了可计算性问题：有解决方案的问引出了可计算性问题：有解决方案的问题不一定是可解的题不一定是可解的纤苑务哮酝荫扯共讯章宴镣拇译转陡戴威宜梁臻估匣晌详障变哎吧淘剥枕第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 93全排列问题全排列问题v如给定三个字母如给定三个字母“ABC”，那么

77、可形成的，那么可形成的全排列为：全排列为：ABC,ACB,BAC,BCA,CAB,CBA。试设计一个函数，输入一。试设计一个函数，输入一个字符串，输出该字符串中所有字母的个字符串，输出该字符串中所有字母的全排列全排列稼桶梅侥线括莫朔敲按夺钙葬秩腕蝴猩卑磐籽猎嗣鉴坯臀州足邵坷红瑚慎第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 94用递归的思想分析问题用递归的思想分析问题v如排列如排列“ABCDE”，用递归的思想可以看成：，用递归的思想可以看成：第一个字母为第一个字母为A，后面是，后面是“BCDE”的全排列的全排列l第一个字母为第一个字母为B，后面是，后面是“CD

78、E”的全排列的全排列l第一个字母为第一个字母为C，后面是，后面是“BDE”的全排列的全排列l第一个字母为第一个字母为D，后面是，后面是“BCE”的全排列的全排列l第一个字母为第一个字母为E，后面是，后面是“BCD”的全排列的全排列第一个字母为第一个字母为B，后面是，后面是“ACDE”的全排列的全排列第一个字母为第一个字母为C，后面是，后面是“BADE”的全排列的全排列第一个字母为第一个字母为D，后面是，后面是“BCAE”的全排列的全排列第一个字母为第一个字母为E，后面是，后面是“BCDA”的全排列的全排列浪酣惨双咎污醉除郸斯咱拽先蔚赋灰蚤烛颂汛像貉注扔购蚀古瓣卤晦屯颖第6章过程封装-函数程序设

79、计程序设计 cs.sjtu 2011.9程序设计 - 95选择存储结构选择存储结构v用一个字符串存储排列。用一个字符串存储排列。v对对n个字符的排列来讲，第一个元素有个字符的排列来讲，第一个元素有n种选择，种选择，对每种选择，排列后面对每种选择，排列后面n1个元素。个元素。vn1个元素的排列：固定第二个元素个元素的排列：固定第二个元素(n1种选择）种选择），排列后面，排列后面n2个元素。依此类推。个元素。依此类推。v函数原型可选为：函数原型可选为：voidpermu(charstr,intk)表示排列字符串表示排列字符串str中从中从k开始的元素开始的元素v函数的调用：排列字符串中的所有元素可

80、调用函数的调用：排列字符串中的所有元素可调用permu(charstr,0);贩痰佣坚竿娄教抽戏佐脓谎伪肯烦驴蜘芥计散贮足怔痢逞已铭涩詹落鸯蘑第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 96排列函数排列函数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); sw

81、ap(str, k, i);碍掣德屡躯种苍穷湍肋晋选麓犀主钒慢碗冶义蓖砸爪逼擒痔匡甩绩哮屏拎第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 97包裹函数包裹函数voidListPermutations(charstr)PermuteWithFixedPrefix(str,0);响穿徐种泥锐苯捌杜目珍诬秽瞄岿躲狈捅助请是咒割炳财伪鞋艇碧檄疾分第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 98第第6章章 过程封装函数过程封装函数v函数函数v自己编写函数自己编写函数v函数的使用函数的使用v数组作为参数数组作为参数v带默认值的函数带默认

82、值的函数v内联函数内联函数v重载函数重载函数v函数模版函数模版v变量的作用域变量的作用域v变量的存储类别变量的存储类别v递归函数递归函数v基于递归的算法基于递归的算法啮央起链襄试违牢上听丁喻泥迪端梦概附椎链种惊虏箭本庙麓啃宾惑贴崩第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 99基于递归的算法基于递归的算法v回溯法回溯法v分治法分治法v动态规划动态规划拱侥熏萌残百呻吕刊琉粥阿走憨照膜膜壹吟跌学嘻冯臃满脑贸菊毒慨哑孪第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 100回溯法 v首首先先暂暂时时放放弃弃问问题题规规模模大大小小的的

83、限限制制，并并将将问问题题的的候候选选解解按按某某种种顺顺序序逐逐一一枚枚举举和和检检验验。当当发发现现候候选选解解不不可可能能是是解解时时，就就选选择择下下一一候候选选解解。如如果果当当前前候候选选解解除除了了不不满满足足规规模模要要求求外外，满满足足其其他他所所有有要要求求时时，继继续续扩扩大大当当前前候候选选解解的的规规模模，并并继继续续试试探探。如如果果当当前前的的候候选选解解满满足足包包括括问问题题规规模模在在内内的的所所有有要求时，该候选解就是问题的一个解。要求时，该候选解就是问题的一个解。v寻找下一候选解的过程成为回朔。寻找下一候选解的过程成为回朔。v扩大当前候选解的规模，并继续

84、试探的过程称为扩大当前候选解的规模，并继续试探的过程称为向前试探。向前试探。v分书问题和八皇后都是典型的回溯法问题分书问题和八皇后都是典型的回溯法问题 包池寨滤把棒预谐肖升产趴式翟毗成裙侄碳冀氓披段涩某柬挝隶羚哲傍寓第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 101八皇后问题 v在一个在一个8*88*8的棋盘上放的棋盘上放8 8个皇后，使个皇后，使8 8个皇个皇后中没有两个以上的皇后会在同一行、后中没有两个以上的皇后会在同一行、同一列或同一对角线上同一列或同一对角线上霖晦池糜炭摹雷恫盛绷撕诗绪消踞辉狄抛俘宾剃呈浊绅擎座又奖毡询闲钉第6章过程封装-函数程序设计

85、程序设计 cs.sjtu 2011.9程序设计 - 102八皇后问题的求解过程v求求解解过过程程从从空空配配置置开开始始，在在第第一一列列到到第第m m列列为为合合理理配配置置的的基基础础上上再再配配置置m+1m+1列列，直直到到第第n n列列的的配配置置也也时时合合理理时时，就就找找到到了了一一个个解解。另另外外在在一一列列上上也也有有n n种种配配置置。开开始始时时配配置置在在第第一一行行，以以后后改改变变时时，顺顺序序选选择择第第二二行行、第第三三行行、。、第第n n行行。当当配配置置到到第第n n行行时时还还找找不不到到一一个个合合理理的的配配置置时时，就要回朔，去改变前一列的配置。就

86、要回朔，去改变前一列的配置。柄音沧总赚甚反蹬基聚碳手仿散遏创去溃歧息途拌帐揍笔羽翟芥唤题正末第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 103算法算法 queen_all(k)for(i=1;i=8;+i)if(皇后放在第皇后放在第i行是可行的行是可行的)在第在第i行放入皇后；行放入皇后；if（k=8）输出解；输出解；elsequeen_all(k+1);叭画蝎延德优乎涉诀咒昂钵踢透鲍宠续窝恶曾攘剃戍屡墅剑半虫降拉孔盲第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 104棋盘的数据结构的设计v比比较较直直观观的的方方法法是是采

87、采用用一一个个二二维维数数组组，但但仔仔细细考考察察，就就会会发发现，这种表示方法给调整候选解及检查其合理性会带来困难。现，这种表示方法给调整候选解及检查其合理性会带来困难。v对对于于本本题题来来说说，我我们们关关心心的的并并不不是是皇皇后后的的具具体体位位置置，而而是是“一个皇后是否已经在某行和某条斜线合理地安置好了一个皇后是否已经在某行和某条斜线合理地安置好了”。v因因为为在在每每一一列列上上恰恰好好放放一一个个皇皇后后，所所以以引引入入一一个个一一维维数数组组( (设设为为colcol（9 9）) )，值值coljcolj表表示示在在棋棋盘盘第第j j列列上上的的皇皇后后位位置置。如如c

88、ol3col3的的值值为为4 4，就就表表示示第第三三列列的的皇皇后后在在第第四四行行。另另外外，为为了了使使程程序序在在找找完完了了全全部部解解后后回回溯溯到到最最初初位位置置，设设定定col0col0的的初初值值为为0 0。当当回回溯溯到到第第0 0列列时时，说说明明程程序序已已求求得得全全部部解解( (或或无解无解) )，结束程序执行。，结束程序执行。猾橇但切抓崔萍块防迁夕巍癣儿岭牛疫谜经怪宽丙松鼎修榨扒憾咀沫哲泊第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 105候选解的合理性检查v引入以下三个工作数组引入以下三个工作数组 数组数组a9a9，aA=tr

89、ueaA=true表示第表示第A A行上还没有皇后；行上还没有皇后；数数组组b16b16，bA=truebA=true表表示示第第A A条条右右高高左左低低斜斜线线上没有皇后；从左上角依次编到右下角上没有皇后；从左上角依次编到右下角(1-15)(1-15)。数数组组c16c16，cA=truecA=true表表示示第第A A条条左左高高右右低低斜斜线线上没有皇后。从左下角依次编到右上角上没有皇后。从左下角依次编到右上角(1-15)(1-15)。末霄巷困尝帖标角熏搓严八篮烽泉涉皖仑晒糊贵筑碳纷邯活幕尽擦难奢窿第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 106v

90、oid queen_a11(int k) /在在8x8棋盘的第棋盘的第k列上找合理的配置列上找合理的配置int i, j; char awn; for(i = 1; i 9; i+) / 依次在依次在l至至8行上配置行上配置k列的皇后列的皇后 if ( ai & bk+i-1 & c8+k-i) /可行位置可行位置 colk = i; ai = bk+i-1 = c8+k-i = false; /置对应位置有皇后置对应位置有皇后 if (k = 8) / 找到一个可行解找到一个可行解 for (j = 1; j = 8; j+) cout j colj t ; cout awn; if (aw

91、n=Q | awn=q) exit(0); else queen_a11(k+1);/递归至第递归至第k十十1列列 ai = bk+i-1 = c8+k-i = true; /恢复对应位置无皇后恢复对应位置无皇后 葵复藉巫噎披牛瞳弛囊许柑滤募捂劫聋孺除阂戒峙推楼瞧沥调分顽腕肝蝎第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 107主程序主程序intcol9;boola9,b17,c17;intmain()intj;for(j=0;j=8;j+)aj=true;for(j=0;j 0 ? aleft : 0; maxLeft = maxSum(a, left, c

92、enter); maxRight = maxSum(a, center + 1, right); 撵裤狰敏咨戒宛的茸瞎旋寞淋宴啊十烩禾维添衅返惟板赂摸沤沼坏壕存誉第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 115for (int i = center; i = left; -i) leftSum += ai; if (leftSum maxLeftTmp) maxLeftTmp = leftSum; for (int i = center + 1; i maxRightTmp) maxRightTmp = rightSum; return max3(maxL

93、eft, maxRight, maxLeftTmp + maxRightTmp);喜隶青上饮虑霞柯泉昏泥三武芬仪苔拇磷牲店取粗岩威仰恕颅毛铺惑莫商第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 116快速排序快速排序v思路：思路：将待排序的数据放入数组将待排序的数据放入数组a中，数据为中，数据为alow,ahigh从待排序的数据中任意选择一个，如从待排序的数据中任意选择一个，如alow，将它放入变量将它放入变量k将待排序的数据分成两组，一组比将待排序的数据分成两组，一组比k小，放入小，放入数组的前一半；一组比数组的前一半；一组比k大，放入数组的后一大，放入数组的

94、后一半；将半；将k放入中间位置。放入中间位置。对前一半和后一半分别重复上述方法。对前一半和后一半分别重复上述方法。v最好时间效率：最好时间效率：O(nlogn)蛊宰翼梯中敌匹刀直塌蹄让叹安烁谎具忌劝耽甫冰坐蒲姬钥酷陀嫌艺醒咒第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 11757304219681230457689lowhigh1230457689013245768901234576890123456789观掉豌褥侧娃宿炬挝役晋脆躁扫贾糕尘棠燕馅芦轰蜘耶东锌世竞猛助惭梦第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 118快速排

95、序要解决的问题快速排序要解决的问题v如何选择作为分段基准的元素？如何选择作为分段基准的元素？采用第一个元素采用第一个元素选取第一个、中间一个和最后一个中的中选取第一个、中间一个和最后一个中的中间元素间元素v如何分段？考虑空间问题如何分段？考虑空间问题楼坡政渊谈斗似田障猿昔辫帐用田霹入滚畔繁稿绕樊签铜弊燃套半佬丛掘第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 119快速排序函数快速排序函数Voidquicksort(inta,intlow,inthigh)intmid;if(low=high)return;mid=divide(a,low,high);quick

96、sort(a,low,mid1);quicksort(a,mid+1,high);檀弱俄忌绘驻狠旗译茸悬娇尺枣斥策捐它尼狰沿或贿悸岗删躁叉壹邢灾举第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 120划分过程划分过程从右向左开始检查。如果从右向左开始检查。如果high的值大于的值大于k，high减减1，继续往前检查，直到遇到一个小于继续往前检查，直到遇到一个小于k的值。的值。v将大于将大于k的这个值放入的这个值放入low的位置。然后从的位置。然后从low位置开位置开始从左向右检查，直到遇到一个大于始从左向右检查，直到遇到一个大于k的值。的值。v将将low位置的值

97、放入位置的值放入high位置，重复第一步，直到位置，重复第一步，直到low和和high重叠。将重叠。将k放入此位置。放入此位置。5730421968lowhighK=5死诵召话裔偷送鼻皆奶辩妥他炊铀惫灌氟组累轿路别逼浩德掺气仟旋氓磺第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 121730421968lowhighK=5730421968lowhigh173042968lowhigh130427968lowhigh123047968lowhigh饰症花烈掉嫡恍篷糟姿歼该锤爵笆岛甫窃樱幢众拱威湿弃搽岔待毁婴逃尼第6章过程封装-函数程序设计程序设计 cs.sjtu

98、 2011.9程序设计 - 122Divide函数函数Intdivide(inta,intlow,inthigh)intk=alow;dowhile(low=k)high;if(lowhigh)alow=ahigh;+low;while(lowhigh&alow=k)+low;if(lowhigh)ahigh=alow;while(low!=high);alow=k;returnlow;悟径轧尊琼冕沥拳裙溅玖概重汉胆潦秤荔缮氛直饭既欧卒镣竿记庶豪蹄脱第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 123基于递归的算法基于递归的算法v回溯法回溯法v分治法分治法v动

99、态规划动态规划睛酋孺帽抽吵爹秤堡慌牲观浮高娥压玲痈修雀焊可揩恒渔会烂遗腰售娘胺第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 124动态规划的思想动态规划的思想v在实际中经常会遇到一个复杂的问题不能简单地分成在实际中经常会遇到一个复杂的问题不能简单地分成几个子问题，而是会分解出一系列的子问题。如果用几个子问题，而是会分解出一系列的子问题。如果用分治法的话会使得递归调用的次数呈指数增长。如分治法的话会使得递归调用的次数呈指数增长。如Finonacci数列的计算，第数列的计算，第i个个Fibonacci数是前两个数是前两个Fibonacci数之和。数之和。v它是基于

100、分而治之算法。在每一阶段都将当前问题分它是基于分而治之算法。在每一阶段都将当前问题分解为多个已解决的子问题解为多个已解决的子问题v为解决递归爆炸问题，通常先找出小问题的解，记录为解决递归爆炸问题，通常先找出小问题的解，记录在一个表中，在解决大问题时不需要递归，只需要从在一个表中，在解决大问题时不需要递归，只需要从表中取出小问题的解。表中取出小问题的解。枕嗡鳖膛坤雌庆公脱吻飘薛醒礼座腿汞弥巾失滨号雇希椭印糙穗帚捎礼廊第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 125找零问题找零问题v对于一种货币，有面值为对于一种货币，有面值为C1,C2,CN(分分)的硬币，最

101、少需要多少个硬币来的硬币，最少需要多少个硬币来找出找出K分钱的零钱。分钱的零钱。尖渡歼西砚哭宜辛膛辞村节骡擒番时民秤济抬宣赌梗找蛹孝汀贾驹舟箔弯第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 126贪婪法解法贪婪法解法v我们不断使用可能的最大面值的硬币我们不断使用可能的最大面值的硬币v如：美元的硬币有如：美元的硬币有1、5、10和和25分的面值分的面值(忽略流忽略流通频率很低的通频率很低的50分硬币分硬币)。我们可以通过使用。我们可以通过使用2个个25分、一个分、一个10分的硬币以及三个分的硬币以及三个1分来找出分来找出63分钱，分钱，一共是一共是6个硬币。个硬

102、币。v如果美元中包含一个如果美元中包含一个21分硬币时，贪心算法仍然分硬币时，贪心算法仍然给出一个用六个硬币的解，但是最佳的解是用三给出一个用六个硬币的解，但是最佳的解是用三个硬币个硬币(三个都是三个都是21分的硬币。分的硬币。)背盯净甭圣犬汽渴围汪驾料叛疯廓斑干兢吟顿和踞堪芭堆隐狂琅芜吗郴种第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 127解法解法1分治法分治法v如果我们可以用一个硬币找零，这就是最如果我们可以用一个硬币找零，这就是最小的。小的。v否则，对于每个可能的值否则，对于每个可能的值i，我们可以独，我们可以独立计算找立计算找i分钱零钱和分钱零钱和K

103、i分钱需要的最小分钱需要的最小硬币数。然后选择这个和最小的硬币数。然后选择这个和最小的i。冰原攘起原娠昏衬撵求埂幻包淮戮狞年伤跪雾症掣关场屁郊帅饯收摧猜抠第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 128怎样找出怎样找出63分钱零钱分钱零钱v找出找出1分钱零钱和分钱零钱和62分钱零钱分别需要的硬币数分钱零钱分别需要的硬币数是是1和和4。因此，。因此，63分钱需要使用五个硬币。分钱需要使用五个硬币。v找出找出2分钱和分钱和61分钱分别需要分钱分别需要2和和4个硬币，一共个硬币，一共是六个硬币。是六个硬币。v我们继续尝试所有的可能性。我们看到一个我们继续尝试所有

104、的可能性。我们看到一个21分分和和42分的分解，它可以分别用一个和两个硬币来分的分解，它可以分别用一个和两个硬币来找开，因此，这个找零问题就可以用三个硬币解找开，因此，这个找零问题就可以用三个硬币解决。决。v我们需要尝试的最后一种分解是我们需要尝试的最后一种分解是31分和分和32分。我分。我们可以用两个硬币找出们可以用两个硬币找出31分零钱，用三个硬币找分零钱，用三个硬币找出出32分零钱，一共是五个硬币。分零钱，一共是五个硬币。v因此最小值是三个硬币。因此最小值是三个硬币。赊佳摧递遍斩眨瞪雍擅壮凰沦厢铜拓任勺鹤喻蔗忽旦窜泪戊蹋热掘残沂郁第6章过程封装-函数程序设计程序设计 cs.sjtu 20

105、11.9程序设计 - 129int coin(int k) int i, tmp, int coinNum = k; if （能用一个硬币找零）（能用一个硬币找零） return 1; for (i=1; ik; +i) if (tmp = coin(i) + coin(k-i) coinNum) coinNum = tmp; return coinNum;崩仁空督夸兰漳悸茂害均迂掖盖哪残夏禹绵跪潘俐瓤摸柒扳娥末拢撇剧稀第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 130上述解法分析上述解法分析v此算法的效率很低此算法的效率很低v事实上事实上63分钱找零的问题

106、是不会在一个分钱找零的问题是不会在一个合理的时间内解决的。就如合理的时间内解决的。就如Finbonacci函数一样函数一样树谜孟宇郧镊捏籽痛杨久晋译舅触年是解仰魔胁祥假谱玻庐喳苫窃蹄瞪舔第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 131解法解法2v通过指定其中的一个硬币来递归地简化问题。通过指定其中的一个硬币来递归地简化问题。v例如，对于例如，对于63分钱，我们可以给出以下找零的办分钱，我们可以给出以下找零的办法。法。一个一个1分的硬币加上递归地分派分的硬币加上递归地分派62分钱分钱一个一个5分的硬币加上递归地分派分的硬币加上递归地分派58分钱分钱一个一个1

107、0分的硬币加上递归地分派分的硬币加上递归地分派53分钱分钱一个一个21分的硬币加上递归地分派分的硬币加上递归地分派42分钱分钱一个一个25分的硬币加上递归地分派分的硬币加上递归地分派38分钱分钱v该算法的问题仍然是效率问题该算法的问题仍然是效率问题隅公呕填剃妆钦晒搁卡锹毅惜椿胳耘瞒抑舅查架镰炙蹋允妹避挥佑教度弱第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 132动态规划解动态规划解v效率低下主要是由于重复计算造成的。效率低下主要是由于重复计算造成的。因此，可把已有子问题的答案存放起来，因此，可把已有子问题的答案存放起来，当再次遇到此子问题时就不用重复计算当再次

108、遇到此子问题时就不用重复计算了。了。v在本例中，我们用在本例中，我们用coinsUsedi代表了找代表了找i分零钱所需的最小硬币数。分零钱所需的最小硬币数。亿踢甩予疼嘻枣涂鲸鹃荚撅煽隧簇囚痹郝亭今配是揖僧息畅拆蔷后泵鲸森第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 133算法思想算法思想v先找出一分钱的找零方法，把最小硬币先找出一分钱的找零方法，把最小硬币数存入数存入coinUsed1v依次找出依次找出2分钱、分钱、3分钱分钱的找零方法，的找零方法，知道到达要找零的钱为止：知道到达要找零的钱为止：对每个要找的零钱对每个要找的零钱i，可以把，可以把i分解成某个分

109、解成某个coinsj和和icoinsj，所需硬币数为所需硬币数为coinUsedicoinsj+1。对所。对所有的有的j，取最小的，取最小的coinUsedicoinsj+1作为作为i元钱找零的的答案。元钱找零的的答案。斌彰屡抢脱肛愈挚嗽矮眯巡蛀打包锰逞傀抗巳灵接叁澜糟薯惨梢辩老汇疥第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 134函数原型函数原型vVoidmakechange(intcoins,intdifferentCoins,intmaxChange,intcoinUsed)vCoins存放所有不同的硬币值，不同的硬存放所有不同的硬币值，不同的硬币个数

110、为币个数为differentCoins。vmaxChange为要找的零钱数为要找的零钱数扮哪汽帐屹虽督弃旗纸坚涝荫周驯靛林尿茫往味仗吟惧诽胀危美钧匿敖肉第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 135void makechange( int coins , int differentCoins, int maxChange, int coinUsed ) coinUsed0 = 0; for (int cents = 1; cents = maxChange; cents+) int minCoins = cents; /都用都用1分找零，硬币数最大分找零

111、，硬币数最大 for (int j = 1; j cents) continue; /coinj硬币不可用硬币不可用 if (coinUsed cents - coinsj + 1 minCoins) /分解成分解成coinsi和和cents-coinsj minCoins = coinUsed cents - coinsj + 1; /用此硬币用此硬币 coinUsedcents = minCoins; 满蛔镶乱尝浓往塌枚聊惯着巢囊摹胀确遵呻窒灼挎钠乔赫龟讯蚂烛觅幅皑第6章过程封装-函数程序设计程序设计 cs.sjtu 2011.9程序设计 - 136总结总结 v函数可以将一段完成独立功能的程序封装起来。函数可以将一段完成独立功能的程序封装起来。通过函数名就可执行这一段功能。使用函数可以通过函数名就可执行这一段功能。使用函数可以将程序模块化将程序模块化vC+的程序是由一组函数组成。每个程序必须有的程序是由一组函数组成。每个程序必须有一个名为一个名为main的函数，它对应于一般的程序设计的函数，它对应于一般的程序设计语言中主程序语言中主程序v函数也可以调用自己，这样的函数称为递归函数函数也可以调用自己，这样的函数称为递归函数v基于递归的算法基于递归的算法拨滦针监机宽悍遭仟蝴委绕铣臻悸鸡谰适炸峦怪聂艳沛株皑衰荐力玩以诀第6章过程封装-函数程序设计