我的解決方案的時間限制超出測試用例。我的解決方案有什麼問題？

Codeforces問題119A- http://codeforces.com/problemset/problem/119/A 我的解決方案的時間限制超出測試用例。我的解決方案有什麼問題？

我的解決辦法：

#include<iostream> 
using namespace std; 
int a,b,i,n; 
int gcd(int x,int y) 
{ 
    int z,c; 
    c=min(x,y); 
    for(i=1;i<=c;i++) 
    { 
     if(((x%i)==0)&&((y%i)==0)) 
     z=i; 
    } 
    return z; 
} 
int main() 
{ 
    cin>>a>>b>>n; 
    while(1) 
    { 

     if(n<gcd(a,n)) 
     { 
      cout<<"1"; 
      break; 
     } 
     else 
     n-=gcd(a,n); 
     if(n<gcd(b,n)) 
     { 
      cout<<"0"; 
      break; 
     } 
     else 
     n-=gcd(b,n); 
    } 
}

我不熟悉的時間constraints.My解決方案是給予正確的結果在常規time.What我的電腦上運行時我應該改變我的解決方案讓它在時間限制下運行？我是否應該避免使用用戶定義的函數？測試用例爲-3,5,9和1,1,100。

來源

2013-12-14 vishal_khanna

「我應該不要使用......功能」否！你應該改進算法，然後再擔心你的算法，然後擔心你的編譯器，然後擔心微內優化，比如內聯一個微小的純函數 – jozefg

從某種意義上講，這比編程問題更像是一個數學問題。如果你研究如何有效地計算'gcd'，那麼一個更好的程序會表明它自己。編程不僅僅是爲了獲得第一個想法而編寫代碼。這也是研究你正在試圖解決的問題，找到解決問題的最佳算法，然後將它們轉換成代碼。 –

嘗試僅計算一次gcd，而不是每個循環兩次。 –

您的代碼絕對準確並且會得出正確的答案，但可以通過一些小的改進來提高效率併成功通過時間限制。

不要在while循環內計算兩次GCD。 GCD是一個昂貴的算法，它運行兩次使您的程序的整體完成時間加倍。這可能是您的程序不能生成TLE的最重要的修補程序。
潛在的優化算法GCD，雖然這是沒有必要通過所有測試用例（如下圖所示）

只使用一次gcd並傳遞codeforces所有測試用例可能看起來像下面的（提交here的實現）：

#include <iostream> 
using namespace std; 

int gcd(int, int); 

int main() 
{ 
    int a, b, n; 
    cin >> a >> b >> n; 
    while (1) { 
     n -= gcd(a, n); 
     if (n == 0) { 
      cout << "0" << endl; 
      return 0; 
     } 
     n -= gcd(b, n); 
     if (n == 0) { 
      cout << "1" << endl; 
      return 0; 
     } 
    } 
} 

int gcd(int u, int v) 
{ 
    int t; 
    while ((t = u % v) != 0) { 
     u = v; 
     v = t; 
    } 
    return v; 
}

來源

2014-04-22 23:45:09 manan

我的解決方案的時間限制超出測試用例。我的解決方案有什麼問題？

回答

相關問題