검색 과 이집트 점 수 를 반복 적 으로 심화 하 다.
검색 이 가능 할 때 까지 위 절 차 를 반복 합 니 다.
반복 적 으로 검색 을 심화 시 키 는 알고리즘 에서 연속 적 인 깊이 우선 검색 이 도입 되 었 고 모든 깊이 제약 은 대상 을 검색 할 때 까지 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.