|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
16.05.2012, 21:54 | #1 |
Пользователь
Регистрация: 04.04.2012
Сообщений: 23
|
Необходимо составить алгоритм решения задачи с одномерным массивом олимпиадного характера
Задача следующая:
В масcиве А размера N за один просмотр необходимо каждый элемент заменить на ближайший следующий за ним элемент, который больше его. Если такого элемента нет, то заменить его на ноль. Можно использовать дополнительную память. Помогите составить алгоритм, всмысле помогите мне связными приложениями, либо своими рассуждениями и предположениями по разработке данной программы =) А я уж как-нибудь сам набросаю =) |
16.05.2012, 22:22 | #2 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
А откуда задача?
Как-то не принято на форумах обсуждать задачи не закончившихся олимпиад. А по окончании обычно решения становятся доступными. |
17.05.2012, 17:55 | #3 |
Пользователь
Регистрация: 04.04.2012
Сообщений: 23
|
Задача из моей курсовой. Просто олимпиадного уровня. Я тупо не могу понять, зачем в курсовой давать олимпиадную задачу.
Хотя она не кажется какой-то сложной, но помойму, тут есть подвох. |
17.05.2012, 23:17 | #4 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Я, честно говоря, не вижу ни "олимпиадности", ни подвоха.
Обычно "олимпиадность" подразумевает либо неординарное решение, либо то, что наиболее очевидное решение оказывается неэффективным (например, не укладывается в заданное время). Здесь же - простой логический путь без вариантов ветвления. Последний раз редактировалось s-andriano; 18.05.2012 в 07:55. |
23.05.2012, 20:24 | #5 |
Пользователь
Регистрация: 04.04.2012
Сообщений: 23
|
Короче я что-то не пойму, как можно это сделать за один проход?
|
23.05.2012, 20:43 | #6 | ||
C++, Java
Старожил
Регистрация: 10.04.2010
Сообщений: 2,665
|
Цитата:
Цитата:
|
||
23.05.2012, 21:22 | #7 |
Пользователь
Регистрация: 04.04.2012
Сообщений: 23
|
Но цикл в цикле это уже n*m проходов
|
23.05.2012, 21:26 | #8 |
Made In USSR!
Старожил
Регистрация: 01.09.2010
Сообщений: 3,657
|
"...В жизни я встречал друзей и врагов.В жизни много всего перевидал.Солнце тело мое жгло, ветер волосы трепал,но я смысла жизни так и не узнал..."
(c) Юрий Клинских aka "Хой" Последний раз редактировалось Mad_Cat; 24.05.2012 в 04:33. |
23.05.2012, 23:48 | #9 |
Пользователь
Регистрация: 04.04.2012
Сообщений: 23
|
Все бы хорошо, только не брики не екситы низя(((
|
24.05.2012, 18:47 | #10 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Элементарная логика:
1. Раз элемент нужно менять на следующий, значит, просматривать массив с начала бесполезно - мы не будем иметь ни какого представления ни об одном из следующих элементов. Следовательно, просматриваем массив с конца. 2. Последний элемент, очевидно, заменяем на 0, но предварительно запоминаем его. Т.к. по условию разрешено использовать дополнительную память - используем ее для хранения некоторой информации о "следующих элементах". Создаем стек. 3. Т.к. нам нужны только "бОльшие" эдементы, формируем в стеке убывающую последовательность: если текущий элемент меньше вершины стека, заменяем его на эту вершину, после чего вершину возвращаем в стек и туда же записываем новый элемент из массива. Если элемент больше вершины стека, опустошаем стек до тех пор, пока вершина стека не окажется больше (ну, либо стек не закончится). Все совершенно элементарно. Сложность O(n), все - за один проход, как и требуется. Тут половина решения уже содержится в условии, а вторая половина восстанавливается при помощи нехитрой логики. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм решения задачи | Amet13 | Помощь студентам | 1 | 21.04.2012 13:16 |
Составить алгоритм (блок-схема) и написать программу для решения задачи(Pascal) | sadim | Помощь студентам | 2 | 18.12.2011 14:53 |
Разработать алгоритм и составить программу для решения задачи. Длину последовательности задать | димон4ик_ | Помощь студентам | 0 | 18.10.2011 10:55 |
Разработать алгоритм и составить программу для решения задачи. Длину последовательности задать | димон4ик_ | Помощь студентам | 2 | 18.10.2011 09:39 |
составить алгоритм решения, реализующий перевод из 10 системы счисления в троичную | Машута | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 09.12.2008 18:20 |