Что такое сумма четных членов Фибоначчи (<4 миллионов)?[Путаница с типами данных больших значений]
https://stackoverflow.com/questions/1644446
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Если начать с 1 и 2, первые 10 членов ряда Фибоначчи будут такими:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Найдите сумму всех четных членов последовательности, число которых не превышает 4 миллионов.
Теперь у меня появилась идея, как это сделать.Но меня смущают типы данных для хранения таких больших данных.Я получаю странные результаты с int. :(
БОЛЕЕ:Это второй вопрос проекта Эйлера.Но я не могу этого понять.В ответ я получаю сумасшедшие значения.Может кто-нибудь выложить идеальную программу?
РЕДАКТИРОВАТЬ:Вот что я написал, чтобы просто вывести Фибоначчи на экран.Голый базовый.Моя переменная сходит с ума, даже когда я даю 100 за предел.Мой код неправильный?
// Simple Program to print Fibonacci series in Console
#include <stdio.h>
int main() {
int x=1,y=2,sum=0,limit=0,i=0,temp=0;
printf("Enter Limit:");
scanf("%d",&limit);
if(limit==1)
printf("%d",x);
else if(limit>1) {
printf("%d %d",x,y);
if (limit>2) {
while (i<limit-2) {
temp=y;
sum=x+y;
x=temp;
y=sum;
printf(" %d",sum);
i++;
}
}
}
printf("\n");
return 0;
}
РЕШЕНО:На самом деле, мне удалось найти решение самостоятельно.Вот моя программа.Оно работает.
#include <stdio.h>
int main() {
int x=1,y=2,sum,limit; //Here value of first 2 terms have been initialized as 1 and 2
int evensum=2; //Since in calculation, we omit 2 which is an even number
printf("Enter Limit: "); //Enter limit as 4000000 (4million) to get desired result
scanf("%d",&limit);
while( (x+y)<limit ) {
sum=x+y;
x=y;
y=sum;
if (sum%2==0)
evensum+=sum;
}
printf("%d \n",evensum);
return 0;
}
Решение 9
Ребята, я получил ответ. Я подтвердил результат, и int может с этим справиться. Вот моя программа:
#include <stdio.h>
int main() {
int x=1,y=2,sum,limit; //Here value of first 2 terms have been initialized as 1 and 2
int evensum=2; //Since in calculation, we omit 2 which is an even number
printf("Enter Limit: "); //Enter limit as 4000000 (4million) to get desired result
scanf("%d",&limit);
while( (x+y)<limit ) {
sum=x+y;
x=y;
y=sum;
if (sum%2==0)
evensum+=sum;
}
printf("%d \n",evensum);
return 0;
}
Спасибо за все ответы и помощь. "Думаю на ногах" на помощь:)
Другие советы
Поскольку вам нужно всего четыре миллиона, скорее всего, int не является вашей проблемой.
Вполне возможно, что ваша программа содержит ошибки и что хранилище данных просто отлично, поэтому вы должны протестировать вашу программу на меньших значениях. Например, ясно, что сумма первых трех четных слагаемых равна 44 (подсказка: каждое третье слагаемое четное), поэтому, если вы запустите свою программу с пределом 50, то вы должны немедленно вернуть 44 обратно. Продолжайте выполнять небольшие тестовые наборы, чтобы получить уверенность в более крупных.
В целях безопасности используйте тип данных long; стандарт C требует, чтобы он содержал не менее 4 миллиардов, но на большинстве машин int также будет содержать 4 миллиарда.
enum { MAX_VALUE = 4000000 };
int sum = 0;
int f_n0 = 0;
int f_n1 = 1;
int f_n2;
while ((f_n2 = f_n0 + f_n1) < MAX_VALUE)
{
if (f_n2 % 2 == 0)
sum += f_n2;
f_n0 = f_n1;
f_n1 = f_n2;
}
printf("%d\n", sum);
Попробуйте изменить это:
while (i<limit-2)
на это:
while (y<limit)
Как написано, ваша программа работает на цикле, пока не достигнет 4-миллионного числа Фибоначчи (то есть, когда я получу 4 миллиона, хотя переполнение, очевидно, происходит в первую очередь). Цикл должен проверить, чтобы увидеть, когда у (большее число Фибоначчи) становится больше, чем 4 миллиона.
Я не программист, но вот адаптация к коду Леффлера без IF-критерия. Он должен работать для MAX_VALUES выше 2 (учитывая, что в синтаксисе программирования нет ошибок), основываясь на паттерне, который я обнаружил в четных рядах Фибоначчи: 0,2,8,34,144,610,2584 ... так интересно: f_n2 = 4 * f_n1 + f_n0. Это также означает, что этой программе требуется только 1/3 вычислений, поскольку она даже не учитывает / не рассчитывает нечетные числа Фибоначчи.
enum { MAX_VALUE = 4000000 };
int sum = 2;
int f_n0 = 0;
int f_n1 = 2;
int f_n2 = 8;
while (f_n2 < MAX_VALUE)
{
sum += f_n2;
f_n0 = f_n1;
f_n1 = f_n2;
f_n2 = 4*f_n1 + f_n0;
}
printf("%d\n", sum);
int достаточно велик для значений в миллионах почти в каждой современной системе, но вы можете использовать long , если вас это беспокоит. Если это все же дает странные результаты, значит, проблема в вашем алгоритме.
Ваша программа печатает F_1 + .. + F_limit, а не F_1 + ... F_n с F_n < ограничить, как вы описали.
Ознакомьтесь со статьей в Википедии по числам Фибоначчи и Sloane A000045 : числа Фибоначчи растут в геометрической прогрессии. Проверка этой таблицы F_48 = 4807526976 который превышает int. F_100 - 354224848179261915075, который наверняка переполняет даже int64_t (хотя ваш стек этого не делает).
Забавное решение — использовать закрытую форму для последовательностей Фибоначчи и закрытую форму для геометрических прогрессий.Конечное решение выглядит так:
sum = ( (1-pow(phi_cb, N+1)) / (1-phi_cb) - (1-pow(onephi_cb,N+1)) / (1-onephi_cb)) / sqrt(5);
где
double phi = 0.5 + 0.5 * sqrt(5);
double phi_cb = pow(phi, 3.0);
double onephi_cb = pow(1.0 - phi, 3.0);
unsigned N = floor( log(4000000.0 * sqrt(5) + 0.5) / log(phi) );
N = N / 3;
конечно, со всеми оговорками относительно преобразований типа double в int.
Каждый новый термин в последовательности Фибоначчи генерируется путем добавления двух предыдущих терминов. Начиная с 1 и 2, первые 10 терминов будут:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Рассматривая термины в последовательности Фибоначчи, значения которых не превышают четырех миллионов, найдите сумму четных членов.
int main()
{
long first = 1, second = 2, next, c;
int sum=0;
for ( c = 1 ; c <100000000; c++ )
{
next = first + second;
if(next>=4000000)
{
next= next-second;
break;
}
first = second;
second = next;
if(next%2==0){
sum=sum+next;
}
}
printf("the sum of even valued term is %d\n",sum+2);
}
Вот моя программа:
#include <iostream>
long int even_sum_fibonacci(int n){
int i = 8;
int previous_i = 2;
int next_i = 0;
long int sum = previous_i + i;;
while(n>next_i){
next_i = i*4 + previous_i;
previous_i = i;
i = next_i;
sum = sum + i;
}
return sum - next_i; //now next_i and i are both the bigger number which
//exceeds 4 million, but we counted next_i into sum
//so we'll need to substract it from sum
}
int main()
{
std::cout << even_sum_fibonacci(4000000) << std::endl;
return 0;
}
Потому что, если вы посмотрите на ряд Фибоначчи (первые несколько четных чисел) 2 8 34 144 610 2584 ... вы увидите, что он соответствует шаблону, который next_number = current_number * 4 + previous_number .
Это одно из решений. Таким образом, результат 4613732
Вы можете попробовать приведенный ниже код.
public static void SumOfEvenFibonacciNumbers()
{
int range = 4000000;
long sum = 0;
long current = 1;
long prev = 0;
long evenValueSum= 0;
while (evenValueSum< range)
{
sum = prev + current;
prev = current;
current = sum;
if (sum % 2 == 0 )
{
evenValueSum = evenValueSum+ sum;
}
}
Console.WriteLine(evenValueSum);
}
Вы можете использовать приведенный выше код.
import numpy as np
M = [[0,1],[1,1]]
F = [[0],[1]]
s = 0
while(F[1][0] < 4000000):
F = np.matmul(M, F)
if not F[0][0]%2:
s+=F[0][0]
print(s)
Мы можем добиться большего успеха за это время (log n). Кроме того, 2 & # 215; Матрицу 2 и двумерный вектор можно снова умножить за O (1) раз. Поэтому достаточно вычислить M n . Следующий рекурсивный алгоритм вычисляет M n
<Ол>Вы также можете использовать повторение для последовательности Эвена Фибоначчи: EFn = 4EFn-1 + EFn-2 с начальными значениями EF0 = 0 и EF1 = 2.
ПРОСТОЕ РЕШЕНИЕ БЫЛО: -
#include <iostream>
using namespace std;
int main(int argc, char** argv) {
int n1=1;
int n2=2;
int num=0,sum;
for (int i=1;i,n1<4000000;i++)
{
cout<<" "<<n1;
num=n1+n2;
if(!(n1%2))
{
sum+=n1;
}
n1=n2;
n2=num;
}
cout<<"\n Sum of even term is = "<<sum;
return 0;
}
