Описание тега knuth
Donald E. Knuth is a computer scientist, best known as the author of the series of books on algorithms The Art of Computer Programming and the creator of the TeX typesetting system.
1
ответ
Какова сложность времени для Алгоритма X для судоку?
Я нашел здесь утверждение, что алгоритм X для судоку имеет O(N^3) временную сложность, где N - размер платы. Это может быть логично, поскольку для судоку двоичная матрица для вычисления имеет N ^ 3 строки. Но это делает проблему судоку разрешимой за…
14 янв '19 в 15:39
1
ответ
Алгоритм Кнута – Морриса – Пратта на основе DFA`?
Я хочу узнать, как работает алгоритм Кнута-Морриса-Пратта. Я смотрел этот учебник из Принстонского университета https://www.youtube.com/watch?v=iZ93Unvxwtw. В этом видео они используют таблицу с длиной алфавита = количество строк и длиной шаблона = …
04 окт '14 в 17:45
1
ответ
Объяснение терминов для алгоритма танцевальных связей Д. Кнута
Я скачал с сайта Д.Кнута алгоритм DLX. В первом разделе, в котором D.Knuth дает обзор проблемы, столбцы разделяются на "основной" и другие столбцы. Каковы эти "основные" столбцы? Заранее спасибо.
06 мар '15 в 14:25
1
ответ
Mastermind алгоритм с длинным кодом
В настоящее время я реализую алгоритм mastermind от knuths. Но я хочу создать программу mastermind, в которой длина кода достигает 15, а количество разных цветов также равно 15. Так что у меня есть проблема с Seed S, упомянутым в алгоритме выше. Ког…
23 янв '17 в 00:28
1
ответ
WordCount: насколько неэффективно решение McIlroy?
Короче говоря: в 1986 году интервьюер попросил Дональда Кнута написать программу, в которой вводятся текст и число N, а также перечисляются N наиболее часто используемых слов, отсортированных по частоте. Кнут создал 10-страничную программу Pascal, н…
21 сен '14 в 09:36
2
ответа
Оценка обозначения стрелки Кнута в функции
У меня проблемы с вычислением обозначения стрелки Кнута, которое is и которое можно найти здесь, в функции. Что я сделал до сих пор: int arrowCount = (int)arrowNum.Value; // Part of BigInteger a = (int)aNum.Value; // the input I BigInteger b = (int)…
24 июн '16 в 04:26
1
ответ
Точное покрытие с использованием Dancing Links
Пройдя через этот вопрос, я попытался реализовать Dancing Links, чтобы решить только точную проблему покрытия. Ниже приведен код, взятый отсюда и измененный (это структура Column-Row, мне нужна структура Row-Column). Он работает нормально, за исключ…
15 мар '14 в 02:51
2
ответа
Где я могу найти график журнала ошибок TeX?
В " Грамотном программировании" Дональда Кнута был, если я правильно помню, график, показывающий эволюцию количества ошибок TeX с течением времени. Этот график оставался плоским в течение последнего десятилетия или около того, предполагая, что TeX т…
23 янв '09 в 12:59
2
ответа
Минимальная циклическая подстрока в большей циклической строке
Я пытаюсь найти алгоритм, который кульд возвращает длину самой короткой циклической подстроки в большей циклической строке. Циклическая строка будет определяться как объединение двух или более одинаковых строк, например, "abababab" или "aaaa"... Теп…
23 июн '11 в 19:39
2
ответа
Расчет функции отказа КМП
Мой профессор решил функцию отказа KMP следующим образом: index 1 2 3 4 5 6 7 8 9 string a a b a a b a b b ff 0 1 2 1 2 3 4 5 1 Из других текстов, которые я проверил онлайн, я обнаружил, что это может быть неправильно, я вернулся, чтобы подтвердить …
20 апр '13 в 21:49
0
ответов
Вход и выход ограничен deque
Как доказать, что число перестановок в возрастающей последовательности, использующих входную ограниченную деку, равно количеству перестановок, использующих выходную ограниченную деку? В книге "Искусство компьютерного программирования" Кнута дается, …
04 авг '16 в 17:24
2
ответа
Как мне начать использовать ассемблер MIX/MMIX Дональда Кнута?
Я бы хотел изучать MIX/MMIX, но я не знаю, какой набор инструментов можно использовать для его написания. Я использовал uVision в прошлом для вещей, связанных с ассемблером ARM, существует ли такой эквивалент для MIX/MMIX?
12 сен '15 в 03:33
0
ответов
Каковы примеры точных проблем покрытия в реальных приложениях?
В информатике проблема точного покрытия - это проблема решения, чтобы определить, существует ли точное покрытие. Точная задача о покрытии является NP-полной [1] и является одной из 21 проблем Карпа с NP-полной.[2] Точная проблема покрытия является с…
17 июл '16 в 08:36
2
ответа
Как лучше всего читать код в формате CWEB в Windows?
У Дональда Кнута есть большое количество программ для чтения на его странице. Но они в основном в "странном" формате CWEB... Что может быть лучшим способом сделать их подходящими для чтения в Windows?
15 июн '09 в 16:14
1
ответ
Как работает тест Кнута "Мужчина или мальчик"?
Кто-нибудь может объяснить, как тест " Человек или мальчик" возвращает значение -67? Я тщетно пытался записать результат или отследить его с помощью отладчика. Любая помощь будет оценена. Список различных реализаций можно найти здесь.
17 ноя '09 в 06:17
3
ответа
Перестановки Java с наименьшим возможным числом случайных чисел
Я хочу создать перестановку array a и я не хочу использовать служебные функции, такие как java.util.Collections() , Перестановки должны быть рандомизированы, и каждая перестановка должна быть возможной, но нет необходимости в равномерно распределенн…
14 ноя '09 в 15:39
0
ответов
Реализация алгоритма Knuths Mastermind Java
Я пытаюсь реализовать алгоритм Knuths Mastermind в Java. Алгоритм объясняется в данной статье, статья. Это то, как я реализовал это до сих пор, но это занимает больше, чем максимум 5 догадок, чем алгоритм должен принять. private static void makeGues…
01 ноя '13 в 22:42
3
ответа
Как работают операции LDA, STA, SUB, ADD, MUL и DIV на машинном языке Кнута MIX?
Я читал книгу "Искусство компьютерного программирования" Дональда Кнута, том 1. Теперь я закончил первую часть, где объяснялась вся математика, и это было очень приятно. К сожалению, на с. 121 он начинает объяснять этот вымышленный машинный язык под…
04 янв '14 в 17:29
2
ответа
Искусство программирования Кнута, третье издание, и пример евклидова алгоритма
Я только начал читать том 1 искусства Кнута по программированию и попал в раздел на странице 4, где он описывает евклидов алгоритм. Он утверждает шаги, чтобы найти наибольший общий делитель двух чисел. Вы можете прочитать больше об этом здесь https:…
18 авг '15 в 06:32
0
ответов
Алгоритм Дональда Кнута для Mastermind
Я работаю над алгоритмом Дональда Кнута 1977 года для Mastermind ( здесь). Я реализовал некоторые шаги, но я не знаю, как рассчитать количество возможных вариантов, которые будут исключены для каждого возможного результата. Integer Bulls <- 0 WHI…
28 июн '12 в 08:46