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