Необходимо составить алгоритм решения задачи с одномерным массивом олимпиадного характера - Паскаль, Turbo Pascal, PascalABC.NET

Маленыч · 16.05.2012, 21:54

Задача следующая:

В масcиве А размера N за один просмотр необходимо каждый элемент заменить на ближайший следующий за ним элемент, который больше его. Если такого элемента нет, то заменить его на ноль. Можно использовать дополнительную память.

Помогите составить алгоритм, всмысле помогите мне связными приложениями, либо своими рассуждениями и предположениями по разработке данной программы =)
А я уж как-нибудь сам набросаю =)

s-andriano · 16.05.2012, 22:22

А откуда задача?
Как-то не принято на форумах обсуждать задачи не закончившихся олимпиад. А по окончании обычно решения становятся доступными.

Маленыч · 17.05.2012, 17:55

Задача из моей курсовой. Просто олимпиадного уровня. Я тупо не могу понять, зачем в курсовой давать олимпиадную задачу.
Хотя она не кажется какой-то сложной, но помойму, тут есть подвох.

s-andriano · 17.05.2012, 23:17

Я, честно говоря, не вижу ни "олимпиадности", ни подвоха.

Обычно "олимпиадность" подразумевает либо неординарное решение, либо то, что наиболее очевидное решение оказывается неэффективным (например, не укладывается в заданное время).
Здесь же - простой логический путь без вариантов ветвления.

Маленыч · 23.05.2012, 20:24

Короче я что-то не пойму, как можно это сделать за один проход?

_-Re@l-_ · 23.05.2012, 20:43

Цитата:

Просто олимпиадного уровня.

Хм? Что-то? Вот тут есть задачи с контестов и олимпиад, сравните со своей "олимпиадной".

Цитата:

Короче я что-то не пойму, как можно это сделать за один проход?

Сложность алгоритма, если я правильно понимаю, здесь будет O(N^2), в общем, цикл в цикле будет.

Маленыч · 23.05.2012, 21:22

Но цикл в цикле это уже n*m проходов

Mad_Cat · 23.05.2012, 21:26

Тырк

Цитата:

Все бы хорошо, только не брики не екситы низя(((

там их как бы и нет

Маленыч · 23.05.2012, 23:48

Все бы хорошо, только не брики не екситы низя(((

s-andriano · 24.05.2012, 18:47

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

Все совершенно элементарно. Сложность O(n), все - за один проход, как и требуется. Тут половина решения уже содержится в условии, а вторая половина восстанавливается при помощи нехитрой логики.

16.05.2012, 21:54	#1
Маленыч Пользователь Регистрация: 04.04.2012 Сообщений: 23	Необходимо составить алгоритм решения задачи с одномерным массивом олимпиадного характера Задача следующая: В масcиве А размера N за один просмотр необходимо каждый элемент заменить на ближайший следующий за ним элемент, который больше его. Если такого элемента нет, то заменить его на ноль. Можно использовать дополнительную память. Помогите составить алгоритм, всмысле помогите мне связными приложениями, либо своими рассуждениями и предположениями по разработке данной программы =) А я уж как-нибудь сам набросаю =)

17.05.2012, 23:17	#4
s-andriano Старожил Регистрация: 08.04.2012 Сообщений: 3,229	Я, честно говоря, не вижу ни "олимпиадности", ни подвоха. Обычно "олимпиадность" подразумевает либо неординарное решение, либо то, что наиболее очевидное решение оказывается неэффективным (например, не укладывается в заданное время). Здесь же - простой логический путь без вариантов ветвления. Последний раз редактировалось s-andriano; 18.05.2012 в 07:55.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Алгоритм решения задачи	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

16.05.2012, 22:22	#2
s-andriano Старожил Регистрация: 08.04.2012 Сообщений: 3,229	А откуда задача? Как-то не принято на форумах обсуждать задачи не закончившихся олимпиад. А по окончании обычно решения становятся доступными.

17.05.2012, 17:55	#3
Маленыч Пользователь Регистрация: 04.04.2012 Сообщений: 23	Задача из моей курсовой. Просто олимпиадного уровня. Я тупо не могу понять, зачем в курсовой давать олимпиадную задачу. Хотя она не кажется какой-то сложной, но помойму, тут есть подвох.

23.05.2012, 20:24	#5
Маленыч Пользователь Регистрация: 04.04.2012 Сообщений: 23	Короче я что-то не пойму, как можно это сделать за один проход?

23.05.2012, 21:22	#7
Маленыч Пользователь Регистрация: 04.04.2012 Сообщений: 23	Но цикл в цикле это уже n*m проходов

23.05.2012, 23:48	#9
Маленыч Пользователь Регистрация: 04.04.2012 Сообщений: 23	Все бы хорошо, только не брики не екситы низя(((

24.05.2012, 18:47	#10
s-andriano Старожил Регистрация: 08.04.2012 Сообщений: 3,229	Элементарная логика: 1. Раз элемент нужно менять на следующий, значит, просматривать массив с начала бесполезно - мы не будем иметь ни какого представления ни об одном из следующих элементов. Следовательно, просматриваем массив с конца. 2. Последний элемент, очевидно, заменяем на 0, но предварительно запоминаем его. Т.к. по условию разрешено использовать дополнительную память - используем ее для хранения некоторой информации о "следующих элементах". Создаем стек. 3. Т.к. нам нужны только "бОльшие" эдементы, формируем в стеке убывающую последовательность: если текущий элемент меньше вершины стека, заменяем его на эту вершину, после чего вершину возвращаем в стек и туда же записываем новый элемент из массива. Если элемент больше вершины стека, опустошаем стек до тех пор, пока вершина стека не окажется больше (ну, либо стек не закончится). Все совершенно элементарно. Сложность O(n), все - за один проход, как и требуется. Тут половина решения уже содержится в условии, а вторая половина восстанавливается при помощи нехитрой логики.