c++ - 迭代差异

Question

这是一个spoj问题。它有效，但它太慢了。

问题是:

迭代差异

You are given a list of N non-negative integers a(1), a(2), ... , a(N). You replace the given list by a new list: the k-th entry of the new list is the absolute value of a(k) - a(k+1), wrapping around at the end of the list (the k-th entry of the new list is the absolute value of a(N) - a(1)). How many iterations of this replacement are needed to arrive at a list in which every entry is the same integer?

例如，让 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 次迭代。

输入

The input will contain data for a number of test cases. For each case, there will be two lines of input. The first line will contain the integer N (2 <= N <= 20), the number of entries in the list. The second line will contain the list of integers, separated by one blank space. End of input will be indicated by N = 0.

输出

For each case, there will be one line of output, specifying the case number and the number of iterations, in the format shown in the sample output. If the list does not attain the desired form after 1000 iterations, print 'not attained'.

示例输入

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) { ... }

如果无法实现，将打破循环。 基本上，它只是一遍又一遍地做同样的事情。它实际上并不慢。 谢谢 xan 的回答。