다음 알고리즘에 대한 반복 관계 방정식 찾기

Question

특정 소셜 네트워크 사이트의 월 사용자 수는 다음과 같습니다.

F(n)= F(n-1)*120% + 100*n where F(0)=0  

이 매월 100 새로운 사용자 인해 사람들에게 소셜 네트워크를 초대 사용자에게 있기 때문에 광고와 더 많은 사용자가 달에 추가 20 %의 추가 된 것을 의미한다. 또한 첫 달에는 사용자가 없습니다. 우리가이 재귀 번호에 연결하면

어쨌든 우리가 얻을 것이다 :

F(0)=0 
F(1)=F(0)*1.2 + 100*1=100 
F(2)=F(1)*1.2 + 100*2=320 
F(3)=F(2)*1.2 + 100*3=684 
F(4)=F(3)*1.2 + 100*4=1220.8 
F(5)=F(4)*1.2 + 100*5=1964.96 
.... 

가 어쨌든 나는 그 질문의 첫 번째 부분에 답이있다. 이제 나는 그 재귀 관계를 풀어 나가야합니다. 재발 관계를 풀 수있는 방정식을 찾아야합니다. 즉, 함수 2를 전달하면 함수를 호출하지 않고도 320을 출력하는 함수입니다.

대답

는 실제로 :

내가 그 해결책에 도달하는 방법을 이해하지 않습니다. 그 대답은 HERE입니다. 나는 해결책을 얻는 것이 아니라 그것을 해결하는 방법을 이해하고 싶습니다.

Answer 1

수학보기

대신 1.2 내가 a를 사용하는 것 대신 100의 내가 b 사용합니다 (! A> 1, B를 = 0) :

F(n) = aF(n-1) + bn ==> 
F(n) = a (aF(n-2) + bn) + bn 
    = a^2 F(n-2) + ab(n-1)+bn 
    = a^3F(n-2) + a^2 * b * (n-2)+a*b*(n-1)+b*n=... 
    = a^n F(0) + a^(n-1) * b * (n-(n-1)) + .... + bn 
    = 0 + a^(n-1)* nb + a^(n-2)* (n-1)b + ... + a^0 *1*b - 
      [a^(n-1)* (n-1)b + a^(n-2) * (n-2)b + ... + 0) 

우리가 쓰는 경우 :

A = a^(n-1)* nb + a^(n-2)* (n-1)b + ... + a^0 *1*b 
B = a^(n-1)* (n-1)b + a^(n-2) * (n-2)b + ... 

당신 ne 에 A-B을 찾으십시오.

다음

A = b (a^n + a^n-1 + a^n-2 + ....)' 
B = b/a * (a^(n-1)+....)' - a 

우리가 C = a^n + a^n-1 + a^n-2 + ....을 할 경우 우리는 C = (a^(n+1) - a)/(a - 1)을 알고 단순히 당신이 C를 계산할 수 있습니다 '그리고 마지막으로 당신이 A와 B와 자신의 차이 A - B을 계산할 수 있습니다.

알고리즘과 실시간 작업보기

내가 알고리즘의 맥락에서 얘기하고 싶어하지만, 난 상관에게있어 약 O 및 Θ 및 Ω, ...에 대한 정확한 시간을 실행하지. 나는 당신의 알고리즘을 볼 때

는 그래서 그것은 Θ을 말할 (A ^N) 어떤 계산없이, 당신은 1 십억원 대체 할 경우 함수가 기하 급수적으로 너무 제거 증가하기 때문에, 그것은 당신의 Θ 표기에 영향을주지 않기 때문에 일부 상수 또는 다항식 함수 (0으로 변환하지 않음)는 지수 실행 시간을 변경하지 않으며 최종 결과에서 다항식 함수를 제거합니다. 그래서이 경우 나는 단단한 수학을 결코 시도하지 않습니다.실생활에없는 학술 논문이나 시험을 쓸 때 견고한 수학을 사용하겠습니다.

Answer 2

이전에 게시 한 솔루션을 생각해 냈으면합니다. 이것은 내가 처리 한 것이며 올바른 해결책이 될 수있는 방정식 (비 재귀 적)을 가졌기 때문에 추측 할 수 있습니다.

Answer 3

가 F (n)은 A *의 F를 = (N-1) + B * N

여기서 우리가있는 것은 선형 첨가 지수 같다.

아이디어 찾는 것이 사실 확인 C 및 D는 다음 식 :

F (N) + C에 * N + D = A * (F (N-1) + C를 * (N-1) + D)

은 우리가 다른 기능을 도입 할 수있다 : G (N) = F (N) + C * N + D

G (n)은 A * g를 = (N-1)

G (n) = E * A^n (시작 조건에서 E를 찾을 수 있음)

F (n) = A^nC * nD

* N + A * DDA * C

B의 * N = A * C 형 * (N-1) + A * DC * 노스 다코타 = (A *의 CC) :

는 이제 실제로 C와 D을 찾을 수 있습니다

B = C를 * (A-1) - 이것은 우리에게 제공한다 C

0 = A * DDA * C - 이것은 우리에게 D를 (C 이미 알려져 제공) 일반

Answer 4

f(n)=af(n-1)+bn =a[af(n-2)+b(n-1)+b(n-1)]=a^2f(n-2)+(a+1)b(n-1) -ab 

줄 것이다 f (n) = a * n * x + n * y + z

,210

지금 F (1) = A * X + Y + Z = 1 F (2) = (a^2) * X + 2Y + Z = F (3) = ...

우리 이 선형 시스템으로 x, y, z를 얻을 수 있습니다