재귀를 사용하는 C 프로그램은 최적화되고 고정 될 필요가있다.

Question

나는 사용자가 3 개의 숫자 인 a, b, c을 입력하는 작업을 해결하고 있었다. 목표는 ca 및 b의 합계를 얻을 수 있는지 확인하는 것입니다. 각 단계에서 a을 b에 추가하고 b을 a에 추가 할 수 있습니다. 입력 한 숫자로 가능한지 알아야합니다. 입력 한 숫자는 0과 10^18 사이입니다. 아래는 재귀를 사용하여 작성한 코드입니다. a=4 b=6 c=38에 대한 작업을 해결

예 :

1. a=4 b=10
2. a=14 b=10
3. a=14 b=24
4. a=38 b=24 print YES
이

내 아래 코드는하지만 낮은 숫자 아니라 그 일을 내가 생각하는 나는 더 큰 것을 가진 전투를 잃고있다. 숫자 ... 나는 어떤 부분이 무엇을하고 있는지에 대한 몇 가지 코멘트를 덧붙였다.

도움이 필요한 것은 더 잘 작동하고 더 빨리 작동해야하며 더 최적화하는 방법을 알지 못합니다.

//the function that I'm using 
int task(long long int a, long long int b, long long int c, long long int d, int p) 
{ //a, b and c are long long integers that are submited by the user, d is the sum of 
    //the unchanged a and b, and p is a flag 
    if(!a && !b && c) return 0; //0+0 will never get to 1 
    if(c==d) return 1; //if I get with c to d, it is confirmed yes, 
         //did the math with a pen :) 
    if(c<d || c<=0) // I thought this is a nice case to stop 
    { 
     return 0; 
    } 
    if(p==1) 
    { 
     if(a>c) return 0; //if the flag p is one, that means i changed a, 
          //so compare a 
    } 
    if(p==2) 
    { 
     if(b>c) return 0; //if p is two, i changed b so compare b 
    } 
    if(c-d>0) return task(a+b, b, c-b, d, 1)||task(a, b+a, c-a, d, 2); 
      //recursion call with OR operator so every step is checked 

}//one part is a=a+b b=b c=c-b, i decrement c so fewer steps are needed, 
//the other part is when i add a to b 

int main() 
{ 
    long long int a,b,c; 
    scanf("%I64d%I64d%I64d",&a,&b,&c); //scaning 
    int p; //the flag for the first numbers 
    if(a>b) p=1; //i dont know if i need this step at all xD 
    else p=2; //but to make sure 
    if((a==1 || b==1) && c) printf("YES"); //a=1 b=1 and c>=1 means i can get to c, 
              //even with a+b+b+b.. 
    else if(a==c || b==c) printf("YES"); //if one of the numbers are already same 
             //with c, no need to check 
    else if(task(a,b,c,a+b,p)) printf("YES"); //if the function returns 1, print YES 
    else printf("NO"); //or print NO 


    return 0; 
} 

Answer 1

아마이 문제를 올바르게 이해하지 못하고 있지만 여기에는 두 가지 다른 반복 접근법이 있습니다. 아마도 이것은 당신을 따라 도울 수 있습니다 :

#include <stdio.h> 

int old_task(long a, long b, long c) 
{ 
    size_t iteration; 
    long left = a, right = b; 
    for(iteration = 0; (left < c) && (right < c); ++iteration) 
    { 
     printf("NOT %ld: %ld, %ld < %ld\n", iteration, left, right, c); 
     if(iteration % 2) 
     left += right; 
     else 
     right += left; 
    } 
    printf("STOP %ld: %ld, %ld < %ld\n", iteration, left, right, c); 
    return ((left == c) || (right == c)) ? 1 : 0; 
} 

int task(long a, long b, long c) 
{ 
    long f; 
    /*long i = 0;*/ 
    for(f = a; f < c; f+= a) 
    { 
     /*printf("Checking: %li * %li + %li * %li == %li\n", a, ++i, b, (c - f)/b, c);*/ 
     if((c - f) % b == 0) 
      return 1; 
    } 
    return 0; 
} 

int main() 
{ 
    long a,b,c; 
    scanf("%ld %ld %ld",&a,&b,&c); //scaning 

    printf("%s\n\n", task(a, b, c) ? "YES" : "NO"); 
    return 0; 
} 

Answer 2

선형 대수학으로 풀 수 있다고 생각합니다. 의 당신이있어 말을하자 = 3, B = 4, C = 15 그래서 당신이 찾고있는 무엇을

3x + 4y = 15 
x = (15-4y)/3 

그래서

당신이 3으로 분할하는 경우가 더 나머지 부분이 없어야합니다. 15-4y는 모듈로 3이어야하므로 선형 대수학이 온다고 생각합니다.

그냥 생각입니다.

Answer 3

내 아래 코드는 그렇지 않은 낮은 숫자

잘 그것의 일을한다. 입력 2 2 3을 입력하십시오. 가장 명백한 오류는 다음과 같습니다

 
In function 'main': 
warning: format '%I64d' expects type 'int *', but argument 2 has type 'long long int *' 
warning: format '%I64d' expects type 'int *', but argument 3 has type 'long long int *' 
warning: format '%I64d' expects type 'int *', but argument 4 has type 'long long int *' 

이 그것을 수정 %Ld와 %I64d를 교체하려면.

하지만 난 더 큰 숫자와 전투를 잃어버린 것 같아 ...

물론

스택 오버 플로우를 만들 수있는 재귀 솔루션; 스택 공간이 덜 필요한 프로그램에 대해서는 this answer을 참조하십시오.