Исследование логических задачек

[fantik]

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

Я когда ещё учился в школе, ещё когда сталкивался с физикой (и в общем-то любил её), т.е. в 10 классе, я услышал эту задачку от нашего учителя - замечательного физика...

Правда она звучала в таком контексте:
"Типа в мои годы был случай... Абитуриенту в МИФИ сказали: хочешь поступить без экзаменов - реши задачку. Отвели этого ещё школьника на крышу здания МИФИшного, дали в руки барометр, секундомер и калькулятор и сказали: какова высота этого здания?
И типа этот чувак должен был догадаться, что барометр нужен для того, чтобы считать, скока летит вообще какая-нить хрень с крыши...
И типа чувак догадался и поступил без экзаменов" ))

[fantik]

А ещё я помню была такая байка...

Типа тоже в МИФИ экзамен по физике... Дело летом, жара... И профессоров все студенты задолбали... Ну один из них взял и перевернул график на подоконнике другой стороной и каждого входящего студента просит объяснить: "Почему солнце с той стороны светит, а графин здесь нагревается"...

Ну чуваки - народ сообразительный, никто не знают, но все давай
отвечать: "При наложении когерентных волн образуется дифракция..."
Профессора ржут, но автомат не ставят...

И тут типа заходит один студентик... И так сходу и отвечает: "Да какой-то дебил его просто взял да перевернул"....

Экзаменационная комиссия вся от смеха легла, а студенту тому пятёрку сразу поставили... за смелость и смекалку ))

[Eugene]

А ещё я помню была такая байка...

И тут типа заходит один студентик... И так сходу и отвечает: "Да какой-то дебил его просто взял да перевернул"....

Экзаменационная комиссия вся от смеха легла...

Студент сказал не "дебил", а "козёл". Это важно, потому что весь юмор состоял в том, что у пошутившего препода фамилия была КОзел. С ударением на первом слоге.

[iOleg]

Про альпиниста так и не решил - точнее решил, но весьма опасным методом - наподобие баджо-джампинга Т.е. приявязать 50 м. кусок веревки вверху и на уступе и, прямо по середине и крепко держась, обрезать его и изображать Тарзана с криками ИХАААА. Накатавшись вдоволь использовать 25 м кусок для того, чтобы сползти вниз.

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

Инсеадовская задачка пока в голове Интересно было бы решить

Соросовская прикольная... Я зачем-то думал построить типа домика и внутри измерить его диагональ. Оказывается трех кирпичей вполне хватит

Про пятерки и 21 неинтересно - простым подборм вариантов решается, не стал заморачиваться

Про Нильса Бора чумовая!

[iOleg]

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

Вполне жизнеспособные методы имхо! Ты прям Нильс Бор какой-то

[GM]

x iOleg
"Про Нильса Бора чумовая!"

Тогда вот Вам её продолжение, наслаждайтесь :

"А вот и рещения задачи предложенные им:

Измерить время падения барометра с вершины башни. Высота башни однозначно рассчитывается через время и ускорение свободного падения.
Данное решение является наиболее традиционным и потому наименее интересным.


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


Измерить время всплывания барометра со дна заполненной водой башни . Скорость всплывания барометра измерить в ближайшем бассейне
или ведре. В случае , если барометр тяжелее воды , привязать к нему воздушный шарик.


Положить барометр на башню . Измерить величину деформации сжатия башни. Высота башни находится через закон Гука.


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


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


Натереть барометром шерсть на вершине и у основания башни. Измерить силу взаимного отталкивания вершины и основания. Она будет
обратно пропорциональна высоте башни.


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


Положить башню на землю. Перекатывать барометр от вершины к основанию,считая число оборотов.(Способ имени 38 попугаев)


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


Измерить вес барометра на поверхности и на дне ямы, полученной в предыдущем опыте. Разность значений однозначно определит высоту
башни.


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


Поставить башню на барометр, измерить величину деформации барометра. Для расчета высоты башни необходимо также знать ее массу и
диаметр.


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


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


Нагреть воздух в башне до определенной температуры, предварительно ее загерметизировав. Проделать в башне дырочку, около которой
закрепить на пружине барометр. Построить график зависимости натяжения пружины от времени. Проинтегрировать график и, зная диаметр
отверстия, найти количество воздуха,вышедшее из башни вследствие теплового расширения. Эта величина будет прямо пропорциональна
объему башни. Зная объем и диаметр башни, элементарно находим ее высоту.


