例1 雞兔同籠
【問題描述】
一個籠子里面關了雞和兔子（雞有2 只腳，兔子有4 只腳，沒有例外），已知籠子里面腳的總數a，問籠子里面至少有多少只動物，至多有多少只動物？
【輸入資料】
第1 行是測驗資料的組數n，后面跟著n 行輸入，每組測驗資料占1 行，包括一個正整數a (a < 32768)，
【輸出要求】
n 行，每行輸出對應一個輸入，輸出是兩個正整數，第一個是最少的動物數，第二個是最多的動物數，兩個正整數用空格分開，如果沒有滿足要求的情況出現，則輸出2 個0，
【輸入樣例】
2
3
20
【輸出樣例】
0 0
5 10
（1）編程思路，
由于雞有2 只腳，兔子有4 只腳，因此籠子里面腳的總數一定是個偶數，如果有奇數只腳，則輸入不正確，即沒有滿足要求的情況出現，則輸出2 個0，
當a是偶數時，若要動物數目最少，則應使動物盡量有4 只腳，而要動物數目最多，則應使動物盡量有2 只腳，因此本題無需用回圈窮舉，只需按上面的分析找到相應的計算式子即可，
如果總腳數a 是4 的倍數，則動物最少數目為a / 4（全部為兔子），最多為a / 2（全部為雞），
如果總腳數a 不是4 的倍數，則動物最少數目為a/4+1（除1只雞外，其余全部為兔子），最多為a / 2（全部為雞），
因此，撰寫一個簡單的選擇結構實作相應的判斷和計算輸出就可以了，
（2）源程式，
#include <stdio.h>
int main()
{
int n,i,a;
scanf("%d",&n);
while (n--)
{
scanf("%d",&a);
if (a%2!=0)
printf("0 0\n");
else if (a % 4!=0)
printf("%d %d\n",a/4+1,a/2);
else
printf("%d %d\n",a/4,a/2);
}
return 0;
}
習題1
1-1 P1348 Couple number
本題選自洛谷題庫 （https://www.luogu.org/problem/P1348）
【題目描述】
任何一個整數N都能表示成另外兩個整數a和b的平方差嗎？如果能，那么這個數N就叫做Couple number，你的作業就是判斷一個數N是不是Couple number，
【輸入格式】
僅一行，兩個長整型范圍內的整數n1和n2，之間用1個空格隔開，
【輸出格式】
輸出在n1到n2范圍內有多少個Couple number，
注意：包括n1和n2兩個數，且n1<n2，n2 - n1 <= 10 000 000，
【輸入樣例】
1 10
【輸出樣例】
7
（1）編程思路，
本題的關鍵問題是如何判斷一個數N是不是Couple number，
設N=a2-b2，則N=(a+b)(a-b)
由于a，b均為整數，則a+b與a-b的奇偶性一定相同，
如果a+b是奇數，奇數乘奇數一定是奇數，因此N一定是奇數，
如果a+b是偶數，偶數乘偶數一定是4的倍數，因此N也一定是4的倍數，
由此可知，Couple number要么是奇數，要么是4的倍數，
反過來，一個奇數或一個4的倍數的數是否一定是Couple number呢？我們可以很簡單地構造出a和b來，
若N是奇數，可設N=2k-1 （k是整數），可取a=k,b=k-1，則N= a2-b2=(a+b)(a-b)=2k-1，
若N是4的倍數，可設N=4k （k是整數），可取a=k+1,b=k-1，則N= a2-b2=(a+b)(a-b)=4k，
若N是偶數但不是4的倍數，可設N=2k （k為奇數），則N無論如何分解因數，一定只能分解為一個偶數和一個奇數相乘，這樣(a+b)與(a-b)中一定一個為奇數，另一個為2的奇數倍，但是(a+b)和(a-b)同奇偶性，因此N無法表示成兩個整數a和b的平方差，
（2）源程式，
#include <stdio.h>
int main()
{
int n1,n2,i,cnt=0;
scanf("%d%d",&n1,&n2);
for (i=n1;i<=n2;i++)
if (i%2!=0 || i%4==0)
cnt++;
printf("%d\n",cnt);
return 0;
}
1-2 整數解
本題選自HDU OJ （http://acm.hdu.edu.cn/showproblem.php?pid=2092）
Problem Description
有二個整數，它們加起來等于某個整數，乘起來又等于另一個整數，它們到底是真還是假，也就是這種整數到底存不存在，實在有點吃不準，你能快速回答嗎？看來只能通過編程，
例如：
x + y = 9，x * y = 15 ? 找不到這樣的整數x和y
1+4=5，1*4=4，所以，加起來等于5，乘起來等于4的二個整數為1和4
7+(-8)=-1，7*（-8）=-56，所以，加起來等于-1，乘起來等于-56的二個整數為7和-8
Input
輸入資料為成對出現的整數n，m（-10000<n,m<10000），它們分別表示整數的和與積，如果兩者都為0，則輸入結束，
Output
只需要對于每個n和m，輸出“Yes”或者“No”，明確有還是沒有這種整數就行了，
Sample Input
9 15
5 4
1 -56
0 0
Sample Output
No
Yes
Yes
（1）編程思路，
設 x+y=n x*y=m，可得 x*(n-x)=m x2-nx+m=0
求解這個以x為未知數的一元二次方程，
令 dlt=n2-4m，
若dlt<0，則方程無實根，x和y更不可能為整數，因此，輸出“No”，
若dlt==0，可求得x=y=n/2，且x和y均為整數，因此，輸出“Yes”，
若dlt>0，根據一元二次方程求根公式求得方程兩個實根x1和x2（這兩個實根不一定是整數），且取整數分別賦給x和y，若滿足x+y==n且 x*y==m，則輸出“Yes”，否則輸出“No”，
（2）源程式，
#include <stdio.h>
#include <math.h>
int main()
{
int n,m,dlt,x,y;
while (1)
{
scanf("%d%d",&n,&m);
if (n==0 && m==0) break;
dlt=n*n-4*m;
if (dlt<0)
printf("No\n");
else if (dlt==0)
printf("Yes\n");
else
{
x=(n+(int)sqrt(1.0*dlt))/2;
y=(n-(int)sqrt(1.0*dlt))/2;
if (x+y==n && x*y==m)
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}
1-3 Distance on Chessboard
本題選自北大POJ （http://poj.org/problem?id=1657）
Description
國際象棋的棋盤是黑白相間的8 * 8的方格，棋子放在格子中間，如下圖所示：
王、后、車、象的走子規則如下：
王：橫、直、斜都可以走，但每步限走一格，
后：橫、直、斜都可以走，每步格數不受限制，
車：橫、豎均可以走，不能斜走，格數不限，
象：只能斜走，格數不限，
寫一個程式，給定起始位置和目標位置，計算王、后、車、象從起始位置走到目標位置所需的最少步數，
Input
第一行是測驗資料的組數t（0 <= t <= 20），以下每行是一組測驗資料，每組包括棋盤上的兩個位置，第一個是起始位置，第二個是目標位置，位置用"字母-數字"的形式表示，字母從"a"到"h"，數字從"1"到"8"，
Output
對輸入的每組測驗資料，輸出王、后、車、象所需的最少步數，如果無法到達,就輸出"Inf".
Sample Input
2
a1 c3
f5 f8
Sample Output
2 1 2 1
3 1 1 Inf
（1）編程思路，
本題給定一個棋盤上的起始位置和終止位置，分別判斷王、后、車、象從起始位置到達終止位置需要的步數，
首先，王、后、車、象彼此獨立，分別考慮就可以了，分析王、后、車、象的行走規則特點，從而推出它們從起點到終點的步數，
假設起始位置與終止位置在水平方向上的距離是 x，它們在豎直方向上的距離是y，
根據王的行走規則，它可以橫、直、斜走，每步限走一格，所以需要的步數是min(x,y)+abs(x-y)，即x，y 中較小的一個加上x 與y 之差的絕對值，
根據后行走的規則，它可以橫、直、斜走，每步格數不受限制，所以需要的步數是1（x 等于y 或者 x 等于0 或者 y 等于0）或者2(x 不等于y)，
根據車行走的規則，它可以橫、豎走，不能斜走，格數不限，需要步數為1（x 或者y 等于0）或者2(x 和y 都不等于0)，
根據象行走得規則，它可以斜走，格數不限，棋盤上的格點可以分為兩類，第一類是它的橫坐標和縱坐標之差為奇數，第二類是橫縱坐標之差為偶數，對于只能斜走的象，它每走一步，因為橫縱坐標增加或減小的絕對值相等，所以橫坐標和縱坐標之差的奇偶性無論如何行走都保持不變，因此，上述的第一類點和第二類點不能互相到達，如果判斷出起始點和終止點分別屬于兩類點，就可以得出它們之間需要無數步的結論，如果它們屬于同一類點，象從起始點走到終止點需要1（x 的絕對值等于y 的絕對值）或者2（x 的絕對值不等于y 的絕對值），
（2）源程式，
#include <stdio.h>
#include <math.h>
int main()
{
int n;
char begin[5], end[5]; // 用 begin 和 end 分別存盤棋子的起止位置
int x, y;
scanf("%d", & n);
while( n--)
{
scanf("%s %s", begin, end);
x = abs(begin[0] - end[0]);
y = abs(begin[1] - end[1]);
if(x == 0 && y == 0)
printf("0 0 0 0\n"); // 起止位置相同，所有棋子都走0步
else{
if(x < y)printf("%d",y); //王的步數
else printf("%d",x);
if(x == y || x == 0 || y == 0) printf(" 1"); //后的步數
else printf("2");
if(x == 0 || y == 0) printf(" 1"); //車的步數
else printf(" 2");
if(abs(x-y) % 2 != 0) printf(" Inf\n"); //象的步數
else if(x == y) printf(" 1\n");
else printf(" 2\n");
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/65032.html
標籤：C