Программа C для вычисления наибольшего общего делителя дает неверный ответ

Я написал следующую программу, которая берет два числа из командной строки и возвращает gcd этих чисел.

#include <stdio.h>

int to_int(char *input)
{
        return *input - '0';
}

int main(int argc, char *argv[])
{
        if (argc < 2) return 1;
        int a = to_int(argv[1]);
        int b = to_int(argv[2]);
        int i;
        int result;
        for (i = 1; i <= a && i <= b; i++) {
                if (a%i==0 && b%i==0) {
                        result = i;
                }
        }
        printf("%d\n", result);
        return 0;
}

Однако, когда я даю ему числа 4 и 16, он возвращает ответ 1. Это неверно. НОД 4 и 16 равен 4. Однако я не могу найти, что не так с моим кодом. Другие примеры, которые я нашел в Интернете, похоже, используют тот же алгоритм, что и я (проверьте, делятся ли оба числа на i без остатка, и если да, то НОД равен i).

Может ли кто-нибудь указать мне на ошибку в моем коде?


c modulus greatest-common-divisor
person TPens    schedule 19.12.2020    source источник
comment
Ответ на самом деле правильный, потому что НОД 4 и 1 равен 1. Обратите внимание, что вы используете только первый символ 16, поэтому 16 становится 1.   -  person Xaver    schedule 19.12.2020
comment
if (argc < 2) return 1; должно быть if (argc < 3) return 1; `argv[0] всегда является именем программы   -  person ryyker    schedule 19.12.2020
comment
Прочитайте документацию вашего компилятора C (например, GCC) и отладчика (например, GDB...)   -  person Basile Starynkevitch    schedule 19.12.2020

Ответы (2)


arrow_upward
3
arrow_downward

Ваша функция to_int делает не то, что вы думаете.

Выражение *input - '0' берет код первого символа в input и вычитает код символа '0'. Таким образом, результатом является число, соответствующее первому символу заданной строки, а не всей строке.

Вам нужно выполнить эту операцию в цикле, умножая результат на 10 перед добавлением значения следующей цифры.

person dbush    schedule 19.12.2020
comment
На самом деле, используйте atoi - person Basile Starynkevitch; 19.12.2020
comment
@BasileStarynkevitch, вам, вероятно, следует использовать вместо этого sscanf или strtol: string-to-an-integer" title="в чем разница между sscanf или atoi для преобразования строки в целое число"> stackoverflow.com/questions/3420629/ - person Dock; 20.12.2020

arrow_upward
2
arrow_downward

Некоторые дополнительные предложения: (читать встроенные комментарии)

    // if (argc < 2) return 1;//need argc to be 3
    // (argv[0] always contains program name)
    if (argc < 3) return 1;//test for num arguments
    if(!(is_num(argv[1]) && is_num(argv[2]))) return 1;//test for number
    int a = atoi(argv[1]);//when available use library functions
    int b = atoi(argv[2]);
    int max = a>b?a:b;// determine larger of two inputs
    int i;
    int result= 0;
    //for (i = 1; i <= a && i <= b; i++) {//this is backwards,count from largest 
    for (i = max; i >= 1 ; i--) {//start at max, then decrement i
        if (a%i==0 && b%i==0) {
            result = i;
            break;//break out of loop when solution found
        }
    }
    printf("%d\n", result);
    return 0;

Если требуется функция поддержки, создайте ее, чтобы убедиться, что ввод является числом:

bool is_num(char *input)
{
    if(!input) return false;
    int len = strlen(input);
    if(!((input[0] == '-') || (input[0] == '+') || (isdigit(input[0])))) return false;
    for(int i = 1;i<len;i++)
    {
        if(!isdigit(input[i])) return false;
    }
    return true;
}
person ryyker    schedule 19.12.2020