Измерить с помощью барометра высоту половины башни. Высоту башни вычислить, умножив полученное значение на 2.


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


Выкачать из башни воздух. Закачать его туда снова в строго фиксированном количестве. Измерить барометром давление (!) внутри башни. Оно
будет обратно пропорционально объему башни. А по объему высоту мы уже находили.


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


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


Уравновесить башню и барометр на рычаге. Зная плотность и диаметр башни, плечи рычага и массу барометра, рассчитать высоту башни.


Измерить разность потенциальных энергий барометра на вершине и у основания башни. Она будет прямо пропорциональна высоте башни.


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


Поместить барометр в произвольной точке пространства. Измерить расстояние между барометром и вершиной и между барометром и
основанием башни,а также угол между направлением от барометра на вершину и основание. Высоту башни рассчитать по теореме косинусов."

[IvanGr]

...Неужели никто не знает вариант с тремя выключателями и ТРЕМЯ лампочками? )

Условие формулируй - узнаем.

Жень, да то же самое там, и решение то же, просто в итоге имеем одну горящую лампочку, одну теплую и не горящую, и одну холодную и не горящую...

[visitoR]

Уважаемые!
Опубликуйте, пожалуйста, решение задачки про 12 шариков!
(Судя по молчанию в этой теме, можно считать, что все интересующиеся ее уже порешали.)

[GM]

Решение Eugene:

Дано: 12 внешне идентичных шариков, из которых 11 - стандартных и 1 - уникальный, вес которого отличен от других. Найти уникальный и выяснить, легче или тяжелее он по отношению к стандарту. Использовать не более 3 сравнений-взвешиваний.
Алгоритм решения:
1. Разбить 12 ш. на 3 группы по 4 ш. в каждой.
2. Сравнить вес двух из групп между собой.
3. Если вес групп не равен, перейти к п. 10.
4. Поскольку вес обеих групп равен, они содержат только стандартные шарики. Возьмем 3 из них и сравним с 3 из оставшихся 4 подозрительных.
5. Если взвешивание показало не равный вес, перейти к п. 7.
6. Уникальный шарик - последний оставшийся. Сравнив его вес с любым из стандартных, узнаем, легче он или тяжелее. Задача решена.
7. Если подозрительная группа тяжелее (легче) стандартной, то она содержит уникальный шарик, который соответственно тяжелее (легче) стандартного. Возьмем 2 из 3-х подозрительных шариков и сравним между собой (по одному на каждую чашу весов).
8. Если весы в равновесии, то уникальный шарик - оставшийся из предыдущих трех. Задача решена.
9. Если вес шариков не равный, выберем из них уникальный по определенному в п. 7 условию. Задача решена.
10. Если сравнение групп по 4 в п.2 дало не равновесный результат, отметим для дальнейшего исследования шарики в "тяжелой" и в "легкой" группе. Оставшиеся 4 шарика отметим как гарантировано стандартные. Возьмем 2 "тяжелых" и 2 "легких" шарика на одну чашу весов и 1 "легкий" и 3 стандартных на другую чашу.
11. Если взвешивание показывает равновесие, то уникальный шарик - один из трех оставшихся вне весов шариков: двух "тяжелых" и одного "легкого". Иначе, перейти к п. 14.
12. Сравним между собой два оставшихся "тяжелых".
13. Если сравнение выявило более тяжелый шарик, то он - уникальный. Иначе - уникальный оставшийся "легкий". Задача решена.
14. Если взвешивание показывает, что 2 "тяжелых" + 2 "легких" тяжелее 1 "легкого" с 3 стандартными, то уникальный шарик либо "легкий" со второй чаши, либо - один из двух "тяжелых" с первой чаши. Далее перейти к п. 12.
15. В последнем возможном варианте результатов взвешивания в п. 10, уникальный шарик - один из двух "легких" с первой чаши. Сравним один из них с любым стандартным.
16. Если взвешивание выявило более легкий шарик, то он - искомый уникальный. Иначе, уникальный - оставшийся вне весов легкий шарик. Задача решена.
P.S. Мой опыт показывает, что со спичками задачку решает рано или поздно практически каждый первый.

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

