程序设计基础w06chap06数据组织一递推思想数组定义字符数组part1课件

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

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

3、务分析：令fact(n)表示n的阶乘，依据后项与前项的关系，可以写出下面的“递推”公式：fact(1) = 1 - 起始条件（边界条件）fact(n) = n * fact(n-1) - 通项公式算法实现：根据前后项的关系，显然，用循环结构来实现这种递推关系是非常自然的。请看下面的代码实现。6【任务 A】6#include using namespace std;int main()int N;cout please input N (N N;int fact;for (int n=1; n=N; n+)if (n = 1)fact = 1;/ 起始条件elsefact = n * fact;

4、 / fact_n = n * fact_n_1cout fact( N ) = fact endl;return 0;7#include 7【任务 B】王小二自夸刀功不错，有人放一张饼在砧板上，问他：“饼不许离开砧板，如果切刀，你最多能将饼分成多少块？”刀刀刀刀8【任务 B】刀刀刀刀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由于要求最多的块数，所以每刀都是让每

5、两条线都有交点。用归纳法不难得到： q(0) = 1 - 初始条件（边界条件） q(n) = q(n-1) + n - 通项公式9在编程之前要找到规律9#include using namespace std;int main()int q;for (int n=0; n=100; n+)if (n = 0) / 起始条件q = 1;elseq = n + q; / q_n = n + q_n_1cout q(100) = q endl;return 0;10#include 10数组是计算机语言提供的组织多个数据的一种重要方式：提供了多个同类型的数据（值）在内存中连续存放的工具提供了对无限量

6、内存单元进行高效“命名”的途径提供了在程序运行过程中动态改变“变量名称”的手段是一些重要算法思想的实现基础数组11数组是计算机语言提供的组织多个数据的一种重要方式：数组11类型说明符 数组名常量表达式 ;TYPE array_nameconst_expr;例：float sheep_weight10;int _a20011000; char student_name20; 说明1. 数组变量的名称，必须符合语言对变量命名的要求；2. 用方括号将常量表达式括起；3. 常量表达式定义了数组元素的个数；数组的定义12类型说明符 数组名常量表达式 ;数组的定义12注意：在使用VC+6.0进行编程时，数

7、组元素的数目，要使用常量表达式，其中不能包含变量例如int n; n = 5;int an;不合法！因为 n 是变量，不是常量VC+ 6.0:error C2057: expected constant expression13注意：在使用VC+6.0进行编程时，数组元素的数目，要使用数组中每个元素所在的内存单元，可以通过“数组名位置下标”来访问（赋值、读取）。数组元素的位置下标从 0 开始计数。例如，int a5；定义了一个含有5个整数的数组，各元素的“变量名称”分别为：a0, a1, a2, a3, a4是5个带下标的变量，它们的类型是相同的。该数组的效果与下面的变量定义相同：int a0

8、, a1, a2, a3, a4;数组中元素的“名称”14数组中每个元素所在的内存单元，可以通过“数组名位置下标”数组元素的位置关系与内存地址 a a0 a1 a2 a3 a4说明：a0元素的内存地址，即&(a0)，也被称为“数组的地址（元素首地址）”。数组名与下标一起使用时，是一个变量，表示下标值指定位置的元素。数组名单独使用时，表示数组首地址，是一个指针常量（也称常量指针），可赋值给同类型指针。sizeof(a) = sizeof(a0) * number15数组元素的位置关系与内存地址 a15所有类型均可以用下面的格式来初始化数组（变量）：type_name array_nameN =

9、v1, v2, . , vN ;其中，v1, v2等表示常量表达式。例如：int a5 = 3, 5, 4, 1, 2 ;char b5 = c, h, 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() / 在定义时设定值

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

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

12、or (int i=0; i10; i+) cout Ai int(Ai); cout Bi endl; return 0; / char_test_3.cpp阅读示例代码3，注意总结21#include 阅读示例代码3，注意总2222#include using namespace std;int main() / 在定义时设定值，被称为“变量初始化” charA1 = BeiJing;/ 一共给出了7个字符 intB1 = 1,2,3,4,5; / 一共给出了5个整数 cout sizeof(A1) sizeof(A1) endl; cout sizeof(B1) sizeof(B1) e

