Метод грубой силы. Методы разработки алгоритмов n Метод грубой силы Алгоритм грубой силы паскаль

и следующую функцию: function show(pos, path, w, h) { var canvas = document.getElementById("canID"); // получаем объект канваса var ctx = canvas.getContext("2d"); // у него есть свойство - контекст рисования var x0 = 10, y0 = 10; // положение левого верхнего угла карты canvas.width = w+2*x0; canvas.height = h+2*y0; // меняем размеры канваса (чуть больше, чем w x h) ctx.beginPath(); // начало рисования ломаной линии ctx.moveTo(x0+pos.x,y0+pos.y)// переходим на 0-й город for(var i=1; i Пример результата вызова функции приведен справа. Смысл команд рисования должен быть ясен из их названия и комментариев в коде. Сначала рисуется замкнутая ломаная линия (путь коммивояжёра). Затем - окружности городов и поверх них - номера городов. Работа с канавасом в JavaScript несколько громоздка и в дальнейшем мы будем использовать класс draw , который эту работу упрощает и одновременно позволяет получать картинки в svg-формате.

Перебор в таймере

Реализация переборного алгоритма поиска кратчайшего пути в таймере не представляет труда. Для сохранения лучшего пути в массиве minWay , напишем функцию копирования значений элементов массива src в массив des :

Function copy(des, src) { if(des.length !== src.length) des = new Array(src.length); for(var i=0; i

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

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

int BFSearch(char *s, char *p)

for (int i = 1; strlen(s) - strlen(p); i++)

for (int j = 1; strlen(p); j++)

if (p[j] != s)

if (j = strlen(p))

Функция BFSearch ищет подстроку p в строке s и возвращает индекс первого символа подстроки или 0, если подстрока не найдена. Хотя в общем случае этот метод, как и большинство методов грубой силы, малоэффективен, в некоторых ситуациях он вполне приемлем.

Наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке, считается алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), суть которого в следующем.

Алгоритм Бойера-Мура

Простейший вариант алгоритма Бойера-Мура состоит из следующих шагов. На первом шаге строится таблица смещений для искомого образца. Процесс построения таблицы будет описан ниже. Далее совмещается начало строки и образца и начинается проверка с последнего символа образца. Если последний символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. Если же символы совпадают, производится сравнение предпоследнего символа образца и т.д. Если все символы образца совпали с наложенными символами строки, значит найдена подстрока и поиск окончен. Если же какой-то (не последний) символ образца не совпадает с соответствующим символом строки, мы сдвигаем образец на один символ вправо и снова начинаем проверку с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки.

Величина сдвига в случае несовпадения последнего символа вычисляется по правилу: сдвиг образца должен быть минимальным, таким, чтобы не пропустить вхождение образца в строке. Если данный символ строки встречается в образце, то смещается образец таким образом, чтобы символ строки совпал с самым правым вхождением этого символа в образце. Если же образец вообще не содержит этого символа, то образец сдвигается на величину, равную его длине, так что первый символ образца накладывается на следующий за проверявшимся символом строки.

Величина смещения для каждого символа образца зависит только от порядка символов в образце, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа образца. Поясним все вышесказанное на простом примере. Пусть есть набор из пяти символов: a, b, c, d, e и нужно найти вхождение образца “abbad” в строке “abeccacbadbabbad”. Следующие схемы иллюстрируют все этапы выполнения алгоритма:

Таблица смещений для образца “abbad”.

Начало поиска. Последний символ образца не совпадает с наложенным символом строки. Сдвигаем образец вправо на 5 позиций:

Три символа образца совпали, а четвертый – нет. Сдвигаем образец вправо на одну позицию:

Последний символ снова не совпадает с символом строки. В соответствии с таблицей смещений сдвигаем образец на 2 позиции:

Еще раз сдвигаем образец на 2 позиции:

Теперь, в соответствии с таблицей, сдвигаем образец на одну позицию, и получаем искомое вхождение образца:

Реализуем указанный алгоритм. Прежде всего, следует определить тип данных «таблица смещений». Для кодовой таблицы, состоящей из 256 символов, определение структуры будет выглядеть так:

BMTable MakeBMTable(char *p)

for (i = 0; i <= 255; i++) bmt->bmtarr[i] = strlen(p);

for (i = strlen(p); i <= 1; i--)

if (bmt->bmtarr] == strlen(p))

bmt->bmtarr] = strlen(p)-i;

