考察DFS的應用，判斷兩個數的因子。
1 #include <stdio.h>
2
3 int f1,f2;
4
5 void DFS(int m,int n,int k){
6 if(n==1){
7 f2=1;
8 if(m==1)
9 f1=1;
10 }
11 if(f1&&f2||k==1)
12 return;
13 if(m%k==0)
14 DFS(m/k,n,k-1);
15 if(n%k==0)
16 DFS(m,n/k,k-1);
17 DFS(m,n,k-1);
18 }
19
20 int main(){
21 int a,b,temp;
22 while(scanf("%d %d",&a,&b)>=0){
23 if(a<b){
24 temp=a;
25 a=b;
26 b=temp;
27 }
28 f1=f2=0;
29 DFS(a,b,100);
30 temp=(!f1&&f2)?b:a;
31 printf("%d\n",temp);
32 }
33 return 0;
34 }
//zju 1003 Crashing Balloon
#include<stdio.h>
#include<string.h>
int used[101];
int scoremin,scoremax;
int dive(int n,int cnt)
{
int i;
if(n==1)
return 1;
for(i=cnt;i<=100;i++)
if(n%i==0)
{
if(dive(n/i,i+1))
return 1;
}
return 0;
}
int DFSb(int n,int cnt)
{
int i;
if(n==1)
return 1;
for(i=cnt;i<101;i++)
{
if(used[i]==0)
{
if(n%i==0)
{
if(DFSb(n/i,i+1))
return 1;
}
}
}
return 0;
}
int DFSa(int n,int cnt)
{
int i;
if(n==1)
{
if(DFSb(scoremax,2))
return 1;
return 0;
}
for(i=cnt;i<101;i++)
{
if(n%i==0)
{
used[i]=1;
if(DFSa(n/i,i+1))
return 1;
used[i]=0;
}
}
return 0;
}
int main()
{
int temp,flag1,flag2,i;
while(scanf("%d%d",&scoremin,&scoremax)!=EOF)
{
if(scoremin>scoremax)
{
temp=scoremin;
scoremin=scoremax;
scoremax=temp;
}
if(scoremin==scoremax)
{
printf("%d\n",scoremin);
continue;
}
flag1=flag2=0;
if(scoremin==1&&scoremax>1)
{
if(dive(scoremax,2))
printf("%d\n",scoremax);
else
......余下全文>>
在百度搜出來的說是一個游戲.....
On every June 1st, the Children's Day, there will be a game named "crashing balloon" on TV. The rule is very simple. On the ground there are 100 labeled balloons, with the numbers 1 to 100. After the referee shouts "Let's go!" the two players, who each starts with a score of "1", race to crash the balloons by their feet and, at the same time, multiply their scores by the numbers written on the balloons they crash. After a minute, the little audiences are allowed to take the remaining balloons away, and each contestant reports his\her score, the product of the numbers on the balloons he\she's crashed. The unofficial winner is the player who announced the highest score.
就是這個.
閣下慢慢研究哈~~~~~
