主页 / 问题 / 661194
Accepted
TorSen
Asked:2020-05-03 02:51:38 +0000 UTC2020-05-03 02:51:38 +0000 UTC

长代码执行还是无限循环？

  • 772

有 2 个列表存储数字的数字。那么，您需要找到这些数字的 GCD。如果我们采用数字 9239923923999 - 99992399 - 一切似乎都很好，它起作用了。如果 99999999999999 和 9，那么我只是等待 .. 如果我在某个地方有一个无限循环，或者代码本身是弯曲的，因此需要很长时间来计算，我怎么能理解？如果是第二个选项，如何加速？？GCD算法取值如下：

{
   while (a != b) {
        if (a > b) {
            long tmp = a;
            a = b;
            b = tmp;
        }
        b = b - a;
    }
    return a; 
    }

因为减去存储在列表中的两个数字比模除法更容易。减法本身：

{

    Item * tempfirst = A->Head;
    Item * tempsecond = B->Head;
    while (tempfirst && tempsecond)
    {
        if (tempfirst->digit < tempsecond->digit)
        {
            Item * CurrentItem = tempfirst;
            CurrentItem->digit += 10;
            CurrentItem = CurrentItem->next;
            while (CurrentItem->digit <= 0) 
            {
                CurrentItem->digit += 9;
                CurrentItem = CurrentItem->next;
            }
            CurrentItem->digit -= 1;
        }
        tempfirst->digit -= tempsecond->digit;
        tempfirst = tempfirst->next;
        tempsecond = tempsecond->next;
    }
        tempfirst = A->Tail;
        while (tempfirst) 
        {
            if (tempfirst->digit != 0)
                break;
            A->Tail = tempfirst->prev;
            A->Tail->next = NULL;
            free(tempfirst); 
            tempfirst = A->Tail; 
            A->size--;
        }
        return A;
    }

}

对于其余部分，我似乎可以确定..但是我觉得在减法中某处有错误或其他原因。

c

2 个回答

  1. Best Answer

    好吧，你给......所以你可以在胡萝卜阴谋之前计算GCD ......

    很明显，你需要计算余数！毕竟，想一想 - 即使您只是通过普通算术从 99999999999999 中减去 9，即使需要 1 纳秒，也需要 10 ^ 13 纳秒，或 10,000 秒 - 3 小时。而您，使用复杂的程序？！

    • 4

  2. 欧几里德的求最大公约数 (gcd) 的算法，写成有余数的除法：

    U gcd(U a, U b)
{
  while (b) {
    U t = b;
    b = a % b;
    a = t;
  }
  return a;
}

    哪里U：typedef unsigned long U;

    如果没有有效的实现a % b，那么可以尝试一种使用x >> 1（右移）和x & 1（偶数/奇数）按位运算的算法：

    U gcd(U a, U b)
{
  if (a == b)
    return a;
  if (a == 0)
    return b;
  if (b == 0)
    return a;
  // a != b and > 0
  if (a & 1) { // a is odd
    if (b & 1) {// b is odd
      // both odd, diff is even, reduce larger arg
      return (a > b) ? gcd((a - b) >> 1, b) : gcd((b - a) >> 1, a);
    } else { // a is odd, b is even
      return gcd(a, b >> 1);
    }
  } else if (b & 1) { // a is even, b is odd
    return gcd(a >> 1, b);
  }
  // a is even, b is even
  return gcd(a >> 1, b >> 1) << 1; // non tail-recursive
}

    使用示例：

    #include <stdio.h>

int main(void)
{
  printf("%lu\n", gcd(99999999999999, 9));
  return 0;
}

    运行示例：

    $ cc *.c && time ./a.out
9
./a.out  0.00s user 0.00s system 0% cpu 0.001 total

    可以看到代码是瞬间执行的。

    • 0

相关问题