第二周 简单题(一).ppt

1、2020/7/22,1,第二讲,简单计算题（一）,ACM算法与程序设计,2020/7/22,2,简单计算题,主要目的：通过编写一些简单计算题的程序焘悉CC+语言的基本语法 基本思想：解决简单的计算问题的基本过程包括将一个用自然语言描述的实际问题抽象成一个计算问题给出计算过程继而编程实现计算过程，并将计算结果还原成对原来问题的解答。这里首要的是读懂问题接清输入和输出数据的含义及给出的格式并且通过输入输出样例验证自己的理解是否正确。,2020/7/22,3,题目内容 已知正方形的边长，试编程求出其面积。 输入描述 输入不超过50个正整数的数据n (1=n=10000)，每个正整数间以空格隔开。 输

2、出描述 每次读入一个正整数，便输出其正方形的面积数，输出每个面积后再回车。,先看一个超级简单的题目：,2020/7/22,4,输入样例 1 2 3 4 输出样例 1 9 25 49,2020/7/22,5,初学者很常见的一种写法：,#include void main() int a,b; scanf(“%d”, ,2020/7/22,6,有什么问题呢？,这就是下面需要解决的问题,2020/7/22,7,第一部分,基本输入输出,2020/7/22,8,输入_第一类：,输入不说明有多少个Input Block,以EOF或1为结束标志。 读入一个输入对应一个输出，输入数据可以是多组,读入一个参数,

