Как записать Последовательность Fibonacci?
bool proc_num(std::vector<int>&v, int LB, int UB) {
bool check = false;
for( int i=LB+2 ; i<UB; i++) {
for(int j = i-1; j>LB; j--) {
if(v[j] == 0){
v[j] = v[i];
check = true;
} else if(v[j] == v[i]) {
v[j]= v[j]+v[i];
v[i] = 0;
check = true;
}
}
}
return check;
}
Можно просто добавить логическое значение, чтобы убедиться, что хотя бы одно из условий if выполнено.
2 ответа
Существует большая информация о Последовательности Fibonacci на Википедия и на вольфрам . Намного больше, чем Вы, возможно, нуждается. Так или иначе хорошо, чтобы изучить, как использовать эти ресурсы для нахождения (быстро, если возможный), в чем Вы нуждаетесь.
формула последовательности Выдумки Записи к бесконечному
В математике, это дано в рекурсивной форме:
В программировании, бесконечный не существует. Можно использовать рекурсивную форму, переводящую математическую форму непосредственно на языке, например, в Python, которым это становится:
def F(n):
if n == 0: return 0
elif n == 1: return 1
else: return F(n-1)+F(n-2)
Попытка это на Вашем любимом языке и видит, что эта форма требует много из времени, поскольку n становится больше. На самом деле это - O (2 <глоток> n ) вовремя.
Продолжаются на сайтах, которые я связал с Вами и буду видеть это (на вольфрам ):
Этого довольно легко реализовать и очень, очень быстро вычислить, в Python:
from math import sqrt
def F(n):
return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))
другой способ сделать это следует определению (от Википедия ):
первое количество последовательности 0, второе число равняется 1, и каждое последующее количество равно сумме предыдущих двух чисел самой последовательности, приводя к последовательности 0, 1, 1, 2, 3, 5, 8, и т.д.
, Если Ваш язык поддерживает итераторы, можно сделать что-то как:
def F():
a,b = 0,1
while True:
yield a
a, b = b, a + b
Дисплей startNumber к endNumber только от последовательности Выдумки.
, После того как Вы знаете, как генерировать Числа Фибоначчи, просто необходимо циклически повторить канавку числа и проверка, если они проверяют данные условия.
предположим теперь Вы записали f (n), который возвращает энный термин Последовательности Fibonacci (как та с sqrt (5))
На большинстве языков, как которые можно сделать что-то:
def SubFib(startNumber, endNumber):
n = 0
cur = f(n)
while cur <= endNumber:
if startNumber <= cur:
print cur
n += 1
cur = f(n)
В Python я использовал бы форму итератора и пошел бы для:
def SubFib(startNumber, endNumber):
for cur in F():
if cur > endNumber: return
if cur >= startNumber:
yield cur
for i in SubFib(10, 200):
print i
Моя подсказка к [1 111], учатся читать , в чем Вы нуждаетесь. Euler проекта (Google для него) обучит Вас делать так :P Удача и развлекайтесь!
Идею позади последовательности Fibonacci показывают в следующем коде Python:
def fib(n):
if n == 1:
return 1
elif n == 0:
return 0
else:
return fib(n-1) + fib(n-2)
Это означает, что выдумка является функцией, которая может сделать одну из трех вещей. Это определяет выдумку (1) == 1, выдумка (0) == 0 и выдумка (n), чтобы быть:
выдумка (n-1) + выдумка (n-2)
, Где n является произвольным целым числом. Это означает, что выдумывают (2), например, расширяется до следующей арифметики:
fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1
Мы можем вычислить выдумку (3) тот же путь с арифметикой, показанной ниже:
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0
важная вещь понять вот состоит в том, которые выдумывают (3), не может быть вычислен, не вычисляя выдумку (2), который вычисляется путем знания определений выдумки (1) и выдумки (0). Наличие самого вызова функции как функция fibonacci делает назван рекурсией, и это - важная тема в программировании.
Это походит на присвоение домашней работы, таким образом, я не собираюсь делать запустить/закончить часть для Вас. Python является замечательно выразительным языком для этого, хотя, таким образом, это должно иметь смысл, если Вы понимаете математику, и будет, надо надеяться, учить Вас рекурсии.Удачи!
Редактирование: Одна потенциальная критика моего кода состоит в том, что он не использует суперудобный урожай функции Python, который делает выдумку (n) функцией намного короче. Мой пример универсален, хотя, с тех пор не много языков вне Python на самом деле имеет урожай.