程序设计基础徐明星w06－chap06－数据组织一－递推思想－数组定义－字符数组－part1

1、,6 数据的组织与处理（一）数组,2014.10.27 III-3200,1,递推的解题思路 数组的概念、定义和初始化 字符数组、字符串处理 筛法的解题思路 数组元素的查找（线性查找与二分查找） 数组排序的思路（冒泡排序法） 多维数组（维以上）,学 习 目 标,2,【任务 一】 A、B、C、D、E 五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自在湖边的树丛中找地方睡着了。 日上三竿，A第一个醒来，他将鱼平分作五份，把多余的一条扔回湖中，拿自己的一份回家去了。B第二个醒来，也将鱼平分为五份，扔掉多余的一条，只拿走自己的一份。接着 C、D、E 依次醒来，也都按同样的办法分鱼。 问五人至少合伙捕到多少条鱼

2、？每个人醒来后看到的鱼数是多少条？,3,为了解决上面这种类型的问题，需要学习和运用“递推”的思想，以及如何使用“数组”这种数据组织的形式来实现递推的过程。 下面先来介绍“递推”的算法思想。,4,递推是计算机数值计算中的一个重要算法，可以将复杂的运算化为若干重复的简单运算，以便充分发挥计算机长于重复处理的特点。 通常，使用循环结构来实现重复处理。解决此类问题的关键是：分析简单情况，归纳总结出前后项的关系（通项公式）。,递 推,5,【任务 A】 求自然数n的阶乘。 任务分析： 令fact(n)表示n的阶乘，依据后项与前项的关系， 可以写出下面的“递推”公式： fact(1) = 1 - 起始条件（

3、边界条件） fact(n) = n * fact(n-1) - 通项公式 算法实现： 根据前后项的关系，显然，用循环结构来实现这种递推关系是非常自然的。请看下面的代码实现。,6,#include using namespace std; int main() int N; cout N; int fact; for (int n=1; n=N; n+) if (n = 1) fact = 1;/ 起始条件 else fact = n * fact; / fact_n = n * fact_n_1 cout fact( N ) = fact endl; return 0; ,7,【任务 B】 王

4、小二自夸刀功不错，有人放一张饼在砧板上，问他：“饼不许离开砧板，如果切刀，你最多能将饼分成多少块？”,刀,刀,刀,刀,8,在编程之前要找到规律 分析： 令q(n)表示切n刀能分成的块数。从前面的图中可以找出下列关系： q(1) = 1 + 1 = 2 q(2) = 1 + 1 + 2 = 4 q(3) = 1 + 1 + 2 + 3 = 7 q(4) = 1 + 1 + 2 + 3 + 4 = 11 由于要求最多的块数，所以每刀都是让每两条线都有交点。用归纳法不难得到： q(0) = 1 - 初始条件（边界条件） q(n) = q(n-1) + n - 通项公式,9,#include usin

5、g namespace std; int main() int q; for (int n=0; n=100; n+) if (n = 0) / 起始条件 q = 1; else q = n + q; / q_n = n + q_n_1 cout q(100) = q endl; return 0; ,10,数组是计算机语言提供的组织多个数据的一种重要方式： 提供了多个同类型的数据（值）在内存中连续存放的工具 提供了对无限量内存单元进行高效“命名”的途径 提供了在程序运行过程中动态改变“变量名称”的手段 是一些重要算法思想的实现基础,数组,11,类型说明符 数组名常量表达式 ; TYPE ar

6、ray_nameconst_expr; 例：float sheep_weight10; int _a20011000; char student_name20; 说明 1. 数组变量的名称，必须符合语言对变量命名的要求； 2. 用方括号将常量表达式括起； 3. 常量表达式定义了数组元素的个数；,数组的定义,12,注意：在使用VC+6.0进行编程时，数组元素的数目，要使用常量表达式，其中不能包含变量 例如int n; n = 5; int an;不合法！ 因为 n 是变量，不是常量,VC+ 6.0: error C2057: expected constant expression,13,数组中

7、每个元素所在的内存单元，可以通过“数组名位置下标”来访问（赋值、读取）。数组元素的位置下标从 0 开始计数。 例如，int a5；定义了一个含有5个整数的数组，各元素的“变量名称”分别为： a0, a1, a2, a3, a4 是5个带下标的变量，它们的类型是相同的。该数组的效果与下面的变量定义相同： int a0, a1, a2, a3, a4;,数组中元素的“名称”,14,数组元素的位置关系与内存地址,a a0 a1 a2 a3 a4 说明： a0元素的内存地址，即 其中，v1, v2等表示常量表达式。 例如：int a5 = 3, 5, 4, 1, 2 ; char b5 = c, h,

