Was ist die Summe von Even Terms In Fibonacci (<4 Millionen)? [Large Wert Datentyp Verwirrung]
https://stackoverflow.com/questions/1644446
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Mit dem Start mit 1 und 2, wobei die ersten 10 hinsichtlich der Fibonacci-Folge wird sein:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Hier finden Sie die Summe aller geradzahlige Terme in der Sequenz, die nicht übersteigen 4.000.000.
Nun habe ich die Idee, wie dies zu tun. Aber ich bin verwirrt über die Datentypen, wie große Datenmengen zu halten. Ich erhalte seltsame Ergebnisse mit int. : (
MEHR: Sein Projekt Euler zweite Frage. Aber ich kann es nicht bekommen. Ich verrückt Werte als Antwort. Kann jemand bitte das ideale Programm schreiben?
EDIT: Hier ist, was ich für nur Druck Fibonacci Bildschirm geschrieben. Bare Basic. Meine Variable geht noch verrückt, wenn ich 100 für die Grenze geben. Ist mein Code falsch?
// 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;
}
GELÖST: Eigentlich habe ich es geschafft, die Lösung selbst zu bekommen. Hier ist mein Programm. Es funktioniert.
#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;
}
Lösung 9
Jungs, bekam ich die Antwort. Ich bestätigte das Ergebnis und int kann damit umgehen. Hier ist mein Programm:
#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;
}
Thx für alle Antworten und Hilfe. „Denken an meinen Füßen“ zur Rettung:)
Andere Tipps
Da Sie nur auf vier Millionen wollen sich, es ist wahrscheinlich, dass int nicht Ihr Problem.
Es ist durchaus möglich, dass Ihr Programm Buggy ist und dass die Datenspeicherung nur in Ordnung ist, so sollten Sie Ihr Programm auf kleinere Werte testen. Zum Beispiel, es ist klar, dass die Summe der ersten drei geraden Terme ist 44 (Hinweis: Jeder dritte Term ist auch) so, wenn Sie Ihr Programm mit einer Obergrenze von 50 läuft, dann sollten Sie sofort 44 zurück. Halten Sie kleine Testfälle laufen Vertrauen in den größeren zu erhalten.
Zur Sicherheit verwenden, um den ‚long‘ Datentyp; der C-Standard verlangt, dass mindestens 4 Milliarden zu halten, aber auf den meisten Maschinen, ‚int‘ wird auch 4000000000 halten.
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);
Ändern folgt aus:
while (i<limit-2)
folgt aus:
while (y<limit)
Wie schon geschrieben, Ihr Programm ist das Radfahren, bis es zum 4000000. Fibonacci-Zahl wird (das heißt, wenn ich auf 4 Millionen bekommt, obwohl Überlauf offensichtlich zuerst eintritt). Die Schleife sollte überprüfen, wenn y (die größere Fibonacci-Zahl) größer als 4 Millionen.
Ich bin kein Programmierer, aber hier ist eine Anpassung an Leffler Code ohne das IF-Kriterium. Es sollte über 2 für MAX_VALUES arbeiten (da gibt es keine Fehler in der Programmierung Syntax), basierend auf einem Muster, das ich in der auch nur für Fibonacci-Reihe gefunden: 0,2,8,34,144,610,2584 ... so interessant: f_n2 = 4 * f_n1 + f_n0. Das bedeutet auch, dieses Programm nur 1/3 der Berechnungen benötigt, da es nicht einmal betrachten / berechnet die ungeraden Fibonacci-Zahlen.
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 ist groß genug für Werte in die Millionen auf nahezu jedem modernen System, aber Sie können long verwenden, wenn Sie darüber besorgt sind. Wenn das immer noch Sie seltsame Ergebnisse gibt, dann ist das Problem mit dem Algorithmus ist.
Mit BigInt .
Dann wieder Werte unsigned int speichert bis zu über 4 Milliarden, so dass Sie keine Probleme, auch mit „Summe aller Fibonacci-Zahlen bis zu 4 Millionen“, die sein sollten (was offensichtlich sein, hat weniger als 8 mil) ?
Ein Fehler, den Sie wahrscheinlich sehen, ist die schlechte Formatierung des printf () Aussagen. Mit einem printf ( "% d% d"), gefolgt von einem printf ( "% d"), Zahlen von 3, 5, 8, 13, 21, 34, 55 wird gedruckt, wie: 3 5 813 21 3455 das sieht so aus, flippig Ausgang mit wild unangemessenen Zahlen. Sie benötigen noch ein paar Leerzeichen oder Zeilenumbrüche: printf ( "% d% d \ n"), printf ( "% d \ n")
.Ich sehe auch nicht, wo du eigentlich bist Überprüfung nur für die gleichen Bedingungen zur Summe beitragen.
Ihr Programm druckt F_1 + .. + F_limit und nicht F_1 + ... F_n mit F_n Überprüfen Sie den Wikipedia-Artikel über Fibonacci-Zahlen und Sloane A000045 : Fibonacci-Zahlen wächst exponentiell. Überprüfen Sie dieses Tabelle F_48 = 4807526976 die überschreitet Int. F_100 ist 354224848179261915075 die sicherlich überläuft sogar int64_t (Ihr Stapel nicht, obwohl).
Eine amüsante Lösung ist, die geschlossene Form für die Fibonacci-Sequenzen und die geschlossenen Form für die geometrischen Progressionen zu verwenden. Die End-Lösung sieht wie folgt aus:
sum = ( (1-pow(phi_cb, N+1)) / (1-phi_cb) - (1-pow(onephi_cb,N+1)) / (1-onephi_cb)) / sqrt(5);
Dabei steht
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;
mit allen Einschränkungen in Bezug auf Doppel in int-Typkonvertierungen natürlich.
Jeder neue Begriff in der Fibonacci-Folge wird durch Addition der beiden vorherigen Bedingungen erzeugt. Mit dem Start mit 1 und 2, wobei die ersten 10 Begriffe werden:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
die Bedingungen der Fibonacci-Folge, deren Werte Durch die Berücksichtigung der nicht vier Millionen überschreiten, findet die Summe der geradzahlige Bedingungen.
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);
}
Hier ist mein Programm:
#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;
}
Denn wenn man an der Fibonacci-Reihe sehen (auf den ersten geraden Zahlen) 2 8 34 144 610 2584 ... Sie werden sehen, dass es das Muster übereinstimmt, next_number = aktuelle_zahl * 4 + previous_number .
Dies ist eine der Lösungen. Das Ergebnis ist also 4613732
Sie können den Code unten versuchen.
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);
}
Sie können den obigen Code verwenden.
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)
Wir können es besser machen als dies in O (log n) Zeit. Darüber hinaus können eine 2 × 2-Matrix und ein zweidimensionaler Vektor multipliziert werden wieder in O (1) Zeit. Daher genügt es, M n zu berechnen. Die folgenden rekursiven Algorithmus berechnet M n
- Wenn n = 0, das Rück I 2
- Wenn n = 1, Rückkehr M.
- Wenn n = 2 m.
- Rekursiv berechnen N = M M und eingestellt P = N 2 .
- Wenn n = 2m + 1, P = PM.
- Zurück P. Wir haben T (n) = T (n / 2) + O (1), und von Master-Satz T (n) = O (log n)
Sie können auch Wiederholung verwenden für Even Fibonacci-Folge ist: EFn = 4EFn-1 + 2-EFn mit Seed-Werten EF0 = 0 und EF1 = 2.
SIMPLE Lösung wäre: -
#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;
}
