Как найти порядковый номер числа фибоначчи - Исправление недочетов и поиск решений вместе с Examum.ru

Загрузить PDF

Последовательность Фибоначчи – это ряд чисел, в котором каждое последующее число равно сумме двух предыдущих чисел. Числовые последовательности часто встречаются в природе и искусстве в виде спиралей и «золотого сечения». Самый простой способ вычислить последовательность Фибоначчи – это создать таблицу, но такой метод не применим к большим последовательностям. Например, если нужно определить 100-й член последовательности, лучше воспользоваться формулой Бине.

1
Нарисуйте таблицу с двумя столбцами. Количество строк таблицы зависит от количества чисел последовательности Фибоначчи, которые нужно найти.
- Например, если нужно найти пятое число последовательности, нарисуйте таблицу с пятью строками.
- Используя таблицу, нельзя найти некоторое случайное число без вычисления всех предыдущих чисел. Например, если нужно найти 100-е число последовательности, нужно вычислить все числа: от первого до 99-ого. Поэтому таблица применима только для нахождения первых чисел последовательности.
2
В левом столбце напишите порядковые номера членов последовательности. То есть напишите цифры по порядку, начиная с единицы.
- Такие цифры определяют порядковые номера членов (чисел) последовательности Фибоначчи.
- Например, если нужно найти пятое число последовательности, в левой колонке напишите следующие цифры: 1, 2, 3, 4, 5. То есть нужно найти с первого по пятое число последовательности.
3
В первой строке правой колонки напишите 1. Это первое число (член) последовательности Фибоначчи.
- Имейте в виду, что последовательность Фибоначчи всегда начинается с 1. Если последовательность начинается с другого числа, вы неправильно вычислили все числа вплоть до первого.
4
К первому члену (1) прибавьте 0. Получится второе число последовательности.
- Запомните: чтобы найти любое число последовательности Фибоначчи, просто сложите два предыдущих числа.
- Чтобы создать последовательность, не забудьте о 0, который стоит перед 1 (первым членом), поэтому 1 + 0 = 1.
5
Сложите первый (1) и второй (1) члены. Получится третье число последовательности.
- 1 + 1 = 2. Третий член равен 2.
6
Сложите второй (1) и третий (2) члены, чтобы получить четвертое число последовательности.
- 1 + 2 = 3. Четвертый член равен 3.
7
Сложите третий (2) и четвертый (3) члены. Получится пятое число последовательности.
- 2 + 3 = 5. Пятый член равен 5.
8

Сложите два предыдущих числа, чтобы найти любое число последовательности Фибоначчи. Этот метод основан на формуле: $F_{{n}}=F_{{n-1}}+F_{{n-2}}$ .^[1] Эта формула не является замкнутой, поэтому при помощи этой формулы нельзя найти любой член последовательности без вычисления всех предыдущих чисел.

Реклама

1
2

В формулу подставьте порядковый номер числа (вместо ). – это порядковый номер любого искомого члена последовательности.
3

В формулу подставьте золотое сечение. Золотое сечение приблизительно равно 1,618034; подставьте в формулу это число.^[5]
4

Вычислите выражение в скобках. Не забывайте про правильный порядок выполнения математических операций, в котором выражение в скобках вычисляется в первую очередь:.
5

Возведите числа в степени. Возведите в соответствующие степени два числа, которые находятся в числителе.
6

Вычтите два числа. Перед тем как приступить к делению, вычтите числа, которые находятся в числителе.
7
Полученный результат разделите на квадратный корень из 5. Квадратный корень из 5 приблизительно равен 2,236067.
- В нашем примере: ${frac {11,180339}{2,236067}}=5,000002$ .
8
Полученный результат округлите до ближайшего целого числа. Последний результат будет десятичной дробью, которая близка к целому числу. Такое целое число представляет собой число последовательности Фибоначчи.
- Если в вычислениях использовать неокругленные числа, вы получите целое число. Работать с округленными числами намного легче, но в этом случае вы получите десятичную дробь.^[6]
- В нашем примере вы получили десятичную дробь 5,000002. Округлите ее до ближайшего целого числа и получите пятое число последовательности Фибоначчи, которое равно 5.
Реклама

Об этой статье

Эту страницу просматривали 27 790 раз.

