如何在这个基于欧几里德算法的 gcd 程序中放置计数变量？

Question

首先这是计算GCD的欧几里得算法（懂的可以直接跳到代码）

GCD(m,n)=GCD(n,m mod n) 然后你继续执行这个函数，直到你得到这样的东西：GCD(m,n)=GCD(answer,0)。当你得到这个时，你就停下来，这就是我的程序试图做的。但是我也想找到另一件事。实际到达答案所需的递归 GCD 数 calls/divisions（出于对话目的，我们将此变量称为 COUNT）。例如

GCD(60,24) = GCD (24, 12) = GCD (12, 0) =12 所以这里的 COUNT 是 3（包括最后一个），因为我们使用了 Euclid 算法两次。

P.S 在下面的代码中，我试图打印 COUNT 以及数字组合的 GCD 值，但我似乎得到了错误的答案。

P.P.S希望我已经解释清楚了。

这是代码

#include<stdio.h>
int gcd(int m , int n);
int count=0;
int main()
{
    int m,n;
    for(m=1;m<=10;m++)
    {
        for(n=1;n<=m;n++)
        {
            printf("gcd of %d, %d is :%d",m,n,gcd(m,n));
            printf(" with %d iterations\n",count);
        }
    }
}

int gcd(int m , int n)
{
    if(n==0)
    {
        return m;
        count=0;
    }
    if(m<n)
    {
        //swapping both a and b
        m=m+n;
        n=m-n;
        m=m-n;
    }
    else
    {
        count++;
        return gcd(n, m%n); 
    }
}

Answer 1

首先，你的count = 0在return语句之后。因此，它永远不会被执行！

但是，即使你切换了count = 0和return，它仍然是不正确的，因为你基本上是在增加count之后将count设置为0。例如：

gcd(60,24) => count++ => count = 1
gcd(24, 12) => count++ => count = 2
gcd(12, 0) => count = 0 => count = 0

正确的做法是：

count = 0
gcd(60,24) => count++ => count = 1
gcd(24, 12) => count++ => count = 2
gcd(12, 0) => count++ => count = 3

此外，您的代码流程不正确。如果你调用 gcd(5, 15) 会发生什么？你交换了 5 和 15，但你根本没有 return 任何东西！修复它的方法是删除 else 语句。

这是重构后的代码：

#include<stdio.h>

int gcd(int m , int n);
int gcd_wrapper(int m, int n);

int count=0;

int main(){
    int m,n;
    for(m=1;m<=10;m++)
    {
        for(n=1;n<=m;n++)
        {
            printf("gcd of %d, %d is :%d",m,n,gcd_wrapper(m,n));
            printf(" with %d iterations\n",count);
        }
    }
    return 0;
}

int gcd_wrapper(int m, int n) {
    count = 0;
    return gcd(m, n);
}

int gcd(int m , int n){
    count++;
    if(n == 0){
        return m;
    }
    if(m < n){
        //swapping both a and b
        m=m+n;
        n=m-n;
        m=m-n;
    }
    return gcd(n, m%n); 
}

如何在这个基于欧几里德算法的 gcd 程序中放置计数变量？

How to place the count variable in this gcd program based on Euclid's algorithm?

algorithm

recursion

count

greatest-common-divisor