Программерские задачки - Страница 8 - Nalchik On Line - Форум Нальчика и КБР
Nalchik On Line - Форум Нальчика и КБР
Вернуться   Nalchik On Line - Форум Нальчика и КБР > Hard & Soft > Soft > Developing
Перезагрузить страницу Программерские задачки
Результаты опроса: Постить ещё задачки?
Нет 0 0%
Да 2 1.15%
Да, и задачи, не связанные с программированием, тоже 0 0%
Да, но не только для С, а и для других языков тоже 1 0.57%
171 98.28%
Голосовавшие: 174. Вы ещё не голосовали в этом опросе

Ответ
Опции темы
  (#106) Непрочитано
grand Master
Сообщений: 1,049
Регистрация: 18.02.2007
Репутация: 76 Рейтинг
10.02.2008, 18:05

Цитата:
Сообщение от Alex Thresher
... Но в этом виде задача очень популярна, быстро узнаваема и крайне проста.
Да, вспомнил, действительно.


Ответить с цитированием
  (#107) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
14.02.2008, 12:03

Задача 16
Задача, на самом деле, решается просто. Воспользуемся терминологией вагонов и включённого/выключенного света.

Пусть тот вагон, в который мы попали в самом начале, будет иметь номер 0. Включим в нём свет. Перейдём в следующий (1-й) вагон, выключим в нём свет. Вернёмся в 0-й вагон: свет выключен? Если да, то в цепочке 1 вагон (только 0-й), если нет, выключим свет во 2-м вагоне и снова проверим 0-й... Количество вагонов в цепочке равно порядковому номеру последнего вагона, в котором был выключен свет.

Итого, чтобы проверить цепочку из N вагонов, нам понадобится O(NІ) операций и О(1) дополнительной памяти (фактически, нужен только счётчик, указывающий текущий вагон, и переменная, содержащая номер последнего вагона, в котором был выключен свет).


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
  (#108) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
09.03.2008, 19:04

Задача 17

Алгоритмическая задача. Знания языков программирования и операционок не нужны.

Существует алгоритм хранения данных, образующий сбалансированное бинарное дерево (см. красно-чёрное дерево). Свойства красно-чёрного дерева: добавление за O(log n), удаление за O(log n). Однако в общем случае, для того, чтобы найти следующий по величине элемент в дереве, надо подниматься по всем родителям данного элемента, пока не появится возможность уйти вправо, а затем спуститься до самого конца, выбирая каждый раз самую левую ветвь. Это занимает O(2h) = O(2 * log(n)) = O(log(n)) времени. Предложите изменение красно-чёрного дерева, которое не изменит остальные его свойства (т.е. добавление за O(log n) и удаление за O(log n)), но позволит найти следующий по величине элемент за О(1).


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
  (#109) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
16.03.2008, 10:33

Что, никто не хочет попробовать свои силы в алгоритмизации?!


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
  (#110) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
19.03.2008, 14:56

Ладно...

Задача 17
Решение, на самом деле, простое: сделать дополнительную структуру данных (читай: двусвязный линейный список), отражающую содержимое дерева в линейном виде, и сделать линки от каждого узла дерева к соответствующему узлу этой структуры. Это можно представить себе в виде "тени" от узлов дерева, которая получилась бы, если бы свет падал вертикально сверху:
Код:
           5                |
     3     .     8          | Дерево (номера - это содержимое узлов)
  1  .  4  .  7  .  9       |
  .  .  .  .  .  .  . 
  .  .  .  .  .  .  .       | указатели между деревом и дополнительной структурой-"тенью"
  .  .  .  .  .  .  .
  1' 3' 4' 5' 7' 8' 9'      | дополнительная структура (двусвязный список)
Легко доказать, что ротации красно-чёрного дерева эту структуру менять не будут. Формальное доказательство я здесь приводить не буду, но основная логика понятна и так: дерево всегда строится таким образом, чтобы каждый элемент был больше любого левого, но меньше любого правого. Ротации не заставляют элементы меняться местами, меняются только указатели; значит, вследствие ротаций содержимое этой дополнительной структуры, отражающей порядок элементов в дереве, не изменится.

Добавление элемента теперь будет включать в себя создание нового узла в дополнительной структуре-"тени". Поскольку новый элемент в дереве всегда добавляется к уже существующему, а у существующего есть указатель на соответствущий ему объект-"тень", то при добавлении надо будет только изменить несколько указателей в структуре-"тени". (Внесение элемента в двусвязный список рядом с другим известным элементом, думаю, каждый сможет написать). Поскольку выполняется конечное количество действий, то сложность операции добавления (O(log n)) не изменится.

Удаление ещё проще: в самом удаляемом элементе есть указатель на его собственную "тень". Удалить объект из двусвязного списка легко, и тоже занимает конечное количество операций, поэтому удаление узла из дерева по-прежнему займёт O(log n) времени.

Зато теперь для каждого узла дерева будут известны следующий и предыдущий узлы за конечное число действий - O(1).


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
  (#111) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
19.03.2008, 18:49

Задача 18
Попробуем всё же выжать из вас хоть что-нибудь по алгоритмике. Знания языков программирования и операционных систем не нужны.

Дано бинарное дерево и два указателя на какие-то узлы в нём. Задача: найти самого нижнего их общего родителя (понятно, что самый верхний всегда будет корневым узлом).

Возможных решений здесь уйма, поэтому я ограничу варианты:
  1. В каждом узле есть переменная, содержимое которой можно менять;
  2. Менять содержимое узлов нельзя, но есть O(n) доступной дополнительной памяти;
  3. Менять содержимое узлов нельзя, но есть O(1) доступной дополнительной памяти.
Разумеется, требуется описать свой алгоритм для каждого случая и объяснить, почему он наиболее эффективен.

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


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
  (#112) Непрочитано
grand Master
Сообщений: 1,049
Регистрация: 18.02.2007
Репутация: 76 Рейтинг
19.03.2008, 20:55

1. Начальное заполнение неизвестно. Первый пробегает до корня, поднимая флажок. Второй пробегает до корня, сбрасывая флажок. Первый снова бежит к корню, до первого сброшенного флажка.
2. Идем от обоих узлов до корня с трассировкой, т.е. записывая путь. Потом по этим путям параллельно идем в обратную сторону, от корня, пока не найдем первое отличие.
3. Идем от обоих узлов до корня, запоминаем расстояние от корня. Поднимаем более глубокий до одного уровня с менее глубоким. Далее синхронно обоими идем вверх, до первого совпадения.


Ответить с цитированием
  (#113) Непрочитано
Maniac
grand Master
Аватар для SiERRA
Сообщений: 12,520
Регистрация: 04.10.2008
Адрес: Нальчик
Возраст: 31
Репутация: 1414 Рейтинг
19.11.2015, 12:50

не знал куда запостить



Посетить домашнюю страницу SiERRA
Ответить с цитированием
Понравилось: Понравилось: Мышь (19.11.2015), Валерка (19.11.2015), Волченок (20.11.2015), ewcha (19.11.2015), PhilL (19.11.2015), Um_nic (11.03.2021), Zid@ne (19.11.2015)
  (#114) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
Talking 11.03.2021, 03:16

Задача 19.

Ну что, воскресим старую тему?

Вот в этом сообщении я дал условие задачи № 5: «Определить, зацикливается ли однонаправленный связный список». А вот здесь дал решение для трёх вариантов: 1) элементы списка можно менять, 2) элементы списка менять нельзя, но есть много дополнительной памяти, 3) элементы списка менять нельзя, и есть фиксированное количество дополнительной памяти.

Решение для третьего варианта — так называемый алгоритм «Заяц и черепаха», предложенный в 1967 году Робертом Флойдом и популяризированный Дональдом Кнутом, — доказанно является наиболее оптимальным для этой задачи. Решение состоит в создании двух указателей, один из которых («черепаха») за каждую итерацию цикла перемещается на один шаг, а другой («заяц») — на два. Либо «заяц» добежит до конца списка, либо в какой-то момент он будет указывать на тот же элемент, что и «черепаха», и произойдёт это не больше чем за O(n).

Но не всегда есть возможность идти оптимальным путём. Поэтому вот вам четвёртый вариант этого условия:
4) Дан тот же самый однонаправленный связный список, менять содержимое нельзя. Нужно узнать, зацикливается ли он, при том, что:
  • количество дополнительной памяти, которую можно использовать, это О(1),
  • и при этом разрешается использовать только один указатель.
С этой задачей именно в таком варианте мне пришлось столкнуться в реальной жизни, по работе.

Последний раз редактировалось Alex Thresher; 11.03.2021 в 12:32. Причина: Форматирование


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
  (#115) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
18.03.2021, 14:18

Что-то я не вижу желающих решить. Ладно... Публикую решение:

Задача 19

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

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

Итак, во время прохода по связному списку я смотрю на встретившиеся мне адреса элементов и запоминаю самый маленький и самый большой из них (2 переменные). Вдобавок я начинаю считать посещённые элементы (1 переменная). Зная размер элемента и разницу между самым большим и самым маленьким адресами, я могу разделить второе на первое и посчитать, сколько элементов теоретически могло бы разместиться в этой памяти, если бы они занимали её всю (1 переменная), — на самом деле их там, скорее всего, меньше. Я считаю шаги, и если я в какой-то момент сделал уже больше шагов, чем может быть элементов, но при этом не вышел за границы памяти, значит, согласно принципу Дирихле, хотя бы один элемент я посетил дважды. Если же я выхожу за установленные ранее границы, тогда я запоминаю новые границы и соответственно меняю верхний предел количества элементов. Все посещённые ранее элементы лежат внутри новых, расширенных границ, поэтому можно продолжать считать с достигнутого числа шагов, а не сбрасывать счётчик шагов.

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

Этот алгоритм не является быстрым, однако он позволяет решить задачу, используя только один указатель, над которым нет контроля, и считанное число дополнительных переменных, — которые, правда, могут быть довольно большими.

Последний раз редактировалось Alex Thresher; 18.03.2021 в 14:22.


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
Ответ


Вернуться Nalchik On Line - Форум Нальчика и КБР > Hard & Soft > Soft > Developing

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Логические задачки Аха БеседКа 1329 31.08.2020 17:21
В школьных классах решают межнациональные задачки и отвечают на межэтнические вопросы никанет Новости 103 21.12.2013 11:04
Включаем мозги... Решаем задачки dzora93 БеседКа 17 24.12.2011 01:09
Веселые задачки AcedTect Флудилка 54 30.04.2011 08:04