Теперь напишем функцию, осуществляющую поиск.

int BMSearch(int startpos, char *s, char *p)

pos = startpos + lp - 1;

while (pos < strlen(s))

if (p != s) pos = pos + bmt->bmtarr];

for (i = lp - 1; i <= 1; i--)

if (p[i] != s)

return(pos - lp + 1);

Функция BMSearch возвращает позицию первого символа первого вхождения образца p в строке s. Если последовательность p в s не найдена, функция возвращает 0. Параметр startpos позволяет указать позицию в строке s, с которой следует начинать поиск. Это может быть полезно в том случае, если вы захотите найти все вхождения p в s. Для поиска с самого начала строки следует задать startpos равным 1. Если результат поиска не равен нулю, то для того, чтобы найти следующее вхождение p в s, нужно задать startpos равным значению «предыдущий результат плюс длина образца».

Бинарный (двоичный) поиск

Бинарный поиск используется в том случае, если массив, в котором осуществляется поиск, уже упорядочен.

Переменные lb и ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный элемент. Поиск начинается всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, то нужно перейти к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением ub становится (m – 1) и на следующей итерации проверяется половина исходного массива. Таким образом, в результате каждой проверки вдвое сужается область поиска. Например, если в массиве 100 чисел, то после первой итерации область поиска уменьшается до 50 чисел, после второй – до 25, после третьей до 13, после четвертой до 7 и т.д. Если длина массива равна n, то для поиска в массиве элементов достаточно около log 2 n сравнений.

Рис. 11.6. Процедура создания списка Рис. 11.7. Графическое изображение стека Рис. 11.8. Пример бинарного дерева Рис. 11.9. Шаг преобразования дерева к бинарному

Задача сортировки ставится следующим способом. Пусть имеется массив целых или вещественных чисел Требуется переставить элементы этого массива так, чтобы после перестановки они были упорядочены по неубыванию: формула" src="http://hi-edu.ru/e-books/xbook691/files/178-2.gif" border="0" align="absmiddle" alt=" Если числа попарно различны, то говорят об упорядочении по возрастанию или убыванию. В дальнейшем будем рассматривать задачу упорядочения по неубыванию, так как остальные задачи решаются аналогично. Существует множество алгоритмов сортировки, каждый из которых имеет свои характеристики по скорости. Рассмотрим самые простые алгоритмы в порядке увеличения скорости их работы.

Сортировка обменами (пузырьком)

Этот алгоритм считается самым простым и самым медленным. Шаг сортировки состоит в проходе снизу вверх по массиву. При этом просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то они меняются местами.

После первого прохода по массиву «вверху» (в начале массива) оказывается самый «легкий» (минимальный) элемент-отсюда аналогия с пузырьком, который всплывает (рис. 11.1
). Следующий проход делается до второго сверху элемента, таким образом, второй по величине элемент поднимается на правильную позицию и так далее.

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

подзаголовок">Сортировка выбором

Сортировка выбором выполняется несколько быстрее, чем сортировка методом пузырька. Алгоритм заключается в следующем: нужно найти элемент массива, имеющий наименьшее значение, переставить его с первым элементом, затем проделать то же самое, начав со второго элемента и т.д. Таким образом, создается отсортированная последовательность путем присоединения к ней одного элемента за другим в правильном порядке. На i-м шаге выбирается наименьший из элементов a[i] ... а[n], и меняем его местами с a[i]. Последовательность шагов изображена на рис. 11.2
.

