简单计算题一.ppt

第二讲,简单计算题（一）,ACM算法与程序设计,简单计算题,主要目的：通过编写一些简单计算题的程序焘悉CC+语言的基本语法 基本思想：解决简单的计算问题的基本过程包括将一个用自然语言描述的实际问题抽象成一个计算问题给出计算过程继而编程实现计算过程，并将计算结果还原成对原来问题的解答。这里首要的是读懂问题接清输入和输出数据的含义及给出的格式·并且通过输入输出样例验证自己的理解是否正确。,最小公倍数,http:/acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1178 http:/acm.hdu.edu.cn/showproblem.php?pid=1108,Problem Description 求两个正整数的最小公倍数。 Input 输入数据含有不多于50对的数据，每对数据由两个正整数(0n1,n2100000)组成。 Output 对于每组数据n1和n1，计算最小公倍数，每个计算结果应占单独一行。,Sample input: 6 5 18 12 Sample output: 30 36,题目分析,最小公倍数等于两数之积除以最大公约数 利用辗转相除法求最大公约数。,欧几里德算法,只要两数不相等，就反复用 大数减小数，直到相等为止， 此相等的数就是两数的最大公 约数。,int gcd(int x,int y) while (x!=y) if (xy) x=x-y; else y=y-x; return x; ,#include int gcd(int int) ； Int main() int x,y; while(cinxy) coutx/gcd(x,y)*yend1; return 0; ,int gcd(int a,int b)return !b?a:gcd(b,a%b);,POJ 2750 鸡兔同笼,http:/poj.grids.cn/problem?id=2750,Problem Description 一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。 Input 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，每行一个正整数a (a 32768)。 Output 输出包含n行，每行对应一个输入,包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开 如果没有满足要求的答案，则输出两个0。,Sample input: 2 3 20 Sample output: 0 0 5 10,#include void main() int nCases,I,nFeet； /InCases表示输入测试数据的组 数，nFeet表示输入的脚数 scanf(“%d”, ,The Story of ZCS,1、Link http:/222.197.181.37/ShowProblem.aspx?ProblemID=1088 2、Description Love and Eternal lay hid in night; God said “Let CS be“ and all was light. Walking alone in darkness, lonely and never knew what I would go through. How many times I walked lonely in the campus, how many times I woke up with a start at midnight, and how many times I sang a sorrow song but no one cared about? The terrible feeling is just like a albatross around my neck until I met CS. My door is opened and the sky is lightened.It is a moment for my renaissance, which makes me understand the meaning of sunshine and rainbow once again. When I catch sight of you, you are the only one in my view. When you are out of sight, you are the only one in my heart. When I am awake, you are the only one in my mind. When I am asleep, you are the only one in my dream. You are my only one.I want to catch sight of you every minute and every second. - Letter from Kamel (ZS) to CS,The Story of ZCS,Kamel has lots of photos of CS. He wants to fill his desktop with her photos. The desktop is made up of m rows and n columns. One photo occupies b consecutive squares in a row or b consecutive squares in a column. He want to know want to know whether it is possible to cover his desktop with CS's photos while no two photos overlap with each other and the whole desktop is full? You may assume that Kamel has tens of thousands of photos of CS. If it is possible then print “YES“ else print “NO“.,The Story of ZCS,3、Input The first line of the inputs is T(no more than 120), which stands for the number of test cases you need to solve. Each line has three numbers M,N,B (1 = M,N = 1000, 1 = B = M,N). 4、Output Each “YES“ or “NO“ occupies one line.,5、Sample Input 2 4 8 4 5 7 3 6、Sample Output YES NO 7、Source kamel,The Story of ZCS,分析,The Story of ZCS,证明,#include void main() int T,M,N,B; scanf(“%d“, ,The Story of ZCS,1021 Fibonacci Again,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 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.,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/Others),题目分析：,能被3整除的整数的特点？,还要看程序吗？,如果两个数的和能被3整除，这两个数有什么特点？,关于能否被3整除，这两个数一共有多少种组合？,#include int main() long n; while(scanf(“%ld“, ,http:/acm.hdu.edu.cn/showproblem.php?pid=1008,Elevator,这是2004浙江省省赛最简单的一题，当时训练水平相对较高的队员基本上10分钟之内解决该题，这是一个没有算法的简单模拟题目。 入门训练的好选择,题目评述：,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 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 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, followed by N positive numbers. All the numbers in the input are less than 100. A test case with N = 0 denotes the end of input. This test case is not to be processed. Output Print the total time on a single line for each test case.,Sample input: 1 2 3 2 3 1 0 Sample output: 17 41,int main() int n, i, a101; while(scanf(“%d“, ,http:/acm.hdu.edu.cn/showproblem.php?pid=1061,Rightmost Digit,Problem Description Given a positive integer N, you should output the most right digit of NN. Input The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.Each test case contains a single positive integer N(1=N=1,000,000,000). Output For each test case, you should output the rightmost digit of NN.,Sample input: 2 3 4 Sample output: 7 6,数据规模 很大 暴力方法 该打 基本思路 规律,#include main() int T,i,a,digit; long n; scanf(“%d“,人见人爱AB,求AB的最后三位数表示的整数（1=A,B=10000） 2 3 12 6 8 984,HDOJ_2035 人见人爱AB,最暴力的暴力？ 改进的暴力？ 还有规律么？,#include int main() int a,b,i,a0,m; while(scanf(“%d%d“, ,附:,初学者常见问题,一、编译错误,Main函数必须返回int类型(正式比赛) 不要在for语句中定义类型 _int64不支持，可以用long long代替 使用了汉语的标点符号 itoa不是ansi函数 能将整数转换为字符串而且与ANSI标准兼容的方法是使用sprintf()函数 int num = 100; char str25; sprintf(str, “ %d“ , num); 另外，拷贝程序容易产生错误,常见的代码：, scanf(“%dn“, ,思考,上面程序 有什么问题？,其他问题：,1、需要什么基础？( C/C+ ),4 、可以退课吗? ( Of course! ),3 、如何加入集训队?,2、英语不好怎么办？(问题不大),