Насчет задачи с автобусами. По всей видимости я не правильно понял условия: если автобус двигается abcd, то он идет из a в b, из b в c, из с в d, а после d он уже никуда не идет. Т.е. его движение однонаправлено. Т.е. он может из a приехать в d, но не может из d приехать в a. Наверное меня сбил с толку пример, где все движение показано в одном направлении. И в таком случае это совсем иная задача.
Задача 1.
Итак, нам нужно проверить вхождение слова «АБ» в слове из 10 букв. Для этого нам придется сделать цикл из (10-2) итераций, и в каждом проверить на нулевые значения 2 ячейки(потому что первое слово состоит из 2-х букв). Всего 8*2 действий. Теперь нужно найти скажем слово «АБВГ». Оно потребует (10-4) итерации, в каждой из которых нужно проверить 4 элемента массива. Всего действий 6*4=24.
Теперь ищем слово из 4-х букв в слове из 20 букв, т.е. увеличивает в 2 раза оба слова. В результате получаем (20-4)*4 = 64 проверки, а это увеличение в 4 раза, а не в 2!
И где здесь O(n + m)? Тут явная O(n * m).
И именно из-за этого я не стал дальше оптимизировать свой алгоритм, хотя приведение к нулю — просто само бросается в глаза.
Задача с яйцами ваше решение почти не убежало от моего.
Ваши задачи решаются за три минуты.
1) Есть изначальный прямоугольник, и есть вырезанный прямоугольник. Разрез нужно провести через центры обоих. Причем положение вырезанного куска не важно, если он полностью содержится в первоначальном прямоугольнике.
2) Задача с яйцами стандартна. В общем случае нужно разбить весь диапазон этажей N на карманы (M), так чтобы М*М=N. Если яиц у нас три, тогда M*M*M=N. В нашем случае N=100, значит M=10. Первым делом проверяем 10 этаж, если яйцо не разбилось, тогда 20, если не разбилось, тогда 30… Т.е. первое яйцо тратим на выявление правильного десятка. А уже вторым яйцом узнаем конкретный этаж внутри этого десятка. Итого за 20 бросков мы гарантировано узнаем нужный этаж. Но этот алгоритм можно оптимизировать, если разбить этажи так, чтобы в первый карман попало больше этажей, чем в последний. Например так: 15-14-13-12-11-9-8-7-6-5. Тогда мы гарантировано узнаем нужный этаж за 16 бросков.
Задачи:
1) Переводим символы в числа. Т.е. А-1, B-2, C-3…
Создаем массив длинной равный количеству букв в алфавите. Записываем в него по индексу букв из первого слова количества раз, которое оно там встречается. Если букв нет, ставим 0. За первый проход по второму слову метим позиции, которые содержат буквы, которых нет в нашем первом слове(в первом примере это буква О). Этим бы быстро исключили заведомо неправильные проверки. По оставшимся позициям делаем так: предварительно создаем ещё один массив такой же длины(1 раз). Обнуляем его. И считаем сколько раз каждая буква попалась. Сверяем его с эталонным массивом (по имеющимся буквам). Если получили совпадение, то оно и есть искомый результат. Сложность O(n*m), где n-длина первого слова, m- длина второго слова. Зачему, что если требуется применить поиск несколько раз к разным словам и разным эталонам, то выделенные массивы нужно всего ли обнулять, т.е. сэкономить на процессе выделении памяти.
2) Я здесь вижу немного измененный волновой алгоритм поиска пути в лабиринте. Создаем массив с длиной равной количеству остановок. Забиваем их все очень большим числом. Начальную ячейку (стартовую остановку) делаем равной нулю. Теперь в цикле проигрываем каждый из автобусов. Автобус стартует с первой остановки, запоминая число в ней (K). Если на следующей остановке хранимое число больше, чем K +1, то ложим в него значение k+1.
Если же это число меньше чем K, то заменяем запомненное число вместо K. И так до бесконечности, тока ячейка массива финальной остановки не станет равной какому-то числу меньшему изначального. Значение этого числа и будет равно количеству автобусов. Для надежности (может быть найден не самый оптимальный путь), надо прогнать цикл ещё количество раз, которое равно количеству автобусов.
Хотя только счас дошло, что это не гарантирует оптимальности в случае, когда приходится пересаживаться между одними и теме же автобусами. Но можно обрабатывать только те ячейки, число в которых не больше чем номер цикла (итерации). Мне кажется, что находить оптимальный алгоритм есть смысл зная количество остановок, количество автобусов, среднее число остановок и разряженность остановок (сколько автобусов проходит через одну остановку). Алгоритмы, которые работают хорошо на плотных массивах могут работать не оптимально на разряженных.
Также надо ставить флаг, что за каждый цикл было изменена хоть 1 ячейка. Если флаг не сработал, то задача не имеет решения.
3) За один проход. Достаточно знать максимальную сумму массива, которых заканчивался предыдущей (при проходе) ячейкой. Если она больше 0, то плюсуем её со значением текущей ячейки массива, иначе оставляем только текущее значение. Решение очевидно.
Итак, нам нужно проверить вхождение слова «АБ» в слове из 10 букв. Для этого нам придется сделать цикл из (10-2) итераций, и в каждом проверить на нулевые значения 2 ячейки(потому что первое слово состоит из 2-х букв). Всего 8*2 действий. Теперь нужно найти скажем слово «АБВГ». Оно потребует (10-4) итерации, в каждой из которых нужно проверить 4 элемента массива. Всего действий 6*4=24.
Теперь ищем слово из 4-х букв в слове из 20 букв, т.е. увеличивает в 2 раза оба слова. В результате получаем (20-4)*4 = 64 проверки, а это увеличение в 4 раза, а не в 2!
И где здесь O(n + m)? Тут явная O(n * m).
И именно из-за этого я не стал дальше оптимизировать свой алгоритм, хотя приведение к нулю — просто само бросается в глаза.
Задача с яйцами ваше решение почти не убежало от моего.
1) Есть изначальный прямоугольник, и есть вырезанный прямоугольник. Разрез нужно провести через центры обоих. Причем положение вырезанного куска не важно, если он полностью содержится в первоначальном прямоугольнике.
2) Задача с яйцами стандартна. В общем случае нужно разбить весь диапазон этажей N на карманы (M), так чтобы М*М=N. Если яиц у нас три, тогда M*M*M=N. В нашем случае N=100, значит M=10. Первым делом проверяем 10 этаж, если яйцо не разбилось, тогда 20, если не разбилось, тогда 30… Т.е. первое яйцо тратим на выявление правильного десятка. А уже вторым яйцом узнаем конкретный этаж внутри этого десятка. Итого за 20 бросков мы гарантировано узнаем нужный этаж. Но этот алгоритм можно оптимизировать, если разбить этажи так, чтобы в первый карман попало больше этажей, чем в последний. Например так: 15-14-13-12-11-9-8-7-6-5. Тогда мы гарантировано узнаем нужный этаж за 16 бросков.
Задачи:
1) Переводим символы в числа. Т.е. А-1, B-2, C-3…
Создаем массив длинной равный количеству букв в алфавите. Записываем в него по индексу букв из первого слова количества раз, которое оно там встречается. Если букв нет, ставим 0. За первый проход по второму слову метим позиции, которые содержат буквы, которых нет в нашем первом слове(в первом примере это буква О). Этим бы быстро исключили заведомо неправильные проверки. По оставшимся позициям делаем так: предварительно создаем ещё один массив такой же длины(1 раз). Обнуляем его. И считаем сколько раз каждая буква попалась. Сверяем его с эталонным массивом (по имеющимся буквам). Если получили совпадение, то оно и есть искомый результат. Сложность O(n*m), где n-длина первого слова, m- длина второго слова. Зачему, что если требуется применить поиск несколько раз к разным словам и разным эталонам, то выделенные массивы нужно всего ли обнулять, т.е. сэкономить на процессе выделении памяти.
2) Я здесь вижу немного измененный волновой алгоритм поиска пути в лабиринте. Создаем массив с длиной равной количеству остановок. Забиваем их все очень большим числом. Начальную ячейку (стартовую остановку) делаем равной нулю. Теперь в цикле проигрываем каждый из автобусов. Автобус стартует с первой остановки, запоминая число в ней (K). Если на следующей остановке хранимое число больше, чем K +1, то ложим в него значение k+1.
Если же это число меньше чем K, то заменяем запомненное число вместо K. И так до бесконечности, тока ячейка массива финальной остановки не станет равной какому-то числу меньшему изначального. Значение этого числа и будет равно количеству автобусов. Для надежности (может быть найден не самый оптимальный путь), надо прогнать цикл ещё количество раз, которое равно количеству автобусов.
Хотя только счас дошло, что это не гарантирует оптимальности в случае, когда приходится пересаживаться между одними и теме же автобусами. Но можно обрабатывать только те ячейки, число в которых не больше чем номер цикла (итерации). Мне кажется, что находить оптимальный алгоритм есть смысл зная количество остановок, количество автобусов, среднее число остановок и разряженность остановок (сколько автобусов проходит через одну остановку). Алгоритмы, которые работают хорошо на плотных массивах могут работать не оптимально на разряженных.
Также надо ставить флаг, что за каждый цикл было изменена хоть 1 ячейка. Если флаг не сработал, то задача не имеет решения.
3) За один проход. Достаточно знать максимальную сумму массива, которых заканчивался предыдущей (при проходе) ячейкой. Если она больше 0, то плюсуем её со значением текущей ячейки массива, иначе оставляем только текущее значение. Решение очевидно.