Обобщающая последовательность Фибоначчи с помощью SICStus Prolog

Я пытаюсь найти решение для запроса по обобщенной последовательности Фибоначчи (GFS). Вопрос: есть ли GFS, у которых 885 в качестве 12-го числа? Начальные 2 числа могут быть ограничены от 1 до 10.

Я уже нашел решение найти N-е число в последовательности, начинающейся с (1, 1), в которой я явно определяю начальные числа. Вот что у меня есть для этого:

fib(1, 1).
fib(2, 1).

fib(N, X) :-
    N #> 1,
    Nmin1 #= N - 1,
    Nmin2 #= N - 2,
    fib(Nmin1, Xmin1),
    fib(Nmin2, Xmin2),
    X #= Xmin1 + Xmin2.

Для упомянутого запроса я подумал, что следующее поможет, в котором я повторно использую метод fib без явного определения начальных чисел, поскольку теперь это нужно делать динамически:

fib(N, X) :-
    N #> 1,
    Nmin1 #= N - 1,
    Nmin2 #= N - 2,
    fib(Nmin1, Xmin1),
    fib(Nmin2, Xmin2),
    X #= Xmin1 + Xmin2.

fib2 :-
    X1 in 1..10,
    X2 in 1..10,
    fib(1, X1),
    fib(2, X2),
    fib(12, 885).

... но это не похоже на работу.

Разве невозможно таким образом определить начальные числа, или я делаю что-то ужасно неправильно? Я не прошу решения, но любой совет, который мог бы помочь мне решить это, был бы очень признателен.

Источник

6 ответов

Под SWI-Прологом:

:- use_module(library(clpfd)).

fib(A,B,N,X):-
    N #> 0,
    N0 #= N-1,
    C #= A+B,
    fib(B,C,N0,X).
fib(A,B,0,A).

task(A,B):-
    A in 1..10,
    B in 1..10,
    fib(A,B,11,885).
Источник

Определите предикат gfs(X0, X1, N, F), где X0 и X1 - значения для базовых случаев 0 и 1.

Источник

Может быть, не решение в строгом смысле, но я поделюсь им, тем не менее. Вероятно, единственный выигрыш - показать, что для этого не нужен ни компьютер, ни калькулятор. Если вы знаете трюк, это можно сделать на медвежонке.

Если F_n - это n-й Термин обычной Фибо-последовательности, начиная с F_1 = F_2 = 1, то n-й Термин обобщенной последовательности будет G_n = F_ {n-2} * a + F_ {n- 1} * б. Определить F _ {- 1} = 1, F_0 = 0

(Действительно, по индукции

  • G_1 = F _ {- 1} * a + F_0 * b = 1 * a + 0 * b = a
  • G_2 = F_0 * a + F_1 * b = 0 * a + 1 * b = b
  • G_ {n + 1} = F_ {n-1}a + F_n b = (F_ {n-3} + F_ {n-2}) a + (F_ {n-2} + F_ {n-1}) * b = G_n + G_ {n-1}

)

Таким образом, G_12 = F_10 * a + F_11 * b = 55a + 89b.

Теперь вы можете либо искать решения уравнения 55a + 89b = 885 с вашим компьютером

ИЛИ ЖЕ

делай математику:

Остатки мод 11 ( пояснения):

55a + 89b = 0 + 88b + b = b; 885 = 880 + 5 = 80 * 11 + 5 = 5

Таким образом, b = 5 mod 11, но, поскольку 1 <= b <= 10, b действительно равно 5. 89 * 5 = 445 и 885-445 = 440. Теперь разделим на 55 и получим a=8.

Источник

Я бы сказал, что вы делаете что-то ужасно неправильно... Когда вы звоните fib(1, X1)переменная X1 - это число, которое выполняет функция fib вернет, в этом случае это будет 1, из-за базового случая fib(1, 1).,

Источник

Без базовых случаев, fib/2 не имеет решения; независимо от того, как вы называете это в fib2. Примечание: если вы используете рекурсию, вам нужен как минимум один базовый вариант.

Источник

Рассматривать fib(N,F1,F2) так что вы сможете заменить fib(Nmin1, Xmin1) а также fib(Nmin2, Xmin2) с простым fib(Nmin2, Xmin2, Xmin1),

Источник
Другие вопросы по тегам