რისი მონაცემები ან სტრუქტურები გამოიყენება ყველაზე დიდი საერთო გამყოფის (GCD) ძებნის ალგორითმში?

მეტოქის საერთო უდიდესი გამყოფის (მგგ, GCD) გამოთვლა მუშაობს მთელ რიცხვებზე. ძირითადი მონაცემებია ორი მთელი რიცხვი, რომლისთვისაც უნდა იპოვოს მაქსიმალური გამყოფი, რომელიც ორივე რიცხვს ნაწილს გარეშე ნაწილს.

სხვადასხვა დროს გამოიყენება ეუკლიდეს ალგორითმი, რომელიც თანმიმდევრულად იცვლის რიცხვების წყვილს (b, a % b), სანამ დარჩენილი არ გახდება ნული. საბოლოოდ რჩება ბოლო ნულოვანი გამყოფი — ეს არის GCD.

მაგალითი Swift-ში:

func gcd(_ a: Int, _ b: Int) -> Int {
    var a = a
    var b = b
    while b != 0 {
        let temp = b
        b = a % b
        a = temp
    }
    return a
}

შედეგი = gcd(48, 18) // შედეგი იქნება 6