Рубрика «рекурсия» - 3

в 8:10, , рубрики: php, Алгоритмы, алгоритмы поиска, древовидное меню, древовидные структуры, ненормальное программирование, рекурсивные запросы, рекурсивные перечисления, рекурсия

К написанию этой статьи сподвигли многие часы раздумий и экспериментов в области построения иерархических списков. Изначально логика обкатывалась на SQL запросах на стороне СУБД, но особенности этого языка заставили выполнить реализацию на стороне приложения PHP. Здесь я покажу как пройти от корня иерархии до каждого конечного элемента и обратно, логика реализуема на любом языке программирования.

Итак, тестовая иерархия, с которой нам предстоит работать:

image

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

Создадим таблицу:

CREATE TABLE [dbo].[Test](
	[uid] [int] IDENTITY(1,1) NOT NULL,  -- уникальное поле, автоинкрементное
	[pid] [int] NULL,                    -- это поле указывает на элемент уровнем выше, содержит uid родителя
	[name] [varchar](255) NULL,
	[access] [varchar](50) NULL,         -- права доступа
) ON [PRIMARY]

Читать полностью »

в 11:19, , рубрики: java, Алгоритмы, задачи, Программирование, рекурсия

Здравствуй!

В этой статье речь пойдет о задачах на рекурсию и о том как их решать.
image

Кратко о рекурсии

Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Самый простой вариант увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.

В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию).

О рекурсии сказано много. Вот несколько хороших ресурсов:
Читать полностью »

в 13:41, , рубрики: bzip2, Deflate, PNG, zip-бомба, zlib, архиватор, Демосцена, информационная безопасность, рекурсия

В старые времена были популярны zip-бомбы. Такая бомба — это рекурсивный архив, который распаковывается сам в себя. Его иногда можно использовать для DoS-атаки. Например, пресловутый файл 42.zip имеет размер 42 килобайта. Если начать его распаковку, то процесс будет идти до тех пор, пока набор данных не достигнет верхнего предела распаковки в 4,3 гигабайта. При этом процесс займет более 4,5 петабайт в оперативной памяти (4 503 599 626 321 920 байт).

Программист и хакер Дэвид Фифилд (David Fifield) задумался, где ещё можно применить «архивные бомбы». Сразу на ум приходит графический формат PNG, в котором используется алгоритм сжатия DEFLATE в библиотеке zlib.
Читать полностью »

в 8:05, , рубрики: C, c++, python, Алгоритмы, и все-все-все, не дао, не затем их пишут, Не читайте теги, несчастная функция, постижение достижений, Программирование, прокрустова архитектура, рекурсия, Серверная оптимизация, Совершенный код

Рекурсия: см. рекурсия.

О бедной рекурсии замолвите слово, или всё, что вы не знали и не хотите о ней знать - 1Все программисты делятся на 112 категорий: кто не понимает рекурсию, кто уже понял, и кто научился ею пользоваться. В общем, гурилка из меня исключительно картонный, так что постигать Дао Рекурсии тебе, читатель, всё равно придётся самостоятельно, я лишь постараюсь выдать несколько волшебных пенделей в нужном направлении.

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

— Как она сложена?
— Превосходно! Только рука немного торчит из чемодана.

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

  def fib(n):
    if n<0: raise Exception("fib(n) defined for n>=0")
    if n>1: return fib(n-1) + fib(n-2)
    return n

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

  @memoized
  def fib(n):
    if n<0: raise Exception("fib(n) defined for n>=0")
    if n>1: return fib(n-1) + fib(n-2)
    return n

И заканчивая вообще:

  def fib(n):
    if n<0: raise Exception("fib(n) defined for n>=0")
    n0 = 0
    n1 = 1
    for k in range(n):
      n0, n1 = n1, n0+n1
    return n0

Читать полностью »

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

Недавно очередной раз отработал со студентам 2-го курса 2-семестровую дисциплину «Алгоритмические языки». Обзорно рассмотрели несколько дюжин языков программирования. Один из студентов, Вадим Шукалюк, захотел получше с ними познакомиться, получить более четкое представление о каждом из них. Посоветовал ему провести небольшое исследование. Чем и увлёк. Предлагаю свой отчёт по проделанной за несколько месяцев вместе с ним работе.

У каждого языка программирования есть свои достоинства и недостатки. Одна из важнейших характеристик транслятора с любого языка — это скорость исполнения программ. Очень трудно или даже невозможно получить точную оценку такой скорости исполнения. Ресурс http://benchmarksgame.alioth.debian.org/ предлагает игровую форму для проверки такой скорости на разных задачах. Но число языков, представленных на этом ресурсе, довольно невелико. Предельную ёмкость стека, критическую величину для рекурсивных вычислений проверить проще, но она может меняться в разных версиях транслятора и быть зависимой от системных настроек.

