описание гипотезы Коллатца в вики https://ru.wikipedia.org/wiki/Гипотеза_Коллатца цитирую : Берём любое натуральное число N. Если оно чётное, то делим его на 2, а если нечётное, то умножаем на 3 и прибавляем 1 (получаем 3*N + 1). Над полученным числом выполняем те же самые действия, и так далее. Гипотеза Коллатца заключается в том, что какое бы начальное число N мы ни взяли, рано или поздно мы получим единицу.
Попробуем сделать шаг в сторону и исследовать преобразование с вычитанием 1 т.е. умножаем на3 и вычитаем 1 (получаем 3*N - 1). результат делим на 2 до нечетного значения и т.д. Результат с вычитанием 1 состоит в том, что есть несколько точек остановки, а не только в единице. Примеры c преобразованием вида 3*N-1 :
Целью данной публикации попытка предложить способ расчета синуса и косинуса достаточно быстро для тех платформ, где отсутствуют эти функции (микроконтроллеры) или там где скорость расчета важнее точности.
Хочу предложить Хабру свою версию нерекурсивного алгоритма генерации всех разбиений целого числа в лексикографическом порядке. Толчком послужила майская заметка. В предлагаемом алгоритме также идея переноса крайне правого элемента.
Причины по которым захотелось предложить свой вариант алгоритма в том, что во всех увиденных мной алгоритмах на каждом шагу есть поиск по массиву. Мне показалось это несколько избыточным. Сам алгоритм будем рассматривать как описание перестановки единичных кубиков (квадратиков) на плоскости (справа налево) и их периодическое рассыпание по горизонтальной оси.
Предлагаемый ниже нерекурсивный алгоритм несколько отличается от изложенных в книге Липского [1] и обнаруженных мной в русскоязычном сегменте интернета. Надеюсь будет интересно.
Ниже приведен алгоритм точного решения целочисленной задачи о рюкзаке. Предлагаемый алгоритм требует меньше вычислительных ресурсов и возможно несколько проще алгоритма динамического программирования (ДП).
Причина побудившая автора к публикации
Первая версия описания алгоритма было послана мною в институт математики им. С. Л. Соболева Сибирского отделения РАН, откуда был прислан ответ что указанный алгоритм известен давно. Цитирую:
Одно из его первых упоминаний в книге Кереллера Nemhauser, Ullman, Discrete dynamic programming and capital allocation, Management Science, 15 p. 494-505, 1969.
Тем не менее я решил ознакомить сообщество с алгоритмом, т.к. в известных мне учебниках по дискретной математике я его не обнаружил (возможно плохо искал). В первой версии алгоритма была ошибка, указанная мне пользователем wataru. За это ему большое спасибо. Я постарался эту ошибку устранить. До алгоритма я дошел самостоятельно, так что надеюсь ничьих прав не нарушаю. Возможно кому нибудь описание будет интересно и пригодится.