Вне зависимости от номера текущего шага i, последовательность a...a[i] является упорядоченной. Таким образом, на(n - 1)-м шаге вся последовательность кроме а[n] оказывается отсортированной, а а[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

подзаголовок">Сортировка простыми вставками

Просматривается массив, и каждый новый элемент a[i] вставляется на подходящее место в уже упорядоченную совокупность a,...,a. Это место определяется последовательным сравнением a[i] с упорядоченными элементами a,...,a. Таким образом, в начале массива «вырастает» отсортированная последовательность.

Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a...a стоят на правильных местах и никуда более не переместятся. В случае сортировки простыми вставками можно утверждать, что последовательность a...a упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы.

Рассмотрим действия алгоритма на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a...a и неупорядоченную a[i]...a[n].

На следующем, i-м каждом шаге алгоритма, берем a[i] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами, и процесс повторяется (рис. 11.3
).

Таким образом, в процессе вставки мы «просеиваем» элемент X к началу массива, останавливаясь в случае, если

• найден элемент, меньший X;
• достигнуто начало последовательности.

опред-е">алгоритмом линейного поиска, когда последовательно проходится весь массив, и текущий элемент массива сравнивается с искомым. В случае совпадения запоминается индекс(ы) найденного элемента.

Однако в задаче поиска может быть множество дополнительных условий. Например, поиск минимального и максимального элемента, поиск подстроки в строке, поиск в массиве, который уже отсортирован, поиск с целью узнать, есть или нет нужный элемент без указания индекса и т.д. Рассмотрим некоторые типовые задачи поиска.

Поиск подстроки в тексте (строке). Алгоритм «грубой силы»

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

Алгоритм «грубой силы» является самым простым и самым медленным и заключается в проверке всех позиций текста на предмет совпадения с началом образца. Если начало образца совпадает, то сравнивается следующая буква в образце и в тексте и так далее до полного совпадения с образцом или отличия с ним в очередной букве.

подзаголовок">Алгоритм Бойера-Мура

Простейший вариант алгоритма Бойера-Мура состоит из следующих шагов. На первом шаге строится таблица смещений для искомого образца. Далее совмещается начало строки и образца и начинается проверка с последнего символа образца. Если последний символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. Если же символы совпадают, производится сравнение предпоследнего символа образца и т.д. Если все символы образца совпали с наложенными символами строки, значит, найдена подстрока, и поиск окончен. Если же какой-то (не последний) символ образца не совпадает с соответствующим символом строки, мы сдвигаем образец на один символ вправо и снова начинаем проверку с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки.

Величина сдвига в случае несовпадения последнего символа вычисляется по правилу: сдвиг образца должен быть минимальным - таким, чтобы не пропустить вхождение образца в строке. Если данный символ строки встречается в образце, то образец смещается таким образом, чтобы символ строки совпал с самым правым вхождением этого символа в образце. Если же образец вообще не содержит этого символа, то образец сдвигается на величину, равную его длине так, что первый символ образца накладывается на следующий за проверявшимся символом строки.

Величина смещения для каждого символа образца зависит только от порядка символов в образце, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа образца. Поясним все вышесказанное на простом примере. Пусть есть набор из пяти символов: а, b, с, d, e и нужно найти вхождение образца «abbad» в строке «abeccacbadbabbad». Следующие схемы иллюстрируют все этапы выполнения алгоритма:

формула" src="http://hi-edu.ru/e-books/xbook691/files/ris-page184-1.gif" border="0" align="absmiddle" alt="

Начало поиска. Последний символ образца не совпадает с наложенным символом строки. Сдвигаем образец вправо на 5 позиций:

формула" src="http://hi-edu.ru/e-books/xbook691/files/ris-page185.gif" border="0" align="absmiddle" alt="

Последний символ снова не совпадает с символом строки. В соответствии с таблицей смещений сдвигаем образец на две позиции:

формула" src="http://hi-edu.ru/e-books/xbook691/files/ris-page185-2.gif" border="0" align="absmiddle" alt="

Теперь в соответствии с таблицей сдвигаем образец на одну позицию и получаем искомое вхождение образца:

формула" src="http://hi-edu.ru/e-books/xbook691/files/ris-page185-4.gif" border="0" align="absmiddle" alt="

формула" src="http://hi-edu.ru/e-books/xbook691/files/ris-page186.gif" border="0" align="absmiddle" alt="

Функция BMSearch возвращает позицию первого символа первого вхождения образца Р в строке S. Если последовательность Р в S не найдена, функция возвращает 0 (напомним, что в ObjectPascal нумерация символов в строке String начинается с 1). Параметр StartPos позволяет указать позицию в строке S, с которой следует начинать поиск. Это может быть полезно в том случае, если требуется найти все вхождения Р в S. Для поиска с самого начала строки следует задать StartPos равным 1. Если результат поиска не равен нулю, то для того, чтобы найти следующее вхождение Р в S, нужно задать StartPos равным значению «предыдущий результат плюс длина образца».

Бинарный (двоичный) поиск

Бинарный поиск используется в том случае, если массив, в котором он осуществляется, уже упорядочен.

Переменные Lb и Ub содержат соответственно левую и правую границы отрезка массива, где находится нужный элемент. Поиск всегда начинается с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, то нужно перейти к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится (М-1), на следующей итерации проверяется половина исходного массива. Таким образом, в результате каждой проверки вдвое сужается область поиска. Например, если в массиве 100 чисел, то после первой итерации область поиска уменьшается до 50 чисел, после второй - до 25, после третьей до 13, после четвертой до 7 и т.д..gif" border="0" align="absmiddle" alt="

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

Например, если указан массив

Var S:array of char,

то под него один раз в начале выполнения программ выделяются 10 байтов оперативной памяти.

Динамические структуры характеризуются непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки.

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

Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным. Элемент динамической структуры состоит из двух полей:

• информационного поля или поля данных, в котором содержатся те данные, ради которых и создается структура; в общем случае информационное поле само является интегрированной структурой: записью, вектором, массивом, другой динамической структурой и т.п.;
• поля связок, в которых содержатся один или несколько указателей, связывающих данный элемент с другими элементами структуры.

Когда связное представление данных применяется для решения прикладной задачи, для конечного пользователя «видимым» делается только содержимое информационного поля, а поле связок используется только программистом-разработчиком.

Достоинства связного представления данных:

• возможность обеспечения значительной изменчивости структур;
• ограничение размера структуры только доступным объемом машинной памяти;
• при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей;
• большая гибкость структуры.

Вместе с тем связное представление не лишено и недостатков, основные из которых:

Последний недостаток - наиболее серьезный, и именно им ограничивается применимость связного представления данных. Если в смежном представлении данных (массивы) для вычисления адреса любого элемента нам во всех случаях достаточно было номера элемента и информации, содержащейся в дескрипторе структуры, то для связного представления адрес элемента не может быть вычислен из исходных данных. Дескриптор связной структуры содержит один или несколько указателей, позволяющих войти в структуру, далее поиск требуемого элемента выполняется следованием по цепочке указателей от элемента к элементу. Поэтому связное представление практически никогда не применяется в задачах, где логическая структура данных имеет вид вектора или массива - с доступом по номеру элемента, но часто применяется в задачах, где логическая структура требует другой исходной информации доступа (таблицы, списки, деревья и т.д.).

К динамическим структурам, используемым в программировании, относятся:

• динамические массивы (были рассмотрены в теме 6);
• линейные списки;
• стек;
• очередь, дек;
• деревья.

Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Длина списка равна числу элементов, содержащихся в нем, список нулевой длины называется пустым. Линейные связные списки являются простейшими динамическими структурами данных.

Графически связи в списках удобно изображать с помощью стрелок, как было показано в разделе описания указателей. Если элемент списка не связан с любым другим, то в поле указателя записывают значение, не указывающее ни на какой элемент (пустой указатель). Такая ссылка в Паскале обозначается Nil, а на схеме обозначается перечеркнутым прямоугольником. Ниже приведена структура односвязного списка (рис. 11.4
), т.е. связь идет от одного элемента списка к другому в одном направлении . Здесь поле D - это информационное поле, в котором находятся данные (любой допустимый в языке Паскаль тип), поле N (NEXT) - указатель на следующий элемент списка.

Каждый список должен иметь следующие указатели: Head - голова списка, Cur - текущий элемент списка, иногда в односвязных списках также используется указатель Tail - хвост списка (в двухсвяхных списках он используется всегда). Поле указателя последнего элемента списка пустое, в нем находится специальный признак Nil, свидетельствующий о конце списка и обозначаемый перечеркнутым квадратом.

Двухсвязный линейный список отличается от односвязного наличием в каждом узле списка еще одного указателя В (Back), ссылающегося на предыдущий элемент списка (рис. 11.5
).

Структура данных, соответствующая двухсвязному линейному списку описывается на языке Паскаль следующим образом:

маркер">

Метод Грубой Силы

Полный перебор (или метод «грубой силы» от англ. brute force ) - метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от размерности пространства всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

Смотреть что такое "Метод Грубой Силы" в других словарях:

Полный перебор (или метод «грубой силы» от англ. brute force) метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от размерности пространства всех возможных решений задачи. Если пространство решений… … Википедия

Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) простой алгоритм сортировки. Для понимания и реализации этот алгоритм простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²). Алгоритм… … Википедия

