Qual è la somma dei termini pari in Fibonacci (< 4 milioni)? [Confusione di tipo di dati di grande valore]
https://stackoverflow.com/questions/1644446
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Iniziando con 1 e 2, i primi 10 termini della serie Fibonacci saranno:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Trova la somma di tutti i termini con valore pari nella sequenza che non supera i 4 milioni.
Ora, ho avuto l'idea di come farlo. Ma sono confuso sui tipi di dati per contenere tali big data. Sto ottenendo strani risultati con int . : (
ALTRO: la sua seconda domanda su Project Euler Ma non riesco a capirlo. Ottengo valori folli come risposta. Qualcuno può pubblicare il programma ideale?
EDIT: ecco cosa ho scritto solo per stampare Fibonacci sullo schermo. Bare Basic. La mia variabile impazzisce anche quando do 100 per il limite. Il mio codice è sbagliato?
// 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;
}
RISOLTO: in realtà, sono riuscito a ottenere la soluzione da solo. Ecco il mio programma Funziona.
#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;
}
Soluzione 9
Ragazzi, ho ottenuto la risposta. Ho confermato il risultato e int può gestirlo. Ecco il mio programma:
#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;
}
Grazie per tutte le risposte e l'aiuto. " Pensando in piedi " in soccorso :)
Altri suggerimenti
Dato che vuoi solo fino a quattro milioni, è probabile che int non sia un tuo problema.
È possibile che il tuo programma sia difettoso e che l'archiviazione dei dati sia corretta, quindi dovresti testare il tuo programma su valori più piccoli. Ad esempio, è chiaro che la somma dei primi tre termini pari è 44 (suggerimento: ogni terzo termine è pari), quindi se esegui il tuo programma con un limite di 50, dovresti immediatamente recuperare 44. Continua a eseguire piccoli casi di prova per avere fiducia in quelli più grandi.
Per motivi di sicurezza, utilizzare il tipo di dati "long"; lo standard C richiede che contenga almeno 4 miliardi, ma sulla maggior parte delle macchine, "int" conterrà anche 4 miliardi.
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);
Prova a cambiare questo:
while (i<limit-2)
a questo:
while (y<limit)
Come scritto, il tuo programma sta andando in bicicletta fino a raggiungere il 4 milionesimo numero di Fibonacci (cioè quando arrivo a 4 milioni, sebbene ovviamente l'overflow avvenga per primo). Il loop dovrebbe verificare quando y (il numero di Fibonacci più grande) diventa maggiore di 4 milioni.
Non sono un programmatore, ma ecco un adattamento al codice di Leffler senza il criterio IF. Dovrebbe funzionare per MAX_VALUES sopra 2 (dato che non ci sono errori nella sintassi di programmazione), basato su un modello che ho trovato nella serie fibonacci anche solo: 0,2,8,34,144,610,2584 ... così interessante: f_n2 = 4 * f_n1 + f_n0. Questo significa anche che questo programma necessita solo di 1/3 dei calcoli, dal momento che non considera nemmeno / calcola i numeri dispari di 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 è abbastanza grande per valori in milioni su quasi tutti i sistemi moderni, ma puoi usare long se sei preoccupato. Se ciò ti dà ancora risultati strani, allora il problema è con il tuo algoritmo.
Utilizza BigInt .
Quindi, unsigned int memorizza valori fino a oltre 4 miliardi, quindi non dovresti avere problemi nemmeno con la somma di tutti i numeri di fibonacci fino a 4 milioni " (che, ovviamente, deve essere inferiore a 8 mil)?
Un bug che probabilmente stai vedendo è la formattazione errata delle tue istruzioni printf (). Con un printf ("% d% d") seguito da un printf ("% d"), i numeri di 3, 5, 8, 13, 21, 34, 55 verranno stampati come: 3 5 813 21 3455 che certamente sembra un output funky con numeri selvaggiamente inappropriati. Hai bisogno di qualche spazio in più o di avanzamenti di riga: printf ("% d% d \ n "), printf ("% d \ n ").
Inoltre non vedo dove stai effettivamente controllando solo i termini pari per contribuire alla somma.
Il tuo programma stampa F_1 + .. + F_limit e non F_1 + ... F_n con F_n < limite come descritto.
Consulta l'articolo di Wikipedia su Numeri di fibonacci e Sloane A000045 : i numeri di Fibonacci crescono esponenzialmente. Verifica questa tabella F_48 = 4807526976 che supera int. F_100 è 354224848179261915075 che sicuramente trabocca anche di int64_t (il tuo stack no, comunque).
Una soluzione divertente è usare la forma chiusa per le sequenze di Fibonacci e la forma chiusa per le progressioni geometriche. La soluzione finale è simile alla seguente:
sum = ( (1-pow(phi_cb, N+1)) / (1-phi_cb) - (1-pow(onephi_cb,N+1)) / (1-onephi_cb)) / sqrt(5);
dove
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;
ovviamente con tutte le avvertenze relative alle conversioni da doppie a int.
Ogni nuovo termine nella sequenza di Fibonacci viene generato aggiungendo i due termini precedenti. Iniziando con 1 e 2, i primi 10 termini saranno:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Considerando i termini nella sequenza di Fibonacci i cui valori non superano i quattro milioni, trova la somma dei termini a valore pari.
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);
}
Ecco il mio programma:
#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;
}
Perché se guardi la serie di fibonacci (ai primi pochi numeri pari) 2 8 34 144 610 2584 ... vedrai che corrisponde allo schema che next_number = current_number * 4 + previous_number .
Questa è una delle soluzioni. Quindi il risultato è 4613732
Puoi provare il codice qui sotto.
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);
}
Puoi usare il codice sopra.
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)
Possiamo fare meglio di così in O (log n) time. Inoltre, un 2 & # 215; 2 matrici e un vettore bidimensionale possono essere nuovamente moltiplicati nel tempo O (1). Pertanto è sufficiente calcolare M n . Il seguente algoritmo ricorsivo calcola M n
- Se n = 0, restituisce I 2
- Se n = 1, restituisce M.
- Se n = 2m.
- Calcola ricorsivamente N = M m e imposta P = N 2 .
- Se n = 2m + 1, impostare P = PM.
- Restituisci P. Abbiamo T (n) = T (n / 2) + O (1) e dal teorema del maestro T (n) = O (log n)
Puoi anche usare la ricorrenza per la sequenza Even Fibonacci è: EFn = 4EFn-1 + EFn-2 con valori di seme EF0 = 0 e EF1 = 2.
LA SOLUZIONE SEMPLICE DOVREBBE: -
#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;
}