Была ли эта статья полезной?

Источник

Номер числа Фибоначчи?

Coursera не принимает решение.

Условие задачи:
Дано натуральное число A. Определите, каким по счету числом Фибоначчи оно является,то есть выведите такое число n, чтоF[n]=A
Если А не является числом Фибоначчи,выведите число -1
-1
Примеры:
Тест 1
Входные данные: 8
Вывод программы: 6

Тест 2
Входные данные: 10
Вывод программы: -1

Тест 3
Входные данные: 13
Вывод программы: 7

Не могу найти ошибку

n = int(input())
f = 0
res = 1
f0 = 1
i = 0
while i < n:
    res = f
    f = f0 + f
    f0 = res
    i += 1
    if n == f:
        print(i)
        break
if n < 0 or n != f:
    print(-1)
elif n == 0:
    print(0)

Вопрос задан

более трёх лет назад
8622 просмотра

Здесь
while i < n:
Должно быть
while f <= n:

А после цикла проверяйте только n==0, а второй проверки не нужно, во всех остальных случаях возвращайте -1.

Пригласить эксперта

но мне больше нравится этот варант

def get_fib_ind(n):
    ind = 0
    a, b = 0, 1
    while b <= n:
        ind += 1
        a, b = b, a+b
        if a == n:
            return ind
    return -1
    
print(
    get_fib_ind(
        int(input())
    )
)

n это число на проверку т. е. по условию А которое вводится пользователем, а вы в цикле сравниваете его с порядковым номером i.
n нужно сравнивать с числами фиэбоначчи

Если номер числа A=1 принимать за n=2 (хотя единица — это и первое и второе число в последовательности Фибоначчи), то:

a = int(input())
fib_1 = 0
fib_2 = 1
fib_summ = 1
n = 0
res = -1
while fib_1 <= a:
    fib_summ = fib_1 + fib_2
    fib_1 = fib_2
    fib_2 = fib_summ
    n += 1
    if fib_1 == a:
        res = n
    elif a == 0:
        res = 0
print(res)

Показать ещё
Загружается…

26 мая 2023, в 18:34

1000 руб./за проект

26 мая 2023, в 18:17

4000 руб./за проект

26 мая 2023, в 18:11

1000 руб./в час

Минуточку внимания

Источник

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

Position / Ordinal	Fibonacci number
1	1
2	1
3	2
4	3
5	5
6	8
7	13
8	21
9	34
10	55
11	89
12	144
13	233
14	377
15	610
16	987
17	1,597
18	2,584
19	4,181
20	6,765
21	10,946
22	17,711
23	28,657
24	46,368
25	75,025
26	121,393
27	196,418
28	317,811
29	514,229
30	832,040
31	1,346,269
32	2,178,309
33	3,524,578
34	5,702,887
35	9,227,465
36	14,930,352
37	24,157,817
38	39,088,169
39	63,245,986
40	102,334,155
41	165,580,141
42	267,914,296
43	433,494,437
44	701,408,733
45	1,134,903,170
46	1,836,311,903
47	2,971,215,073
48	4,807,526,976
49	7,778,742,049
50	12,586,269,025
51	20,365,011,074
52	32,951,280,099
53	53,316,291,173
54	86,267,571,272
55	139,583,862,445
56	225,851,433,717
57	365,435,296,162
58	591,286,729,879
59	956,722,026,041
60	1,548,008,755,920
61	2,504,730,781,961
62	4,052,739,537,881
63	6,557,470,319,842
64	10,610,209,857,723
65	17,167,680,177,565
66	27,777,890,035,288
67	44,945,570,212,853
68	72,723,460,248,141
69	117,669,030,460,994
70	190,392,490,709,135
71	308,061,521,170,129
72	498,454,011,879,264
73	806,515,533,049,393
74	1,304,969,544,928,657
75	2,111,485,077,978,050
76	3,416,454,622,906,707
77	5,527,939,700,884,757
78	8,944,394,323,791,464
79	14,472,334,024,676,220
80	23,416,728,348,467,684
81	37,889,062,373,143,900
82	61,305,790,721,611,590
83	99,194,853,094,755,490
84	160,500,643,816,367,100
85	259,695,496,911,122,600
86	420,196,140,727,489,660
87	679,891,637,638,612,200
88	1,100,087,778,366,101,900
89	1,779,979,416,004,714,200
90	2,880,067,194,370,816,000
91	4,660,046,610,375,530,000
92	7,540,113,804,746,346,000
93	12,200,160,415,121,877,000
94	19,740,274,219,868,220,000
95	31,940,434,634,990,100,000
96	51,680,708,854,858,330,000
97	83,621,143,489,848,430,000
98	135,301,852,344,706,740,000
99	218,922,995,834,555,170,000
100	354,224,848,179,261,900,000

