80 메가마인드가 10×8 직사각형에 배열되어 있습니다. 세로줄마다 가장 키가 큰 사람이 나타났고, 그 중 개를 키우는 메가마인드가 가장 낮았다. 그런 다음 그들은 각 가로 줄에서 가장 낮은 것을 발견했으며 그 중 모자를 쓴 메가 마인드가 가장 큰 것으로 판명되었습니다. 문제는 누가 더 키가 크냐는 것입니다. 메가마인드는 개와 함께 또는 모자를 쓰고 있습니까?
Megamind는 사다리를 사용하여 집 지붕에 올라가고 싶어합니다. 식료품 저장실에는 많은 사다리가 있지만 불행히도 대부분의 사다리가 충분하지 않습니다. 연속으로 두 단계가 누락된 사다리는 메가마인드로 오를 수 없습니다. 그의 모든 계단은 원래 N 계단이었습니다. 모든 계단에는 명확하게 정의된 바닥과 상단이 있습니다. Megamind가 등반할 수 있는 사다리 옵션은 몇 개입니까?
우리는 N >= 2라고 가정합니다. 첫 번째와 두 번째 가로대 사이(더 정확하게는 두 번째 가로대 사이)에서 사다리를 자릅니다. 상단에는 N-1 단계의 계단이있는 작은 계단이 있고 하단에는 한 곳이 있습니다. 둘 다 정확하다고 보장되지만 일반적으로 일부 단계는 누락됩니다.
MM이 오를 수 있다면 사다리를 옳다고 부릅니다. 사다리의 잠재적 단계 수를 차수라고 합니다.
편의를 위해 다음 표기법을 도입합니다. n차의 일반 계단 수와 하단 계단이 누락된 경우 q(n; false), 하단 계단이 있는 경우 q(n; true)로 표시됩니다. 차수가 n인 모든 일반 계단의 수는 q(n)으로 표시됩니다.
두 가지 경우가 있습니다.
1. 상위 사다리는 하위 단계가 있습니다. 그러면 N차의 "복합" 사다리의 총 수는 q(N-1; true) * 2와 같습니다. 차수가 1인 일반 계단의 수는 2입니다.
반면에, 분명히 q(N-1; true) = q(N-2)입니다. 따라서 이 경우에 대한 올바른 옵션의 총 개수는 2*q(N-2)입니다.
2. 상위 사다리에는 하위 단계가 없습니다. 차수가 N인 복합 계단의 총 수는 q(N-1; false) * 1이므로 복합 계단이 정확하려면 1차의 낮은 계단에 가로대가 있어야 합니다.
한편, q(N-1; 거짓) = q(N-2; 참) = q(N-3). 따라서 올바른 옵션의 총 개수는 q(N-3)입니다.
따라서: 모든 계단에는 명확하게 정의된 바닥과 상단이 있습니다.
80 메가마인드가 10×8 직사각형에 배열되어 있습니다. 세로줄마다 가장 키가 큰 사람이 나타났고, 그 중 개를 키우는 메가마인드가 가장 낮았다. 그런 다음 그들은 각 가로 줄에서 가장 낮은 것을 발견했으며 그 중 모자를 쓴 메가 마인드가 가장 큰 것으로 판명되었습니다. 문제는 누가 더 키가 크냐는 것입니다. 메가마인드는 개와 함께 또는 모자를 쓰고 있습니까?
4ke에서는 그렇게 보였습니다.
X >= Y >= Z --> X >= Z
(5)
Megamind는 사다리를 사용하여 집 지붕에 올라가고 싶어합니다. 식료품 저장실에는 많은 사다리가 있지만 불행히도 대부분의 사다리가 충분하지 않습니다. 연속으로 두 단계가 누락된 사다리는 메가마인드로 오를 수 없습니다. 그의 모든 계단은 원래 N 계단이었습니다. 모든 계단에는 명확하게 정의된 바닥과 상단이 있습니다. Megamind가 등반할 수 있는 사다리 옵션은 몇 개입니까?
텍스, 더 쉽습니다. 피보나치 토끼 수열이 그려졌습니다.
F(1) = 2
F(2) = 3
F(N) = F(N-1)+F(N-2)
// 반복되지 않는 공식이 있는지 모릅니다. 아직 제대로 이해하지 못했습니다.
확신하는?
F(1) = 1
F(2) = 2
F(3) = 4
F(4) = 7
F(5) = 12
F(6) = 19
F(7) = 33(???)
확신하는.
1단계 2옵션 포함(예/아니오)
2개 = 3개 옵션 포함(둘 다 첫 번째 옵션이 없고 두 번째 옵션이 없음)
등.
내 공식이 맞습니다.
코메르산트
내 공식이 맞습니다.
재귀 공식은 e이지만 나에게는 그렇게 간단하지 않습니다. 그러나 결과와 해 자체는 실제로 피보나치 수 F(N+2)입니다. 정확한 증거를 제시하는 일만 남았습니다. MD , 어디서 공식을 얻었습니까? 작은 숫자에 대한 옵션만 계산하시겠습니까?
나는 공식의 완전한 출력을 가지고 있습니다. 내가 기다리는 동안.
4ke에서는 그렇게 보였습니다.
X >= Y >= Z --> X >= Z
재귀 공식은 e이지만 나에게는 그렇게 간단하지 않습니다. 그러나 결과와 해 자체는 실제로 피보나치 수 F(N+2)입니다. 정확한 증거를 제시하는 일만 남았습니다. MD , 어디서 공식을 얻었습니까? 작은 숫자에 대한 옵션만 계산하시겠습니까?
나는 공식의 완전한 출력을 가지고 있습니다. 내가 기다리는 동안.
c(n)을 MM이 올라갈 수 없는 n개의 계단을 가진 계단의 수라고 하자. 다음 옵션을 고려하십시오.
십
100
다음은 세 개의 계단 시리즈 중 낮은 단계입니다. 1 - 계단이 있고, 0 - 아니요. 분명히, n >= 2
c(n) = c(n-1) + c(n-2) + 2^(n-2), c(0) = 0, c(1) = 0 (1)
올라갈 수 있는 총 계단 수는 다음 공식으로 표시됩니다. 2^n - c(n) =? F(n+2)
증명해 봅시다. 기능 정의
f(n+2) = 2^n - c(n); f(2) = 1을 계산하고 f(3) = 2는 해당하는 피보나치 수와 동일합니다. (2)
n > 1인 경우 (2)의 값 c(n)을 (1)에 대입하면 다음을 얻습니다.
2^n - f(n+2) = 2^(n-1) - f(n+1) + 2^(n-2) - f(n) + 2^(n-2), 2의 거듭제곱 취소하면 다음을 얻습니다.
f(n+2) = f(n+1) + f(n), 계산된 값을 고려 f(2) = F(2) = 1, f(3) = F(3) = 2 , f(n+2) = F(n+2)
그건 그렇고, 나는 다른 해결책을 가지고 있습니다 (2의 거듭 제곱은 없습니다).
MM이 오를 수 있다면 사다리를 옳다고 부릅니다. 사다리의 잠재적 단계 수를 차수라고 합니다.
편의를 위해 다음 표기법을 도입합니다. n차의 일반 계단 수와 하단 계단이 누락된 경우 q(n; false), 하단 계단이 있는 경우 q(n; true)로 표시됩니다. 차수가 n인 모든 일반 계단의 수는 q(n)으로 표시됩니다.
두 가지 경우가 있습니다.
1. 상위 사다리는 하위 단계가 있습니다. 그러면 N차의 "복합" 사다리의 총 수는 q(N-1; true) * 2와 같습니다. 차수가 1인 일반 계단의 수는 2입니다.
반면에, 분명히 q(N-1; true) = q(N-2)입니다. 따라서 이 경우에 대한 올바른 옵션의 총 개수는 2*q(N-2)입니다.
2. 상위 사다리에는 하위 단계가 없습니다. 차수가 N인 복합 계단의 총 수는 q(N-1; false) * 1이므로 복합 계단이 정확하려면 1차의 낮은 계단에 가로대가 있어야 합니다.
한편, q(N-1; 거짓) = q(N-2; 참) = q(N-3). 따라서 올바른 옵션의 총 개수는 q(N-3)입니다.
따라서 다음과 같은 반복 관계가 있습니다.
q(N) = 2*q(N-2) + q(N-3).
선형이며 har입니다. 이에 대한 방정식은 다음과 같습니다.
z^3 - 2*z - 1 = 0
분명히 다음과 같은 요인으로 분해됩니다.
(z + 1) * (z^2 - z - 1) = 0.
따라서 근은 z_1 = ( 1 + sqrt(5) ) / 2 = fi, z_2 = 1 - fi, z_3 = -1입니다.
방정식에 대한 일반적인 솔루션은 선형 조합입니다.
q(n) = C_1*z_1^n + C_2*z_2^n + C_3*z_3^n (***).
처음 몇 가지 옵션에 대한 수동 계산은 다음과 같은 수의 옵션을 제공합니다. 피보나치 수(F_0 = 0, F_1 = 1):
q(1) = 2 = F_3,
q(2) = 3 = F_4,
q(3) = 5 = F_5,
q(4) = 8 = F_6,
q(5) = 13 = F_7 등
패턴은 분명합니다. (***)로 대체:
F_3 = C_1*z_1 + C_2*z_2 - C_3(***).
F_4 = C_1*z_1^2 + C_2*z_2^2 + C_3(***).
F_5 = C_1*z_1^3 + C_2*z_2^3 - C_3(***).
먼저, 이 세 방정식에서 k-you C_i가 고유하게 결정됩니다(시스템의 주요 결정자는 거의 0이 아닌 Vandermonde 행렬식임). 반면에 C_1 = 1/sqrt(5) = -C_2 및 C_3 = 0이면 문자 그대로 피보나치 수를 얻습니다.
따라서 답은 N차의 일반 계단 수는 F_{N+2}와 같습니다.
그건 그렇고, 나는 다른 해결책을 가지고 있습니다 (2의 거듭 제곱은 없습니다).
피보나치의 경우 동일한 재귀 관계가 적용됩니다. q(N) = 2*q(N-2) + q(N-3).
따라서 계열이 일치하려면 계열의 연속 3개 값의 일치를 증명하는 것으로 충분했습니다.