재귀 시퀀스의 반복 방법

Question

재귀 시퀀스 a (n) = - a (n-1) + n-1은 어떻게 풀릴까요? 전방 및 후방 반복을 시도했지만 a (n)에 대해 명시 적 솔루션을 얻을 수 없었습니다.

Answer 1

귀하의 첫 번째 단계는 패턴이 신흥 볼 수 결과 테이블을

f(n)=x 

n | x 
----- 
0 | 7 
1 | -7  (-7 + 1 - 1) 
2 | 8  (7 + 2 - 1) 
3 | -6  (-8 + 3 - 1) 
4 | 9  (6 + 4 - 1) 
5 | -5  (-9 + 5 - 1) 
6 | 10  (5 + 6 - 1) 
7 | -4  (-10 + 7 - 1) 
8 | 11  (4 + 8 - 1) 
9 | -3  (-11 + 9 - 1) 

을 작성해야합니다. 솔루션의 각 쌍 [(0, 1), (2, 3), (4, 5), ...]은 (7, -7)으로 시작하여 n의 두 점마다 1을 증가시키면서 14의 차이가 있습니다. 우리는이를 일반화 할 수 있습니다

f(0) = 7 
f(n) = 7 + k - 14 * b 
    where k is the increment value (each 1 k per 2 n) 
     b is 1 when n is odd, else 0. 

이제 우리는 단지 n의 관점에서 k 및 b을 정의해야합니다. k 너무 열심히 안, 어디 보자 :

n | k 
0 | 0 
1 | 0 
2 | 1 
3 | 1 

그 아무것도 당신을 생각 나게 하는가? 그것은 바닥에 떨어진 div2입니다.

7 + (n // 2) - 14 * b 

b

나에게 mod 2처럼 보이는

n | b 
0 | 0 
1 | 1 
2 | 0 
3 | 1 

지금

! 모듈러스는 나눗셈 문제의 나머지 부분이며, 숫자가 짝수인지 홀수인지를 확인할 수있는 좋은 방법입니다. n이 홀수 일 때 우리는 b==1을 원하기 때문에 일반 모듈러스도 찾고 있습니다.

f(0) = 7 
f(n) = 7 + (n // 2) - 14 * (n%2) 
    where (//) is the floor division function 
     (%) is the modulo function 

---

이제 우리는 함수에 모두 함께 그 넣을 수 있습니다. 이동이입니다 하스켈은 단순히 심히 아니라 재귀 를 구현하기 때문에

func f(n int) int { 
    return 7 + n/2 - 14 * (n % 2) 
} 

파이썬에서 그것은, 우리가

f :: Int -> Int 
f n = 7 + n `div` 2 - 14 * (n `mod` 2) 

또는

있어 하스켈에서

def f(n): 
    return 7 + n//2 - 14 * (n%2) 

을의 ...

f :: Int -> Int 
f 0 = 7 
f n = f (n-1) + n - 1