Алгоритм Брента?

Для памятки, потом доделать.

Суть в том, что хочется за линейное время O(N), а не квадратичное, что легко.

В "Вики" всё описано хорошо, а на практике весь найденный в сети код - какая-то ерунда, не проходящая почти ни одного теста. Мой алгоритм для целочисленного массива, похоже, не менее крив пока что :(

Компилировал в консоли Studio 2015.

#include <iostream>
using namespace std;

bool detectCycle(int *a, int n, int &start, int &length) {
 if (n < 1) return false;
 else if (n == 1) {
  start = 0; length = 1; return true;
 }
 else if (n == 2) {
  if (a[0] == a[1]) {
   start = 0; length = 1; return true;
  }
  else return false;
 }
 int first_pointer = 0;
 int second_pointer = 1;
 int power = 1;
 length = 1;
 while (second_pointer < n-1 && second_pointer != first_pointer) {
  if (length == power) {
   power *= 2;
   length = 0;
   first_pointer = second_pointer;
  }
  second_pointer++;
  length++;
 }
 if (second_pointer == n) return false;
 start = first_pointer-1;
 return true;
}

int main() {
 int a[] = { 1,2,3,4,2,1,2,3,4,2 };
 int n = sizeof(a)/sizeof(a[0]);
 int start = -1, length = 0;
 bool res = detectCycle(a,n,start,length);
 if (res == false) cout << "No loop";
 else cout << "Loop with item number " << start << ", " << length << " items";
 cin.get();
 return 0;
}

06.09.2018, 14:32 [1826 просмотров]