Size: a a a

2020 August 26

КГ

Константин Громов... in pro.algorithms
Vadim Ushakov
Если совесть не особо гложет, можно легко найти в электронном варианте
Причём тут совесть?)
Она у меня есть в электроне )
Не могу с компа книги читать..
источник

N

Nikolay in pro.algorithms
Дана невалидная последовательность скобок.  Надо из нее путем удаление несбалансированных сделать валидную.
источник

АР

Антон Русаков... in pro.algorithms
Nikolay
Дана невалидная последовательность скобок.  Надо из нее путем удаление несбалансированных сделать валидную.
очевидно, что в таком виде задача смысла не имеет.
источник

АР

Антон Русаков... in pro.algorithms
(()))- можно удалить одну скобку и будет валидная, можно удалить три и тоже будет валидная.
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Nikolay
Дана невалидная последовательность скобок.  Надо из нее путем удаление несбалансированных сделать валидную.
удали все
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
будет валидная
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
источник

ВВ

Вадим Великодный... in pro.algorithms
Проблема в том, что непонятно, какие несбалансированные.
(())())
Можно удалением одной скобки получить как (())(), так и (()()).
источник

АР

Антон Русаков... in pro.algorithms
и мы пришли к выводу, что даже если требовать удалить минимальное число скобок, то ответ будет неоднозначным.
источник

ВВ

Вадим Великодный... in pro.algorithms
Антон Русаков
и мы пришли к выводу, что даже если требовать удалить минимальное число скобок, то ответ будет неоднозначным.
Именно!
источник

N

Nikolay in pro.algorithms
надо найти все возможные варианты удаления, которые делают последовательность валидной
источник

ВВ

Вадим Великодный... in pro.algorithms
Это достаточно важное уточнение.
источник

С

Сергей in pro.algorithms
Nikolay
надо найти все возможные варианты удаления, которые делают последовательность валидной
источник

AT

Anatoly Tomilov in pro.algorithms
какая для случайной перестановки первых N натуральных чисел сложность сортировки следующим алгоритмом?
#include <utility>
#include <algorithm>
#include <vector>
#include <random>
#include <iostream>

int main()
{
   std::vector<size_t> v(10);
   std::iota(std::begin(v), std::end(v), size_t{0});
   std::random_device rd;
   std::mt19937 g(rd());
   std::shuffle(std::begin(v), std::end(v), g);
   for (size_t i = 0; i < std::size(v); ++i) {
       size_t j = v[i];
       while (j != i) {
           std::swap(v[j], j);
       }
       v[i] = j;
   }
   std::copy(std::cbegin(v), std::cend(v), std::ostream_iterator<int>(std::cout, " "));
   std::cout << std::endl;
}
источник

AT

Anatoly Tomilov in pro.algorithms
какая асимптотика?
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
Anatoly Tomilov
какая для случайной перестановки первых N натуральных чисел сложность сортировки следующим алгоритмом?
#include <utility>
#include <algorithm>
#include <vector>
#include <random>
#include <iostream>

int main()
{
   std::vector<size_t> v(10);
   std::iota(std::begin(v), std::end(v), size_t{0});
   std::random_device rd;
   std::mt19937 g(rd());
   std::shuffle(std::begin(v), std::end(v), g);
   for (size_t i = 0; i < std::size(v); ++i) {
       size_t j = v[i];
       while (j != i) {
           std::swap(v[j], j);
       }
       v[i] = j;
   }
   std::copy(std::cbegin(v), std::cend(v), std::ostream_iterator<int>(std::cout, " "));
   std::cout << std::endl;
}
O(N)
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
каждая итерация внутреннего цикла увеличивает число циклов в перестановке на 1
источник

AT

Anatoly Tomilov in pro.algorithms
круто, спс). Эта сортировка имеет какое-то название или она очевидна?
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
не уверен что видел где-либо название)
источник

AT

Anatoly Tomilov in pro.algorithms
действительно. В худшем случае N присвоений и 2*N сравнений+изменений индекса
источник