[Архив!] Чистая математика, физика, химия и т.п.: задачки для тренировки мозгов, никак не связанные с торговлей - страница 584
Вы упускаете торговые возможности:
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Регистрация
Вход
Вы принимаете политику сайта и условия использования
Если у вас нет учетной записи, зарегистрируйтесь
В один проход:
Создаем пустую копию массива такого же размера, инициализируем его двойками.
Идем с начала массива. Встретили 1 - пишем в копию, начиная с начала, встретили 3 - пишем в копию, начиная с конца.
К тому же надо отслеживать одновременно три указателя!
Подкину задачку.
Боян конечно, но на собеседованиях как апофеоз знаний на сортировку массивов катит ))
Итак, задача на сортировку
есть масив из N ячеек, в котором в произвольном порядке размещены единицы, двойки и тройки.
Построить самый оптимальный алгоритм сортировки.
На одном проходе посчитать, на втором заполнить массив.
В один проход:
Создаем пустую копию массива такого же размера, инициализируем его двойками.
Идем с начала массива. Встретили 1 - пишем в копию, начиная с начала, встретили 3 - пишем в копию, начиная с конца.
Без копии (а то скажете, что заполнение копии - отдельный проход)
n=0, m=0
Идем с начала массива. Встретили 1 - меняем ее с n-м элементом с начала массива, не равным 1 (по построению это всегда будет 2), n++, если встретили 3 - меняем с m-м с конца, не равным 3, m++, и если на замену попалась 1, то проделываем действия, указанные в первой части.
Без копии (а то скажете, что заполнение копии - отдельный проход)
n=0, m=0
Идем с начала массива. Встретили 1 - меняем ее с n-м элементом с начала массива, не равным 1 (по построению это всегда будет 2), n++, если встретили 3 - меняем с m-м с конца, не равным 3, m++, и если на замену попалась 1, то проделываем действия, указанные в первой части.
Без копии (а то скажете, что заполнение копии - отдельный проход)
n=0, m=0
Идем с начала массива. Встретили 1 - меняем ее с n-м элементом с начала массива, не равным 1 (по построению это всегда будет 2), n++, если встретили 3 - меняем с m-м с конца, не равным 3, m++, и если на замену попалась 1, то проделываем действия, указанные в первой части.
Отличный способ.
Уменьшение количества проходов не всегда дает прирост к скорости.
A+B=...
Без копии (а то скажете, что заполнение копии - отдельный проход)
n=0, m=0
Идем с начала массива. Встретили 1 - меняем ее с n-м элементом с начала массива, не равным 1 (по построению это всегда будет 2), n++, если встретили 3 - меняем с m-м с конца, не равным 3, m++, и если на замену попалась 1, то проделываем действия, указанные в первой части.
Хорошая идея.