如何轉換這個Python代碼C++

我有在Python工作的算法，我想轉換爲C++：如何轉換這個Python代碼C++

def gcd(a, b):  
    if (a % b == 0): 
     return b 
    else: 
     return gcd(b, a % b) 

def solution(N, M): 
    lcm = N * M/gcd(N, M) 
    return lcm/M

我在與大的輸入值的問題，M和N多導致整數溢出，並使用long來存儲它的值似乎沒有幫助，除非我做錯了什麼。

這裏是我當前的代碼：

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

int solution(int N, int M) { 

    // Calculate greatest common divisor 
    int g = gcd(N, M); 

    // Calculate the least common multiple 
    long m = N * M; 
    int lcm = m/g; 

    return lcm/M; 
}

來源

2014-02-22 jaho

你給'solution'提供了什麼值？ –

N和M都在範圍內（1,1,000,000,000）。 – jaho

那麼，一個快速的解決方案就是使用'long long'。這並不意味着更大的價值是安全的，但。 – chris

你計算g=gcd(N,M)，然後m=N*M，然後lcm=m/g，最後返回lcm/M。這與返回N/gcd(N,M)相同。你不需要這些中間計算。擺脫他們。現在沒有溢出問題（除非M = 0，也就是說，你沒有防範）。

int solution(int N, int M) { 
    if (M == 0) { 
     handle_error(); 
    } 
    else { 
     return N/gcd(N,M); 
    } 
}

來源

2014-02-22 21:43:43

這就是它，很好看！我討厭那樣的事情。錯誤處理不是必需的，因爲M和N都保證至少爲1. – jaho

儘管答案避免了OP解決方案中的問題，但這並沒有突出顯示問題。它更好地瞭解OP解決方案中存在的實際問題。這個錯誤非常常見，常常被忽視。 –

意圖應該是'爲什麼我的解決方案不起作用'而不是'只給我正確的解決方案'。 –

首先，更改：

long m = N * M; 
int lcm = m/g;

要：

long long m = (long long)N * M; 
int lcm = (int)(m/g);

在一般情況下，你不妨改變每int你代碼到unsigned long long ...

但是，如果您手邊有一些BigInt課程，那麼您可能需要使用它。

這裏是一個免費：http://planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=9735&lngWId=3

它存儲任何可想到的大小的自然數，支持C++提供所有算術運算符。

來源

2014-02-22 21:35:09

我試過這種方法的多種組合，它似乎仍然不起作用。 – jaho

你沒有說爲什麼這種方法不起作用，瑪麗安。你是否遇到'long long'的編譯錯誤？這不是C++ 03的一部分，但它是一個相當標準的擴展。它是C++ 11的一部分。 –

沒有編譯時錯誤，但結果仍然不正確。你可以在這裏測試它自己：https://codility.com/demo/take-sample-test/chocolates_by_numbers – jaho

-1

問題出在long m = N*M. 乘法只發生在32位整數。由於兩者都是int類型，所以發生溢出。

修正是long long m = (long long)N*M

來源

2014-02-22 21:36:48

如何轉換這個Python代碼C++

回答

相關問題