Чистая математика, физика, логика (braingames.ru): задачки для мозгов, не связанные с торговлей - страница 213
Вы упускаете торговые возможности:
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Регистрация
Вход
Вы принимаете политику сайта и условия использования
Если у вас нет учетной записи, зарегистрируйтесь
Задача для программистов (вес задачи - 4):
Мегамозгу в очень длинном тексте требуется заменить все буквы «А» на буквы «Б», а все буквы «Б» - на буквы «А». Текстовый редактор позволяет заменить во всём тексте один произвольный набор символов на другой. Например, в результате замены «АА»->«БСАА» строка «АААААЛ» перейдёт в строку «БСААБСАААЛ». Как ему выполнить задачу?
FAQ (c сайта):
Вы не знаете алфавита текстового редактора. Единственное, что вы знаете, это то, что он содержит символы "А" и "Б".
(Разъяснение от Mathemat'a: в первом поле (ЧТО заменяем) и во втором (НА ЧТО заменяем) можно пользовать только символы А и Б и ничего больше, даже пробелы нельзя: алфавит текста и текстового редактора нам не известен. Мне до сих пор непонятно, почему это ключевое разъяснение отсутствует в тексте самой задачи, но, увы, так оно и есть.)
В условии об этом прямо не сказано, но я так понимаю, что все остальные символы, кроме А и Б, должны остаться неизменными. Это так?Да.
Что значит "очень длинный текст"?
1. Вручную все замены сделать невозможно.
2. Любая данная последовательность символов может в нем встретиться.
3. Мегамозг не может использовать для замены последовательности с длиной сравнимой с длиной текста.
Есть ли в "арсенале" текстового редактора символ, отсутствующий в тексте?
Нет.
Можно ли несколько раз производить изменения по всему тексту?
Да.
Можно ли пропускать некоторые последовательности? Например, при замене "АА"->"БСАА" строка "AAAAAЛ" перейдет в строку "БСАААААЛ" (то есть 2ую последовательность пропустили).
Нет.
Можно ли при замене пользоваться регулярными выражениями (либо их аналогами)?
Нет.
Решение задачи меня просто шокировало своей неожиданностью (хотя вполне допускаю и другие решения). Я начал решать ее пару лет назад, после чего исчез с Игр разума на полтора года. Пару дней назад снова воззрился на нее, и около суток назад отправил решение модератору. Ответ я пока не получил, но в верности решения уверен на все 100. Алгоритм проверен на тестовом наборе символов, ошибок не найдено.
Задача для программистов (вес задачи - 4):
Мегамозгу в очень длинном тексте требуется заменить все буквы «А» на буквы «Б», а все буквы «Б» - на буквы «А». Текстовый редактор позволяет заменить во всём тексте один произвольный набор символов на другой. Например, в результате замены «АА»->«БСАА» строка «АААААЛ» перейдёт в строку «БСААБСАААЛ». Как ему выполнить задачу?
FAQ (c сайта):
Решение задачи меня просто шокировало своей неожиданностью (хотя вполне допускаю и другие решения). Я начал решать ее пару лет назад, после чего исчез с Игр разума на полтора года. Пару дней назад снова воззрился на нее, и около суток назад отправил решение модератору. Ответ я пока не получил, но в верности решения уверен на все 100. Алгоритм проверен на тестовом наборе символов, ошибок не найдено.
А нельзя A->АА, Б->ББ, АА->Б, ББ->A?
Можно, но не получится
Например, вот текст "ААААААААААБББББББББ", в результате: "ААААААААААААААААААА"
Задача для программистов (вес задачи - 4):
Мегамозгу в очень длинном тексте требуется заменить все буквы «А» на буквы «Б», а все буквы «Б» - на буквы «А». Текстовый редактор позволяет заменить во всём тексте один произвольный набор символов на другой. Например, в результате замены «АА»->«БСАА» строка «АААААЛ» перейдёт в строку «БСААБСАААЛ». Как ему выполнить задачу?
FAQ (c сайта):
Решение задачи меня просто шокировало своей неожиданностью (хотя вполне допускаю и другие решения). Я начал решать ее пару лет назад, после чего исчез с Игр разума на полтора года. Пару дней назад снова воззрился на нее, и около суток назад отправил решение модератору. Ответ я пока не получил, но в верности решения уверен на все 100. Алгоритм проверен на тестовом наборе символов, ошибок не найдено.
Решается в 4 замены:
A -> АА
Б -> БАБ
АА -> Б
БАБ -> А
Решается в 4 замены:
A -> АА
Б -> БАБ
АА -> Б
БАБ -> А
Не проверял, но такое решение приведено в комментах для решивших. Вот мое решение:
Б -> АБ
ААБ -> Б
АБ -> А
Обратите внимание: первые две замены (точнее, правые их части) формально тождественны.
Кто-нить может сделать менее чем за 4 хода?
-----------------------------------------------------------------------------
И, кстати, что там насчет этой задачки?
Перед вами на столе два тонкостенных непрозрачных сосуда кубической формы (без верхней грани) емкостью 4.096 и 8 литров. Как, имея неограниченный запас воды, быстро отмерить ровно 5 литров?
Задача - тут. Вес задачи - 5.
FAQ:
- стенки очень тонкие, их объем пренебрежимо мал.
- 4.096 - это четыре целых и девяносто шесть тысячных литра, именно так. Ровно 5 литров - это ровно 5, а не, скажем, 5.002 литра.
- непрозрачность означает, что нельзя сделать, например, так: поставить меньший куб в больший и налить воды в больший до краев меньшего. Из-за непрозрачности это нельзя сделать достаточно точно.
- быстро - это действительно быстро, весьма быстро. Решение в десять шагов не будет принято. Оно слишком длинное.
Хитрая задачка. Я решил в три шага.
1) Ставим маленький куб в большой, и заливаем большой куб до краёв. Теперь наклоняем его так чтоб поверхности воды коснулся краешек маленького куба. (если случайно отлили лишнего - подливаем, воды много..).
Возвращаем куб в вертикальное положение. Мы отлили ровно один литр. (длина сегмента AB=5 см, это легко рассчитывается из размеров сторон кубов (20см и 16см, соответственно)).
Аккуратно вынимаем маленький куб, оставляя всю воду (7 литров) в большом кубе.
2. Теперь наклоняем большой куб ровно до момента касания кромкой воды "диагонального" ребра (противоположного ребру через которое выливается вода), при этим воду отливаем в маленький куб.
В большом кубе остаётся ровно половина его объёма (4 литра), в маленьком 3 литра (= 7л - 4л).
3. Теперь наливаем большой куб до краёв или чуть меньше. Аккуратно ставим в него маленький куб с тремя литрами воды. Его объём больше 3 литров, потому он погрузится не полностью, а только ровно настолько, чтобы вытеснить 3 литра воды из большого куба. Теперь маленький куб вынимаем. В большом кубе осталось ровно пять литров (8л - 3л), что и требовалось.
Не проверял, но такое решение приведено в комментах для решивших. Вот мое решение:
Обратите внимание: первые две замены формально тождественны.
Кто-нить может сделать менее чем за 4 хода?
За три глобальных замены решение возможно только при наличии дополнительного символа, присутствующего в допустимом алфавите, но гарантированно отсутствующего в тексте, что по условию задачи не так.
В приведённых условиях четыре хода минимальны. Это можно (но нудно и многословно) доказать. :)
Хитрая задачка. Я решил в три шага.
1) Ставим маленький куб в большой, и заливаем большой куб до краёв. Теперь наклоняем его так чтоб поверхности воды коснулся краешек маленького куба. (если случайно отлили лишнего - подливаем, воды много..).
Возвращаем куб в вертикальное положение. Мы отлили ровно один литр. (длина сегмента AB=5 см, это легко рассчитывается из размеров сторон кубов (20см и 16см, соответственно)).
Аккуратно вынимаем маленький куб, оставляя всю воду (7 литров) в большом кубе.
2. Теперь наклоняем большой куб ровно до момента касания кромкой воды "диагонального" ребра (противоположного ребру через которое выливается вода), при этим воду отливаем в маленький куб.
В большом кубе остаётся ровно половина его объёма (4 литра), в маленьком 3 литра (= 7л - 4л).
3. Теперь наливаем большой куб до краёв или чуть меньше. Аккуратно ставим в него маленький куб с тремя литрами воды. Его объём больше 3 литров, потому он погрузится не полностью, а только ровно настолько, чтобы вытеснить 3 литра воды из большого куба. Теперь маленький куб вынимаем. В большом кубе осталось ровно пять литров (8л - 3л), что и требовалось.
так-то на первом шаге 2 литра отливается )
0.05*0.2*0.2=0.002 м3
так-то на первом шаге 2 литра отливается )
0.05*0.2*0.2=0.002 м3
опять привираешь ;)
площадь треугольника ABC = (0.05*0.2) / 2
итого: ((0.05*0.2) / 2) * 0.2 = 0.001 m^3
Хитрая задачка. Я решил в три шага.
1) Ставим маленький куб в большой, и заливаем большой куб до краёв. Теперь наклоняем его так чтоб поверхности воды коснулся краешек маленького куба. (если случайно отлили лишнего - подливаем, воды много..).
Оригинально, но, похоже, есть противоречие с непрозрачностью. Да и держать большой куб наклоненным без какой-либо опоры не так просто, тут два чела нужны.
2. Теперь наклоняем большой куб ровно до момента касания кромкой воды "диагонального" ребра (противоположного ребру через которое выливается вода), при этим воду отливаем в маленький куб.
И тут аналогичная хрень, особенно с отливанием воды в маленький. Из большого отлить воду в маленький через грань большого без спецприспособлений затруднительно.
Короче, есть решение короче и проще :)
MD: За три глобальных замены решение возможно только при наличии дополнительного символа, присутствующего в допустимом алфавите, но гарантированно отсутствующего в тексте, что по условию задачи не так.
В приведённых условиях четыре хода минимальны. Это можно (но нудно и многословно) доказать. :)
Модераторы утверждают, что на Играх разума еще никто не предоставил решения короче 4 ходов. (Задачу ниже я не предлагал, это просто автоматика движка нашего сайта.)