int fibo(int n){
unsigned int y=0,x=1,sum=0;
for (int i=0; i<n; i++){
sum +=x;
x = y+x;
y = x-y;
}
return sum;
}
int main(int argc, char* argv[])
{
cout << fibo(2);
cin >> "";
return 0;
}
ПОМОГИТЕ С ЗАДАЧКОЙ!
У нас в школе проходит тур олимпиады по информатике. Так вот, задали нам зачачи заочно, так что делаю их дома. Вообще-то, мы в школе изучаем Паскаль, но сначала хочу написать данную прогу на Си, но не могу. Может быть вы мне поможите?
Вот текст задачки:
В 1202 году Леонардо Фибоначчи, рассматривая задачу о размножении кроликов (каждая пара даёт приплод пару в месяц. Кролики не мрут), получил такую последовательность чисел: 1, 1, 2, 3, 5, 8, 13, 21... Написать прогу, которая вычисляет число Фибоначчи с номером n!
Я заметил только, что в этой последовательность каждое число является суммой двух предыдущих, но вот как это использовать, я не знаю, ХЕЛП ПЛИЗ!
Вот текст задачки:
В 1202 году Леонардо Фибоначчи, рассматривая задачу о размножении кроликов (каждая пара даёт приплод пару в месяц. Кролики не мрут), получил такую последовательность чисел: 1, 1, 2, 3, 5, 8, 13, 21... Написать прогу, которая вычисляет число Фибоначчи с номером n!
Я заметил только, что в этой последовательность каждое число является суммой двух предыдущих, но вот как это использовать, я не знаю, ХЕЛП ПЛИЗ!
Фибоначи был великим математиком.
Ты правильно заметил последовательность, знаем о такой.
Но формулы вычисленяи n-члена нету. Нужно складывать все элементы поэтапно перед этим сложив.
Вечером, если раньше никто не возьмется я тебе сдлаю эту прогу.
Ты правильно заметил последовательность, знаем о такой.
Но формулы вычисленяи n-члена нету. Нужно складывать все элементы поэтапно перед этим сложив.
Вечером, если раньше никто не возьмется я тебе сдлаю эту прогу.
СПАСИБО, буду ждать!
Цитата:
Originally posted by DeFaCe
СПАСИБО, буду ждать!
СПАСИБО, буду ждать!
Держи.
Код:
Цитата:
Originally posted by 3D Bob
Держи.
Держи.
Есть небольшой баг. x и y меняются неправильно.
x1 = 1;
x2 = 1;
x3 = x1 + x2;
...
Код:
int fibo(int n)
{
if(n<1)return 0;
int sum = 1;
for(int i=3, x1=1, x2=1; i<=n; i++, x1=x2, x2=sum)
sum += x1;
return sum;
}
{
if(n<1)return 0;
int sum = 1;
for(int i=3, x1=1, x2=1; i<=n; i++, x1=x2, x2=sum)
sum += x1;
return sum;
}
Цитата:
Originally posted by Mоngооsе
Есть небольшой баг. x и y меняются неправильно.
x1 = 1;
x2 = 1;
x3 = x1 + x2;
...
Есть небольшой баг. x и y меняются неправильно.
x1 = 1;
x2 = 1;
x3 = x1 + x2;
...
Код:
int fibo(int n)
{
if(n<1)return 0;
int sum = 1;
for(int i=3, x1=1, x2=1; i<=n; i++, x1=x2, x2=sum)
sum += x1;
return sum;
}
{
if(n<1)return 0;
int sum = 1;
for(int i=3, x1=1, x2=1; i<=n; i++, x1=x2, x2=sum)
sum += x1;
return sum;
}
Я проверял. Он выводил нужную последовательность чисел.
А у тебя как раз таки неправильно.
Я написал
cout << fibo(5);
И он показал не поверите))) 5=)))
Цитата:
Originally posted by 3D Bob
Я проверял. Он выводил нужную последовательность чисел.
А у тебя как раз таки неправильно.
Я написал
cout << fibo(5);
И он показал не поверите))) 5=)))
Я проверял. Он выводил нужную последовательность чисел.
А у тебя как раз таки неправильно.
Я написал
cout << fibo(5);
И он показал не поверите))) 5=)))
Поверю, потому что я тоже на 5 проверял.
fib(1) = 1;
fib(2) = 1;
fib(3) = fib(1) + fib(2) = 1 + 1 = 2;
fib(4) = fib(2) + fib(3) = 1 + 2 = 3;
[color=red]fib(5)[/color] = fib(3) + fib(4) = 2 + 3 = [color=red]5[/color];
Твоя прога выдает последовательность
1, 2, 4, 7, 12, 20...
Чтоб она работала правильно нужно изменить на
Код:
int fibo(int n)
{
[color=red]if(n<3)return 1;[/color]
unsigned int y=0,x=1,sum=[color=red]1[/color];
for (int i=0; i<n[color=red]-2[/color]; i++)
{
sum +=x;
x = y+x;
y = x-y;
}
return sum;
}
{
[color=red]if(n<3)return 1;[/color]
unsigned int y=0,x=1,sum=[color=red]1[/color];
for (int i=0; i<n[color=red]-2[/color]; i++)
{
sum +=x;
x = y+x;
y = x-y;
}
return sum;
}
Цитата:
Originally posted by 3D Bob
Фибоначи был великим математиком.
Ты правильно заметил последовательность, знаем о такой.
Но формулы вычисленяи n-члена нету. Нужно складывать все элементы поэтапно перед этим сложив.
Вечером, если раньше никто не возьмется я тебе сдлаю эту прогу.
Фибоначи был великим математиком.
Ты правильно заметил последовательность, знаем о такой.
Но формулы вычисленяи n-члена нету. Нужно складывать все элементы поэтапно перед этим сложив.
Вечером, если раньше никто не возьмется я тебе сдлаю эту прогу.
Прямо так и нету? А если поискать. Есть вполне конкретная формула, как получить n-ное число Фибоначчи. Я ее точно не помню - но там сумма двух дробей, в знаменателях которых стоит корень из 5...
Так что никаких циклов не надо. :)
Цитата:
Originally posted by S_T
Прямо так и нету? А если поискать. Есть вполне конкретная формула, как получить n-ное число Фибоначчи. Я ее точно не помню - но там сумма двух дробей, в знаменателях которых стоит корень из 5...
Так что никаких циклов не надо. :)
Прямо так и нету? А если поискать. Есть вполне конкретная формула, как получить n-ное число Фибоначчи. Я ее точно не помню - но там сумма двух дробей, в знаменателях которых стоит корень из 5...
Так что никаких циклов не надо. :)
За пол минуты нашел:
http://math.ournet.md/krujok/fibonaccir/fibonaccir.html
Там формула под номером (7) дает выражение для n-ого члена последовательности чисел Фибоначчи.
Цитата:
Originally posted by S_T
За пол минуты нашел:
http://math.ournet.md/krujok/fibonaccir/fibonaccir.html
Там формула под номером (7) дает выражение для n-ого члена последовательности чисел Фибоначчи.
За пол минуты нашел:
http://math.ournet.md/krujok/fibonaccir/fibonaccir.html
Там формула под номером (7) дает выражение для n-ого члена последовательности чисел Фибоначчи.
Формула формулой...
Но самый простой вариант решения должен знать любой начинающий программист, а именно:
Код:
int fib(int n)
{
if(n < 3) return 1;
return (fib(n - 1) + fib(n - 2));
}
{
if(n < 3) return 1;
return (fib(n - 1) + fib(n - 2));
}
Сорри, я просто непарвильно понел суть задачи.
Я почему-то подумал что нужно вывести сумму предыдущих членов.
Тогда это делается еще проше. В моей проге, вместо sum нужно возвратить x;
Вот так.
Я почему-то подумал что нужно вывести сумму предыдущих членов.
Тогда это делается еще проше. В моей проге, вместо sum нужно возвратить x;
Вот так.
Код:
int fibo(int n){
unsigned int y=0,x=1;
for (int i=0; i<n-1; i++){
x = y+x;
y = x-y;
}
return x;
}
unsigned int y=0,x=1;
for (int i=0; i<n-1; i++){
x = y+x;
y = x-y;
}
return x;
}
Цитата:
Originally posted by RelB
Формула формулой...
Но самый простой вариант решения должен знать любой начинающий программист, а именно:
Формула формулой...
Но самый простой вариант решения должен знать любой начинающий программист, а именно:
Код:
int fib(int n)
{
if(n < 3) return 1;
return (fib(n - 1) + fib(n - 2));
}
{
if(n < 3) return 1;
return (fib(n - 1) + fib(n - 2));
}
Твой способ очень невыгоден, с точки зрения реализации и запуска его на компьютере.
Каждый раз программе приходится вызывать ф-цию, а это дополнительные затраты на ресурсы.
Цитата:
Originally posted by 3D Bob
Твой способ очень невыгоден, с точки зрения реализации и запуска его на компьютере.
Каждый раз программе приходится вызывать ф-цию, а это дополнительные затраты на ресурсы.
Твой способ очень невыгоден, с точки зрения реализации и запуска его на компьютере.
Каждый раз программе приходится вызывать ф-цию, а это дополнительные затраты на ресурсы.
Я не говорил, что это выгодное с точки зрения ресурсов решение.
Просто числа фибоначчи являются классической задачей из такого раздела программирования как "рекурсия".