깊이 우선 검색 중인 피보나치 수열의 계산 (어셈블리)

피보나치 수열
자연계 현상에서 자주 나타나는 수열을 가리킨다.해바라기의 종류 수와 개미의 가족도를 따라 나타날 것 같다.발견자는 피보나치입니다.어떻게 알았지?
정의된 공식은 다음과 같습니다.n을 피보나치 수열의 n개로 설정하다

F_{0} = 0

F_{1} = 1

F_{2} = 1

F_{n} = F_{n-1} + F_{n-2}　(n \leq 3)

되다
이 공식을 보면 $F{n} 달러가 있는 곳은 돌아올 수 있을 것 같아요.귀환도 나무 구조일 수 있다.

$F_{n} = F_{n-1} + F_{n-2} 나무 구조로 표현하면 그렇습니다.간단하다
그럼 여기는 $F입니다.{n}달러를 n=4로 바꿔 보십시오.

F_{4} = F_{3} + F_{2}

여기는 $F입니다.{n} = F_{n-1} + F_{n-2} (n\leq3)$를 떠올리십시오.(n\leq3)$F{n}달러의 공식을 적용할 수 있습니다.이번, $F{4} 달러 및 $F{3} 달러 일치.이미 $F{4} 달러는 공식이므로 $F{3}해 보세요.

F_{3} = F_{2} + F_{1}

이러한 공식 중에서 다음과 같은 공식을 얻어낼 수 있다.

F_{4} = F_{3} + F_{2}

F_{4} = (F_{2} + F_{1}) + F_{2}

나무로 표현하면 이런 느낌이에요.

나무의 구조가 정말 좋다.
프로그램 설계
그리고 위에 있는 나무 구조를 프로그램에 넣을 방법을 생각해 보세요.이번에 제출한 과제는 모아서 하는 것이기 때문에 열심히 하겠습니다.이번에 사용한 레지스터는 r1에서 r8까지입니다.일단 다 타봐.또한 실제로는 졸업장을 편집하는 것이 아니므로 이렇게 써도 의미가 없으니 탓하지 마세요.

        number r8, 0
        number r1, 10
        number r2, 1
        number r3, 2
        number r4, 3
        number r5, 0
        number r6, 0
        call r7, fib
        call r7, put
        exit
fib:    add r8, r8, r2
        store r8, r1
        lt r5, r1, r4
        jmpf r5, lnode
        move r1, r2
        jmp end
lnode:  sub r1, r1, r2
        lt r5, r1, r4
        jmpf r5, lnext
        add r6, r6, r2
        load r8, r1
        sub r8, r8, r2
rnode:  sub r1, r1, r3
        lt r5, r1, r4
        jmpf r5, lnext
        add r6, r6, r2
        jmpf r8, end
        load r8, r1
        sub r8, r8, r2
        jmp rnode
lnext:  add r8, r8, r2
        store r8, r1
        jmp lnode
end:    move r1, r6
        ret r7

준비, 호출, 표시, 종료
우선 r8은 창고 지침인 것 같아서 창고의 시작을 지정합니다.

number r8, 0

r1을 n으로 고려하면 이번에 10항의 피보나치 수를 원하기 때문에 10을 지정한다.또한 r1은 응답을 대입하는 레지스터로도 사용된다.

number r1, 10

r2, r3은 $F{n-1},　F_{n-2}달러-1과 -2의 곳이기 때문에 1과 2를 지정합니다.

number r2, 1
number r3, 2

r4는 조건이 다른 조건으로 $n<3달러를 지정하고 싶어서 3을 지정합니다.

number r4, 3

r5는 진위가 있기 때문에 먼저 0(가짜)을 사용합니다.

number r5, 0

r6는 $F입니다.{n}(0\leqn,n\leq2) $개수를 계산하는 레지스터이기 때문에 0을 지정합니다.

number r6, 0

그리고fib 탭을 호출해서 계산을 시작합니다.(이 계산은 잠시 후 진행됩니다.)

call r7, fib

계산이 끝난 후 r1에 저장된 값을 출력합니다.

call r7, put

행복한 exit

exit

레지스터 정리 후

