Последовательности Колакоски

Последовательности Колакоски похожи на тайну зарождения жизни, то есть, просты ровно настолько, чтобы быть самогенерирующимися и неповторимыми.

"Вики" может покинуть нас, на всех страницах энциклопедии

Задача состояла в том, чтобы реализовать метод, вычисляющий следующее значение из последовательности Колакоски, порождённой заданным исходным множеством натуральных значений, а также сделать некую проверку длин серий, позволяющую ответить на вопрос, является ли полученная последовательность "настоящей Колакоски".

Консольное приложение на C++ проверялось в пустом проекте актуальной сборки Visual Studio 2019.

#include <iostream>
#include <vector>

using Sequence = std::vector<int>;

std::ostream& operator << (std::ostream& os, const Sequence& v) {
 //Вывод последовательности в поток
 os << "[ ";
 for (const auto& e : v) {
  std::cout << e;
  if (&e != &v.back()) std::cout << ", ";
 }
 os << "]";
 return os;
}

int next_in_cycle(const Sequence& s, size_t i) {
 return s[i % s.size()];
}

Sequence gen_kolakoski(const Sequence& s, int n) {
 //Генерация последовательности
 Sequence seq;
 for (size_t i = 0; seq.size() < n; ++i) {
  const int next = next_in_cycle(s, i);
  Sequence nv(i >= seq.size() ? next : seq[i], next);
  seq.insert(std::end(seq), std::begin(nv), std::end(nv));
 }
 return { std::begin(seq), std::begin(seq) + n };
}

bool is_possible_kolakoski(const Sequence& s) {
 //Проверка последовательности
 Sequence r;
 for (size_t i = 0; i < s.size();) {
  int count = 1;
  for (size_t j = i + 1; j < s.size(); ++j) {
   if (s[j] != s[i]) break;
   ++count;
  }
  r.push_back(count);
  i += count;
 }
 for (size_t i = 0; i < r.size(); ++i) if (r[i] != s[i]) return false;
 return true;
}

int main() {
 //Тесты и вывод результатов
 std::vector<Sequence> seqs = {
   { 1, 2 }, //1
   { 1, 3 }, //1
   { 1, 2, 3 }, //1
   { 1, 3, 2, 1 }, //0
   { 0, 1 } //0
 };
 for (const auto& s : seqs) {
  auto kol = gen_kolakoski(s, 100);
  std::cout << "Starting set: " << s << ": " << std::endl << "Kolakoski sequence: "
   << kol << std::endl << "Is it kolakoski? " << is_possible_kolakoski(kol) 
   << std::endl << std::endl;
 }
 return 0;
}

02.03.2022, 23:36 [797 просмотров]