过程和函数精选文档.ppt

《过程和函数精选文档.ppt》由会员分享，可在线阅读，更多相关《过程和函数精选文档.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、过程和函数本讲稿第一页，共二十八页过程部分过程部分本讲稿第二页，共二十八页【问题描述】给一维数组输入任意n个整数，假设为n=6：7 4 8 9 1 5请建立一个具有以下内容的方阵：7 4 8 9 1 54 8 9 1 5 78 9 1 5 7 49 1 5 7 4 81 5 7 4 8 95 7 4 8 9 1问题一问题一 变化方阵变化方阵【输入样例】6【输出样例】7 4 8 9 1 54 8 9 1 5 7 8 9 1 5 7 4 9 1 5 7 4 8 1 5 7 4 8 9 5 7 4 8 9 1本讲稿第三页，共二十八页【问题分析】读入n个数放在一个一维数组中之后，就可以放心来处理这个问

2、题了，那么这个数字组成的方阵有什么规律呢？注意到其中的每一行其实就是将第一个数字放置在最后一个位置，其他的向前平移一位，那么这样一个相同的操作，就可以使用过程来完成，单独定义一个平移和插入的操作。每次拿这个一维数组去做这样的过程就可以了。【关键点】平移+过程本讲稿第四页，共二十八页问题二问题二 加法运算加法运算【问题描叙】求a+b的和（-10100a,b 10100）【输入样例】1 2 【输出样例】3本讲稿第五页，共二十八页【问题分析】虽然说的是加法，实际上还是比较复杂的，如果你仔细注意到其中的a、b的取值范围，你就会发现，其实这之中还有减法，而且这个问题也是超过正常数字保存的范围，所以需要高

3、精度。因此我们需要定义两个过程，一个是加法的、一个减法，这样我们把各种的情况都考虑清楚就可以了。【关键点】过程+高精度加减法本讲稿第六页，共二十八页问题三问题三 圣诞树圣诞树【问题描叙】圣诞节要到了，不少商家在宣传板上绘制了圣诞树的图案，如图所示。一棵圣诞树由A和B两部分组成：A是由n（n）个呈三角形的字符矩阵构成的，每个字符矩阵由三个参数ai、bi、ci唯一确定。Ai表示字符矩阵第一行字符的个数；bi表示字符矩阵从第二行开始每一行与它上面那行的字符数之差均为bi；ci则表示字符矩阵的行数。B是一个x行y列的长方形，由x和y这两个参数唯一确定。因为圣诞树是中轴对称的，所以根据所有的参数构成的圣

4、诞树是唯一确定的。简单来讲，我们所说的一棵圣诞树就是像图那样的*矩阵，每一行的字符是指若干个连在一起的*。本讲稿第七页，共二十八页【输入格式】输入数据分若干行。第一行是一个整数n，表示A部分中字符矩阵的个数。以下n行，每行有三个正整数ai、bi、ci（ai为奇数，bi为偶数）。输入数据的最后一行，有两个正整数x、y（y是奇数），表示B部分的行数和列数。【输出格式】对于输入数据给定的圣诞参数，输出与之对应的圣诞树矩阵。【说明】（1）输入数据保证圣诞树不会超出一页纸的范围。（2）要求圣诞树是轴对称的，并且字符矩阵的第一列至少有一个非空格字符，即圣诞树尽量“顶格写”。在以上要求下，输出的圣诞树矩阵一

5、定是唯一的（不考虑每行行末的空格）。本讲稿第八页，共二十八页【输入样例】31 4 35 4 35 4 42 5【输出样例】*本讲稿第九页，共二十八页【问题分析】题目中已经提示我们，圣诞树是由A 和B 两部分构成。因此绘制图形也分两部分来考虑。而A 和B 的绘制都要考虑图形的对称轴。于是，将整个问题分解为三个子问题：（）确定对称轴；（）绘制A 部分；（）绘制B 部分。本讲稿第十页，共二十八页【问题分析】分析子问题：设*个数最多的行有m 个*，那么A 和B 部分的对称轴所在列数就应该是（m ）div 。分析子问题：A 部分分成了n 段树，每一段树的图形打印方式是类似的，所以只需要着眼于如何打印某一

