깊이 우선 검색 연습

dfs (심층 검색) 에 대해 아무것도 모 르 는 33951, 33979, 자신 을 바 꾸 려 고 합 니 다.
단순 한 선택
소수 고리
[제목 설명] 1 부터 20 까지 이 20 개의 수 를 하나의 고리 로 놓 고 인접 한 두 개의 수의 합 을 하나의 소수 로 요구한다.[알고리즘 분석] 매우 뚜렷 합 니 다. 이것 은 역 추적 문제 입 니 다.1 부터 모든 빈 자 리 는 20 가지 가능성 이 있 습 니 다. 채 워 진 숫자 만 합 법 적 이면 앞의 숫자 와 다 릅 니 다.왼쪽 과 인접 한 수의 합 은 하나의 소수 이다.20 번 째 수 는 1 번 째 수 와 소수 여 부 를 판단 해 야 한다.[알고리즘 프로 세 스] 1. 데이터 초기 화;2. 재 귀 작성 수: i 번 째 숫자 입력 이 합 법 적 인지 판단 합 니 다.A. 합 법 적 인 경우: 숫자 를 작성 합 니 다.목표 달성 여 부 를 판단 합 니 다 (20 개 채 워 졌 습 니 다): 예, 결 과 를 인쇄 합 니 다.아니오, 다음 것 을 재 귀적 하 세 요.B. 합 법 적 이지 않 으 면 다음 가능성 을 선택 하 십시오.

#include
#include
using namespace std;

const int N=20,MAXN=1002;
int a[MAXN]={1},sum;// a[0]    1
bool used[MAXN],prime[MAXN];

void print()
{
    sum++;
    for(int i=1;i<=N;i++)
        printf("%d ",a[i]);
    printf("
");
}
void dfs(int t)
{
    for(int i=1;i<=N;i++)//   N      
    {
        if(!used[i]&&prime[i+a[t-1]])
        //a[0]=1   ：t=1 ,  a[0] 0，a[1]      1
        //       1    ，    1，   2
        {
            a[t]=i;
            used[i]=true;
            if(t==20)
                {if(prime[a[20]+a[1]]) print();}//         ，
                //     else                      if     
                //            
            else dfs(t+1);
            used[i]=false;//  
        }
    }
}
int main()
{
    memset(prime,1,sizeof(prime));
    prime[0]=prime[1]=false;
    for(int i=1;i<=2*N-1;i++)//       ，          O(1)
                            //             N+N-1，    2*N-1  
    {
        if(prime[i])
            for(int j=i<<1;j<=2*N-1;j+=i) prime[j]=false;
    }
    dfs(1);// 1    
    printf("%d",sum);
}

[예 2] 배 열 된 출력
[제목 설명] n 개의 정수 가 있 는 집합 (1, 2,..., n 곶, 그 중에서 임의의 r 개 수 를 꺼 내 배열 (r < n) 하고 모든 배열 을 시험 적 으로 보 여 줍 니 다.[알고리즘 분석] 분석 할 만 한 것 이 없어 dfs 에서 가장 간단 한 문제 라 고 할 수 있 습 니 다.

#include
using namespace std;

int n,r,a[1002],tot=0;
bool used[1002];

void print()
{
    tot++;
    for(int i=1;i<=r;i++)
        printf("%d ",a[i]);
    printf("
");
}
void dfs(int t)
{
    for(int i=1;i<=n;i++)// n    
    {
        if(!used[i])
        {
            used[i]=true;
            a[t]=i;
            if(t==r)//   r          
                print();
            else dfs(t+1);
            used[i]=false;//  
        }
    }
}
int main()
{
    scanf("%d%d",&n,&r);
    dfs(1);
    printf("number:%d",tot);
}

[예 3] 정수 의 분할
[제목 설명] 1 보다 큰 자연수 n 은 n 보다 작은 자연수 의 합 으로 나 눌 수 있다.[샘플 입력] 7 [샘플 출력] 7 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 7 = 1 + 1 + 1 + 3 7 = 1 + 1 + 2 + 2 7 = 1 + 1 + 4 7 = 1 + 1 + 4 7 = 1 + 2 + 2 + 2 7 = 1 + 3 + 3 7 = 2 + 2 + 3 7 = 2 + 2 + 3 7 = 2 + 5 7 = 3 + 4 total = 14이렇게 분할 하 는 것 도 동시에 무 거 운 역할 을 할 수 있다.예 를 들 어 2 + 1 + 1 + 1 과 1 + 1 + 2 + 1 + 1 등 은 모두 하나의 상황 이다. 즉, 1 + 1 + 1 + 2 이다.한 개의 수 를 떼 어 낼 때마다 n 에서 한 개의 수 를 빼 고 n 이 0 일 때 한 조 가 나 누 어 졌 습 니 다. 이번 인쇄 는 print 함수 에 매개 변 수 를 전달 하여 분 리 된 수의 개 수 를 표시 합 니 다. 분 리 된 개 수 는 확실 하지 않 기 때 문 입 니 다.

#include
using namespace std;

int n,a[1002]={1},tot,k;

void print(int t)
{
    tot++;
    printf("%d=",n);
    for(int i=1;iprintf("%d+",a[i]);
    printf("%d
",a[t]);
}
void dfs(int t)
{
    for(int i=a[t-1];i<=k;i++)//i<=k   k-i>=0
    {
        if(i//     ，             ，  i    n
        {
            a[t]=i;//  
            k-=i;
            if(k==0)
                print(t);//       t  
                //t           ，      ，            
                //  t     a          
            else dfs(t+1);
            k+=i;//  
        }
    }
}
int main()
{
    scanf("%d",&n);
    k=n;//           n     
    dfs(1);
    printf("total=%d",tot);
}