3、2020/7/22,9,题目分析 怎样判断输入的结束？ scanf函数的原型如下： int scanf(const char *format , argument. ); 其返回值为：成功读取并分配的元素个数。,2020/7/22,10,说明：,Scanf函数返回值就是读出的变量个数，如：scanf( “%d %d”, 如果只有一个整数输入，返回值是1，如果有两个整数输入，返回值是2，如果一个都没有，则返回值是-1。 EOF是一个预定义的常量，等于-1。,2020/7/22,11,例如：,#include int main(void) int a=0,b=0,c=0,k; k=scanf(%d

4、%*d%d, 若输入：1 2 3，则输出为：k=2,a=1,b=3,c=0 注意：常常用while(scanf(“”,)=)来判断循环的进行。,2020/7/22,12,参考源代码,#include int main(void) int a; while(scanf(%d, ,2020/7/22,13,本类输入解决方案：,C语法： while(scanf(%d, while(scanf(%d%d, ,2020/7/22,17,输入_第二类：,输入一开始就会说有N个Input Block,下面接着是N个Input Block。 参见：HDOJ_1090 ,2020/7/22,18,Problem

5、 Description Your task is to Calculate a + b. Input Input contains an integer N in the first line, and then N lines follow. Each line consists of a pair of integers a and b, separated by a space, one pair of integers per line. Output For each pair of input integers a and b you should output the sum

6、of a and b in one line, and with one line of output for each line in input. Sample input: 2 1 5 10 20 Sample output: 6 30,2020/7/22,19,Hdoj_1090源代码：,#include int main() int n,i,a,b; scanf(%d, ,2020/7/22,20,本类输入解决方案：,C语法： scanf(%d, i+ ) . ,2020/7/22,21,输入_第三类：,输入不说明有多少个Input Block,但以某个特殊输入为结束标志。 参见：H

7、DOJ_1091 ,2020/7/22,22,Problem Description Your task is to Calculate a + b. Input Input contains multiple test cases. Each test case contains a pair of integers a and b, one pair of integers per line. A test case containing 0 0 terminates the input and this test case is not to be processed. Output F

8、or each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input. Sample input: 1 5 10 20 0 0 Sample output: 6 30,2020/7/22,23,Hdoj_1091源代码：,#include int main() int a,b; while(scanf(%d %d, ,2020/7/22,24,本类输入解决方案：,C语法： while(s

9、canf(%d, gets(buf); C+语法： 如果用string buf;来保存： getline( cin , buf ); 如果用char buf 255 ; 来保存： cin.getline( buf, 255 );,2020/7/22,27,说明：,scanf(“ %s%s”,str1,str2)，在多个字符串之间用一个或多个空格分隔； 若使用gets函数，应为gets(str1); gets(str2); 字符串之间用回车符作分隔。 通常情况下，接受短字符用scanf函数，接受长字符用gets函数。 而getchar函数每次只接受一个字符，经常c=getchar()这样来使用。

10、,2020/7/22,28,输出_第一类：,一个Input Block对应一个Output Block，Output Block之间没有空行。 参见：HDOJ_1089 ,2020/7/22,29,解决方案：,C语法： . printf(%dn,ans); C+语法： . cout ans endl; ,2020/7/22,30,输出_第二类：,一个Input Block对应一个Output Block，每个Output Block之后都有空行。参见：HDOJ_1095 ,2020/7/22,31,1095源代码,#include int main() int a,b; while(scanf

11、(%d %d, ,2020/7/22,32,解决办法：,C语法： . printf(%dnn,ans); C+语法： . cout ans endl endl; ,2020/7/22,33,第二部分,简单题（一）,2020/7/22,34,最小公倍数, ,2020/7/22,35,Problem Description 求两个正整数的最小公倍数。 Input 输入数据含有不多于50对的数据，每对数据由两个正整数(0n1,n2100000)组成。 Output 对于每组数据n1和n1，计算最小公倍数，每个计算结果应占单独一行。,2020/7/22,36,Sample input: 6 5 18

12、12 Sample output: 30 36,2020/7/22,37,题目分析,最小公倍数等于两数之积除以最大公约数 利用辗转相除法求最大公约数。,2020/7/22,38,#include int gcd(int int) ； Int main() int x,y; while(cinxy) coutx/gcd(x,y)*yend1; return 0; ,#include int gcd(int int) ； Int main() int x,y; while(cinxy) coutx*y/gcd(x,y)end1; return 0; ,2020/7/22,39,欧几里德算法,int

13、 gcd(int x,int y) while (x!=y) if (xy) x=x-y; else y=y-x; return x; ,只要两数不相等，就反复用 大数减小数，直到相等为止， 此相等的数就是两数的最大公 约数。,2020/7/22,40,1021 Fibonacci Again,2020/7/22,41,Problem Description There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n=2). Input Input consists of

14、 a sequence of lines, each containing an integer n. (n 1,000,000). Output Print the word yes if 3 divide evenly into F(n). Print the word no if not.,2020/7/22,42,Sample input: 0 1 2 3 4 5 6 Sample output: no no yes no no no yes,Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java

15、/Others),2020/7/22,43,题目分析：,能被3整除的整数的特点？,还要看程序吗？,如果两个数的和能被3整除，这两个数有什么特点？,关于能否被3整除，这两个数一共有多少种组合？,2020/7/22,44,Hdoj_1021程序清单：,#include int main() long n; while(scanf(%ld, ,2020/7/22,45,POJ 2750 鸡兔同笼,2020/7/22,46,Problem Description 一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。

16、 Input 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，每行一个正整数a (a 32768)。 Output 输出包含n行，每行对应一个输入,包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开 如果没有满足要求的答案，则输出两个0。,2020/7/22,47,Sample input: 2 3 20 Sample output: 0 0 5 10,2020/7/22,48,#include void main() int nCases,I,nFeet； /InCases表示输入测试数据的组 数，nFeet表示输入的脚数 scanf(“%d

17、”, ,2020/7/22,49,课后任务：,1008: Elevator,2020/7/22,50,这是2004浙江省省赛最简单的一题，当时训练水平相对较高的队员基本上10分钟之内解决该题，这是一个没有算法的简单模拟题目。 入门训练的好选择,题目评述：,2020/7/22,51,Problem Description The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floo

18、rs the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled. Input There are multiple test cases. Each case contains a positive integer N, f