Описание тега correctness
В теоретической информатике о правильности алгоритма говорят, когда говорят, что алгоритм корректен в соответствии со спецификацией.
3
ответа
Корректность минимального количества свопов для сортировки массива
Вопрос от здесь: https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/ Я повторю это ниже: учитывая массив из n различных элементов, найдите минимальное количество перестановок, необходимое для сортировки массива. Примеры: Входные …
29 янв '18 в 11:34
3
ответа
Динамическое программирование - максимальный бриллиант
Я пытался решить одну проблему интервью: Дана матрица из n*n. Каждая ячейка содержит 0, 1, -1. 0 означает, что алмаза нет, но путь есть. 1 означает, что в этом месте находится ромб, а путь -1 означает, что путь заблокирован. Теперь вы начинаете с 0,…
21 окт '15 в 08:26
5
ответов
Насколько важно проверять каждый индекс массива в PHP?
Я работаю над довольно большим проектом, в котором есть много мест, где существует такой код: function foo($a, $b, $c, $d, $e, $f) { $clean = array(); $mysql = array(); $clean['a'] = htmlentities($a); $clean['b'] = htmlentities($b); $clean['c'] = ht…
15 фев '11 в 16:59
2
ответа
Как построить без использования локально установленных артефактов
Есть ли способ заставить Maven использовать удаленные артефакты, а не те, которые установлены на вашем компьютере? так как я беспокоюсь об ошибках времени выполнения, а не об ошибках компиляции, сборка сервера недопустима. PS Я знаю, что могу удалит…
23 июл '09 в 13:40
2
ответа
Проверьте, является ли куча min-max кучей
Я написал кучу min-max, то есть кучу, где нахождение минимума и максимума являются постоянными операциями. Теперь я хочу создать тесты для своего класса, поэтому я решил реализовать функцию, которая проверяет, является ли куча min-max-heap. Вот, но …
18 фев '16 в 23:18
1
ответ
Почему производительность равна нулю для следующей логики?
Я написал эту функцию для удобства и получил 0 в производительности и 100% за правильность. A = [-1, -3] B = [1,2,3] C = [1,4,5,6,77,2] Предполагается, что приведенная ниже функция возвращает наименьшее целое число, но не представляет переданный ей …
09 сен '17 в 17:15
1
ответ
Алгоритм SiftDown Количество сравнений
Я недавно работал с siftDown алгоритм, используемый для построения бинарных куч. В книге "Алгоритмы и структуры данных: базовый инструментарий" в упражнении 6.5 указано, что для данной реализации этого алгоритма требуется 2*log(n) Элемент сравнения.…
03 июн '16 в 10:48
1
ответ
Угловой JS, используя директивы правильный путь
Я новичок в Angularjs, и мне нужна помощь. Чего я хочу добиться, так это встроенного редактируемого текстаЭто будет переключаться между текстом и полем вводаТак что текст onClick будет переключаться с поля ввода, чтобы придать ему фокуси когда есть …
09 окт '14 в 16:42
1
ответ
Доказательство правильности алгоритма по индукции
Недавно я начал читать книгу о структурах данных, и она начинается с введения в алгоритмы. В одном упражнении он просит доказать алгоритм по индукции и инвариант цикла. Алгоритм в псевдокоде: Algorithm DEC2BIN(int n, int[] b) Input: int n, array b O…
17 июн '18 в 12:01
2
ответа
Как работает алгоритм для самой длинной возрастающей подпоследовательности [O(nlogn)]?
Я нашел алгоритм, упомянутый в Руководстве автостопщика по конкурсам программирования (примечание: эта реализация предполагает, что в списке нет дубликатов): set<int> st; set<int>::iterator it; st.clear(); for(i=0; i<n; i++) { st.inse…
14 дек '13 в 20:41
1
ответ
Двойная проверка блокировки не является проблемой из-за неявного барьера памяти?
Я рассматриваю фрагмент кода и заметил двойную проверку реализации блокировки для установки блокировки сеанса: Lock lock = getLock(mySession); if (lock == null) { synchronized (myService.class) { lock = getLock(mySession); if (lock == null) { lock =…
22 фев '17 в 17:12
1
ответ
Тройка Hoare с неизвестной переменной в постусловии
Я рассуждаю об упражнении Hoare Logic. Я должен найти все логические выражения B и все программы S а также P которые удовлетворяют тройной {true} if B then S; if B then P; {a >= 0}, предполагая, что оценка B не может изменить магазин, но выполнен…
17 сен '13 в 10:43
1
ответ
Как построить и обосновать цикл-инвариант, который позволяет показать частичную корректность
Мне нужно построить и обосновать инвариант цикла с заданной спецификацией: {n > 0} P {q = | {j: a[j]=x and 0 <= j < n} |} где |A| является числом элементов множества A. Это означает, что q равно числу элементов из массива a, которые равны x…
11 дек '18 в 22:19
3
ответа
Как я могу доказать правильность алгоритма?
У меня есть проблема с этим упражнением в Java, я не понимаю, как доказать этот метод суммы в Java Вот что я сделал: P(0) : If r=0 and i=0 => r=0+a[0] p(i+1) : r'= r + a[i] and i'=i+1 r'=r + a[i] + a[i+1] public static int sum(int[] a) { int r = …
24 янв '19 в 18:01
1
ответ
SQL вычисляет верхний / нижний предел - какой путь правильный?
Я довольно новичок в этом и читаю книгу по анализу данных, я застрял в понимании того, как он вычисляет верхнюю и нижнюю границы диапазонов значений порядка - я, должно быть, уже некоторое время возвращался на эту страницу. Я все время использую Exc…
10 фев '19 в 06:49
1
ответ
Доказательство правильности программы
Функция рекурсивно находит и возвращает наименьший элемент из массива, который имеет целочисленные элементы Min(A, b, e) if (b=e) return A[b] m = (b+e)/2 // floor is taken x = Min(A, b, m) y = Min(A, m +1, e) If(x < y) return x else return y Моим…
06 ноя '15 в 00:48
2
ответа
Проверка правильности алгоритма FFT
Сегодня я написал алгоритм для вычисления быстрого преобразования Фурье из заданного массива точек, представляющих дискретную функцию. Сейчас я пытаюсь проверить, работает ли он. Я пробовал около дюжины различных наборов ввода, и они, кажется, совпа…
19 июн '14 в 21:50
1
ответ
Векторы проверки правильности Rabbit Stream Cipher (v 1.1)
Я не могу найти правильные тестовые векторы для проверки моего кода для шифра Кролика, который я разработал в соответствии с файлом спецификаций с http://www.ecrypt.eu.org/stream/rabbitpf.html. Однако я нашел несколько тестовых векторов в zip-файле …
12 мар '16 в 11:08
1
ответ
Является ли эта реализация алгоритма Negamax правильной
Я пытаюсь реализовать алгоритм Negamax, и я так и думал: public Move getBestMove(Board board){ List<Move> possibleMoves = board.getPossibleMoves(); Move optimalMove; int maxScore; foreach(Move move in possibleMoves){ Board newBoard = board.clo…
20 май '11 в 10:51
4
ответа
Как я могу использовать System.Net.ConnectStream?
Я пытаюсь осмыслить код моего предшественника, который, услужливо, использовал 'var' для объявления всего. У меня есть заявление об использовании, которое ниже: using (var postStream = request.GetRequestStream()) { postStream.Write(byteData, 0, byte…
19 янв '12 в 16:35