6、段树即可。这个小问题是一个关于循环的问题，在循环结构程序设计中已经研究过。分析子问题：B 部分的填充比较容易，填入x 行，每行y 个*即可。再深入分析一下，还有一个巧妙的处理，B 部分实际上相当于A 中的特殊段：ai y，bi ，ci x。于是，子问题 也可以归入子问题。至此，成功解决了输出圣诞树这个问题。【关键点】过程+找规律本讲稿第十一页，共二十八页函数部分函数部分本讲稿第十二页，共二十八页问题问题4 信封问题信封问题【问题描述】在第一轮预选赛中，蓝猫和淘气轻松过关。他们俩准备给远方的啦啦寄去2张他们自己设计的卡片。蓝猫准备的卡片大小为90毫米70毫米，淘气准备的卡片大小为120毫米60毫

7、米，他们发现快递公司的标准信封大小为340毫米245毫米，用那个信封真是浪费了。如果他们自己设计一个120毫米70毫米的信封完全可以装下两张卡片。如果他们设计的卡片太大，快递公司的信封又装不下。（按照快递（按照快递公司的标准来）公司的标准来）现在请你编程帮助他们计算一下，如果给出他们设计的卡片大小，能同时装下这两张卡片的信封最小尺寸是多少？本讲稿第十三页，共二十八页输入格式：输入文件只有一行，有四个用空格隔开的整数，分别表示蓝猫和淘气设计的卡片大小，以毫米为单位输出格式：输出文件只有一行，有两个用空格隔开的整数，表示最小信封的大小，以毫米为单位，要求将较长的边写在前面。【输入样例】90 70

8、120 60【输出样例】120 70【数据范围】在70%的数据中，1N30000；在100%的数据中，1N2000000000；本讲稿第十四页，共二十八页【问题分析】本题简要的题意就是找到两个卡片的长度最长的，宽度最长的，可是第一个和第三个数真的是最大值吗？题意没有说明所以，需要调整：第一种办法是把第一个数和第二个数、第三个数和第四个数从大到小排序。第二种办法是求出第一个数和第二个数的最大值和最小值，第三个数和第四个数的最大值和最小值。解决了这个问题后，我们可以将第一个数和第三个数求最大值，第二个数和第四个数求最大数。这样就可以了吗？本讲稿第十五页，共二十八页【问题分析】注意到数据的范围，如果

9、超出了快递公司的规定如何呢？对，我们还要将刚才求出的卡片的长宽的最大值再和340与245求最小值。这道题目才算结束，不断的求最大值和最小值，这个重复不断要去求值，这样的东西不正好符合我们的函数嘛，所以我们自定义两个最大数和最小数的函数，这样不断的去调用，这个问题就可以完美的解决。【关键点】函数+题意理解本讲稿第十六页，共二十八页问题问题5 5 多数最大公约数多数最大公约数【问题描叙】输入n个正整数求它们的最大公约数。（提示：可用一个数组将n个数存放起来，然后求第一个数和第二个数的公约数，再求第三个数与前两个数公约数的公约数，这样求得前三个整数最大公约数如此类推可求出个整数的最大公约数）【输入样

10、例】3 2 4 8【输出样例】2本讲稿第十七页，共二十八页【问题分析】多个数求最大数，好像没有直接的算法，当然你如果愿意写递归的话也是可以的。那么我们只能两个两个的求最大公约数。那么我们可以把求两个数最大公约数程序段写个函数，然后再把这个最大公约数和后面的每个数求最大公约数。【关键点】函数+最大公约数本讲稿第十八页，共二十八页问题问题6 哥德巴赫猜想哥德巴赫猜想【问题描叙】对6-1000内的偶数验证哥德巴赫猜想：任何一个大于6的偶数总可以分解为两个素数之和。【输出样例】6=3+3 8=3+5 1000=497+503【说明】如果有多组解，需要找到差最小的那两个数。本讲稿第十九页，共二十八页【问

11、题分析】本题当然需要枚举，对象主要有两个：（一）总的和，从6到1000所有的数。（二）第一个数，小于总的和一半，从2到开始。但是这里如何判断是否是素数呢？而且是两个数，那么这里可以采用函数来判断。但是实际上如果数据范围过大，甚至也可以使用先筛选，再判断，这样就没有必要使用函数了，过程也是可以的。【关键点】枚举+素数判断本讲稿第二十页，共二十八页问题问题7 合数查找合数查找【问题描叙】将合数483的各位数字相加（4+8+3）=15，如果将483分解成质因数相乘：483=3*7*23，把这些质因数各位数字相加（3+7+2+3），其和也为15。即某合数的各位数字之和等于它所有质因数的各数字之和。求5

