Простые операции по модулю

Question

Итак, я изучаю C ++, и в одной из книг, которые я читаю, есть пример для поиска GCF (наибольший общий фактор).Функция выглядит следующим образом:

int gcf(int a, int b) {
    if(b == 0) {
        return a;
    }
    else {
        return gcf(b, a%b);
    }
}

Что я не понимаю, так это то, что если я, например, введу 15 и 5, то

a = 15
b = 5
b is not 0 so then the else statement executes
(5, 15%5 = 0) so since b is now 0 it returns, a, which is 5.

Это имеет смысл, но если япоменять местами цифры, почему / как я могу получить один и тот же ответ?

a = 5
b = 15
b is not 0 so then the else statement executes
(15, 5%15) but 5%15 is .3 or 1/3, but in C++, 5%15 returns 5.

Я не понимаю, откуда берется 5, если вообще что-то, так как это целое число, я подумал, что оно может вернуть 0, но это нене вернуть 15, так что не может быть.

Answer 1

То, что вы делаете, это целочисленные вычисления - без учета числа с плавающей запятой или дробей.

5 % 15 - это фактически остаток, который вы получите после деления 5 на 15, и это, конечно, 5 (частное будет 0).

15 |  5 | 0   <-- this is the first call gcf(5, 15)
      0
     ---
      5 | 15 | 3  <-- this is the first recursive call gcf(15, 5)
          15
         ---
           0 |  5 |   <-- this is the second recursive call gcf(5, 0), returns 5

Answer 2

Оператор по модулю отличается от деления, обычно, когда мы делим, возвращаемое значение является частным, но при использовании оператора по модулю возвращаемое значение является его напоминанием. так в вашем случае, когда

**

a = 5 и b = 15, a% b, возвращаемое значение этого было 0,

**

это причина, по которой он вернулся 5. проверьте следующие ссылки для большей ясности по оператору по модулю http://www.cplusplus.com/doc/tutorial/operators/

http://www.cprogramming.com/tutorial/modulus.html

Answer 3

Если вам интересно, фрагмент кода, который вы там написали, называется алгоритмом Евклида, который основан на лемме Евклида (большой сюрприз там).Хотя я слышал от профессора, что некоторые люди могут ссылаться на различные формулировки леммы Евклида.Моя книга по высшей алгебре, в частности, относится к ней как к «равным gcd».В нем говорится:

Пусть a, b, q и c - целые числа с a = qb + c.Тогда gcd (a, b) = gcd (b, c)

gcd (a, b) относится к наибольшему общему делителю a и b.Кажется, это именно то, что вы делаете в своей программе.

Любое целое число a можно записать как qb + c для любого b.Это означает, что a является произведением qb плюс некоторый остаток c.Остаток здесь - это то, что вы вычисляете, когда используете оператор%.Если мы допустим a = 12 и b = 5, то можем написать 12 = 5q + c.Пусть q будет 2. Тогда наш остаток c равен 2. Возможно, эти вещи элементарны, но, надеюсь, это хороший фон для дополнения объяснения вашей книги.

Answer 4

В целочисленном делении 5/15 = 0. Поскольку 5%15 - это остаток, он должен быть равен 5. C и C ++ для любых a и b, a/b*b + a%b = a.