遞歸例題,判斷到達(dá)問題
題目描述:
對(duì)于任意一點(diǎn)(x, y),假設(shè)只有兩種移動(dòng)方式:(x, y) ->(x, x + y)?,(x, y) -> (x + y, y)。給定起點(diǎn)坐標(biāo)(x1, y1),判斷是否可以只通過上述移動(dòng)方式到達(dá)終點(diǎn)坐標(biāo)(x2, y2)。例如起點(diǎn)坐標(biāo)為?(2, 10),終點(diǎn)坐標(biāo)為(26, 12),
則?(2, 10)->(2, 12)->(14, 12)->(26, 12)?是有效的移動(dòng)方式,可以從起點(diǎn)到達(dá)終點(diǎn)。
提示:判斷能否從(x1,y1)通過限定的兩種移動(dòng)方式移動(dòng)到(x2,y2),可以轉(zhuǎn)化為判斷能否從(x1,x1+y1)通過限定的兩種移動(dòng)方式移動(dòng)到(x2,y2)以及能否從(x1+y1,y1)通過限定的兩種移動(dòng)方式移動(dòng)到(x2,y2)。
?
輸入:?
第一行為起點(diǎn)坐標(biāo),第二行為終點(diǎn)坐標(biāo)。
輸出:
如果可以通過上述移動(dòng)方式到達(dá)終點(diǎn),輸出Yes.,否則輸出No.
樣例輸入:
2, 10
26, 12
樣例輸出:
Yes.
#include <stdio.h>
#include <math.h>
#include <string.h>
//遞歸的運(yùn)用
int di(int x,int y,int a,int b)
{
if(x+y==a+b&&(a==x)&&(b==y)) return 1; //一旦符合條件就返回一
else if (x+y>a+b||x>a||y>b) return 0;//只要超出范圍就返回 0
//就是遞歸函數(shù)里x>a ||y>b就行
else return di(x+y,y,a,b)+di(x,x+y,a,b);//xy還小就繼續(xù)加?
}//只要遞歸過程中有一個(gè)符合,返回值就不是0
int main()
{
int x,y;
int a,b;
scanf("%d,%d",&x,&y);
scanf("%d,%d",&a,&b);
if(di(x,y,a,b)==0)
{
printf("No.\n");
}
else printf("Yes.\n");
}
?
標(biāo)簽: