Recursive algorithm for walking stairs

zhaozj2021-02-16  94

topic:

A total of 20 stairs, from below to the top. You can only take a step or two steps at a time, and you can't retreat, how many methods have been taken from this staircase.

analysis:

1 steps only one way of walking (1)

2 steps of steps (11, 2)

3 steps of steps (111, 12, 21)

Five steps in steps (1111, 112, 121, 211, 22)

There are 8 steps (11111, 1112, 1121, 1211, 122, 2111, 212, 221)

6 steps in steps (111111, 11112, 11121, 11211, 1122, 2111, 1212, 1221, 2111, 2112, 2121, 2111, 222)

It can be found that each step of walking method corresponds to a step in which one step is taken less than it steps, and then adds a 2 step before a walking method than it is two steps, and constitutes a Fibonacci number.

The code is as follows: private submmand1_click () DIM S () AS String, Num as long, i as longfor i = 1 to 10upstairs i, s, numdebug.print join (s, vbcrlf) debug.print Num & "Talk" NEXTEND SUB

Sub Upstairs (ByVal Stairnum As integer, Byref Steps () as stay, Byref methodn as long "Save all possible steps in the Stairnum step with" 111222 "format in array Steps (), the number of ways is saved in Methodn in Dim i As LongIf stairnum = 1 Thenmethodn = 1ReDim steps (1 To methodn) steps (1) = 1End IfIf stairnum = 2 Thenmethodn = 2ReDim steps (1 To methodn) steps (1) = 11steps (2) = 2End IfIf stairnum> 2 Thendim A () AS String, B () AS String, Methoda As Long, Methodb As Longupstairs Stairnum - 1, A, Methoda 'recursive call

Upstairs Stairnum - 2, B, Methodb 'recursive call Redim Steps (Methoda Methodb) for i = 1 to methodasteps (i) = 1 & a (i) Nextfor i = 1 to methodbsteps (i methoda) = 2 & b I) Nextmethodn = Methoda Methodb End IF

End Sub

转载请注明原文地址:https://www.9cbs.com/read-13949.html

New Post(0)