Тестировались следующие трансляторы: си (gcc, clang, icc), ассемблер (x86, x86-64), ява (OpenJDK), паскаль (fpc), яваскрипт (Google Chrome, Mozilla Firefox), лисп (sbcl, clisp), эрланг, хаскель (ghc, hugs), дино[1], аук (gawk, mawk, busybox), луа, рубин, бейсик (gambas, libre office), питон-2, пи-эйч-пи, постскрипт (gs), пролог (swipl, gprolog), перл, метапост, ТEХ, тикль, бэш. Исследовались как собственно скорость исполнения нескольких небольших, но трудоёмких алгоритмов, так и:

  • качество оптимизации некоторых трансляторов;
  • особенности при работе с процессорами Intel и AMD;
  • предельное число рекурсивных вызовов (ёмкость стека).

Читать полностью »

в 12:26, , рубрики: javascript, odata, rest, rest api, RESTful, restful api, Веб-разработка, интерфейсы, Программирование, рекурсивные запросы, рекурсия

В дискуссии к предыдущей статье dezconnect поднял интересный вопрос о возможностях OData выполнять рекурсивные запросы (по аналогии с SQL CTE).

В документации OData в разделе 11.2.4.2 описывается опция запроса $expand. Эта опция позволяет получать объекты вместе со связанными объектами. Например, Вы можете получить данные о компании вместе со всеми данными о ее президенте:
http://nitrosdata.com/service/testdb/company(company1)?$expand=president

Без опции $expand результат будет включать только id президента компании (или ссылку при других настройках).
http://nitrosdata.com/service/testdb/company(company1)

В 4й версии OData существенно расширены возможности опции $expand для выполнения рекурсивных запросов.

Читать полностью »

в 14:20, , рубрики: python, ненормальное программирование, рекурсия, метки: , ,

Читая главу «Двоичные деревья» из книги Джона Монгана Programming Interviews Exposed я задумался о том, как чаще всего рекурсию объясняют начинающим программистам: через сортировку, обход двоичного дерева, построение последовательности Фибоначчи и т.д. Неужели нельзя найти пример поинтереснее? Из закоулков сознания вырвался Лисп, который по своей природе неотделим от понятия рекурсии. Более того, небольшой интерпретатор Лиспа — отличный пример для исследования рекурсии.

Каким же будет минимальный интерпретатор Лиспа, написанный на Питоне? К моему удивлению, решение уложилось в семь строк! Свою роль в этом сыграла как выразительность Питона, так и красота и незамысловатость Лиспа.
Читать полностью »

в 15:04, , рубрики: c++, брутфорс, головоломка, рекурсия, метки: , ,

Предыстория

Чтобы летом держать мозг в тонусе я скачал себе сборник головоломок. По началу задания были довольно простыми и не особо требовательными к проявлению логики, но по ходу игры чувствовалось нарастающее усложнение.
В какой-то момент я застрял на головоломке под названием «Китайские шашки». Редкие потуги решить её своими силами не приносили особых плодов на протяжение долгого времени и в итоге я отложил свои муки с решением до лучших времен.
Закончилась зимняя сессия, а до начала учебы еще пара недель — чем не «лучшие времена»? Я заглянул в интернет, дабы проверить есть ли у данной головоломки вообще хоть какое-нибудь решение, и первые же результаты поискового запроса убедили меня в том, что оно действительно существует.
Я не стал подглядывать в прохождение, мне хотелось дойти до него своими силами — или самому решить, или написать программу, которая найдет мне это решение. Однако напрямую применить силу мозга мне так и не удалось, я явно упускал из виду что-то принципиально важное для нахождения решения.
— «Ну всё, пусть эта головоломка поговорит с моим многоядерным другом!» — пронеслось у меня в голове, и я сел за написание брутфорса.

Читать полностью »

в 21:24, , рубрики: автореферентность, квайн, куайн, ненормальное программирование, рекурсия, метки: , , ,

В связи с тем, что моя первая статья, Мультиязыковые квайны, похоже, понравилась коллегам-программистам, хочу продолжить и написать ещё несколько статей про всякие автореферентные штуки. Меня всегда поражала автореферентность — рекурсия, фракталы, квайны, человеческое самосознание… Сейчас я начну разглагольствовать и мне совершенно справедливо накидают чего-нибудь нехорошего в карму. Я лучше посоветую прочитать «Гёдель Эшер Бах» Хофштадтера тем, кто ещё не читал. Это гениальная книга и гимн автореферентности. А теперь к делу.

Автограммы.

Пока программисты пишут квайны на разных языках, те, кто программирование ещё по каким-либо причинам не освоил, могут заняться не менее интересным и довольно таки похожим делом — сочинением автограмм.
Автограммы — это предложения на естественном языке, описывающие собственную внутреннюю структуру.
Читать полностью »

в 13:43, , рубрики: Программирование, рекурсия, метки:

Исследуя обширные пространства интернета мне пришлось потрудиться над тем как же все таки создать не тяжеловесный код на asp.net c# для обработки так называемых «свинных ушей», которые содержат классическую модель родитель-потомок в базе данных. Сразу оговорюсь база в SQL Server 2008, который уже имеет возможность работы с иерархическими данными в ОТВ(CTE — английский вариант аббревиатуры).
Читать полностью »

1...234
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js