Источник

Download Article

The Fibonacci sequence is a pattern of numbers generated by summing the previous two numbers in the sequence.^[1] The numbers in the sequence are frequently seen in nature and in art, represented by spirals and the golden ratio. The easiest way to calculate the sequence is by setting up a table; however, this is impractical if you are looking for, for example, the 100th term in the sequence, in which case Binet’s formula can be used.

1
Set up a table with two columns. The number of rows will depend on how many numbers in the Fibonacci sequence you want to calculate.^[2]
- For example, if you want to find the fifth number in the sequence, your table will have five rows.
- When using the table method, you cannot find a random number farther down in the sequence without calculating all the number before it. For example, if you want to find the 100th number in the sequence, you have to calculate the 1st through 99th numbers first. This is why the table method only works well for numbers early in the sequence.
2
Enter the sequence of terms in the left column. This means just entering a sequence of sequential ordinal numbers, beginning with «1st.»
- The term refers to the position number in the Fibonacci sequence.
- For example, if you want to figure out the fifth number in the sequence, you will write 1st, 2nd, 3rd, 4th, 5th down the left column. This will show you what the first through fifth terms in the sequence are.
Advertisement
3
Enter 1 in the first row of the right-hand column. This is the starting point for the Fibonacci Sequence. In other words, the first term in the sequence is 1.
- The correct Fibonacci sequence always starts on 1. If you begin with a different number, you are not finding the proper pattern of the Fibonacci sequence.
4
Add the first term (1) and 0. This will give you the second number in the sequence.
- Remember, to find any given number in the Fibonacci sequence, you simply add the two previous numbers in the sequence.
- To create the sequence, you should think of 0 coming before 1 (the first term), so 1 + 0 = 1.
5
Add the first term (1) and the second term (1). This will give you the third number in the sequence.^[3]
- 1 + 1 = 2. The third term is 2.
6
Add the second term (1) and the third term (2) to get the fourth number in the sequence.
- 1 + 2 = 3. The fourth term is 3.
7
Add the third term (2) and the fourth term (3). This will give you the fifth number in the sequence.^[4]
- 2 + 3 = 5. The fifth term is 5.
8

Sum the previous two numbers to find any given number in the Fibonacci Sequence. When you use this method, you are using the formula $F_{{n}}=F_{{n-1}}+F_{{n-2}}$ .^[5] Since this is not a closed formula, however, you cannot use it to calculate any given term in the sequence without calculating all the previous numbers.^[6]

1
2

Plug the number for into the formula. The represents whatever term you are looking for in the sequence.
3

Substitute the golden ratio into the formula. You can use 1.618034 as an approximation of the golden ratio.^[10]
4

Complete the calculations in parentheses. Remember to use the order of operations by completing the calculation in parentheses first: .
5

Calculate the exponents. Multiply the two parenthetical numbers in the numerator by the appropriate exponent.
6

Complete the subtraction. Before you divide, you need to subtract the two numbers in the numerator.
7
Divide by the square root of 5. The square root of 5, rounded, is 2.236067.^[11]
- In the example problem, ${frac {11.180339}{2.236067}}=5.000002$ .
8
Round to the nearest whole number. Your answer will be a decimal, but it will be very close to a whole number. This whole number represents the number in the Fibonacci sequence.
- If you used the complete golden ratio and did no rounding, you would get a whole number. It’s more practical to round, however, which will result in a decimal.^[12]
- In the example, after using a calculator to complete all the calculations, your answer will be approximately 5.000002. Rounding to the nearest whole number, your answer, representing the fifth number in the Fibonacci sequence, is 5.

Add New Question

Question

Is «Fibonacci» an English word?

Danoyachtcapt

Top Answerer