8、 i, n, a ; 如果是由字符（char）组成的数组，则还可以使用： char array_nameN = 各种字符; 例如：char b6 = china; / why 6 ? N必须是字符串长度+1，其初始化结果为： b0 = c; b1 = h; ; b4 = a;,数组变量的初始化,16,#include using namespace std; int main() / 在定义时设定值，被称为“变量初始化” char A10 = B, e, i, J, i, n, g; / 一共只给出了7个字符 for (int i=0; i10; i+) cout Ai int(Ai) end

9、l; / 强制类型转换，将字符值转换成整数值，即其ASCII码 / 语法格式： dst_type (src_value) return 0; / char_test.cpp,阅读示例代码1，注意总结,17,18,#include using namespace std; int main() / 在定义时设定值，被称为“变量初始化” char A10 = BeiJing; / 一共只给出了7个字符 for (int i=0; i10; i+) cout Ai int(Ai) endl; / 强制类型转换，将字符值转换成整数值，即其ASCII码 / 语法格式： dst_type (src_val

10、ue) return 0; / char_test_2.cpp,阅读示例代码2，注意总结,19,20,#include using namespace std; int main() / 在定义时设定值，被称为“变量初始化” char A = BeiJing; / 一共给出了7个字符 int B = 1,2,3,4,5; / 一共给出了5个整数 for (int i=0; i10; i+) cout Ai int(Ai); cout Bi endl; return 0; / char_test_3.cpp,阅读示例代码3，注意总结,21,22,#include using namespace

11、std; int main() / 在定义时设定值，被称为“变量初始化” charA1 = BeiJing;/ 一共给出了7个字符 intB1 = 1,2,3,4,5; / 一共给出了5个整数 cout sizeof(A1) sizeof(A1) endl; cout sizeof(B1) sizeof(B1) endl; charA210 = BeiJing;/ 一共给出了7个字符 intB210 = 1,2,3,4,5;/ 一共给出了5个整数 cout sizeof(A2) sizeof(A2) endl; cout sizeof(B2) sizeof(B2) endl; return 0

12、; / char_test_4.cpp,阅读示例代码4，猜猜输出,23,A1,24,这个结尾处的0字符是编译器自动添加的,总结说明,数组变量在“初始化”时（即至少提供了一个初始值），如果提供的初始值数目少于数组元素的个数，则依下标大小顺序，从下标为0的元素开始，逐一设定初始值，缺少初始值的数组元素，将被编译器自动设置成0。 以字符串常量方式对字符数组进行“初始化”时，也同样遵循上述规则。 如果初始化时不设定数组大小（元素数目），则编译器自动根据初始值的数目来设定数组的大小。 当以字符串常量方式对字符数组进行初始化时，编译器设定的数组大小是：“字符串常量长度+1”，即不遵循上述规则！,25,上机

