의 합 무엇입도 약관에서의 피보나치(<4million)?[큰 값 데이터 형식이 혼란]
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. :(
더:프로젝트의 오일러 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;
}
견에 대한 모든 대답하고,도움이됩니다."생각을 내 발에"를 구조:)
다른 팁
당신은 최대 4 백만을 원하기 때문에 int 당신의 문제가 아닙니다.
프로그램이 버그가 많고 데이터 저장소가 괜찮을 가능성이 높으므로 더 작은 값으로 프로그램을 테스트해야합니다. 예를 들어, 처음 3 개 짝수 항의 합은 44 (힌트 : 세 번째 용어마다 짝수)라는 것이 분명합니다. 작은 테스트 케이스를 계속 실행하여 큰 테스트 사례를 확신하십시오.
보안의 경우 '긴'데이터 유형을 사용하십시오. 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)
서면으로, 귀하의 프로그램은 4 백만 번째 Fibonacci 번호에 도달 할 때까지 자전거를 타고 있습니다 (예 : 4 백만에 도달하면 오버플로가 먼저 발생합니다). 루프는 y (더 큰 피보나치 수)가 4 백만보다 클 때를 확인해야합니다.
나는 프로그래머가 아닙니다,하지만 여기에 적응하 Leffler 의 코드가 없는 경우-기준을 사용할 수 있습니다.그것은 작동에 대한 MAX_VALUES2(어 실수가 없에서 프로그래밍이 구문)을 기반으로 패턴을 발견에서도-는 피보나치 시리즈: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 당신이 그것에 대해 걱정한다면. 그것이 여전히 당신에게 이상한 결과를 제공한다면, 문제는 알고리즘에 관한 것입니다.
사용 큰.
다시, unsigned int 최대 40 억 명이 넘는 가치를 저장하므로 "최대 4 백만의 모든 Fibonacci 번호의 합계"에도 아무런 문제가 없어야합니다 (분명히 8 마일 미만이어야 함)?
아마도보고있는 버그 중 하나는 printf () 문의 나쁜 형식입니다. printf ( " %d %d")와 printf ( " %d"), 3, 5, 8, 13, 21, 34, 55의 숫자는 다음과 같이 인쇄됩니다. 매우 부적절한 숫자를 가진 펑키 출력. Printf ( " %d %d n"), printf ( " %d n")가 더 필요합니다.
또한 짝수 용어가 합계에 기여할 수있는 곳에서만 실제로 확인하는 곳을 보지 못합니다.
귀하의 프로그램은 f_1 + .. + f_limit을 인쇄합니다.
Wikipedia 기사를 확인하십시오 피보나치 번호 그리고 슬론 A000045: fibonacci 숫자는 기하 급수적으로 증가합니다. 이것을 확인합니다 테이블 F_48 = 4807526976 int를 초과합니다. F_100은 354224848179261915075로 INT64_T (스택은 그렇지 않습니다).
재미있는 솔루션은 Fibonacci 시퀀스에 닫힌 형태를 사용하고 기하학적 진행을 위해 닫힌 형태를 사용하는 것입니다. 최종 솔루션은 다음과 같습니다.
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;
물론 이중에서 int- 타입 변환에 관한 모든 경고가 있습니다.
Fibonacci 시퀀스의 각각의 새로운 용어는 이전 두 항을 추가하여 생성됩니다. 1과 2로 시작하면 처음 10 가지 용어는 다음과 같습니다.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
값이 4 백만을 초과하지 않는 Fibonacci 시퀀스의 용어를 고려함으로써 값 값이 부여 된 용어의 합을 찾으십시오.
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;
}
Fibonacci 시리즈를 보면 (처음 몇 짝수 숫자로)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)
우리는 O (log n) 시간에서 이것보다 더 잘할 수 있습니다. 또한, 2 × 2 매트릭스 및 2 차원 벡터를 O (1) 시간에 다시 곱할 수 있습니다. 따라서 m을 계산하는 것으로 충분합니다N. 다음과 같은 재귀 알고리즘은 m을 계산합니다N
- n = 0이면 i를 반환합니다2
- n = 1이면 M을 반환합니다.
- n = 2m 인 경우.
- 재귀 적으로 n = m을 계산합니다중, p = n을 설정합니다2.
- n = 2m+1이면 p = pm을 설정하십시오.
- 반환 P 우리는 t (n) = t (n/2) + o (1)과 마스터의 정리 t (n) = o (log n)에 의해 있습니다.
심지어 Fibonacci 시퀀스에도 재발을 사용할 수 있습니다. 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;
}