[Froggetta]

Уважаемые!
Опубликуйте, пожалуйста, решение задачки про 12 шариков!
(Судя по молчанию в этой теме, можно считать, что все интересующиеся ее уже порешали.)

СМОТРИ ТУТ: http://salsa.ru/modules.php?name=Forums&file=viewtopic&t=574&postdays=0&postorder=asc&start=570&sid=9b10359ff03c25cfad0f4756da1f2055

[visitoR]

Спасибо!
А я перестал пытаться решать после того, как понял, что следующая задача решается только за 2 взвешивания:

есть 2 шарика: 1 правильный и 1 неправильный. Найти неправильный и сказать, тяжелее он или легче, при наличии еще одного известного правильного шарика.

Правда, забавно?!

[Eugene]

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

Напоминаю, в черчении перспектива не учитывается; линиями изображаются ребра, т.е. пересечения плоскостей поверхности тела; невидимые линии изображаются штриховой линией (на рисунке их нет - значит, их и на самом деле нет!)
Удачных плодов пространственного воображения!

[IvanGr]

Жень, мне вот кажется, что спереди это дело - просто большой квадрат, и ссё...

[Eugene]

Жень, мне вот кажется, что спереди это дело - просто большой квадрат, и ссё...

Нееее

[fantik]

Жень, а у этого тела могут быть непрямые углы???
У меня вот какая мысль появилась :

[fantik]

ПОчему-то не виден рисунок... сначала был виден???
http://clubs.mfd.ru/pictures/picture.asp?pict_name=Puzzle_view.jpg&pict_id=529
По этой ссылке его мона увидеть

[Eugene]

...По этой ссылке его мона увидеть

Решение, конечно, правильное.
Но стоило ли его вешать на всеобщее обозрение? Может, кто хочет сам порешать?  

[iOleg]

...По этой ссылке его мона увидеть

Решение, конечно, правильное.
Но стоило ли его вешать на всеобщее обозрение? Может, кто хочет сам порешать?  

Я не решил ) хоть и визуал )

[fantik]

...По этой ссылке его мона увидеть

Решение, конечно, правильное.
Но стоило ли его вешать на всеобщее обозрение? Может, кто хочет сам порешать?  

Жень, Ты прав абсолютно, что не стоило...
Я просто сначала никак не мог придумать, как послать картинку в ЛС...
....
Надо было просто ссылку послать...
....
Хотя, я вот когда начал читать ветку, из которой эта тема выросла - специально до конца не дочитывал, чтобы самому подумать...

[fantik]

А кстати - новая задачка....
Правда, она больше математическая, чем логическая...

Пришло несколько полных контейнеров с телевизорами на вокзал. Контейнеры разгрузили, загрузив телевизорами вагоны поезда... Получилось 7 вагонов и ещё пять телевизоров лишних остались...

На след. день пришло опять несколько полных контейнеров с телевизорами... Опять разгрузили-загрузили, получилось 12 вагонов без одного телевизора (т.е. 11 полных и один вагон без одного телевизора)...

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

[Ksenia]

А кстати - новая задачка....

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

А точно вопрос в том, сколько телевизоров помещается в контейнер,
может быть в Вагон

и еще вопросик:  пять телевизоров, которые остались - "их" погрузили на следующий день?

Спасибо

[Eugene]

А точно вопрос в том, сколько телевизоров помещается в контейнер, может быть в Вагон

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

[fantik]

А точно вопрос в том, сколько телевизоров помещается в контейнер, может быть в Вагон

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

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

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

[visitoR]

Емкость вагона может быть разной. Ее можно вычислить следующим образом: ((3 + i * 7) * <емкость контейнера> - 5) / 7, где i = 0, 1, ...
Естественно, есть еще одна формула дающая те же значения.

[visitoR]

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

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

- дан односвязный (цепной) список и два указателя на его голову. Определить, есть ли в списке циклы (без использования дополнительных переменных).

[Froggetta]

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

.... скажи, а вот переменным какие значения присвоить?
________________________________
Не зная покоя и отдыха
При лунном и солнечном свете
Мы делаем деньги из воздуха
Чтоб снова пустить их на ветер

[Eugene]

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

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