13、ndl; charA210 = BeiJing;/ 一共给出了7个字符 intB210 = 1,2,3,4,5;/ 一共给出了5个整数 cout sizeof(A2) sizeof(A2) endl; cout sizeof(B2) sizeof(B2) endl; return 0; / char_test_4.cpp阅读示例代码4，猜猜输出23#include 阅读示例代码4，猜猜输BeiJing0A124这个结尾处的0字符是编译器自动添加的BeiJing0A124这总结说明数组变量在“初始化”时（即至少提供了一个初始值），如果提供的初始值数目少于数组元素的个数，则依下标大小顺序，从下标为

14、0的元素开始，逐一设定初始值，缺少初始值的数组元素，将被编译器自动设置成0。以字符串常量方式对字符数组进行“初始化”时，也同样遵循上述规则。如果初始化时不设定数组大小（元素数目），则编译器自动根据初始值的数目来设定数组的大小。当以字符串常量方式对字符数组进行初始化时，编译器设定的数组大小是：“字符串常量长度+1”，即不遵循上述规则！25总结说明数组变量在“初始化”时（即至少提供了一个初始值），如上机验证26上机验证26数组变量的赋值27数组变量的赋值27程序设计基础w06chap06数据组织一递推思想数组定义字符数组part1课件这是一个伪命题！数组变量的赋值这是一个伪命题！数组变量的赋值所有

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

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

17、signment of arrays34#includeLine 6: erro#include using namespace std;int main()char h = 123456;h = “abcef”;cout h endl;return 0;strcpy(h, abcdef);35#include strcpy(h, 通过cin操作，对字符数组变量进行“赋值”数组中各元素的赋值#includeusing namespace std;int main() char h = 123456789; cin h; / 设键入的是 abcdef cout h endl; / 则程序输出 a

18、bcdef return 0;如果键入的是 123456789012345则程序会输出什么？36通过cin操作，对字符数组变量进行“赋值”数组中各元素的赋值如果是字符数组（变量），则cout会将数组的所有元素一齐输出出来，字符之间无空格。如果是其他类型的元素组成的数组（变量），则cout只会输出该数组变量的地址，也即数组第一个元素所在内存单元的地址。cout是如何根据数据类型来决定输出方式的呢？这个问题，将在下学期面向对象程序设计中予以解答。数组变量的“cout 输出”37如果是字符数组（变量），则cout会将数组的所有元素一齐输出#includeusing namespace std;int

19、 main() char h = tsinghua;h0=a; h1=b;h2=4; h3=7; h4=c;cout h endl; int a = 1,2,3,4,5;a0 = 79; a1 = 88;a2 = 34; a3 = 64; a4 = 99;cout a endl; cout &(a0) = &(a0) endl;return 0; 38#include38上述结果说明：数组a的第一个元素的地址，与a的值相等。即 cout a; 与 cout &(a0); 等效。39上述结果说明：数组a的第一个元素的地址，与a的值相等。39字符数组（字符串）的应用示例“老张开车去东北，撞了！ 肇

20、事司机耍流氓，跑了！” 目击者对交警说：肇事汽车的号码为4位完全平方数，且数字从左到右一个比一个大。 请帮交警算出肇事车的号码。40字符数组（字符串）的应用示例40#include#includeusing namespace std; void find_it() / . int main()find_it( );return 0;41#include41思路I： 令 n 为车号 n为 4 位数 n = i*i, i = 32, 33, , 99 (31*31=961) 对 i 进行枚举，得不同的 n , 对每个 n ，检查 n的各位， 从高位到低位, 是否一个比一个大？即，低位的数值最大。

21、 n n3 n2 n1 n0 n3 n2 n1 n0 42思路I：42void find_it()for (int i=32; i100; i+) int n = i * i;if ( ( (n/1000) (n/100 % 10) ) & ( (n/100 % 10) (n/10 % 10) ) & ( (n/10 % 10) (n % 10) ) ) cout 肇事汽车号码为 n endl;四位数的千位数字 n3 = n / 1000百位数字 n2 = n / 100 % 10十位数字 n1 = n / 10 % 10个位数字 n0 = n % 1043void find_it()四位数的

