n 단계 계단, 한 번에 1보 또는 2보를 걸으면 몇 가지 걷는 방법이 있습니까?
분석
이것은 전형적인 동적 기획 알고리즘 문제이다. 당신이 확정할 수 있는 것은 현재의 가능한 1단계나 2단계, 그리고 이후의 가능한 방법뿐이다.앞으로 가능한 주법은 귀체다.그래서 이 분석에서 귀속 알고리즘의 실현을 얻을 수 있다.모든 귀속 알고리즘은 트리 구조이기 때문이다.그래서 귀속 중의 각 결점을 보여주면 중복된 수치가 많고 중복된 계산이 너무 많아 CPU 자원을 낭비하는 것을 발견할 수 있다.n은 n-1과 n-2를 얻을 수 있고, n-1은 n-2와 n-3를 얻을 수 있기 때문이다.여기서 알 수 있듯이 n-2는 n과 n-1에서 왔고 n이 몇 개면 n-2가 몇 개 있고 n-1이 몇 개면 n-2가 몇 개 있다. 그래서 n-2의 개수는 n의 개수에 n-1의 개수를 더하는 것과 같다. 이 성질은 무엇입니까?바로 피보나 체수열이다.그래서 문제는 n 단계 피보나 절수열의 총체를 구하는 것으로 바뀌었다.외마디로 말하자면, 피보나 체수열도 토끼수열이라고 한다.그래서 비귀속 알고리즘을 얻을 수 있다.
코드 사용법
import Foundation
print(" \(Solution.recursionAnswer(n: -1)) ")
print(" \(Solution.nonRecursiveAnswer(n: 10)) ")
출력
0
143
Program ended with exit code: 0
코드 구현
import Foundation
class Solution {
public static func recursionAnswer(n:Int) -> Int {
guard n >= 1 else {
return 0
}
var resultCounter:Int = 1
if n - 1 > 0 {
resultCounter += Solution.recursionAnswer(n: n - 1)
}
if n - 2 > 0 {
resultCounter += Solution.recursionAnswer(n: n - 2)
}
return resultCounter
}
public static func nonRecursiveAnswer(n:Int) -> Int {
guard n >= 1 else {
return 0
}
if n == 1 {
return 1
}
if n == 2 {
return 2
}
var component0:Int = 1
var component1:Int = 1
var counter:Int = 3
var result:Int = 2
var middleValue:Int = 0
while counter <= n {
middleValue = component0 + component1
component0 = component1
component1 = middleValue
counter += 1
result += middleValue
}
return result
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