- дан односвязный (цепной) список и два указателя на его голову. Определить, есть ли в списке циклы (без использования дополнительных переменных).

По первому пункту - используйте стек. Инструкции push и pop.
По второму. В Си практически не используются цепные списки, только как наследство из Паскаля. Поясни, что такое циклы в списке, которые надо искать.

[zmij]

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

По первому пункту - используйте стек. Инструкции push и pop.

стек нафик не нужен.

Код: [Выделить]

a ^= b ^= a ^= b;

[zmij]

дан односвязный (цепной) список и два указателя на его голову. Определить, есть ли в списке циклы (без использования дополнительных переменных).

список модифицировать можно?

[Eugene]

Раз логические и математические задачки закончились...

Ну как это, "кончились". Вот еще одна древнеегипетская задачка.
Чуть предыстории. Это уже серьезная математическая задача, которая была своеобразным вступительным экзаменом для желающих стать жрецом. Напомню, что выше жрецов там были только фараоны, так что отбирали кандидатов в этот "интеллектуальный спецназ" весьма строго. Претендента заводили в комнату со священным колодцем (о котором и будет задача), давали камень и долото, чтобы выбить ответ, и замуровывали, оставляя только маленькое окошко для света, воздуха и возможности выбросить камень с ответом. Если ответ был правильным, камеру размуровывали и экзаменующийся уже выходил оттуда в ранге жреца. А если не правильным, то... правильно, просто не размуровывали.
Теперь к сути задачи. В круглом священном колодце уровень воды от дна ровно один локоть. В него также опущены две тростинки: одна длиной 2 локтя, другая - 3 локтя. Тростинки упираются нижним концом в края дна, верхним - в стену на противоположной стороне (см. рисунок). Тростинки пересекаются ровно на уровне воды. Требуется определить диаметр священного колодца.

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

[visitoR]

Продвинутым программистам модифицировать список нельзя! (Я сам додумался только до решения с разрушением списка)

[visitoR]

По первому пункту - используйте стек. Инструкции push и pop.

Я переформулирую: без использования дополнительной памяти (хотя ответ уже дан)

По второму. В Си практически не используются цепные списки, только как наследство из Паскаля. Поясни, что такое циклы в списке, которые надо искать.

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

[Eugene]

По первому пункту - используйте стек. Инструкции push и pop.

Я переформулирую: без использования дополнительной памяти (хотя ответ уже дан)

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

[пространные экскурсы в историю программирования сочтены лишними и грохнуты - админ]

[zmij]

Продвинутым программистам модифицировать список нельзя! (Я сам додумался только до решения с разрушением списка)

Это метод с XOR'ом указателей?

дан односвязный (цепной) список и два указателя на его голову. Определить, есть ли в списке циклы (без использования дополнительных переменных).

