高中信息竞赛-一维数组.ppt

循环语句 Description猴子吃桃问题 猴子摘了一堆桃 第一天吃了一半 还嫌不过瘾 又吃了一个 第二天又吃了剩下的一半零一个 以后每天如此 到第n天 猴子一看只剩下一个了 问最初有多少个桃子 Input输入一个数n n 20 Output输出最初的桃子个数SampleInput2SampleOutput4 猴子吃桃问题1538 Description阿姆斯特朗数 如果一个正整数等于其各个数字的立方和 则该数称为阿姆斯特朗数 也称自恋数 如407 4 3 0 3 7 3 试编程求出n n 10000 以内的所有阿姆斯特朗数 Input输入一个数nOutput输出所有的所有阿姆斯特朗数 每行一个数字 阿姆斯特朗数1537 Description已知faibonacci数列的前几个数分别为0 1 1 2 3 5 编程求出此数列的第n项 n由键盘输入 n 60Input输入数字n n 60 Output输出faibonacci数列中的第n个数SampleInput5SampleOutput3 faibonacci数列1539 一维数组的定义和引用 数组是同一数据类型的一组值 10个char或15个long 在内存中顺序存放 整个数组共用一个名字 而其中的每一项又称为一个元素 一 定义方式 类型说明符数组名 常量表达式 longa 4 表明a数组由4个int型元素组成 定义类型 数组名称 元素个数 longa 4 表明a数组由4个int型元素组成其元素分别为 a 0 a 1 a 2 a 3 其序号从0开始 若存放首地址为2000H 则在内存中为 C 不允许对数组的大小作动态的定义 即数组的大小不能是变量 必须是常量 必须是常数 如果要根据不同的数值改变数组的大小 可用常量表达式 如 defineSIZE50intmain intart SIZE 二 一维数组元素的引用 数组必须先定义 具体引用时 赋值 运算 输出 其元素等同于变量 intmain longi a 10 for i 0 i 0 i cout a i cout n 输出 9 8 7 6 5 4 3 2 1 0 定义 赋值 输出 i 0 a 0 0 i 1 a 1 1 a 0 1 2 i 2 a 2 2 9 i 9 a 9 9 三 一维数组的初始化 在定义数组的同时给数组元素赋值 注意 1 对数组中的一部分元素列举初值 未赋值的部分是0 longa 10 0 1 2 3 4 5 2 不能给数组整体赋值 只能一个一个地赋值 longa 10 0 1 2 9 非法 longa 10 0 1 2 3 4 5 6 7 8 9 longa 10 0 1 2 3 4 5 0 0 0 0 3 可以用longa 0 1 2 3 4 5 6 7 8 9 给数组赋值 编译器会自动计算出内的元素项数 并将数组定义为该长度 4 可以给数组全部清0 如 longa 100 0 longn i f 61 0 f 0 0 f 1 1 cin n for i 2 i n 1 i f i f i 1 f i 2 cout f n 1 Fibonacci数列1539 f i f i 1 f i 2 longn i f 61 0 f 1 0 f 2 1 cin n for i 3 i n i f i f i 1 f i 2 cout f n Description 有一对小兔 过一个月之后长成大兔 到第四个月就可以生下一对小兔 并且以后每个月都生下一对小兔 而所生的一对小兔也同样到一个月之后长成大兔 到第四个月就可以生下一对小兔 并且以后也每个月都生下一对小兔 假设所有的兔子均不死亡 问第n个月后共有多少对兔子 请设计一个程序 解决这一问题 Input 一个整数n n 50 Output 第n个月后共有多少对兔子SampleInput 5SampleOutput 3 兔子繁殖1559 includeusingnamespacestd intmain longa 51 0 1 1 1 i n cin n if n 4 cout 1 else for i 4 i n i a i a i 1 a i 3 cout a n system pause 兔子繁殖1559 排序算法 用起泡法对6个数排序 由小到大 将相邻的两个数两两比较 将小的调到前头 第五趟循环1次 for i 1 ia j 1 t a j a j a j 1 a j 1 t includeusingnamespacestd intmain longi j n t a 101 cin n for i 1 i a i for i 1 ia j 1 t a j a j a j 1 a j 1 t for i 1 i n i cout a i system pause includeusingnamespacestd intmain longi j n t a 101 cin n for i 1 i a i for i 1 ia j t a i a i a j a j t for i 1 i n i cout a i system pause 想一想 选择排序方法 Description 给定一串整数数列 求出所有的递增和递减子序列的数目 如数列7 2 6 9 8 3 5 2 1可分为 7 2 2 6 9 9 8 3 3 5 5 2 1 5个子序列 答案就是5 我们称2 9 3 5为转折元素 Input 输入第一行为n 第二行为n个数 Output 输出所有的递增和递减子序列的数目SampleInput 9726983521SampleOutput 5 数列1153 Description输入一串小写字母 以 为结束标志 统计出每个字母在该字符串中出现的次数 若某字母不出现 则不要输出 Input输入一串小写字母 以 为结束标志 中间可能有非法输入 Output输出每个字母在该字符串中出现的次数 若某字母不出现 则不要输出 SampleInputaaaabbbccc SampleOutputa 4b 3c 3 统计字符次数1154 二维数组的定义和引用 一 定义方式 类型说明符数组名 常量表达式 常量表达式 inta 3 4 其元素分别为 a 0 0 a 0 1 a 0 2 a 0 3 a 1 0 a 1 1 a 1 2 a 1 3 a 2 0 a 2 1 a 2 2 a 2 3 表明a数组由3 4个long型元素组成 定义类型 数组名 行数 列数 二 二维数组的引用 与一维数组一样 二维数组必须先定义 其维数必须是常量 具体引用时 赋值 运算 输出 其元素等同于变量 intmain inta 2 3 i j cout a i j for i 0 i 2 i 输出 for j 0 j 3 j cout a i j cout endl 输入 123456 输出 1 2 34 5 6 定义 赋值 输出 三 二维数组的初始化 在定义数组的同时给数组元素赋值 即在编译阶段给数组所在的内存赋值 1 分行赋值 inta 3 4 1 2 3 4 5 6 7 8 9 10 11 12 2 顺序赋值 inta 3 4 1 2 3 4 5 6 7 8 9 10 11 12 依次赋值 3 部分赋值 inta 3 4 1 5 9 a 0 0 1 a 1 0 5 a 2 0 9其余元素为0 inta 3 4 0 1 5 a 0 0 0 a 0 1 1 a 1 0 5 4 分行或全部赋值时 可以省略第一维 第二维不可省 inta 4 1 2 5 6 7 8 9 10 11 12 5 不能给数组整体赋值 只能一个一个地赋值 inta 2 3 1 2 3 12 有一个3 4的矩阵 要求编程序求出其中值最大的那个元素的值 以及其所在的行号和列号 先考虑解此问题的思路 从若干个数中求最大者的方法很多 我们现在采用 打擂台 算法 如果有若干人比武 先有一人站在台上 再上去一人与其交手 败者下台 胜者留台上 第三个人再上台与在台上者比 同样是败者下台 胜者留台上 如此比下去直到所有人都上台比过为止 最后留在台上的就是胜者 程序模拟这个方法 开始时把a 0 0 的值赋给变量max max就是开始时的擂主 然后让下一个元素与它比较 将二者中值大者保存在max中 然后再让下一个元素与新的max比 直到最后一个元素比完为止 max最后的值就是数组所有元素中的最大值 max a 0 0 使max开始时取a 0 0 的值for i 0 imax 如果某元素大于max max a i j max将