실기 경기 상세 해설

실기경기❶ 해설
Challenge-18
실기경기 ①은 1팀 3명이 협력하여 배점이 다른 18문의 수학·정보에 관한 문제를 풀고 제한시간 100분 내에 정답한 문제로 얻은 합계 득점을 겨루는 경기였다.또한 사전 자료에는 출제되는 문제의 6% 정도는 프로그램에 의해 계산을 하지 않으면 해답을 얻을 수 없다는 취지가 적혀 있었다.

이번 경기 내용은 경기 프로그래밍이라고 하는, 주어진 요구를 만족하는 프로그램을 정확하게 기술하는 프로그래밍 콘테스트와 같은 것이며, 이들은 컴퓨터 과학이나 수학의 지식을 필요로 하는 문제가 많이 출제된다 것이 특징이다.

경기 프로그래밍은 국내외 불문하고 개최되고 있어 AtCoder, Topcoder, ACM 국제대학 대항 프로그래밍 콘테스트 등 유명한 콘테스트가 많이 존재한다.특히 이번 형식에 매우 가까운 것으로 Project Euler라고 하는 콘테스트가 있다.이 콘테스트에서는 도전적인 수학/컴퓨터 프로그램의 문제가 출제되고 있으며, 이를 풀기 위해서는 단순한 수학적 통찰 이상의 것이 필요하다.

또한 수학 지식이 있으면 간결하고 효율적으로 문제를 해결할 수 있지만, 많은 경우에는 컴퓨터와 프로그램의 기술이 필요하다.

【소수】의 문제는, 어느 정해진 범위의 소수를 인쇄하면 「1」은 몇회 인쇄되는가 하는 것이었다.범위가 작은 것이라면, 직접 프로그램을 쓰는 것보다 종이에 쓰고 세는 것이 빠르지만, 범위가 큰 경우는, 어떻게 소수를 요구하는가 하는 것이 간이 된다.유명한 방법으로 "엘라토스테네스의 체 체"가 있다.

【타케우치 함수】란, 프로그래밍 언어 처리계의 벤치마크 등에 사용되는, 재귀적으로 정의된 함수이며, 1974년에 타케우치 이루오에 의해 생각된 것이다.재귀 적으로 정의 된 함수에는 피보나치 수열, 아커만 함수 등이 있습니다.

【2진법】의 문제는, 2진법으로 나타내어지고 있는 수를 10진법으로 다시 나타내는 문제였다.열심히 프로그램을 써서 요구할 수도 있으면, PC를 계산기 대신에 사용해 풀 수도 있다.또한 손 계산으로 구할 수도 있지만, 약간의 궁리를 함으로써 손 계산에서도 효율적이고 간단하게 구할 수도 있다.다양한 방법으로 구할 수 있는 재미있는 문제였다.

【합계가 정해진 수열】의 문제는, 자연수의 분할에 관한 문제였다.자연수 n에 대해, 그 순서의 차이를 제외하고 자연수의 합으로서 표현하는 방법의 개수를 분할수라고 부르고, p(n)로 나타내고, 서로 다른 자연수로 분할하는 방법의 개수를 이분할수라고 부른다. n)로 나타내고, 자연수 n에 대해, 홀수의 자연수로 분할하는 방법의 개수를 홀분할수라고 한다.이 때, 질문 1은 q(50)을 구하는 문제이고, 질문 2는 p(50)을 구하는 문제였다.또, 질문 3은 이분할수와 홀분할수는 같다고 하는 「오일러의 ​​분할항등식」보다 q(50)과 같은 값이 된다.

【약수】의 문제는, 약수 함수

에 관한 문제였다.특히, σ₀(n)=d(n), σ₁(n)=σ(n)로 표기될 수도 있다. d(n)나 σ(n)은 구체적인 구하는 방법이 알려져 있고,

반대

된다.여담이지만, σ(n)=2n이 되는 n은 완전수로 알려져 있고, σ(n)=kn이 되는 n은 k배 완전수라고 한다.즉, 완전수란 2배 완전수라고 볼 수 있다.

[부분 문자열]의 문제는 부분 집합의 개념에 관한 문제였다.문자가 모두 다른 길이 n의 문자열의 부분 문자열은, 필요한 집합의 생각보다 2n개의 부분 문자열이 가능하다.문자가 모두 다르다고는 할 수 없는 경우는, 같은 방법으로 얻어진 2 n개의 집합에 대해 합집합을 생각하면, 중복되어 있는 부분이 제거되어 제목의 문자열의 집합을 얻을 수 있다.이번 경우는 n=11로 작기 때문에 2048개 중에서 중복 부분을 제거하는 방법에서도 현실적인 시간으로 풀 수 있지만, n이 큰 경우는 동적 계획법에 의한 방법이 현실적이다 .