вариант не математический. чиста программерский:
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class fucked_up_list
{
  // requirements:

  __STL_CLASS_REQUIRES(_Tp, _Assignable);
public:
  typedef _Tp value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type* iterator;
  typedef const value_type* const_iterator;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

  typedef typename _Base::allocator_type allocator_type;
  allocator_type get_allocator() const { return _Base::get_allocator(); }

protected:
  void _M_insert_aux(iterator __position, const _Tp& __x);
  void _M_insert_aux(iterator __position);

public:
  iterator begin() { return _M_start; }
  const_iterator begin() const { return _M_start; }

  size_type max_size() const
    { return size_type(-1) / sizeof(_Tp); }
  size_type capacity() const
    { return size_type(_M_end_of_storage - begin()); }
  bool empty() const
    { return begin() == NULL; }


  explicit fucked_up_list(const allocator_type& __a = allocator_type())
    : _Base(__a) {}

  fucked_up_list(size_type __n, const _Tp& __value,
         const allocator_type& __a = allocator_type())
    : _Base(__n, __a)
    { _M_finish = uninitialized_fill_n(_M_start, __n, __value); }

  explicit fucked_up_list(size_type __n)
    : _Base(__n, allocator_type())
    { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }


  ~fucked_up_list() { destroy(_M_start); }

  fucked_up_list<_Tp, _Alloc>& operator=(const fucked_up_list<_Tp, _Alloc>& __x);
  void reserve(size_type __n) {
    if (capacity() < __n) {
      const size_type __old_size = size();
      iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
      destroy(_M_start, _M_finish);
      _M_deallocate(_M_start, _M_end_of_storage - _M_start);
      _M_start = __tmp;
      _M_finish = __tmp + __old_size;
      _M_end_of_storage = _M_start + __n;
    }
  }

  void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
  void _M_fill_assign(size_type __n, const _Tp& __val);

  reference front() { return *begin(); }
  const_reference front() const { return *begin(); }

  void push_back(const _Tp& __x) {
    if (_M_finish != _M_end_of_storage) {
      construct(_M_finish, __x);
      ++_M_finish;
    }
    else
      _M_insert_aux(end(), __x);
  }
  void push_back() {
    if (_M_finish != _M_end_of_storage) {
      construct(_M_finish);
      ++_M_finish;
    }
    else
      _M_insert_aux(end());
  }
  void swap(fucked_up_list<_Tp, _Alloc>& __x) {
    __STD::swap(_M_start, __x._M_start);
    __STD::swap(_M_finish, __x._M_finish);
    __STD::swap(_M_end_of_storage, __x._M_end_of_storage);
  }

  iterator insert(iterator __position, const _Tp& __x) {
    size_type __n = __position - begin();
    if (_M_finish != _M_end_of_storage && __position == end()) {
      construct(_M_finish, __x);
      ++_M_finish;
    }
    else
      _M_insert_aux(__position, __x);
    return begin() + __n;
  }
  iterator insert(iterator __position) {
    size_type __n = __position - begin();
    if (_M_finish != _M_end_of_storage && __position == end()) {
      construct(_M_finish);
      ++_M_finish;
    }
    else
      _M_insert_aux(__position);
    return begin() + __n;
  }

  void insert(iterator __position,
              const_iterator __first, const_iterator __last);

  void insert (iterator __pos, size_type __n, const _Tp& __x)
    { _M_fill_insert(__pos, __n, __x); }

  void _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x);

  void pop_back() {
    --_M_finish;
    destroy(_M_finish);
  }
  iterator erase(iterator __position) {
    if (__position + 1 != end())
      copy(__position + 1, _M_finish, __position);
    --_M_finish;
    destroy(_M_finish);
    return __position;
  }
  iterator erase(iterator __first, iterator __last) {
    iterator __i = copy(__last, _M_finish, __first);
    destroy(__i, _M_finish);
    _M_finish = _M_finish - (__last - __first);
    return __first;
  }

  void resize(size_type __new_size, const _Tp& __x) {
    if (__new_size < size())
      erase(begin() + __new_size, end());
    else
      insert(end(), __new_size - size(), __x);
  }
  void resize(size_type __new_size) { resize(__new_size, _Tp()); }
  void clear() { erase(begin(), end()); }

protected:

  iterator _M_allocate_and_copy(size_type __n, const_iterator __first,
                                               const_iterator __last)
  {
    iterator __result = _M_allocate(__n);
    __STL_TRY {
      uninitialized_copy(__first, __last, __result);
      return __result;
    }
    __STL_UNWIND(_M_deallocate(__result, __n));
  }
};

// часть тел функций опущена, дабы не сильно загромождать решение.

// а вот тут начинается решение задачи.
fucked_up_list a_list;
fucked_up_list::iterator p,q;
p = q = a_list.begin();

while (*q) {
  p++;
  q++;
  if (*q) {
    q++;
  }
  if (q == p) {
    // поимели цикл
    break;
  }
}
if (!*q) {
  // таки добрались до хвоста списка  
}


А теперь, для некрутых программеров пояснения  

Общая идея - пускаем указатели по списку с разными скоростями. Будем считать, что у нас p и q - указатели на голову списка и ведут себя как нормальные forward итераторы. соответственно, проверка на конец списка - равенство указателя нулю.

Код: [Выделить]


a_type *p, q;
while (*q) {
  p++;
  q++;
  if (*q) {
    q++;
  }
  if (q == p) {
    // поимели цикл
    break;
  }
}
if (!*q) {
  // таки добрались до хвоста списка  
}


[mashita]

zmij
Мне понравилось название класса  

[zmij]

zmij
Мне понравилось название класса  

я всегда стараюсь давать классам названия, отражающие их суть. в одной довольно серьезной системе, ядро которой я писал, до сих пор используют классы с названиями DLLKiller и OneAss (класс для вызова методов 1С-Бухгалтерии).

