DALVROT, Нет, ничего не меняет. Ведь диллер мог вытащить туз,туз, 10, 5,
а мог, 5, туз, 10, туз. Да и тузы разные (даже если одной масти - это физически разные карты). Просто у вас массив A содержит 1,1,10,5 и все остальные карты.
Вам не надо никакие наборы добавлять в списки. Все различные наборы перебираются сами внутри динамического программирования.
Из ваших наборов надо очень аккуратно считать, сколькими способами их можно вытащить. Плюс они не независимые будут. Например, можно вытащить 10+3+2+5, а можно 10+3+5 и это разные наборы у вас. Хотя первый набор можно перетасовать в 10+3+5+2, но выбрать его так никогда не получится.
Magneto903, Что у вас за PriorityQueue реализация? Посмотрите код, потестируйте. Добавьте в очередь приоритеты a:1,b:3,c:5 и сделайте queue.poll() несколько раз.
Надо, что бы вернулись именно минимальные числа и они из очереди удалялись. Т.е. 3 poll() вернут a,b,c в таком порядке.
Если возвращается максимальный элемент, то вам надо пихать в очередь не newdistance, а -newdistance.
Если все три раза возвращается один и тот же элемент, то значит после poll() надо удалять элемент из очереди или спользовать какой-нибудь pop_front(), pop() метод у queue.
Magneto903, Проверьте
1) queue.poll() удаляет первую вершину.
2) очередь возвращает вершину с МИНИМАЛЬНЫМ приоритетом.
3) Цикл for (var child of graph[startNode].keys()) не нужен.
4) Если child нет в очереди - то надо добавить вершину с приоритетом newdistance. Вы же только обновляете приоритет. если вершины нет.
Можно конкретизировать задачу для незнакомых с блекджеком?
Правильно ли я понимаю, что у вас есть набор возможных карт в колоде. Одна карта уже выдана дилеру. Диллер случайно вытаскивает по одной из оставшихся карт, пока не наберет >=17. И вам надо подсчитать вероятности всех сумм?
Дмитрий, я имел ввиду ассимптотическую сложность по времени. Чем она меньше, тем производительнее код на больших входных данных. Грубо говоря, сложность показывает, как быстро растет время работы при увеличении входных данных.
galaxy, Но так нельзя. Если делать float**, то надо сначала выделить массив из n указателей, а потом для каждой строки отдельно выделять память.
Вы выделили двумерный массив, и преобразовали указатель на первый float элемент в float**. При обращении к a[i][j] тут происходит обращение по адресу, записанному в блоке float-ов.
Никита,
Во-первых, можно соптимизировать код. Вам не нужны на самом деле рекурсивные вызовы. Ведь каждый раз вызов идет только в одну сторону. Надо переписать quicksort с одним циклом while. Вы внутри разбиваете, потом смотрите, в какую сторону нажно идти и меняете переменные. Потом следующая итерация цикла сделает то, что вы хотели сделать вашим рекурсивным вызовом.
Также можно вставить код partition прямо в тело quicksort.
Попробуйте воткнуть в начало srand(ваше-любимое-число). Может жюри подобрали плохой тест. Надо рандомизировать что-то самим. Вмеcто std::swap ручная реализация может быть быстрее.
Но главное, введите тест A=0, B=0, array[0]=array[1]. Все числа в массиве будут одинаковые. Тут ваша реализация будет откусывать по 1 элементу и работать за квадрат.
Можно сделать все числа уникальными, если расширить их до 64-бит, где старшие биты - входные данные, а нижние 32 бита - тупо индекс числа. Найдите тут k-ое число и выведите старшие биты.
Ну, или меняйте ++last с i с некоторой вероятностью, если a[i] == pivot.
Или можно переписать с использованием разбиения Хоара (у вас Ломуто сейчас). Оно на таком вырожденном тесте всегда будет разбивать по середине.
xmoonlight, Очевидный критерий: разбить на n k-или-менее-угольников никогда нельзя (n*k+1)-или-больше-угольник. Потому что все изначальные углы никуда не денутся и по pigeonhole принципу какой-то из n кусков будет более чем k-угольником. Но это если нам так повезет, что мы все границы проводим исключительно хордами и получаем равные по площади куски. Скорее всего придется проводить всякие ломаные да еще и из центров сторон. Поэтому видимо n(k-3) >= количеству вершин в изначальном многоугольнике. Это не обязательное, но, похоже, достаточное условие.
И массив соединений этих точек: [[p1,p2],[p3,p4],.....[pN,p1]]
А [p2, p3]?
Просто по кругу точки замкнуты, же?
Области на которые мы пилим многоугольник - они могут быть как бублики с дрыками? Иметь анклавы? Или обычные человеческие многугольники, хоть и не выпуклые?
Magneto903, Еще варинат есть использовать heap - должно быть сильно быстрее.
Дейкстра работает за O(n^2+m) потому что вам надо n раз искать вершину с минимальным расстоянием ну и вы по каждому ребру ровно один раз посмотрите, улучшает ли оно расстояние до другого конца.
Если минимум искать через хип, то будет O((n+m)log n) операций, что сильно лучше для вашего случая (m < n^2), потому что хип умеет выдавать минимум и изменять значение за log n.
Вы же, кажетcя, ссылку давали на этот сборник алгоритмов.
Там есть heap. Вам надо хранить в хипе пары {расстояние, номер вершины} до всех пока не visited вершин, у которых есть расстояние. Изначально heap пустой совсем.
Вам надо переписать shortestDistanceNode просто брать минимум из minHeap. При изминении distances в цикле по node вам надо добавлять в minHeap новый объект {расстояние, номер вершины}. Именно в таком порядке, чтобы минимальный элемент содержал минимальное расстояние. Ну или функции сравнения переписать.
Но тут ньюанс - в хипе может быть куча копий вершины, ведь вы будете добавлять новую копию каждый раз, когда обновите расстояние. Поэтому еще надо цикл по child пропускать, если вершина из heap уже в visited.
Или вам придется этот minHeap немного переписать, чтобы проддерживать map из номеров вершин в их позиции в хипе. И при каждом изменении массива heapContainer обовлять этот map. Тогда в методе remove не надо будет выполнять линейный поиск через find.
Потом при изменении distance в основном цикле вы должны будете удалить вершину child[0] из хипа перед добовлением ее копии с новым расстоянием.
Magneto903, Нет не надо матрицы смежности, оставьте списки инцидентности. Пусть у вас будет массив списков объектов {конец ребра, цена}. Раньше у вас там был словарь из строк-имен вершин. Но раз мы поменяли на числа, то можно это заменить массивом, который будет быстрее.
Вообще, по идее, если вместо Map использовать массивы ("[]"? Array?) должно еще быстрее быть.
Еще цикл в начале, который проходится по детям startNode - он лишний.
По поводу функции восстановления пути: надо distances[startNode] = 0 делать перед циклом по node. Иначе алгоритм находит путь в эту вершину через какую-то другую. Путь, который начинается в startNode же. В итоге получается цикл, в котором вы и висните.
Magneto903, попробуйте один хеш завести чтобы по вашим вершинам получать эти graphVertex. Сдается мне, что вы когда новую вершину с тем же именем создаете эта библиотека тоже новую вершину создает а не переиспользует старую.
Magneto903, Выглядит правильно.
Видимо, js-боль. Не знаю, попробуйте вместо хэш таблиц использовать тупо массивы. Сделайте, чтобы у вас вершины нумеровались тупо числами от 0 до сколько-их-там. Структуру соседей сделайте массивом-массивов, а не хешами всякими.
Еще, в цикле не надо проверять ```if (child === startNode) {``` можно просто в начале startNode запихать в visited. Это тоже сколько-то ускорит.
Magneto903, Да, в первой реалзации очевидная проблема с visited.
В этой новой реалезации нет того же бага, но все-равно ассимптотика тоже корявая из-за того, что там одна и та же вершина может быть в очереди сколько угодно раз. Да еще и куча выделений памяти и этот массив очереди может сильно вырасти. А главное, операция добавления в очередь там работает за линию, это не куча же а тоже массив. Поэтому в лучшем случае он будет работать в несколько раз медленее, ведь ребер больше чем вершин.
Вообще js явно страдает от отсутствия вменяемых стандартных структур данных.
а мог, 5, туз, 10, туз. Да и тузы разные (даже если одной масти - это физически разные карты). Просто у вас массив A содержит 1,1,10,5 и все остальные карты.
Вам не надо никакие наборы добавлять в списки. Все различные наборы перебираются сами внутри динамического программирования.
Из ваших наборов надо очень аккуратно считать, сколькими способами их можно вытащить. Плюс они не независимые будут. Например, можно вытащить 10+3+2+5, а можно 10+3+5 и это разные наборы у вас. Хотя первый набор можно перетасовать в 10+3+5+2, но выбрать его так никогда не получится.