r1

$F_{n}달러 n의 곳.또한 응답을 저장하고 출력하는 레지스터도 저장합니다.

r2

$F_{n-1}$1의 곳.또한 증량을 책임진다.

r3

$F_{n-2}달러 2의 곳.그거밖에 없어요.

r4

$(3\leqn)$3의 섹션입니다.

r5

모두가 좋아하는 진짜, 가짜 레지스터를 관리한다.1은 진짜이고 0은 가짜다.

r6

계산에 풀린 레지스터를 저장합니다.

r7

문패 입구로 돌아간다.

r8
스택 지침

.초기값은 0입니다.

fib 태그
지금부터 계산을 시작하겠습니다.
우선, 첫 번째 노드의 값을 쌓아 올리기 (r1).
스택 포인터의 값을 1로 설정합니다.

add r8, r8, r2

1번 창고에 있습니다.

store r8, r1

r1이 3보다 작으면 진위 값을 1(진)으로 설정합니다.

lt r5, r1, r4

진짜와 가짜 값이 0이면 왼쪽의 하위 노드로 이동합니다.

jmpf r5, lnode

1이면 3보다 작기 때문에 r6를 1로 만들어 end로 날아간다

move r6, r2
jmp end

라벨
여기는 왼쪽 노드의 처리입니다.(사랑이 아니라 사랑)
여기는 $F입니다.{n} = F_{n-1} + F_{n-2} 달러가 말하는 $F{n-1} 달러가 있는 곳
n(r1)-1.

sub r1, r1, r2

n-1이 3보다 작으면 진위 값을 1로 설정합니다.

lt r5, r1, r4

진위가 0이면 n>=3이므로 왼쪽 하위 노드로 이동하는 사전 처리를 합니다.

jmpf r5, lnext

진위가 1이면 n<3이므로 $F{2}달러 또는 $F{1} $r6에 1을 추가합니다.

add r6, r6, r2

상위 노드로 이동합니다.

load r8, r1

스택 지침 감소

sub r8, r8, r2

이 뒤에 rnode 라벨이 있기 때문에 자동으로 오른쪽의 하위 노드로 이동합니다.
rnode
오른쪽 노드의 처리.
$F_{n-2}달러의 곳
n-2.

sub r1, r1, r3

n-2 < 3 = 1

lt r5, r1, r4

진가 값이 0(n-2>=3)인 경우 왼쪽의 하위 노드로 이동하는 예처리를 합니다.

jmpf r5, lnext

진가값이 1(n-2<3)인 경우 r6에 1을 추가한다.

add r6, r6, r2

오른쪽 노드가 터미널이고 덤프 포인터가 없을 때 트리의 검색이 완료되어end 탭으로 이동합니다.

jmpf r8, end

검색이 끝나지 않았을 때 부모 노드로 돌아갑니다.

load r8, r1
sub r8, r8, r2

이번에는 왼쪽에서 검색을 시작하고 오른쪽 노드가 터미널일 때 부모 노드의 왼쪽 하위 노드도 검색을 마쳤기 때문에 오른쪽의 하위 노드로 이동합니다.

jmp rnode

lnext
현재 노드에서 하위 노드로 이동할 때 현재 노드의 값(n = r1) 처리를 유지합니다.이곳에 와서 처리할 경우 왼쪽의 하위 노드로 이동할 것을 보증합니다.
스택 포인터를 추가하여 현재 노드 값을 스택합니다.

add r8, r8, r2
store r8, r1

왼쪽의 하위 노드로 이동합니다.

jmp lnode

end 태그
탐색이 끝날 때 이리로 오너라.계산된 해를 r1로 이동하는 처리를 호출원으로 되돌려줍니다.

move r1, r6
ret r7

끝맺다
급하게 써서 그림 같은 건 안 넣었는데 기회가 되면 넣고 싶어요.근데 이걸로 쓰면 될 것 같아서요.(부언: 과제를 제출하려면 복사를 하지 마세요. 다소 노력해야 합니다.)
그리고 과제

number r1, 10

장소

call c7, get

로 전환하기만 하면 됩니다.한번 해보세요.