13、验证,26,数组变量的赋值,27,这是一个伪命题！,数组变量的赋值,所有类型的数组变量 均不可以直接赋值,数组变量的赋值,30,int a5; char b5; a = 1,2,3,4,5; b = CHINA;,数组变量的赋值,31,单独一个一个进行赋值 int a5; a0=1; a3=23; 使用for语句，连续赋值 char a5; for (int i=0; i5; i+) ai = A + i;,数组中各元素的赋值,32,使用一些特殊的库函数 （）使用memset函数，格式为 memset(起始地址, 初始值, 空间大小)； 举例： memset(sheep, 0, sizeof(

14、sheep); 将名为 sheep 的数组中的全部元素均初始化为 0。调用此库函数需要加入头文件 。 （）使用字符串处理函数，例如： strcpy(字符数组名，字符串常量或变量); 举例：char school_name20; strcpy(school_name, Tsinghua);,数组中各元素的赋值,33,#include using namespace std; int main() char h = 123456; h = abcdef; cout h endl; return 0; 程序会出什么问题？,Line 6: error: ISO C+ forbids assignmen

15、t of arrays,34,#include using namespace std; int main() char h = 123456; h = “abcef”; cout h endl; return 0; ,strcpy(h, abcdef);,35,通过cin操作，对字符数组变量进行“赋值”,数组中各元素的赋值,#include using namespace std; int main() char h = 123456789; cin h; / 设键入的是 abcdef cout h endl; / 则程序输出 abcdef return 0; 如果键入的是 12345678

16、9012345 则程序会输出什么？,36,如果是字符数组（变量），则cout会将数组的所有元素一齐输出出来，字符之间无空格。 如果是其他类型的元素组成的数组（变量），则cout只会输出该数组变量的地址，也即数组第一个元素所在内存单元的地址。 cout是如何根据数据类型来决定输出方式的呢？这个问题，将在下学期面向对象程序设计中予以解答。,数组变量的“cout 输出”,37,#include using namespace std; int main() char h = tsinghua; h0=a; h1=b; h2=4; h3=7; h4=c; cout h endl; int a = 1,

17、2,3,4,5; a0 = 79; a1 = 88; a2 = 34; a3 = 64; a4 = 99; cout a endl; cout ,38,上述结果说明：数组a的第一个元素的地址，与a的值相等。 即 cout a; 与 cout 等效。,39,字符数组（字符串）的应用示例 “老张开车去东北，撞了！ 肇事司机耍流氓，跑了！” 目击者对交警说：肇事汽车的号码为4位完全平方数，且数字从左到右一个比一个大。 请帮交警算出肇事车的号码。,40,#include #include using namespace std; void find_it() / . int main() find_i

18、t( ); return 0; ,41,思路I： 令 n 为车号 n为 4 位数 n = i*i, i = 32, 33, , 99 (31*31=961) 对 i 进行枚举，得不同的 n , 对每个 n ，检查 n的各位， 从高位到低位, 是否一个比一个大？即，低位的数值最大。 n n3 n2 n1 n0 n3 n2 n1 n0,42,void find_it() for (int i=32; i100; i+) int n = i * i; if ( ( (n/1000) (n/100 % 10) ) ,四位数的千位数字 n3 = n / 1000,百位数字 n2 = n / 100 %

19、10,十位数字 n1 = n / 10 % 10,个位数字 n0 = n % 10,43,现在，车号升级啦！变成了五位！ 闯祸的车号居然还是一个完全平方数! 依然还是从高位到低位一个比一个大！ （越来越大） 这时，程序该怎么编（或修改）呢？,44,思路II（还是以四位数的车号为例说明）： 令 n 为车号 n为 4 位数， n = i*i i = 32, 33, , 99 (31*31=961) 枚举 i 到 n , 查 n 从高位到低位, 是否一个比一个小 将 n 分解为 4 个数字字符: char *itoa( int value, char *string, int radix) valu

20、e: 待转换整数 string: 存放转换结果的字符串指针 radix: 2-16进制整数,45,n= i * i i 3 3 n 1 0 8 9 itoa( n, buf , 10 ); buf 1 0 8 9 0 0 1 2 3 4,46,#include #include using namespace std; int main() char buf5; /定义数组 int i=0, n=0; /定义整数变量,47,for( i=32; i100; i+) / 计数循环 n = i*i; / 构造4位数n itoa( n, buf , 10 ); / 把10 进制数 n 转换为字符串放

21、入 buf 数组 if ( (buf0buf1) ,能把程序改得更简洁清晰吗？,48,for ( i=32; i= bufj+1) break; / 若n符合要求，则FOR循环会全部执行完！ if (j = 3) cout 肇事汽车号码为 n endl; / _for_ return 0; ,修改后的程序，是不是更简洁清晰了？,49,for ( i=32; i= bufj+1) break; / 若n符合要求，则FOR循环会全部执行完！ if (j = 3) cout 肇事汽车号码为 n endl; / _for_ return 0; ,想一想：如何把程序改成能解决五位数（或更多）的车号呢？,

22、50,for ( i=32; i= bufj+1) break; / 若n符合要求，则FOR循环会全部执行完！ if (j = 3) cout 肇事汽车号码为 n endl; / _for_ return 0; ,这些地方需要修改！,51,任务一的解题思路:,假定A、B、C、D、E 五人的编号分别为1、2、3、4、5，整数数组 fishk 表示第 k 个人所看到的鱼数。fish1 表示A所看到的鱼数，fish2 表示 B 所看到的鱼数 fish1 A所看到的鱼数，合伙捕到鱼的总数 fish2 = (fish1 - 1) * 4 / 5 B所看到的鱼数 fish3 = (fish2 - 1) *

23、 4 / 5 C所看到的鱼数 fish4 = (fish3 - 1) * 4 / 5 D所看到的鱼数 fish5 = (fish4 - 1) * 4 / 5 E所看到的鱼数,53,写成一般式fish i = ( fish i - 1 1 ) * 4 / 5i = 2, 3, ,5,这个公式可用于已知 A 看到的鱼数去推算 B 看到的，再推算 C 看到的，.。现在要求的是 A 看到的。能否倒过来，先知 E 看到的再反推 D 看到的，直到A看到的。为此将上式改写为： fish i-1 = fish i * 5 / 4 +1 i = 5, 4,2,54,分析上式 . 当 i = 5 时，fish i

24、 表示 E 醒来所看到的鱼数，该数应满足被整除后余，所以初值设为+ 2. 当 i = 5 时，fish i-1 表示 D 醒来所看到的鱼数，这个数要满足 fish 4 = fish 5 * 5 / 4 + 1 显然，fish 4 必须是整数，所以fish5必须满足 fish 5 % 4 = 0 这个结论同样可以用至 fish 3 , fish 2 和 fish 1 ,55,3 . 按题意要求 5 人合伙捕到的最少鱼数，可以从小往大枚举，即： 可以先让 E 所看到的鱼数最少为 6 条，即 fish 5 初始化为 6 来试，之后每次增加 5 再试，直至递推到 fish 1 ，均为整数。 根据上述思

25、路，我们可以构思如下的程序框图：,56,fish5=fish5+5; for (i=4; i=1; i-) fishi+1%4 !=0 true fales break; fishi=1+ fishi+1*5/4; do while( i= 1),定义数组并初始化,输出计算结果,57,上图的说明：,该图可分为三部分 (1) 是说明部分：包含定义数组 fish6，并初始化为 1 和定义循环控制变量 i，并初始化为 0。 (2) 是 do.while 直到型循环，其循环体又含两块： (2.1) 是枚举过程中的 fish5 的初值设置，一开始 fish5=1+5; 以后每次增 5。 (2.2) 是一

26、个 for 循环，i的初值为 4，终值为 1，步长为 -1，该循环的循环体是一个分支语句，如果 fishi+1不能被 4 整除，则跳出 for 循环（使用 break 语句;）否则，从 fishi+1 算出fishi。,58,当 break 语句让程序退出循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令fish 5 加 5 后再试，即重新进入直到型循环 do while 的循环体。 当正常退出 for 循环时，一定是控制变量 i 从初值 4，一步一步执行到终值 1，每一步的鱼数均为整数，最后 i = 0，表示计算完毕，且也达到了退出直到型循环的条件。 (3) 输出计算结果,59,#i

27、nclude using namespace std; int main() int fish6=1,1,1,1,1,1; / 记录每人醒来后看到的鱼数 int i=0; do fish5=fish5+5; / 让E看到的鱼数增5。 for (i=4; i=1; i-) if ( fishi+1%4 !=0 ) break; / 跳出for循环 else fishi=fishi+1*5/4+1; / 计算第i人看到的鱼数 while( i=1 ); / 当 i=1 继续做do循环 / 输出计算结果 for (i=1; i=5; i+) cout fishi endl; return 0; ,6

28、0,/* /* 程 序 名：9_.cpp（五人合伙捕鱼） * /* 作 者：wuwh * /* 编制时间：2002年10月2日 * /* 主要功能：递推算法的实现 * /* #include / 预编译命令 using namespace std; int main() /主函数 int fish6=1,1,1,1,1,1; / 整型数组，记录每人 / 醒来后看到的鱼数 int i=0;,61,do fish5=fish5+5; for (i=4; i=1; i=i-1) if ( fishi+1%4 !=0 ) break; / 跳出for循环 else fishi=fishi+1*5/4+

29、1; while( i=1 );,62,初始化E=1 E=E+5 break yes 递 E E%4 !=0 D=( E*5/4 )+1 no 推 yes D D%4 !=0 方 C= ( D*5/4 )+1 no yes 向 C C%4 !=0 B= ( C*5/4 )+1 no yes B B%4 !=0 A= ( B*5/4 )+1 no A,63,3121 2496 1996 1596 1276,输出结果,64,#include using namespace std; int main() int fisher6; / 五个人看到的鱼数 for (int num = 6; ; num

30、 += 5) / 对各种可能性进行枚举 int n; for (n=5; n=1; n-) / 对五个人看到的鱼数进行递推 if (n = 5) fishern = num; else / fishern+1 = (fishern - 1) / 5 * 4; if (fishern+1 % 4 != 0) break; / 鱼数num不满足条件，要尝试下一个num，停止递推 else / 下式所得fishern必然满足 fishern % 5 = 1 fishern = fishern+1 * 5 / 4 + 1; if (n = 0) / 说明鱼数num满足所有人的条件 break; / 找到最小鱼数了，停止枚举 / 输