수색…
예제 문제 해결을위한 행렬 지수 계산
F (N)을 찾기 : N 피보나치 수를 토륨. n 이 비교적 작 으면 문제는 아주 쉽습니다. 우리는 f(n) = f(n-1) + f(n-2) 간단한 재귀를 사용할 수도 있고, 같은 함수의 계산을 반복해서 피하기 위해 동적 프로그래밍 접근법을 사용할 수도 있습니다. 그러나 0 <n <109 인 경우, f (n) mod 999983을 찾으면 문제는 무엇을 의미합니까? 동적 프로그래밍은 실패 할 것이므로 어떻게이 문제를 해결할 수 있습니까?
먼저 행렬 지수가 재귀 관계를 나타낼 수있는 방법을 살펴 보겠습니다.
선수 과목 :
- 두 개의 매트릭스가 주어지면 제품을 찾는 방법을 알아야합니다. 더구나 두 행렬의 곱 행렬과 그 중 하나는 다른 행렬을 찾는 방법을 알고 있습니다.
- 치수 (d)의 X (D)의 행렬을 주어 (d 3 로그 (N)) O에서의 N 승을 찾는 방법을 알고있다.
패턴 :
처음에는 재귀 관계가 필요하고 이미 알려진 상태 집합에서 원하는 상태로 이끌 수있는 행렬 M 을 찾고 싶습니다. 우리는 주어진 반복 관계의 k 상태를 알고 있다고 가정하고 (k + 1) 번째 상태를 찾고자합니다. M을 k × k 행렬이라하고, 우리는 재귀 관계의 알려진 상태로부터 행렬 A : [k X 1] 을 만들고, 이제 우리는 행렬 B 를 얻고 자한다 : [k X 1] 다음 상태, 즉 아래와 같이 MXA = B :
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
M X | f(n-2) | = | f(n-1) |
| ...... | | ...... |
| f(n-k) | |f(n-k+1)|
따라서 M을 적절하게 설계 할 수 있다면 우리의 일은 끝날 것입니다! 그런 다음 행렬을 사용하여 반복 관계를 나타냅니다.
유형 1 :
가장 간단한 것으로 시작해 봅시다. f(n) = f(n-1) + f(n-2)
f(n+1) = f(n) + f(n-1) .
f(n) 과 f(n-1) 을 알고 있다고 가정합시다. 우리는 f(n+1) 을 찾고 싶습니다.
위에서 언급 한 상황에서 행렬 A 와 행렬 B 는 다음과 같이 형성 될 수 있습니다.
Matrix A Matrix B
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
[주의 : 매트릭스 A 는 f(n+1) 의존하는 모든 상태가 존재할 수 있도록 항상 설계 될 것이다]
이제 우리는 2X2 행렬 M 을 설계 할 필요가 있습니다. 즉, 위에서 언급 한 것처럼 MXA = B 를 만족해야합니다.
B의 첫 번째 요소는 f(n+1) 실제로 f(n) + f(n-1) . 이를 얻기 위해서는 행렬 A 에서 1 X f (n) 과 1 X f (n-1)이 필요 합니다. 그래서 M 의 첫 줄은 [1 1] 이 될 것입니다.
| 1 1 | X | f(n) | = | f(n+1) |
| ----- | | f(n-1) | | ------ |
[주의 : ----- 우리가이 값에 대해 걱정하지 않는다는 것을 의미합니다.]
마찬가지로, B의 2 항목은 f(n) 단순한 1의 X F (N)를 취함으로써 얻었다 수 있으므로 M의 둘째 행은 [1 0]이다.
| ----- | X | f(n) | = | ------ |
| 1 0 | | f(n-1) | | f(n) |
그런 다음 원하는 2 X 2 행렬 M 을 얻습니다.
| 1 1 | X | f(n) | = | f(n+1) |
| 1 0 | | f(n-1) | | f(n) |
이 행렬은 단순히 행렬 곱셈을 사용하여 유도됩니다.
유형 2 :
f(n) = a X f(n-1) + b X f(n-2) 찾으십시오. 여기서 a 와 b 는 상수입니다.
이것은 f(n+1) = a X f(n) + b X f(n-1) 이다.
여기까지는 행렬의 차원이 종속성의 수와 동일 할 것임을 분명히해야합니다. 즉,이 특정 예에서 다시 2입니다. 따라서 A 와 B 에 대해 크기 2 X 1 의 두 행렬을 작성할 수 있습니다.
Matrix A Matrix B
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
이제 f(n+1) = a X f(n) + b X f(n-1) 이기 때문에 객관적 행렬 M 의 첫 번째 행에 [a, b]가 필요하다. 그리고 B 의 두 번째 항목, 즉 f(n) 대해서는 이미 행렬 A 에 포함되어 있으므로 행렬 M의 두 번째 행을 [1 0]으로 가져옵니다. 이번에 우리는 얻는다.
| a b | X | f(n) | = | f(n+1) |
| 1 0 | | f(n-1) | | f(n) |
아주 간단 하죠?
유형 3 :
당신이이 단계까지 살아남 았다면, 당신은 훨씬 더 오래 자랐습니다. 이제 조금 복잡한 관계에 직면 해 봅시다 : f(n) = a X f(n-1) + c X f(n-3) 찾으십니까?
너! 몇 분 전에, 우리가 본 것은 모두 인접한 상태 였지만 여기에서는 상태 f (n-2) 가 누락되었습니다. 지금?
실제로 이러한 문제를 우리는 다음과 같은 관계를 변환 할 수 더이상이다 f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3) , 도출 f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2) 이다. 자, 이것이 실제로 타입 2에서 기술 된 형식이라는 것을 알 수 있습니다. 그래서 여기에서 객관적인 행렬 M 은 3 X 3 이 될 것이고, 그 원소들은 다음과 같습니다 :
| a 0 c | | f(n) | | f(n+1) |
| 1 0 0 | X | f(n-1) | = | f(n) |
| 0 1 0 | | f(n-2) | | f(n-1) |
이것은 유형 2와 같은 방법으로 계산됩니다. 어려울 경우 펜과 종이로 시도하십시오.
유형 4 :
삶은 지옥처럼 복잡해지고 있으며 문제는 이제 f(n) = f(n-1) + f(n-2) + c 를 찾도록합니다. 여기서 c 는 상수입니다.
이제 이것은 새로운 것이고 과거에 우리가 보았던 모든 것이 곱셈 후에 A의 각 상태는 B 의 다음 상태로 변형됩니다.
f(n) = f(n-1) + f(n-2) + c
f(n+1) = f(n) + f(n-1) + c
f(n+2) = f(n+1) + f(n) + c
.................... so on
그래서, 일반적으로 우리는 이전의 방법으로 그것을 얻을 수는 없지만 c 를 상태로 추가하는 방법은?
| f(n) | | f(n+1) |
M X | f(n-1) | = | f(n) |
| c | | c |
자, M 을 설계하기가 그리 어렵지 않습니다. 다음은 어떻게 완료되었지만 확인하는 것을 잊지 마세요.
| 1 1 1 | | f(n) | | f(n+1) |
| 1 0 0 | X | f(n-1) | = | f(n) |
| 0 0 1 | | c | | c |
유형 5 :
f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e 찾으십시오. 당신을 위해 운동으로 남겨 둡시다. 먼저 상태와 행렬 M 을 찾으십시오. 그리고 귀하의 솔루션과 일치하는지 확인하십시오. 또한 행렬 A 와 B를 찾으십시오.
| a 0 c d 1 |
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 0 1 |
유형 6 :
때때로 재발은 다음과 같이 주어집니다 :
f(n) = f(n-1) -> if n is odd
f(n) = f(n-2) -> if n is even
간단히 말해서 :
f(n) = (n&1) X f(n-1) + (!(n&1)) X f(n-2)
여기서는 홀수 짝수를 기준으로 함수를 나눌 수 있고 두 행렬을 서로 다른 두 행렬로 유지하여 따로 따로 계산할 수 있습니다.
유형 7 :
조금 너무 자신감이 있니? 잘 됐네요. 때로는 관심이있는 곳에서 재발을 두 번 이상 유지해야 할 수도 있습니다. 예를 들어 재발을 다시 시작하려면 다음과 같이하십시오.
g(n) = 2g(n-1) + 2g(n-2) + f(n)
여기서, 반복 g (n) 은 f(n) 의존하며, 이것은 동일한 행렬에서 그러나 증가 된 차원에서 계산 될 수있다. 이 처음부터 행렬 A 와 B를 설계하자.
Matrix A Matrix B
| g(n) | | g(n+1) |
| g(n-1) | | g(n) |
| f(n+1) | | f(n+2) |
| f(n) | | f(n+1) |
여기서, g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n) 이제 위에서 언급 한 프로세스를 사용하여 객관적 행렬 M 을 다음과 같이 찾을 수 있습니다.
| 2 2 1 0 |
| 1 0 0 0 |
| 0 0 2 2 |
| 0 0 1 0 |
그래서, 이것들은이 간단한 기술로 해결하기 위해 사용되는 반복 관계의 기본 범주입니다.