블 루 브리지 컵 겨울방학 작업

겨울방학 숙제: 지금 초등학교 수학 문제 도 그렇게 재 미 있 지 않 아 요.이 겨울방학 숙제 좀 봐.   □ + □ = □    □ - □ = □    □ × □ = □    □ ÷ □ = □     각 사각형 은 1 ~ 13 의 어떤 숫자 를 대표 하지만 중복 할 수 없다.예 를 들 면: 6  + 7 = 13  9  - 8 = 1  3  * 4 = 12  10 / 2 = 5 및: 7  + 6 = 13  9  - 8 = 1  3  * 4 = 12  10 / 2 = 5 는 두 가지 해법 이 라 고 할 수 있다.(덧셈, 곱셈 교환 율 후 다른 방안 을 계산한다)  당신 은 모두 몇 가지 방안 을 찾 았 습 니까?방안 의 수 를 나타 내 는 정 수 를 기입 해 주 십시오.
주의: 당신 이 제출 한 것 은 정수 여야 합 니 다. 불필요 한 내용 이나 설명 문 자 를 쓰 지 마 십시오.
분석: 이 문 제 는 간단 한 전체 배열 이다. 가장 생각 하기 쉬 운 사 고 는 1 ~ 13 을 모두 배열 한 다음 에 앞의 12 개의 숫자 를 하나하나 빈 값 으로 부여 하고 12 개의 숫자 를 모두 확정 한 후에 네 개의 등식 판단 을 하 는 것 이다.동시에 C + + 의 STL 라 이브 러 리 에 기 존 함수 - next 가 있 습 니 다.permutation, 실현 하기 가 더욱 간단 합 니 다.

#include
#include
#include
using namespace std;
int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13};
bool check()
{  
	bool b1=(a[0]+a[1]==a[2]);
	bool b2=(a[3]-a[4]==a[5]);
	bool b3=(a[6]*a[7]==a[8]);
	bool b4=(fabs((a[9]*1.0)/(a[10]*1.0)-a[11]*1.0)<=0.00000000000001);
	if(b1 && b2 &&b3 && b4)
       return true;
    else
       return false;
}
int main()
{
	int res=0;
	do
	{
		if(check())
		{
			res++;
		}
	}while(next_permutation(a,a+13));
	cout<

비록 이런 방법 은 실행 할 수 있 지만, 가장 나 쁜 방법 은 효율 이 너무 낮 기 때문이다.우 리 는 깊 은 검색 에 가 지 를 자 르 는 방법 으로 프로그램 을 최적화 시 킬 생각 이다.

#include
#include
#include
using namespace std;

int res=0;
int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13};
void dfs(int start)
{
	if(start>=3 )
	  if(a[0]+a[1]!=a[2]) return ;//                ，   ，        
	if(start>=6)
	  if(a[3]-a[4]!=a[5]) return ;//            ，    
	if(start>=9)
	  if(a[6]*a[7]!=a[8]) return ;
	if(start>=12)
	  if(a[11]*a[10]==a[9])
	  {
	  	for(int i=0;i<12;i++)
	  	  cout<

두 번 째 최적화 방법 을 사용 할 수 있 는 이 유 는 각 등식 을 판단 할 때 1 ~ 13 의 모든 배열 이 끝 날 때 까지 기다 릴 필요 가 없 기 때 문 입 니 다. 우 리 는 이미 배열 한 앞의 몇 개의 숫자 를 판단 할 수 있 습 니 다. 예 를 들 어 우 리 는 앞의 세 개의 숫자 를 찾 았 습 니 다. 1, 2, 4 이때 첫 번 째 등식 판단 을 할 수 있 습 니 다. 1 + 2! =4. 그러면 1, 2, 4 를 접두사 로 배열 하면 계속 판단 하지 않 고 가지치기 효 과 를 얻 을 수 있 습 니 다.
PS: 블 루 브리지 컵 문제 도 많이 다 르 지 않 아 요. 경기 가 곧 다가 오 니까 행운 을 빌 어 요.