검색 과 이집트 점 수 를 반복 적 으로 심화 하 다.

반복 적 으로 검색 을 심화 시 키 는 것 은 실질 적 으로 하계 의 깊이 를 제한 하 는 우선 검색 이다.즉, K 층 의 깊이 를 우선 검색 할 수 있 습 니 다. 실행 가능 한 해 가 발견 되 지 않 으 면 K + 1 후
검색 이 가능 할 때 까지 위 절 차 를 반복 합 니 다.
반복 적 으로 검색 을 심화 시 키 는 알고리즘 에서 연속 적 인 깊이 우선 검색 이 도입 되 었 고 모든 깊이 제약 은 대상 을 검색 할 때 까지 1 씩 추가 되 었 습 니 다.이렇게 하면 된다
중복 검색 많이 한 거 알 아 요.그러나 그 장점 은:
1. 공간 비용 이 적다   각 깊이 에 서 는 사실상 깊이 우선 검색 이지 만 깊이 는 제한 되 어 있 으 며 DFS 의 공간 소 모 는 잘 알려 져 있다.
2. 깊 은 가지치기 에 좋다
3. 시간 효율 이 낮 지 않 습 니 다. 중복 검색 을 하지만 이해 하기 어렵 지 않 습 니 다. 지난번 검색 은 다음 검색 과 약간 부족 한 것 이 아 닙 니 다.
교체 심화 검색 알고리즘 은 모방 범위 우선 검색 의 깊이 우선 검색 임 을 알 수 있다.깊이 우선 검색 의 선형 저장 요 구 를 만족 시 킬 수 있 을 뿐만 아니 라 최소 깊이 의 목표 노드 를 발견 할 수 있다.
실제 응용 을 보면 반복 적 으로 검색 을 심화 시 키 는 효과 가 좋 고 넓 은 검색 보다 느 리 지 않 지만 공간 복잡 도 는 깊이 우선 검색 과 마찬가지 로 넓 은 검색 보다 훨씬 적다.
검색 알고리즘 을 사용 할 때 정확 한 검색 방식 을 선택 하 는 것 이 중요 하 다.넓 은 검색 을 해 야 하 는 문제 가 있 지만 충분 한 공간 이 없 으 며 시간 이 넉넉 하 다. 이런 문제 에 부 딪 히 면 반복 적 으로 검색 알고리즘 을 심화 시 킬 수 있다.
제목:http://acm.nefu.edu.cn/JudgeOnline/problemshow.php?problem_id=358
제목: 진 점 수 를 드 리 겠 습 니 다. 최소한 의 몇 가지 특수 한 진 점 수 를 합 쳐 야 합 니 다. 이 서열 을 출력 해 야 합 니 다.만약 서로 다른 방안 이 있다 면, 점수 개수 가 같은 상황 에서 가장 큰 분 모 를 최소 화 할 것 이다.또 같다 면, 다음 큰 분 모 를 가장 크게..........................................................예 를 들 어 2 / 3 = 1 / 2 + 1 / 6 이지 만 2 / 3 = 1 / 3 + 1 / 3 은 허용 되 지 않 습 니 다. 덧셈 이 같 기 때 문 입 니 다.한 점수 a / b 에 대해 서 는 표현 방법 이 여러 가지 가 있 지만 어떤 것 이 가장 좋 습 니까? 우선, 가산 이 적은 것 이 가산 보다 많은 것 이 좋 고, 그 다음 에 가산 수가 같은 것 은 가장 작은 점수 가 클 수록 좋다.

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;
const int INF = ~0U>>1;
const int N = 10;

int dep,flag;
int ans[N],d[N];

int gcd(int a,int b)
{
    return b ? gcd(b,a%b):a;
}

void dfs(int a,int b,int k)
{
    if(k == dep + 1) return;
    if(b % a == 0 && b / a > d[k-1])
    {
        d[k] = b / a;
        if(!flag || d[k] < ans[k])
             memcpy(ans,d,sizeof(d));
        flag = 1;
        return;
    }
    int s = b / a;
    if(s <= d[k-1]) s = d[k-1] + 1;
    int t = (dep - k + 1) *  b / a;
    if(t > INF / b) t = INF / b;
    if(flag && t >= ans[dep]) t = ans[dep] - 1;
    for(int i=s;i<=t;i++)
    {
        d[k] = i;
        int m = gcd(i*a - b,b*i);
        dfs((i*a-b)/m,b*i/m,k+1);
    }
}

void Work(int a,int b)
{
    d[0] = 1;
    flag = 0;
    for(dep=1;dep <= N;dep++)
    {
        dfs(a,b,1);
        if(flag)
        {
            printf("1/%d",ans[1]);
            for(int i=2;i<=dep;i++)
                printf("+1/%d",ans[i]);
            cout<<endl;
            break;
        }
    }
}

int main()
{
    int a,b;
    while(cin>>a>>b)
    {
        cout<<a<<"/"<<b<<"=";
        Work(a,b);
    }
    return 0;
}