프로젝트 오일러 # 163 이해

Question

this problem에 대한 해결책을 찾는 데 오랜 시간을 보냈습니다. 나는 십자가의 삼각형을 그렸고 간단한 경우 삼각형을 세 었으며 어떤 종류의 패턴을 찾았다. 불행히도, 나는 벽에 부딪쳤다. 나는 내 프로그래밍/수학 능력이이 문제의 전제 조건을 충족시키지 않았 음을 확신한다.

포럼에 액세스하려면 온라인 솔루션을 찾았습니다. 나는 대부분의 방법을 전혀 이해하지 못했고 어떤 것은 너무 복잡해 보였습니다.

누구든지 내게이 문제를 이해시킬 수 있습니까? 그 중 하나가 여기에 있습니다 : http://www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles (Problem C) 하나의 기능을 사용할 수 있습니다.

어떻게 그런 해결책을 생각해 냈습니까? 이 시점에서이 흥미로운 문제의 배경을 이해하고 싶습니다. 솔루션을 찾는 것이 오일러 정신의 일부가 아니라는 것을 압니다. 그러나 나는이 문제를 아무렇게나 해결하지 못했을 것이라고 확신합니다.

Answer 1

이것은 본질적으로 여러 가지 조합을 계산하는 기술인 열거 형 조합에서 문제입니다. 그것은 아름다운 주제이지만, 당신이 준 참조에서 닌자 트릭을 감상 할 수있을 때까지 약간의 워밍업이 필요할 것입니다.

한편, 문제에 대한 해결책 스레드의 의견은 많은 사람들이 무차별 대입 방식을 사용하여 문제를 해결했다는 것을 나타냅니다. 가장 일반적인 트릭 중 하나는 다이어그램에서 세 줄의 모든 가능한 조합을 가져 와서 가장 큰 삼각형 안에있는 삼각형을 생성하는지 확인하는 것입니다.

줄이 여섯 방향 중 하나에 있음을 알면 검색 공간을 상당히 줄일 수 있습니다. 병렬 인 두 개의 라인을 포함하는 라인의 조합은 삼각형을 산출하지 않기 때문에, 트리플의 각 라인이 다른 방향을 갖도록 라인 트리플을 반복 할 수 있습니다.

세 줄이 주어지면 교차점을 계산하십시오. 세 가지 가능성이 있습니다 1) 선이 일치 함 - 모두 공통점에서 교차 함 2) 선 두 개가 삼각형 바깥의 한 점에서 교차 함 3) 교차점 3 개가 모두 구별되며 모두 내부에 있음 바깥 쪽 삼각형

조건 (3)을 만족하는 콤보를 계산하면 완료됩니다. 테스트해야하는 라인 콤보 수는 O (n)이며, 이는 과도하지 않습니다.

EDIT1 : 질문을 다시 읽으면 무차별 방식의 개요보다 조합 솔루션/공식에 대한 설명을 얻는 데 더 많은 관심이있는듯한 인상을받습니다. 그렇다면 그렇게 말하면이 대답을 삭제할 것입니다.그러나 나는이 경우의 질문이이 사이트에 적합하지 않다고 말하고 싶다.

EDIT2 : a combinatorics solution by Bill Daly and others도 참조하십시오. 그것은 수학적으로 다른 것보다 조금 부드럽습니다.

Answer 2

project euler에 대해이 문제를 해결하지 못했고 사용자가 제공 한 질문과 해결책이 사라졌습니다. 단일 기능의 경우, 제시된 방법론은 궁극적으로 단순한 패턴 발견이었다. 솔버는 제시된 질문을 교차로에서 나온 삼각형의 유형에 따라 세 부분으로 나누었습니다. 이런 종류의 문제에 대해 상당히 표준적인 접근 방법입니다. 더 큰 패턴을 더 작은 패턴으로 나누면 더 쉽게 해결할 수 있습니다. 내가 생각할 수있는 삼각형의 다양한 형태를 표현하는 데 사용 된 함수는 매우 급한 패턴을 찾는 마음 또는 일부 숫자 이론/기하학으로 생성되었습니다. 또한이 설명과 지식의 범위를 벗어납니다. 이 문제는 프로그래밍과 관련이 없습니다. 그것은 기본적으로 완전히 수학입니다. 좋아하는 사이트를 읽으면 질문에 도달하는 데 필요한 논리를 볼 수 있습니다.