SICP 문제(1.19) 문제 요약
반복 구법에서 관건은 다음과 같은 변환이다.
Fib(0)를 구하여 b1로 설정합니다.
Fib(1)를 구하여 a1로 설정합니다.
피보나치 수로 정의하면 a1+b1은 Fib(2)
이어 b2를 a1, a2를 a1+b1로 하면 a2+b2가 Fib(3)
이렇게 계속 바꾸면 a(n-1)+b(n-1)를 통해 Fib(n)를 구할 수 있다.
현재의 관건은 상기 변환 중의 연속 두 번의 변환을 한 번의 변환으로 바꾸는 방법을 찾아내는 것이다.
우선 성명합니다. 이것은 제 생각에는 머리를 깨뜨려도 생각나지 않습니다. 저는 책 제목의 힌트에 따라 왔습니다.
우선 우리가 정리한 대로,
유등식1:
b2=a1
a2=a1+b1이어서 책의 힌트에 따라 등식 2로 등식 1을 표현한다.
등식2:
b2=b1p+a1q
a2=b1q+a1q+a1p등식 2 로 얻을 수 있는 것은:
등식 3:
b3=b2p+a2q
a3=b2q+a2q+a2p등식 2를 등식 3에 대입합니다.
b3 = b2p+a2q = (b1p+a1q)p+(b1q+a1q+a1p)q
=>b3 = b1pp + a1qp + b1qq + a1qq + a1pq
=>b3= b1(pp + qq) + a1 (qp + qq + pq)
=>b3= b1 (pp + qq) + a1 (qq + 2pq)
a3 = b2q+a2q+a2p = (b1p+a1q)q+(b1q+a1q+a1p)q+(b1q+a1q+a1p)p
=> a3= b1pq + a1qq + b1qq + a1qq + a1pq + b1qp + a1qp + a1pp
=> a3= b1 (pq + qq + qp) + a1(qq + qq +pq+ qp + pp)
=> a3= b1 (pq + qq + pq) + a1(qq + pp) + a1 (qq + pq + qp)
=> a3=b1(qq+2pq) + a1(qq + pp) + a1(qq +2pq)명령p2=(pp+qq)q2=(qq+2pq)
다음과 같은 이점이 있습니다.
b3=b1p2 + a1 q2
a3=b1q2 + a1 p2 + a1q2그래서 p2=(pp+qq)q2=(qq+2pq)는 문제입니다.
위의 공식을 코드로 변환하여 제목을 작성한 프로세스 주체로 변환한 결과는 다음과 같습니다.
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(+ (* p p) (* q q))
(+ (* q q) (* 2 q p))
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