No, it is the name of mathematician Leonardo of Pisa.
Question

How do I deduce Binet’s fibonacci number formula?

Orangejews

Community Answer

One way is to interpret the recursion as a matrix multiplication. Take a vector of two consecutive terms like (13, 8), multiply by a transition matrix M = (1,1; 1,0) to get the next such vector (21,13). That gives a formula involving M^n, but if you diagonalize M, computing M^n is easy and that formula pops right out.
Question

Who discovered this sequence?

Leonardo Bonacci

See more answers

Ask a Question

200 characters left

Include your email address to get a message when this question is answered.

Submit

Video

Thanks for submitting a tip for review!

References

About This Article

Article SummaryX

To calculate the Fibonacci sequence up to the 5th term, start by setting up a table with 2 columns and writing in 1st, 2nd, 3rd, 4th, and 5th in the left column. Next, enter 1 in the first row of the right-hand column, then add 1 and 0 to get 1. Write 1 in the column next to “2nd,” then add the 1st and 2nd term to get 2, which is the 3rd number in the sequence. Continue this pattern of adding the 2 previous numbers in the sequence to get 3 for the 4th term and 5 for the 5th term. To learn more, including how to calculate the Fibonacci sequence using Binet’s formula and the golden ratio, scroll down.

Did this summary help you?

Thanks to all authors for creating a page that has been read 246,510 times.

Did this article help you?

Источник

Сама задача: http://www.codeabbey.com/index/task_view/fibonacci-sequence—ru,
мой код:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<long double> fib{0, 1};
    for(int i = 1; i < 1000; i++) // По условию все числа из первой тысячи
                                  // значений последовательности
    {
        fib.push_back(fib[i] + fib[i-1]);
    }

    int N; // Первая строчка должна содержать количество проводимых тестов
    cin >> N;

 long double value[N];
for(int i = 0; i < N; i++)
{
    cin >> value[i];
}

    int begin, end;
    for (int i = 0; i < N; i++)
    {
        if(value[i] > fib[fib.size() / 2]) // Если value находится во второй половине последовательности
        {
            begin = fib.size() / 2;
            while(value[i] > fib[begin]) 
            {
                begin /= 2;
            }
            begin *= 2; // Возвращаюсь на шаг назад
                        // ибо после выполнения цикла
                        // value выходит из диапозона
            end = fib.size();
            for( ; begin < end; begin++)
            {
                if(fib[begin] == value[i]) {cout << begin << " "; break;}
            }
        }

        else
        {
            end = fib.size() / 2;
            while (value[i] < fib[end])
            {
                end /= 2;
            }
            end *= 2; // То же самое что и в первой ветви
            begin = 0;
            for ( ; begin < end; begin++)
            {
                if(fib[begin] == value[i]) {cout << begin << " "; break;}
            }
        }
    }

    return 0;
}

Можно было бы не делать такую дичь и просто написать

for(int i = 0; i < N; i++)
    for(int j = 0; j < fib.size(); j++)
        if(value[i] == fib[j]) cout << j + 1 << " ";


Но во время чтения одной умной книжки мне стало интересно воссоздать упрощенную версию алгоритма binary_search() и в общем вот :)
На сайте с задачей также любезно предлагают ввод данных чтобы проверить прогу, мне дали такой:
Ради небольшого теста я попробовал ввести только несколько из них, а конкретнее - самый первый, второй и четвертый.

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

vector<long double> fib{0, 1}; 
    long double value;
         cin >> value;

    int i = 1;
    int number_of_element = 1;
    while (value > fib.back()) {
        fib.push_back(fib[i] + fib[i-1]);
        i++;
        number_of_element++;
    }
    cout << fixed << "Element: " << fib[i-1] << " It's number: " << --number_of_element;

чтобы узнать, в чем я не прав и заодно проверить, мб просто числа попадаются больше первой тысячи. Вводил то же самое по очереди: первое, второе и третье числа из Test data.
Во всех трех результатах полученное прогой число было практически идентично введенному, приблизительно до 19 знака (я много раз сбивался со счета по этому это не точно), номер элемента тоже не превышал тысячи. Исходя из этого я сделал вывод, что у машины просто произошла ошибка после определенного количества знаков. Можно ли как-то исправить эту проблему?

Источник