12、00以内具有上述特点的所有合数。【说明】输出的时候都需要保留原来存在的零，同 时如果数值相等，零的个数多的在前面。本讲稿第二十一页，共二十八页【问题分析】先还是要产生500个自然数，当然是枚举了。再者就是判断素数，需要筛或者函数判断，这其中需要分解求和，也可以写个函数。【关键点】频繁使用函数本讲稿第二十二页，共二十八页问题问题8 8 围棋比赛围棋比赛【问题描述】参加完智取能量棒的比赛，蓝猫又来到了围棋的赛场。这儿的围棋比赛有特殊的规定：有N个人要参加围棋比赛，该比赛要进行K场对弈。每个人最多参加两场对弈，最少参加零场对弈。每个人都有一个与其他人不相同的等级（用一个正整数来表示）。在对弈中，等级

13、高的人必须用黑色的棋子，等级低的人必须用白色的棋子。每人最多只能用一次黑色的棋子和一次白色的棋子。为了增加比赛的可观度，鸡大婶希望K场对弈中双方的等级差的总和最小。本讲稿第二十三页，共二十八页比如有7个选手，他们的等级分别是30；17；26；41；19；38；18，要进行3场比赛。最好的安排是：选手2 vs 选手7，选手7 vs 选手5，选手 6 vs 选手4，此时等级差的总和等于(18-17)+(19-18)+(41-38)=5达到最小。输入格式：输入文件第一行有两个正整数N,K接下来有N行，第i+1行表示第i 个人的等级。输出格式：输出文件仅包含一个数，表示最小的等级差的总和【输入样例】【

14、输出样例】7 3 5 30 17 26 41 19 38 18【数据范围】在70%的数据中，1N3000；在100%的数据中，1N100000；保证所有输入数据中等级的值小于108，1KN-1。本讲稿第二十四页，共二十八页【问题分析】从数据中分析我们知道有种策略：先对等级排序，无所谓大小，然后求出等级差，再对等级差排序，可是等级差有多少个呢？（N-1个），然后再取出前K个个人的情况。所有需要进行数组地址传递。【关键点】数组做参数+贪心本讲稿第二十五页，共二十八页问题问题9 切橡皮泥游戏切橡皮泥游戏【问题描叙】聪明的小明有n块橡皮泥（只考虑长度，不考虑高与宽），现在想把这些橡皮泥块切割成k块长度

15、相同的小橡皮泥条（原橡皮泥块可以有剩余），整数k是已知的。小明希望得到的橡皮泥条越长越好，请你设计一个程序帮助小明计算能够得到的小橡皮条的最大长度。题目中的长度单位都是厘米。原橡皮泥块的长度都是正整数，切割得到的小橡皮泥条的长度也是正整数。输入:第一行是两个正整数n和k(1 n 10000，1 k 10000)，n是原橡皮泥的块数，k是需要得到的小橡皮泥条的数目。接下来的n行，每行有一个1到10000之间的正整数，表示原n块橡皮泥每块的长度。本讲稿第二十六页，共二十八页输出:输出能够切割得到的小橡皮泥条的最大长度。如果得到的小橡皮泥条最大长度小于1厘米，则输出”0”。样例：输入（plas.in

16、）：3 7232124456输出（plas.out）：114本讲稿第二十七页，共二十八页【问题分析】枚举其中的每一个长度，从1到10000，然后判断，判断可以写个函数。时间效率O（10000*n），注意到n的范围，这种方法在极限数据下是超时的，那么如何解决呢?其实在这里我们可以看到小橡皮泥的枚举的长度是递增有序的，我们无非是在这个范围内找到一个符合条件的答案而已，那么我们应该如何解决呢？二分查找给我们提示，我们可以在这范围内查找left:=0;right:=10000;while leftright do begin mid:=(left+right)div 2;if judge(mid)then left:=mid else right:=mid-1;end;【关键点】二分枚举+函数。本讲稿第二十八页，共二十八页