Связь чисел Фибоначчи и числа "сочетаний" - QBasic

Формулировка задачи:

Чтобы понять о чем идет речь я приведу частный пример. дано 5 натуральных чисел 1, 2, 3, 4, 5. составим из этих чисел следующие сочетания. Порядок строго соблюдается!! 1) 1, 2, 3, 4, 5 2) 12, 3, 4, 5 3) 1, 23, 4, 5 4) 1, 2, 34, 5 5) 1, 2, 3, 45 6) 1, 23, 45 7) 12, 3, 45 8) 12, 34, 5 Нужно составить программу, которая для произвольного числа N могла бы сосчитать число приведенных выше в качестве примера сочетаний. Алгоритм к моему удивлению алгоритм оказался прост, точно такой же (рекурсия) каким вычисляются числа Фибоначчи. то есть количество сочетаний (n)= Фибоначчи(n+1) Вопрос Как обобщить программу, чтобы она вычисляла количество любых сочетаний? то есть в нашем примере должны добавиться и такие сочетания 9) 123, 45 10) 12345 11) и так далее. Сколько их?
REM
REM  1 23 4 56 78 9 ... N
REM
REM  Fibonachi AND "Sochetania"
REM
 
DECLARE FUNCTION f! (n!)
 
CLS
FOR i = 1 TO 20
   PRINT f(i)
NEXT
END
 
FUNCTION f (n)
   IF n <= 3 THEN
      f = n
   ELSE
      f = f(n - 1) + f(n - 2)
   END IF
END FUNCTION

Код к задаче: «Связь чисел Фибоначчи и числа "сочетаний" - QBasic»

textual
DIM a(1 TO 20) AS LONG, i AS LONG, j AS LONG, m AS LONG, k AS LONG, n AS LONG, p AS LONG, txt AS STRING
n = 5 'количество чисел
m = n - 1 'количество запятых
FOR k = m TO 0 STEP -1 'перебираем запятые между числами, от n-1 зяпятых до 0
    IF k = 0 THEN 'если запятых нет, то просто выводим ряд чисел
        txt = ""
        FOR i = 1 TO n
            txt = txt + LTRIM$(STR$(i))
        NEXT i
        PRINT txt
    ELSE
        FOR i = 1 TO k: a(i) = i: NEXT i
        IF k = m THEN p = 1 ELSE p = k
        DO 'генерация всех сочетаний из m по k
            'вывод чисел
            j = 0
            txt = ""
            FOR i = 1 TO k
                WHILE j < a(i)
                    j = j + 1
                    txt = txt + LTRIM$(STR$(j))
                WEND
                txt = txt + ","
            NEXT i
            FOR i = j + 1 TO n
                txt = txt + LTRIM$(STR$(i))
            NEXT i
            PRINT txt
           
            IF a(k) = m THEN p = p - 1 ELSE p = k
            IF p THEN
                FOR i = k TO p STEP -1
                    a(i) = a(p) + i - p + 1
                NEXT i
            END IF
        LOOP WHILE p
    END IF
NEXT k
PRINT "Kol-vo:"; 2 ^ m

8   голосов, оценка 3.750 из 5


СОХРАНИТЬ ССЫЛКУ