Bu tamsayıların lineer bir birleşimi açısından iki pozitif tamsayıların en büyük ortak bölenini yazmak için Öklid bölünmesi uygular

Question

Tamsayılar açısından iki pozitif tamsayıların en büyük ortak bölenini yazabilen bir program yazmaya çalışıyorum.

353 = 23 * 15 + 8

15 = 1 * 8 + 7

8: Örneğin, ben aşağıdaki adımları kullanarak gcd bulacağını, en Rakamları 353 ve 15 olduğunu varsayalım = 1 * = 7 * 1

yüzden gcd bu kadar uygulamış 1'dir 7 + 1

7:

//div_algo always takes int1 >= int2 
int div_algo(int int1, int int2) 
{ 
    if (int2 == 0) //we are done 
     return int1; 
    int factor = 0; 
    int remainder = 0; 
    factor = int1/int2; //this is useful for linear combination 
    remainder = int1 % int2; 
    return div_algo(int2, remainder); 
} 

Sorun şu ki, eğer lineer kombinasyonu bulmak istersem, temelde geriye doğru çalışırım. Yani, benim örnekle devam:

1 = 1 * 8 - 1 * 7 (yerine 7 = 15-1 * 8)

1 = 1 * 8 - 1 * 15 + 1 * 8 = 2 * 8-1 * 15 (yerine 8 = 353 - 23 * 15)

1 = 2 * 353 - 46 * 15-1 * 15 = 2 * 353 - 15

47 ve orada gidin. Yaşadığım problem, önceki denklemleri nasıl değiştireceğimi bilmemek, böylece yedeklemeyi geri alabilmem.

Answer 1

Aramak istediğiniz öğeleri saklayacak başka bir parametre ekleyin. Böyle bunu uygulayabilirsiniz:

int div_algo(int int1, int int2, vector<int>& factors) 
{ 
    if (int2 == 0) //we are done 
     return int1; 
    int factor = 0; 
    int remainder = 0; 
    factors.push_back(int1/int2); //this is useful for linear combination 
    remainder = int1 % int2; 
    return div_algo(int2, remainder, factors); 
} 

Not Ekle faktörler için & kullanımını. Diziyi kopyalamak istemezsiniz, ancak aynı orijinal diziye bir referans göndermeniz yeterlidir. Vektöre int'u, gerekli gördüğünüz verileri saklayabilecek bir yapıyla değiştirebilirsiniz.

Yapabileceğiniz diyoruz için:

vector<int> factors; 
div_algo(353, 15, factors); 
for (int x : factors) cout << x << " ";