22、千位数字 n3 = n 现在，车号升级啦！变成了五位！闯祸的车号居然还是一个完全平方数!依然还是从高位到低位一个比一个大！（越来越大）这时，程序该怎么编（或修改）呢？四位数的千位数字 n3 = n / 1000百位数字 n2 = n / 100 % 10十位数字 n1 = n / 10 % 10个位数字 n0 = n % 1044现在，车号升级啦！变成了五位！四位数的千位数字 n3 = n思路II（还是以四位数的车号为例说明）： 令 n 为车号 n为 4 位数， n = i*i i = 32, 33, , 99 (31*31=961) 枚举 i 到 n , 查 n 从高位到低位, 是否一个比一

23、个小 将 n 分解为 4 个数字字符: char *itoa( int value, char *string, int radix) value: 待转换整数string: 存放转换结果的字符串指针radix: 2-16进制整数45思路II（还是以四位数的车号为例说明）：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 446 #include#includeusing namespace std; int main() char buf5; /定义数组 int i=0, n=0; /定义整数变量47

24、#include47for( i=32; i100; i+) / 计数循环 n = i*i; / 构造4位数n itoa( n, buf , 10 ); / 把10 进制数 n 转换为字符串放入 buf 数组 if ( (buf0buf1) & / 如果buf中的 (buf1buf2) & / 字符串从左至右 (buf2buf3) ) / 一个比一个小cout 肇事汽车号码为 / 则输出 n endl; / _if_ / _for_ return 0; 能把程序改得更简洁清晰吗？48for( i=32; i100; i+) for ( i=32; i100; i+) n = i*i; itoa

25、( n, buf , 10 ); int j; for (j=0; j = bufj+1) break; / 若n符合要求，则FOR循环会全部执行完！if (j = 3)cout 肇事汽车号码为 n endl; / _for_ return 0; 修改后的程序，是不是更简洁清晰了？49for ( i=32; i100; i+) for ( i=32; i100; i+) n = i*i; itoa( n, buf , 10 ); int j; for (j=0; j = bufj+1) break; / 若n符合要求，则FOR循环会全部执行完！if (j = 3)cout 肇事汽车号码为 n

26、endl; / _for_ return 0; 想一想：如何把程序改成能解决五位数（或更多）的车号呢？50for ( i=32; i100; i+) for ( i=32; i100; i+) n = i*i; itoa( n, buf , 10 ); int j; for (j=0; j = bufj+1) break; / 若n符合要求，则FOR循环会全部执行完！if (j = 3)cout 肇事汽车号码为 n endl; / _for_ return 0; 这些地方需要修改！51for ( i=32; i=1; i-) fishi+1%4 !=0 true fales break; fi

27、shi=1+ fishi+1*5/4; do while( i= 1)定义数组并初始化输出计算结果57定义数组并初始化输出计算结果57上图的说明：该图可分为三部分(1) 是说明部分：包含定义数组 fish6，并初始化为 1 和定义循环控制变量 i，并初始化为 0。(2) 是 do.while 直到型循环，其循环体又含两块：(2.1) 是枚举过程中的 fish5 的初值设置，一开始 fish5=1+5; 以后每次增 5。(2.2) 是一个 for 循环，i的初值为 4，终值为 1，步长为 -1，该循环的循环体是一个分支语句，如果 fishi+1不能被 4 整除，则跳出 for 循环（使用 bre

28、ak 语句;）否则，从 fishi+1 算出fishi。58上图的说明：该图可分为三部分58当 break 语句让程序退出循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令fish 5 加 5 后再试，即重新进入直到型循环 do while 的循环体。当正常退出 for 循环时，一定是控制变量 i 从初值 4，一步一步执行到终值 1，每一步的鱼数均为整数，最后 i = 0，表示计算完毕，且也达到了退出直到型循环的条件。(3) 输出计算结果59当 break 语句让程序退出循环时，意味着某人看到的鱼数#include using namespace std;int main() int

29、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循环elsefishi=fishi+1*5/4+1;/ 计算第i人看到的鱼数 while( i=1 ); / 当 i=1 继续做do循环 / 输出计算结果 for (i=1; i=5; i+)cout fishi endl; return 0;60#include 60/*/* 程 序 名：9_.cpp（五人合伙捕鱼） */* 作 者：wuwh

30、 */* 编制时间：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+1; while( i=1 ); 6262 初始化E=1 E=E+5 break yes 递 E

31、 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 初始化E=1 E=E+56331212496199615961276输出结果643121输出结果64#include using namespace std;int main() int fisher6; / 五个人看到的鱼数 for (int num = 6; ; num += 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满足