Quelle est la somme des termes pairs de Fibonacci (<4 millions)? [Confusion de types de données de grande valeur]
https://stackoverflow.com/questions/1644446
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
En commençant par 1 et 2, les 10 premiers termes de la série de Fibonacci seront:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Trouvez la somme de tous les termes pairs de la suite ne dépassant pas 4 millions.
Maintenant, j'ai eu l'idée de comment faire cela. Mais je suis confus au sujet des types de données pour contenir de telles données volumineuses. Je reçois des résultats étranges avec int . : (
PLUS: Son projet 2e question Euler. Mais je ne peux pas l'obtenir. Je reçois des valeurs folles comme réponse. Quelqu'un peut-il s'il vous plaît publier le programme idéal?
EDIT: Voici ce que j'ai écrit pour simplement imprimer Fibonacci à l'écran. Bare Basic. Ma variable devient folle même quand je donne 100 pour la limite. Est-ce que mon code est faux?
// 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;
}
RESOLU: En fait, j'ai réussi à obtenir la solution moi-même. Voici mon programme. Cela fonctionne.
#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;
}
La solution 9
Les gars, j'ai eu la réponse. J'ai confirmé le résultat et int peut le gérer. Voici mon programme:
#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;
}
Merci pour toutes les réponses et l'aide. "Penser sur mes pieds" à la rescousse:)
Autres conseils
Étant donné que vous ne voulez que quatre millions, il est probable que int ne soit pas votre problème.
Il est tout à fait possible que votre programme soit bogué et que le stockage des données fonctionne correctement. Vous devez donc tester votre programme sur des valeurs plus petites. Par exemple, il est clair que la somme des trois premiers termes pairs est 44 (indice: chaque troisième terme est pair), donc si vous exécutez votre programme avec un maximum de 50, vous devriez immédiatement obtenir 44 en retour. Continuez à exécuter de petits cas de test pour gagner la confiance des plus grands.
Pour des raisons de sécurité, utilisez le type de données 'long'; la norme C impose de contenir au moins 4 milliards de dollars, mais sur la plupart des machines, «int» en tiendra également 4 milliards.
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);
Essayez de changer ceci:
while (i<limit-2)
à ceci:
while (y<limit)
Comme indiqué précédemment, votre programme fonctionne jusqu’à atteindre le 4 millionième nombre de Fibonacci (c’est-à-dire lorsque je parviens à 4 millions, bien que le dépassement de capacité se produise évidemment en premier). La boucle devrait vérifier si y (le plus grand nombre de Fibonacci) devient supérieur à 4 millions.
Je ne suis pas un programmeur, mais voici une adaptation au code de Leffler sans critère IF. Cela devrait fonctionner pour MAX_VALUES au-dessus de 2 (étant donné qu'il n'y a pas d'erreur dans la syntaxe de programmation), basé sur un motif que j'ai trouvé dans la série paire-fibonacci: 0,2,8,34,144,610,2584 ... si intéressant: f_n2 = 4 * f_n1 + f_n0. Cela signifie également que ce programme n'a besoin que d'un tiers des calculs, puisqu'il ne prend même pas en compte / ne calcule pas les nombres impairs de Fibonacci.
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 est assez grand pour des valeurs de plusieurs millions sur presque tous les systèmes modernes, mais vous pouvez utiliser long si cela vous inquiète. Si cela vous donne toujours des résultats étranges, le problème vient de votre algorithme.
Utilisez BigInt .
Encore une fois, unsigned int stocke des valeurs allant jusqu'à 4 milliards de dollars, vous ne devriez donc pas avoir de problèmes, même avec "la somme de tous les nombres de Fibonacci jusqu'à 4 millions". (qui, évidemment, doit être inférieur à 8 mil)?
Un problème que vous constatez probablement est la mauvaise mise en forme de vos instructions printf (). Avec un printf ("% d% d") suivi d'un printf ("% d"), les nombres de 3, 5, 8, 13, 21, 34, 55 seront imprimés comme suit: 3 5 813 21 3455 ce qui ressemble certainement à une sortie funky avec des nombres extrêmement inappropriés. Vous avez besoin de quelques espaces ou sauts de ligne supplémentaires: printf ("% d% d \ n"), printf ("% d \ n").
Je ne vois pas non plus où vous recherchez réellement les termes pairs pour contribuer à la somme.
Votre programme imprime F_1 + .. + F_limit et non F_1 + ... F_n avec F_n < limiter comme vous l'avez décrit.
Consultez l'article Wikipedia sur les numéros de Fibonacci et Sloane A000045 : le nombre de Fibonacci augmente de façon exponentielle. Vérification de cette tableau F_48 = 4807526976 qui dépasse int. F_100 est 354224848179261915075 qui déborde sûrement même int64_t (votre pile ne le fait pas, cependant).
Une solution amusante consiste à utiliser la forme fermée pour les séquences de Fibonacci et la forme fermée pour les progressions géométriques. La solution finale ressemble à ceci:
sum = ( (1-pow(phi_cb, N+1)) / (1-phi_cb) - (1-pow(onephi_cb,N+1)) / (1-onephi_cb)) / sqrt(5);
où
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;
avec toutes les mises en garde concernant les conversions de type double à type int bien sûr.
Chaque nouveau terme de la séquence de Fibonacci est généré en ajoutant les deux termes précédents. En commençant par 1 et 2, les 10 premiers termes seront:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
En considérant les termes de la suite de Fibonacci dont les valeurs ne dépassent pas quatre millions, trouvez la somme des termes de valeur paire.
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);
}
Voici mon programme:
#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;
}
Parce que si vous regardez la série fibonacci (aux premiers chiffres pairs) 2 8 34 144 610 2584 ... , vous verrez qu'il correspond au motif next_number = current_number * 4 + previous_number .
C’est l’une des solutions. Le résultat est donc 4613732
Vous pouvez essayer le code ci-dessous.
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);
}
Vous pouvez utiliser le code ci-dessus.
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)
Nous pouvons faire mieux que cela en temps O (log n). De plus, un 2 & # 215; La matrice 2 et un vecteur bidimensionnel peuvent être à nouveau multipliés en un temps O (1). Par conséquent, il suffit de calculer M n . L'algorithme récursif suivant calcule M n
- Si n = 0, retourne I 2
- Si n = 1, retournez M.
- Si n = 2m.
- Calculez récursivement N = M m et définissez P = N 2 .
- Si n = 2m + 1, définissez P = PM.
- Retour P. Nous avons T (n) = T (n / 2) + O (1), et par le théorème du maître T (n) = O (log n)
Vous pouvez également utiliser la récurrence pour la séquence Même Fibonacci est: EFn = 4EFn-1 + EFn-2 avec des valeurs de semences EF0 = 0 et EF1 = 2.
UNE SOLUTION SIMPLE SERAIT: -
#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;
}
