Python에서 반복 관계를 해결하는 방법

Question

반복 관계에 숫자로 답하는 코드를 작성하려고합니다. 관계 자체는 간단하며 다음과 같이 정의됩니다. 변수 x는 정수

• P (I) = P (I + 2)/2 + P이다 (I-1)/2의 경우 I> 0 및 I < X
• P (0) = P (2)/2
• P (I) = 1이면 I> = X

이이 코드도이다.

from __future__ import division 
def p(i): 
    if (i == 0): 
     return p(2)/2 
    if (i >= x): 
     return 1 
    return p(i-1)/2+p(i+2)/2 


x = 4 
#We would like to print p(0) for example. 

물론 이것은 실제로 p (0)을 계산할 수 없습니다. 어떻게 이것을 파이썬에서 할 수 있습니까?

---

그러므로 해결 numpy.linalg.solve 연립 방정식의 시스템을 구축 할 수 있는가?

Answer 1

선형 대수학을 사용하여 해결할 수 있습니다. 아래에서 수행 한 작업은 간단한 하드 코딩 된 번역입니다. p(0)에서 p(3)에 대한 방정식은 오른쪽이 =0이되도록 재정렬하여 코딩합니다. 기본 사례로 되풀이 관계에 나타나는 p(4) 및 p(5)의 경우 오른쪽에 =1이 있습니다.

• -p(0) + p(2)/2 = 0

• p(i-1)/2 - p(i) + p(i+2)/2 = 0 I> 0 및 I < X

• p(i) = 1위한 만약> = X 여기서

는 n=4

,536,913 위해 하드 코딩 프로그램

import numpy 
a=numpy.array([[-1, 0, 0.5, 0, 0, 0], # 0 
       [0.5, -1, 0,0.5, 0, 0], # 1 
       [0, 0.5, -1, 0, 0.5, 0], # 2 
       [0, 0, 0.5, -1, 0, 0.5], # 3 
       [0, 0, 0, 0, 1, 0], # 4 
       [0, 0, 0, 0, 0, 1], # 5 
       ]) 
b=numpy.array([0,0,0,0,1,1]) 
# solve ax=b 
x = numpy.linalg.solve(a, b) 
print x 

편집은 프로그래밍 방식으로 행렬을 구성하는 코드이며 n=4에 대해서만 테스트되었습니다!

n = 4 

# construct a 
diag = [-1]*n + [1]*2 
lowdiag = [0.5]*(n-1) + [0]*2 
updiag = [0.5]*n 
a=numpy.diag(diag) + numpy.diag(lowdiag, -1) + numpy.diag(updiag, 2) 

# solve ax=b 
b=numpy.array([0]*n + [1]*2) 
x = numpy.linalg.solve(a, b) 

print a 
print x[:n] 

이 질문에서 의견의 솔루션을 일치

[[-1. 0. 0.5 0. 0. 0. ] 
[ 0.5 -1. 0. 0.5 0. 0. ] 
[ 0. 0.5 -1. 0. 0.5 0. ] 
[ 0. 0. 0.5 -1. 0. 0.5] 
[ 0. 0. 0. 0. 1. 0. ] 
[ 0. 0. 0. 0. 0. 1. ]] 
[ 0.41666667 0.66666667 0.83333333 0.91666667] 

를 출력합니다.

Answer 2

당신의 코드가 그렇게해야하는 것처럼 보이기 때문에 혼란 스럽습니다.

def p(i): 
    x = 4 # your constant should be defined in-function 

    if (i == 0): 
     return p(2)/2 
    elif (i >= x): 
     return 1 
    return p(i-1)/2+p(i+2)/2 

큰 문제는 재귀입니다. p(1)의 경우 :

p(0)/2     +     p(3)/2 
p(2)/2     +   p(2)/2 + p(4)/2 
p(1)/2     +    p(1)/2 + 1/2 
# each side of the operator is now the same as the original problem! 
# that's a sure sign of infinite recursion. 

출력으로는 무엇을 기대합니까?

Answer 3

여기에서의 문제는 재귀가 명시 적이지 않기 때문에 시작하는 위치에 관계없이 무한 재귀로 끝나지 만 결국 해결할 선형 방정식의 시스템을 산출하게됩니다. 이것이 파이썬을 사용하여 풀어야 할 문제라면 파이썬을 사용하여이 방정식 시스템의 계수를 계산하고이를 해결하기 위해 Cramer의 규칙을 사용합니다.

편집 : 구체적으로 알려지지 않은 사항은 p (0), ..., p (x-1)입니다. 방망이 바로 하나의 계수 행 벡터는 (p (0) -p (2)/2 = 0에서부터) (1, 0, -1/2, 0, ..., 0)이고, 나머지는 모두 형태 (..., -1/2, 1, 0, -1/2, ...). 이들 중 x-1 (p (1), ..., p (x-1) 각각에 하나씩)이 있으므로 시스템에 고유 한 해가 있거나 전혀 없습니다. 직관적으로, 항상 독특한 해결책이있는 것처럼 보입니다.

마지막 두 방정식은 p (x)와 p (x + 1)를 특징으로하기 때문에 고유 할 것입니다. 따라서이 항은 생략됩니다. Cramer 규칙의 RHS에 대한 열 벡터는 (0, 0, ..., 0, 1/2, 1/2)이 될 것이라고 나는 믿는다.

Numpy는 매트릭스를 지원합니다.