フィボナッチの偶数項の合計（＆400万）とは何ですか？ [大きな値のデータ型の混乱]
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、...
シーケンス内の400万を超えないすべての偶数値の項の合計を見つけます。
今、私はこれを行う方法のアイデアを得ました。しかし、私はそのようなビッグデータを保持するためのデータ型について混乱しています。 int を使用すると、奇妙な結果が得られます。 ：（
詳細：そのプロジェクトオイラー2番目の質問。しかし、私はそれを得ることができません。私は答えとしてクレイジーな値を取得します。誰かが理想的なプログラムを投稿してもらえますか？
編集：以下は、フィボナッチをスクリーンに印刷するために書いたものです。素朴。制限に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;
}
すべての返信とヘルプのThx。 「自分の足で考える」救助に：）
他のヒント
最大400万個しか必要ないため、 int は問題ではない可能性があります。
プログラムにバグがあり、データストレージが適切である可能性が非常に高いため、小さい値でプログラムをテストする必要があります。たとえば、最初の3つの偶数項の合計が44（ヒント：3項ごとに偶数）であることは明らかです。したがって、キャップを50にしてプログラムを実行すると、すぐに44に戻ります。小さなテストケースを実行し続けて、大きなテストケースの信頼性を高めます。
セキュリティのために、 'long'データ型を使用します。 C標準では、少なくとも40億を保持する必要がありますが、ほとんどのマシンでは、「int」も40億を保持します。
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)
書かれているように、プログラムは400万番目のフィボナッチ数に達するまで循環しています（つまり、400万に達すると、明らかにオーバーフローが最初に発生します）。ループは、y（より大きなフィボナッチ数）が400万を超えるときを確認する必要があります。
私はプログラマーではありませんが、IF基準のないレフラーのコードへの適応です。偶数のみのフィボナッチシリーズで見つかったパターンに基づいて、2を超えるMAX_VALUESで動作するはずです（プログラミング構文に間違いがない場合）：0、2、8、34、144、610、2584 ... * 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 を使用できます。それでも奇妙な結果が得られる場合、問題はアルゴリズムにあります。
BigInt 。
次に、 unsigned int は最大40億を超える値を格納するため、「最大400万個のフィボナッチ数の合計」であっても問題はないはずです。 （明らかに、8 mil未満でなければなりません）？
おそらく目にするバグの1つは、printf（）ステートメントのフォーマットの誤りです。 printf（ ""％d％d ""）の後にprintf（ ""％d ""）が続く場合、3、5、8、13、21、34、55の数字は次のように印刷されます。 3 5 813 21 3455 これは確かに、不適切な数値を持つファンキーな出力のように見えます。 さらにスペースまたは改行が必要です：printf（＆quot;％d％d \ n＆quot;）、printf（＆quot;％d \ n＆quot;）。
また、合計に寄与する偶数項のみを実際にチェックしている場所もわかりません。
プログラムはF_1 + .. + F_limitを出力し、F_1 + ... F_nとF_n＆lt;を出力します説明したとおりに制限します。
フィボナッチ番号およびスローン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);
where
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型への変換に関するすべての警告付き。
フィボナッチ数列の各新しい用語は、前の2つの用語を追加して生成されます。 1と2から始めると、最初の10個の用語は次のようになります。
1、2、3、5、8、13、21、34、55、89、...
値が400万を超えないフィボナッチ数列の項を考慮することにより、偶数値の項の合計を見つけます。
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 。
これは解決策の1つです。結果は 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)
O（log n）時間でこれよりもうまくやることができます。さらに、2×2行列と2次元ベクトルは、O（1）時間で再び乗算できます。したがって、M n を計算すれば十分です。 次の再帰アルゴリズムは、M n
を計算します- n = 0の場合、I 2 を返します
- n = 1の場合、Mを返します。
- n = 2mの場合
- N = M m を再帰的に計算し、P = N 2 と設定します。
- n = 2m + 1の場合、P = PMに設定します。
- Pを返します。 T（n）= T（n / 2）+ O（1）があり、マスターの定理によりT（n）= O（log 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;
}
