-2

我正在解决一项任务 - 用户正在输入 3 个数字，a, b, c. 目标是找出是否可以c求和a和b。在每个步骤中都允许添加atob和bto 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;
}
4

3 回答 3

0

我下面的代码可以很好地处理低数字

它没有。尝试输入2 2 3。最明显的错误是：

在函数'main'中：
 警告：格式“%I64d”需要类型“int *”，但参数 2 的类型为“long long int *”
 警告：格式“%I64d”需要类型“int *”，但参数 3 的类型为“long long int *”
 警告：格式“%I64d”需要类型“int *”，但参数 4 的类型为“long long int *”

要更正它，请替换%I64d为%Ld。

但我认为我正在输掉与更大数字的战斗......

当然，您的递归解决方案会使堆栈溢出；对于需要较少堆栈空间的程序，请参阅此答案。

于 2017-02-15T14:08:05.293 回答
-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;
}
于 2014-12-18T22:24:11.223 回答
-1

我认为它可以用线性代数来解决。假设你有 a = 3、b = 4 和 c = 15。所以你要找的是

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

所以如果你把它除以 3 它应该没有余数。我认为这是线性代数，因为 15-4y 应该是 0 模 3。

这只是一个想法。

于 2014-12-18T22:24:55.940 回答