Связь чисел Фибоначчи и числа "сочетаний" - 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

Решение задачи: «Связь чисел Фибоначчи и числа "сочетаний"»

Листинг программы

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

Объяснение кода листинга программы

Код представляет собой реализацию вычисления чисел Фибоначчи и их связи с числами сочетаний. Вот список действий, которые происходят в коде:

Задаются константы:
- n = 5 - количество чисел в ряду (общее количество чисел Фибоначчи, которые будут выведены).
- m = n - 1 - количество запятых между числами в ряду (количество чисел сочетаний, которые будут выведены).
В цикле перебираются запятые между числами, от n-1 запятых до 0:
- Если запятых нет, то просто выводится ряд чисел.
- Если есть запятая, то генерируются все сочетания из m по k (количество чисел сочетаний, которые будут выведены).
В подцикле генерируются все числа сочетаний от m до k:
- Выводятся числа сочетаний.
- Если a(k) = m, то p = p - 1 (поскольку последнее число сочетаний уже было выведено).
- Если p не равно 0, то в цикле перебираются числа от k до p, при этом a(i) присваивается a(p) + i - p + 1 (поскольку числа Фибоначчи определяются как a(i) = a(i-1) + a(i-2)).
После завершения цикла выводится общее количество чисел сочетаний, которое равно 2 в степени m.