중요한 부분을 자크리 설명하면, 1문자째로부터 k문자째까지의 문자를 이용한 부분 문자열이 생겼다고 한다.이들 부분 캐릭터 라인과 한층 더 말미에 k+1 캐릭터째를 추가한 것의 화집합을 구해, 이것을 1 캐릭터째로부터 k+1 캐릭터째까지의 문자를 이용한 서브 캐릭터 라인으로 한다.이하 이것을 반복하여 구해 나가는 방법이다.

【정수】의 문제는, 택시수, 콜라츠 예상, 골드바흐의 예상 등의 정수론의 미해결 문제를, 프로그래밍을 이용해 맛보는 문제였다.다음은 이러한 문제와 관련된 몇 가지 설명입니다.

• 택시 수 문제의 확장으로 다음 명제가 알려져 있습니다. "모든 자연수 N에 대해, 3차 곡선 x³+y³=m이 x도 y도 모두 양이 되는 적어도 N개의 정점을 가지는 정수 m0가 존재한다."

• 콜라츠 예상의 문제는 처음으로 본 「타케우치 함수」의 문제와 출제가 닮았고, 모두 재귀적인 조작의 횟수를 요구하는 문제였다.또한 2011년 센터 시험에서는 수학Ⅱ·B의 제6문의 수치 계산과 컴퓨터를 출제 테마로 한 문제로 이 문제와 마찬가지로 유명한 콜라츠 예상을 테마로 한 문제가 출제되었다.

• 보통 골드바흐의 예상이라고 하면 「모든 2보다 큰 짝수는, 2개의 소수의 합으로서 표현할 수 있다」라고 하는 내용을 떠올린다고 생각한다.이 예상의 이름의 유래는, 1742년에 골드바흐가 오일러에의 서한으로 「5보다 큰 임의의 자연수는, 3개의 소수의 합으로 표현할 수 있다」라고 말한 것에 유래한다.또한 비슷한 예상으로 "5보다 큰 홀수는 3개의 소수의 합으로 표현할 수 있다"라는 "약한 골드바흐의 예상"이나 "4보다 큰 짝수는 2개의 기소수의 합으로 표현할 수 있다"라는 "강한 골드 바흐의 예상' 등이 있다.

【드레미 암호】의 문제는, 복문자 환자식 암호에 관한 문제였다.질문 1은 실제로 디코딩하는데 필요한 암호문의 구조를 해석하는 문제이고, 질문 2는 실제로 환자표를 작성해, 그것에 근거해 인코딩하는 문제였다.환자식 암호는 소설 등에도 등장할 수 있으며, 유명한 것은 에드가 알란 포의 황금충, 에도가와 란호의 XNUMX전 동화, 아서 코난 도일의 셜록 홈즈 시리즈의 춤 인형 등이 있다 .

【문자열 조작】의 문제는 함수에 의한 문자열 조작의 순서에 의한 문제였다.프로그래밍을 하는데 있어서, 캐릭터 라인이나 배열 등의 조작이나 분석의 기술 등은 필요하게 되는 것이며, 실제로 어떻게 조작을 실시하면 원하는 결과를 얻을 수 있는가 하는 것을 생각시키는 문제로 이었다.

【수열 조작】의 문제는, 배열 조작이나 점화식에 관한 문제였다.질문 1과 같이 n이 작은 경우는 구체적으로 손 계산으로 순서대로 구하는 것이 가능하다.질문 2에 관해서는, 실제로 sn을 써내는 것은 힘들지만, tn에 관해서는 점화식을 세울 수 있으므로, 거기까지 가면 손 계산에서도 구할 수 있다.

'경기 안내'의 경기 취지에도 쓰여진 것처럼 사회에서는 과학기술상의 문제를 해결할 때 컴퓨터를 사용하여 복잡한 계산을 하는 경우가 많다.또, 친밀한 과학 현상에는, 이과·수학·정보 등 다양한 것이 복잡하게 얽혀 있어, 프로그래밍에 의해 과학 기술상의 문제를 해결하고 있는 일도 많다.이번 문제는 프로그래밍에 의한 문제 해결의 유용성과 수학적 사고의 필요성을 느낄 수 있는 매우 좋은 문제였다.
사이타마 대학 대학원 이공학 연구과 나카가와 유이치