以下のコードは、完全に正常にコンパイルおよび実行されます。ただし、行を置き換えると
int d=xgcd(x,y,&m,&n);
cout<<d << " = "<<m<<" * "<<x<<" + "<<n<<" * "<<y<<endl;
と
cout<< xgcd(x,y,&m,&n) << " = "<<m<<" * "<<x<<" + "<<n<<" * "<<y<<endl;
そして、本来あるべきものではなくゼロになりますm
。n
ですから、この行動の不一致の背後にある理由は何なのか疑問に思っています。何か不足していますか?
これは C++ で書かれたコードで、フラグ -O0 を指定して gcc 4.72 を使用しています。
testXGCD.cpp:
#include"xgcd.h"
#include<iostream>
#include<cstdlib>
using namespace std;
int main(int argc, char** argv) {
// Read the command line parameter
int x=atoi(argv[1]), y=atoi(argv[2]);
int m=0,n=0;
int d=xgcd(x,y,&m,&n);
// Output the result;
cout<<d << " = "<<m<<" * "<<x<<" + "<<n<<" * "<<y<<endl;
}
xgcd.h:
#ifndef XGCD
#define XGCD
#include<vector>
// Perform the extended Euclidean Algorithm.
// Find (m,n) and return it. pp and qp are two pointers to store the
// coefficients of m and n so 1 = pm + qn.
const int xgcd(int m, int n, int* pp = 0, int* qp = 0) {
// The temp variable to store the remainder.
int temp;
// Create a container to store the quotients.
std::vector<int> quotients;
// Start the Euclidean algorithm.
while(!(m==0)) {
// store the quotient for the extended Euclidean algorithm.
quotients.push_back(n/m);
temp = m;
m = n%m;
n = temp;
}
// Before performing the magic pattern Bud Brown showed us in class,
// put base value 0 and 1 to the end.
quotients.back() = 1;
quotients.push_back(0);
// Create an iterator to traverse the quotients and do the trick.
typename std::vector<int>::reverse_iterator rip = quotients.rbegin();
rip+=2;
// Do the trick here!
while(rip!=quotients.rend()) {
*rip=*rip * *(rip-1) + *(rip-2);
rip++;
}
// If there are odd number of quotients, the last value should be
// it's negative. Otherwise, the second last value should be negative.
if(quotients.size() % 2) {
if(pp!=0)
*pp=-quotients[0];
if(qp!=0)
*qp=quotients[1];
}else{
if(pp!=0)
*pp=quotients[0];
if(qp!=0)
*qp=-quotients[1];
}
return temp;
}
#endif
元のテンプレートの実装を変更したため、xgcd.h には c ファイルではなくヘッダー ファイルを使用し、宿題の問題のために別の実装ファイルをわざわざ作成しませんでした。
なぜこのような違いがあるのか 知っている人はいますか?