|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
26.05.2017, 10:28 | #1 |
Регистрация: 26.05.2017
Сообщений: 4
|
Жадный алгоритм, псевдокод
Здравствуйте ребята, с программированием прям чтоб в лоб, столкнулся только сейчас, до этого наши пути не пересекались, а жаль. Поехали:
В общем перед спецкурсом по анализу алгоритмов (неспрашивайте почему у меня этот курс), нам дали прорешать некоторые задачи для того чтобы определить наш бэкграунд. За сложные я браться не стал, а вот с теми, которые попроще (на первый взгляд) попробовал разобраться самостоятельно. Вот одна их них. Я то понимаю, что нужно найти сумму по k от i до j от Аk и чтобы она была равна M, но как это сделать? Ознакомившись с определением «Жадный алгоритм» и условиями его применимости, попробовал сформулировать следующее доказательство оптимальности (Надежный шаг): Всегда существует такая последовательность чисел, сумма которой равна M, и первым числом этой последовательности является A[i]. Осталось его найти. Нужно присвоить A[i]= A[1] и тогда A[1] + A[2] + A[3]…. Если сумма равна M – отлично, конец алгоритма, а если после прибавления последнего числа сумма становиться больше M, текущее A[i] нужно убрать из массива, и присвоить новое A[i]= A[2], т.е. следующему числу, и так далее, пока сумма не совпадет с М. Соответственно, псевдокод будет примерно: 1. A ←{A[1],..., A[n]} – задаем массив 2. Присвоить A[i]= первое число массива. Eсли (вот тут как то описать последовательное суммирование начиная с A[i] и до тех пор пока сумма не будет равна M), то пункт 4, иначе (т.е. сумма больше М) – пункт 3 3. Убрать из массива А первое число, повторить пункт 2. 4. Конец алгоритма Если и неправильно написано, то хотя бы логично)) поэтому имеет место быть. Остается открытым вопрос о времени работы алгоритма, я понимаю что длительность его работы будет зависеть от размера массива, и скорее всегда эта зависимость линейна - O (n), так ли это? И является ли описанный алгоритм жадным, или я открыл не ту дверь?
Don't try to deny what you feel
|
26.05.2017, 12:14 | #2 |
Забанен
Форумчанин Подтвердите свой е-майл
Регистрация: 01.11.2006
Сообщений: 420
|
Правильно я понимаю Вашу задачу?
Код:
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
|
26.05.2017, 12:14 | #3 |
Лис
Старожил
Регистрация: 18.09.2015
Сообщений: 2,409
|
1) Путаете равенство и присвоение. Видно отсутствие навыка программирования.
Поэтому ваш псевдокод никуда не годиться. Если логика у вас была бы правильная то и записано было-бы верно. Что в голове, то и на языке! Вам надо больше читать учить. 2) Таки да зависит от размера массива, но таки нет не линейная. Если бы вы записали алгоритм верно, и вспомнили определения "сложности алгоритма" то вы бы подсчитали число операция сложения и получили-бы T(n/2*(n-1)). 3) Тут задача не корректная. В том смысле, что к ней не применим термин жадный алгоритм. Вот если бы у вас было не число автомобилей которое всегда положительно, а дебет=прибыль-убытки, то можно было бы говорить что задача имеет жадный алгоритм, но таки ваш алгоритм не жадный, а ленивый.
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал . |
26.05.2017, 12:19 | #4 |
Старожил
Регистрация: 12.01.2011
Сообщений: 19,500
|
почему?
Ушел с форума, https://www.programmersforum.rocks, alex.pantec@gmail.com, https://github.com/AlexP11223
ЛС отключены Аларом. |
26.05.2017, 15:40 | #5 |
Регистрация: 26.05.2017
Сообщений: 4
|
Да, вот к этому частному случаю просят спроектировать жадный алгоритм O (n) для решения этой проблемы в целом и написать псевдокод.
Don't try to deny what you feel
|
26.05.2017, 15:41 | #6 | |
Регистрация: 26.05.2017
Сообщений: 4
|
Цитата:
Don't try to deny what you feel
|
|
26.05.2017, 15:46 | #7 |
Регистрация: 26.05.2017
Сообщений: 4
|
Мой научный руководитель решил что мне пришла пора осваивать новые горизонты))
Don't try to deny what you feel
|
26.05.2017, 18:46 | #8 |
Лис
Старожил
Регистрация: 18.09.2015
Сообщений: 2,409
|
Time_for_Coffe
Раз запал остался. Тогда перепишете свой псевдо код, и не ленитесь пишите подробнее. Потом можно заменить с ленивого алгоритма на жадный. А затем отыскать алгоритм со сложность O(n).
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал . |
26.05.2017, 20:06 | #9 |
Забанен
Форумчанин Подтвердите свой е-майл
Регистрация: 01.11.2006
Сообщений: 420
|
Что то сомневаюсь за O(n)
При n = 10 как минимум надо перебрать эти периоды что уже O(n^2) Код:
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
|
30.05.2017, 20:18 | #10 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
Можно за N log
Например, бинарный поиск Можно за N log Например, set Можно за N, если ввести ограничения на сумму количества автомобилей. Мол, если она не больше 10^6, то обычный массив позволит решить за N. Еще за N можно двумя указателями, чет сразу не подумал Последний раз редактировалось Dekay; 31.05.2017 в 00:41. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Задача.Жадный алгоритм | Тамерлан Абилов | Помощь студентам | 1 | 24.06.2015 20:10 |
Жадный алгоритм? | Loki_veil | Помощь студентам | 0 | 27.06.2012 12:05 |
Жадный алгоритм | merhaba1992 | Помощь студентам | 1 | 05.11.2011 00:24 |
Жадный алгоритм в программировании | nikita92 | Помощь студентам | 0 | 26.11.2010 20:20 |
Жадный алгоритм и перебор | mailjaffka | Помощь студентам | 10 | 17.05.2010 16:20 |