dim s(20) as long
input n
s(1)=1
s(2)=2
if n<3 then 
  print s(n)
else
  for i=3 to n 
    s(n)=s(n-1)+s(n-2)
  next i
end if
print s(n)

以上

谢谢 maxumi

有那么简单吗?
(持怀疑态度)
这是排列组合问题.

循环的变量写错.

不好意思, 确实写错了, 不是s(n)=s(n-1)+s(n-2), 是s(i)=s(i-1)+s(i-2).

这个问题确实是递推, 不要持怀疑态度.

i阶可以通过先走i-1阶, 再走1阶, 也可以通过先走i-2阶, 再走2阶, 所以s(i)=s(i-1)+s(i-2).

以上

嗯,事实证明你是正确的.

DECLARE FUNCTION next$ (a$)
DEFLNG A-Z

n = 20

FOR i = 0 TO (n / 2)
    s$ = STRING$(i, "2") + STRING$(n - i * 2, "1")
    z$ = s$
    DO
      c = c + 1
      PRINT z$
      z$ = next$(z$)
    LOOP UNTIL z$ = ""
NEXT
PRINT c

DEFSNG A-Z
FUNCTION next$ (a$)
l = LEN(a$)
FOR i = 1 TO l
    b$ = MID$(a$, i, 1) + b$
NEXT
i = INSTR(b$, "12")
IF i > 0 THEN
   MID$(a$, l - i, 2) = MID$(b$, i, 2)
   IF i > 1 THEN MID$(a$, l - i + 2) = LEFT$(b$, i - 1)
   next$ = a$
END IF
END FUNCTION

用递归做嘛！还是用Pascal比较顺手一点！

Const Max=20;

Function Steps(Max,i:integer);
Var j:integer;
Begin
  if Max<2 then i:=i+1
    else for j:=1 to 2 do Step(Max-j,i);
End; 

Var i:integer;

Begin
  i:=0;
  Step(Max,i);
  writeln(i);
End.

是个费波拉契数列，可以用费波拉契数列的同项公式求，
f(n)=(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)/sqrt(5)
sqrt是算术平方根