Introduction

الدرس 10 من 20 في دورة ألغاز رياضية على Coddy.

إن القاسم المشترك الأكبر (GCD) لعددين صحيحين موجبين x و y هو أكبر قاسم مشترك بين x و y.

على سبيل المثال،

GCD(6, 15) = 3
GCD(7, 13) = 1
GCD(18, 30) = 6

يمكن أيضاً تعريف القاسم المشترك الأكبر لثلاثة أعداد صحيحة موجبة أو أكثر بأنه أكبر قاسم مشترك بينهم جميعاً. ويقال عن عددين صحيحين موجبين أو أكثر أنهم أوليان فيما بينهما إذا كان القاسم المشترك الأكبر لهما هو 1. [Weisstein, Eric W. "Greatest Common Divisor." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

خوارزمية إقليدس لإيجاد القاسم المشترك الأكبر (GCD)

تعتمد الطريقة التي قدمها إقليدس لحساب القواسم المشتركة الكبرى على حقيقة أنه، بالنظر إلى عددين صحيحين موجبين x و y بحيث يكون y > x، فإن القواسم المشتركة لـ x و y هي نفسها القواسم المشتركة لـ y - x و x.

لذا، تعتمد طريقة إقليدس لحساب القاسم المشترك الأكبر لعددين صحيحين موجبين على استبدال العدد الأكبر بالفرق بين العددين، وتكرار ذلك حتى يتساوى العددان: وهذا هو القاسم المشترك الأكبر لهما.

مثال: GCD(6, 15) = GCD(6, 15 - 6) = GCD(6, 9) = GCD(6, 9 - 6) = GCD(6, 3) = GCD(6 - 3, 3) = GCD(3, 3) = 3

التحدي

سهل

اكتب كود python، باسم gcd، يستقبل متجهًا من عددين صحيحين، v، ويجد القاسم المشترك الأكبر (GCD) لهذين الرقمين المعطيين.

يرجى ملاحظة أن v[0] <= v[1].

جرّب بنفسك

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"

int main() {
    int v[4096];
    int vn = 0;
    char line[65536];
    if (!fgets(line, sizeof(line), stdin)) line[0] = '\0';
    char* tok = strtok(line, " \t\r\n");
    while (tok) { v[vn++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
    int r = gcd(v, vn);
    printf("%d\n", r);
    return 0;
}