迭代差分

Question

這是一個spoj問題。它有效，但速度太慢。

這裏有一個問題：

迭代差異

現在給你N個非負整數a（1），（2），...， 一個列表（N）。用新列表替換給定列表：新列表的第k個條目是a（k）-a（k + 1）的絕對值，在列表的末尾打包 （k- （N） - a（1））的絕對值爲 ）。需要多少次迭代才能得到一個列表，其中每個條目都是相同的整數？

例如，讓N = 4並從列表(0 2 5 11)開始。連續迭代爲：

2 3 6 11 
1 3 5 9 
2 2 4 8 
0 2 4 6 
2 2 2 6 
0 0 4 4 
0 4 0 4 
4 4 4 4 

因此，在這個例子中需要8次迭代。

輸入

輸入將包含若干測試案例數據。對於每種情況， 將會有兩行輸入。第一行將包含 整數N（2 < = N < = 20），列表中的條目數。 第二行將包含整數列表，用空格隔開一個空格。輸入端將被N表示= 0

輸出

對於每一種情況，將有一行輸出，指定的情況下 數和迭代次數，在輸出示例 中顯示的格式。如果列表未在迭代1000 後達到所需表單，則打印「未達到」。

採樣輸入

4 
0 2 5 11 
5 
0 2 5 11 3 
4 
300 8600 9000 4000 
16 
12 20 3 7 8 10 44 50 12 200 300 7 8 10 44 50 
3 
1 1 1 
4 
0 4 0 4 
0 

樣本輸出

Case 1: 8 iterations 
Case 2: not attained 
Case 3: 3 iterations 
Case 4: 50 iterations 
Case 5: 0 iterations 
Case 6: 1 iterations 

---

我不知道該怎麼做，使之更快。我嘗試使用數組，但是我嘗試分配內存並將一個數組設置爲另一個時遇到各種問題。

我該如何加快速度？這裏是我的代碼：

#include <iostream> 
#include <vector> 
#include <cmath> 
#include <sstream> 
#include <string> 

using namespace std; 

bool checker(vector<int>& nums2) { 
    int n = nums2[0]; 
    for (int i = 1; i < nums2.size(); i++) 
    { 
     if (n != nums2[i]) 
     return false; 
    } 
    return true; 
} 

vector<int> iterate(vector<int>& nums, int& iter, bool& attained) { 
    if (iter == 1000) { 
     attained = false; 
     return nums; 
    } 
    vector<int> nums2; 

    for (int i = 0; i < nums.size(); i++) { 
     if (i == nums.size() - 1) 
     nums2.push_back((int)abs((double)nums[i] - (double)nums[0])); 
     else 
     nums2.push_back((int)abs((double)nums[i] - (double)nums[i + 1])); 
    } 

    iter++; 
    return nums2; 
} 

int main() 
{ 
    int N = -1, count = 1; 

    while (1) { 
     int num = 0; 
     vector<int> nums; 
     string List = ""; 
     stringstream ss; 
     cin >> N; 

     if (N == 0) 
     break; 

     cin.ignore(); 
     cin.clear(); 
     getline(cin, List); 

     ss << List; 

     while (ss >> num) { 
     nums.push_back(num); 
     } 

     int iterations = 0; 
     bool attained = true; 
     while (!checker(nums)) { 
     nums = iterate(nums, iterations, attained); 
     } 

     if (!attained) 
     cout << "case " << count << ": not attained"; 
     else 
     cout << "case " << count << ": " << iterations << " iterations" << endl; 
     count++; 
    } 
} 

Answer 1

我修好了。這是主函數中while循環的問題。條件是：

while (!checker(nums)) { ... } 

它會留在循環和反覆調用迭代函數，因爲如果它不能達到，那麼檢查將永遠是假的。因此，將條件改爲：

while (!checker(nums) && attained) { ... } 

如果無法達到則會打破循環。基本上，它一直被卡住做同樣的事情一遍又一遍;實際上並不慢。 謝謝你的回答。

Answer 2

如果你希望它是一個小快，你應該在調試陣列的變化，以避免矢量分配工作。如果你希望它更快地成爲lot，你需要對問題進行一些分析以找到更好的算法。例如，如果你兩次看到相同的列表，那麼你將處於一個循環中，並且會超過1000次迭代。如果您旋轉列表，結果將會相同，您可以在檢查重複列表時考慮這些列表。

Answer 3

你的實現在我的主流lapton上執行了25ms的1000次迭代。修正了一個，因爲有一個bug，而case 2將永遠執行。

要做到更快，你可以重複使用相同的載體，並修改它的地方，你iterator()函數簽名看起來像：

void iterate(vector<int>& nums); 

這個版本把我的機器上7毫秒，因爲它不分配內存循環。