[visitoR]

Если бы я хотел стать жрецом, то мне бы это не удалось!:)
В том смысле, что сдаюсь и хочу посмотреть на решение задачи про колодец.
В принципе, она решается, но для этого надо решить уравнение 4 степени x^4 - 2x^3 + 5x^2 - 10x + 5 = 0. А я не настолько трудолюбив.
Также было бы интересно посмотреть, как это можно решить обладая только школьными знаниями.

[visitoR]

Не сложная математическая задачка:


Не отрывая карандаша от бумаги пересечь все помеченные грани ровно один раз.

[Eugene]

Не сложная математическая задачка...

Юморист

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

[visitoR]

... стоит использовать школьную тригонометрию.

Пробовал! Все равно вместо трактора танк получается!:)
Там получаются и синусы, и косинусы одновременно. А чтобы выразить один через другой надо взять корень от 1 - Х*Х.

[Lev]

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

Я решал эту задачку через подобие треугольников. Сначала получилась система из 11 урвнений с 11-ю неизвестными - уравнения все простенькие - первого порядка. Вроде все решается, но лениво как-то. Потом, с помощью того же подобия получил 7 уравнеий с 7-ю неизвестными - все равно лениво. Я загнал эту систему уравнений в MathCad (довольно удобная математическая программа), но там она решается почему-то не однозначно, в зависимости от "предварительных значений" искомых переменных. В общем, то ли я в MathCadе не разобрался, то ли неправильно систему записал, но в этой задаче, рассматривая разные пары подобных треугольников, можно составить уравнений больше чем неизвестных, т.е. методов решения этой задачи достаточно много.

[Eugene]

Я решал эту задачку через подобие треугольников. Сначала получилась система из 11 урвнений с 11-ю неизвестными - уравнения все простенькие - первого порядка. Вроде все решается, но лениво как-то. Потом, с помощью того же подобия получил 7 уравнеий с 7-ю неизвестными - все равно лениво. Я загнал эту систему уравнений в MathCad (довольно удобная математическая программа), но там она решается почему-то не однозначно, в зависимости от "предварительных значений" искомых переменных. В общем, то ли я в MathCadе не разобрался, то ли неправильно систему записал, но в этой задаче, рассматривая разные пары подобных треугольников, можно составить уравнений больше чем неизвестных, т.е. методов решения этой задачи достаточно много.

Как говорится, Гы!
Конечно, все решение строится на подобии треугольников. Их там куча. И уравнений можно написать море. Хитрость в том, чтобы эти уравнения были независимыми (см., например, "Критерий Кронекера-Капелли"). Судя по реакции МатКада, у Вас они именно зависимые. Увы.

[visitoR]

все простенькие - первого порядка.

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

[Lev]

все простенькие - первого порядка.

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

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

[Lev]

Решение задачи о священном колодце высылаю в ЛС

[Eugene]

Во.   Вспомнил классическую задачку по логике.
Есть два брата-близнеца. Зовут их, положим, Чук и Гек. Известно, что один из них все время врет, другой - всегда говорит только правду. Но кто - не известно.
Требуется, задав одному из братьев только один вопрос, узнать, как зовут каждого.

[KatNY]

А вот ещё задачка:

Есть 2 верёвки, каждая из которых сгорает ровно за 1 час. При этом скорость горения ни одной, ни второй верёвки не постоянна. Это означает, что верёвка может, к примеру, сгореть на половину за одну минуту, а на вторую половину догорать ещё 59 минут (вариантов горения бесконечно много).
Требуется отмерить с помощью этих 2-х верёвок и зажигалки (зажигалок) ровно 15 минут.

[GM]

x KatNY

Ответы в ЛС проверять будете?

[Eugene]

...Есть 2 верёвки, каждая из которых сгорает ровно за 1 час...

Неужели я еще не давал эту задачку? Был не прав, каюсь.  

[KatNY]

Неужели я еще не давал эту задачку? Был не прав, каюсь.  

А может и давал, я могла забыть, каюсь

To    GM:
Быстро сообразили, поздравляю!

И Lev тоже правильный ответ уже прислал

Пора учреждать приз самому сообразительному форумянину по итогам этой ветки ))