У этого термина существуют и другие значения, см. Перебор. Полный перебор (или метод «грубой силы», англ. brute force) метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных… … Википедия

Обложка первого издания брошюры «Документы Бейла…» Криптограммы Бейла три зашифрованных сообщения, как то полагается, несущих в себе информацию о местонахождении клада из золота, серебра и драгоценных камней, зарытого якобы на терр … Википедия

Snefru это криптографическая однонаправленная хеш функция, предложенная Ральфом Мерклом. (Само название Snefru, продолжая традиции блочных шифров Khufu и Khafre, также разработанных Ральфом Мерклом, представляет собой имя египетского… … Википедия

Попытка взлома (дешифрования) данных, зашифрованных блочным шифром. К блочным шифрам применимы все основные типы атак, однако существуют некоторые, специфичные лишь для блочных шифров, атаки. Содержание 1 Типы атак 1.1 Общие … Википедия

Нейрокриптография раздел криптографии, изучающий применение стохастических алгоритмов, в частности, нейронных сетей, для шифрования и криптоанализа. Содержание 1 Определение 2 Применение … Википедия

Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600. Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр … Википедия

Криптографическая хеш функция Название N Hash Создан 1990 Опубликован 1990 Размер хеша 128 бит Число раундов 12 или 15 Тип хеш функция N Hash криптографическая … Википедия

Задача коммивояжёра (коммивояжёр бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… … Википедия

У меня есть математическая проблема, которую я решаю методом проб и ошибок (я думаю, это называется грубой силой), и программа отлично работает, когда есть несколько параметров, но по мере добавления дополнительных переменных/данных требуется больше времени и дольше для запуска.

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

3 ответа

Как правило, вы можете количественно оценить, насколько хорошо алгоритм будет масштабироваться, используя нотацию большого вывода для анализа ее темпа роста. Когда вы говорите, что ваш алгоритм работает под "грубой силой", он неясно, в какой степени он будет масштабироваться. Если ваше решение "грубой силы" работает, перечисляя все возможные подмножества или комбинации набора данных, то оно почти наверняка не будет масштабироваться (оно будет иметь асимптотическую сложность O (2 n) или O (n!), соответственно). Если ваше решение для грубой силы работает, найдя все пары элементов и проверив их, оно может масштабироваться достаточно хорошо (O (n 2)). Однако, без дополнительной информации о том, как работает ваш алгоритм, это трудно сказать.

По определению алгоритмы грубой силы глупы. Вам будет намного лучше с более умным алгоритмом (если он у вас есть). Лучший алгоритм уменьшит работу, которая должна быть выполнена, надеюсь, в той степени, в которой вы можете это сделать, не требуя "масштабирования" на нескольких машинах.

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

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

Чтобы убедиться, что рекурсия завершена, важно заказать массив данных. Чтобы быть эффективными и ограничивать количество рекурсий, важно также начать с более высоких значений данных.

Конкретно, здесь рекурсивная реализация Java для этой проблемы - с копией вектора результата coeff для каждой рекурсии, как ожидалось в теории.

Import java.util.Arrays; public class Solver { public static void main(String args) { int target_sum = 100; // pre-requisite: sorted values !! int data = new int { 5, 10, 20, 25, 40, 50 }; // result vector, init to 0 int coeff = new int; Arrays.fill(coeff, 0); partialSum(data.length - 1, target_sum, coeff, data); } private static void printResult(int coeff, int data) { for (int i = coeff.length - 1; i >= 0; i--) { if (coeff[i] > 0) { System.out.print(data[i] + " * " + coeff[i] + " "); } } System.out.println(); } private static void partialSum(int k, int sum, int coeff, int data) { int x_k = data[k]; for (int c = sum / x_k; c >= 0; c--) { coeff[k] = c; if (c * x_k == sum) { printResult(coeff, data); continue; } else if (k > 0) { // contextual result in parameters, local to method scope int newcoeff = Arrays.copyOf(coeff, coeff.length); partialSum(k - 1, sum - c * x_k, newcoeff, data); // for loop on "c" goes on with previous coeff content } } } }

Но теперь этот код находится в специальном случае: последний тест значения для каждого коэффициента равен 0, поэтому копия не нужна.

В качестве оценки сложности мы можем использовать максимальную глубину рекурсивных вызовов как data.length * min({ data }) . Конечно, он не будет хорошо масштабироваться, а ограниченным фактором будет память трассировки стека (опция -Xss JVM). Код может выйти из строя с ошибкой для большого набора data .

Чтобы избежать этих недостатков, процесс "прекращения" полезен. Он заключается в замене стека вызовов метода на программный стек для хранения контекста выполнения для последующей обработки. Вот код для этого:

Import java.util.Arrays; import java.util.ArrayDeque; import java.util.Queue; public class NonRecursive { // pre-requisite: sorted values !! private static final int data = new int { 5, 10, 20, 25, 40, 50 }; // Context to store intermediate computation or a solution static class Context { int k; int sum; int coeff; Context(int k, int sum, int coeff) { this.k = k; this.sum = sum; this.coeff = coeff; } } private static void printResult(int coeff) { for (int i = coeff.length - 1; i >= 0; i--) { if (coeff[i] > 0) { System.out.print(data[i] + " * " + coeff[i] + " "); } } System.out.println(); } public static void main(String args) { int target_sum = 100; // result vector, init to 0 int coeff = new int; Arrays.fill(coeff, 0); // queue with contexts to process Queue contexts = new ArrayDeque(); // initial context contexts.add(new Context(data.length - 1, target_sum, coeff)); while(!contexts.isEmpty()) { Context current = contexts.poll(); int x_k = data; for (int c = current.sum / x_k; c >= 0; c--) { current.coeff = c; int newcoeff = Arrays.copyOf(current.coeff, current.coeff.length); if (c * x_k == current.sum) { printResult(newcoeff); continue; } else if (current.k > 0) { contexts.add(new Context(current.k - 1, current.sum - c * x_k, newcoeff)); } } } } }

С моей точки зрения, трудно быть более эффективным в одном выполнении потока - механизм стека теперь требует копий массива coeff.