第二周 简单题(一)

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

2、数，输出每个面积后再回车。 先看一个超级简单的题目：8/20/20223输入样例 1 2 3 4输出样例 1 9 25 498/20/20224初学者很常见的一种写法：#includevoid main() int a,b; scanf(“%d”,&a); Printf(“%d”,a*a);8/20/20225有什么问题呢？这就是下面需要解决的问题8/20/20226第一部分基本输入输出8/20/20227输入_第一类：输入不说明有多少个Input Block,以EOF或1为结束标志。读入一个输入对应一个输出，输入数据可以是多组 读入一个参数 8/20/20228题目分析 怎样判断输入的结束？

3、scanf函数的原型如下： int scanf(const char *format , argument. );其返回值为：成功读取并分配的元素个数。 8/20/20229说明：Scanf函数返回值就是读出的变量个数，如：scanf( “%d %d”, &a, &b ); 如果只有一个整数输入，返回值是1，如果有两个整数输入，返回值是2，如果一个都没有，则返回值是-1。EOF是一个预定义的常量，等于-1。8/20/202210例如：#include int main(void)int a=0,b=0,c=0,k;k=scanf(%d%*d%d,&a,&b,&c);printf(k=%d,a=

4、%d,b=%d,c=%dn,k,a,b,c);若输入：1 2 3，则输出为：k=2,a=1,b=3,c=0注意：常常用while(scanf(“”,)=)来判断循环的进行。8/20/202211参考源代码#include int main(void)int a;while(scanf(%d,&a)=1)printf(%dn,a*a);return 0;8/20/202212本类输入解决方案：C语法：while(scanf(%d,&a) = 1) . C+语法：while( cin a) . 8/20/202213读入两个参数题目内容 缩写程序计算两个整数的差。输入描述 输入数据含有不超过50个

5、整数对，每个整数及每对整数的运算结果都不会超过输出描述 对于每次读入的一对整数，输出前者减去后者的差。每个结果以回车结束。8/20/202214输入样例 1 3 5 7输出样例 -2 -28/20/202215参考源代码#include int main(void)int a,b;while(scanf(%d%d,&a,&b)=2)printf(%dn,a-b);return 0;8/20/202216输入_第二类：输入一开始就会说有N个Input Block,下面接着是N个Input Block。 参见：HDOJ_1090 8/20/202217Problem Description You

6、r 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 of a and b in one

7、 line, and with one line of output for each line in input. Sample input: 2 1 5 10 20 Sample output: 6 308/20/202218Hdoj_1090源代码：#include int main() int n,i,a,b; scanf(%d,&n);for(i=0;in;i+) scanf(%d %d,&a, &b); printf(%dn,a+b); 8/20/202219本类输入解决方案：C语法：scanf(%d,&n) ; for( i=0 ; i n; for( i=0 ; in ; i+

8、 ) . 8/20/202220输入_第三类：输入不说明有多少个Input Block,但以某个特殊输入为结束标志。参见：HDOJ_1091 8/20/202221Problem 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

9、 input and this test case is not to be processed.Output For 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 0Sample output: 6 308/20/202222Hdoj_1091源代码：#include int main() int a,b;whil

10、e(scanf(%d %d,&a, &b) &(a!=0 & b!=0) printf(%dn,a+b); 8/20/202223本类输入解决方案：C语法：while(scanf(%d,&n) & n!=0 ) . C+语法：while( cin n & n != 0 ) . 8/20/202224输入_第四类：输入是一整行的字符串的参见：HDOJ_1048 8/20/202225本类输入解决方案：C语法： char buf20; gets(buf); C+语法：如果用string buf;来保存： getline( cin , buf ); 如果用char buf 255 ; 来保存： ci

11、n.getline( buf, 255 );8/20/202226说明：scanf(“ %s%s”,str1,str2)，在多个字符串之间用一个或多个空格分隔；若使用gets函数，应为gets(str1); gets(str2); 字符串之间用回车符作分隔。通常情况下，接受短字符用scanf函数，接受长字符用gets函数。而getchar函数每次只接受一个字符，经常c=getchar()这样来使用。8/20/202227输出_第一类：一个Input Block对应一个Output Block，Output Block之间没有空行。 参见：HDOJ_10898/20/202228解决方案：C语法

12、： . printf(%dn,ans); C+语法： . cout ans endl; 8/20/202229输出_第二类：一个Input Block对应一个Output Block，每个Output Block之后都有空行。参见：HDOJ_1095 8/20/2022301095源代码#include int main() int a,b; while(scanf(%d %d,&a, &b) != EOF) printf(%dnn,a+b); 8/20/202231解决办法：C语法： . printf(%dnn,ans); C+语法： . cout ans endl endl; 8/20/2

13、02232第二部分简单题（一）8/20/202233 最小公倍数 8/20/202234Problem Description 求两个正整数的最小公倍数。 Input 输入数据含有不多于50对的数据，每对数据由两个正整数(0n1,n2100000)组成。 Output 对于每组数据n1和n1，计算最小公倍数，每个计算结果应占单独一行。 8/20/202235Sample input: 6 5 18 12 Sample output: 30 368/20/202236题目分析最小公倍数等于两数之积除以最大公约数利用辗转相除法求最大公约数。8/20/202237#includeint gcd(in

14、t int) ；Int main() int x,y; while(cinxy) coutx/gcd(x,y)*yend1; return 0; #includeint gcd(int int) ；Int main() int x,y; while(cinxy) coutx*y/gcd(x,y)y) x=x-y; else y=y-x; return x; 只要两数不相等，就反复用大数减小数，直到相等为止，此相等的数就是两数的最大公约数。8/20/2022391021 Fibonacci Again 8/20/202240Problem Description There are anothe

15、r kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n=2). Input Input consists of 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.8/20/202241Sample input: 0 1 2 3 4 5 6Sample outpu

16、t: no no yes no no no yesTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)8/20/202242题目分析：能被3整除的整数的特点？还要看程序吗？如果两个数的和能被3整除，这两个数有什么特点？关于能否被3整除，这两个数一共有多少种组合？8/20/202243Hdoj_1021程序清单：#includeint main() long n; while(scanf(%ld,&n) != EOF) if (n%8=2 | n%8=6) printf(yesn); els

17、e printf(non);return 0;8/20/202244POJ 2750 鸡兔同笼8/20/202245Problem Description 一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。 Input 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，每行一个正整数a (a 32768)。Output 输出包含n行，每行对应一个输入,包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开 如果没有满足要求的答案，则输出两个0。8/20/2022

18、46Sample input: 2 3 20Sample output: 0 0 5 108/20/202247#includevoid main() int nCases,I,nFeet； /InCases表示输入测试数据的组 数，nFeet表示输入的脚数 scanf(“%d”,& nCases)； for(i=0;j inCases;i+) scanf(“%d”,& nFeet); if(nFeet % 2 !=0) /如果有奇数只脚，则没有满足题 意的答案，因为不论2只还是4只，都是偶数 printf(“0 0n”)； else if(nFeet % 4 !=0) /若要动物数目最少，使

19、动物尽量有4只脚，若要动物数目最多，使动物尽量有2只脚 printf(“%d %dn”, nFeet / 4 + 1, nFeet / 2)； else printf(“%d %dn”, nFeet / 4, nFeet / 2); 8/20/202248课后任务：1008: Elevator8/20/202249 这是2004浙江省省赛最简单的一题，当时训练水平相对较高的队员基本上10分钟之内解决该题，这是一个没有算法的简单模拟题目。 入门训练的好选择题目评述：8/20/202250Problem 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 floors 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