Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Общие вопросы по программированию, компьютерный форум
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 26.05.2017, 10:28   #1
Time_for_Coffe
 
Аватар для Time_for_Coffe
 
Регистрация: 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
Time_for_Coffe вне форума Ответить с цитированием
Старый 26.05.2017, 12:14   #2
Plague
Забанен
Форумчанин Подтвердите свой е-майл
 
Аватар для Plague
 
Регистрация: 01.11.2006
Сообщений: 420
По умолчанию

Правильно я понимаю Вашу задачу?
Код:
Введите N: 10
Массив А:
124 183 113 114 111 115 170 168 150 136
Ведите M: 338
Ответ:
В период с 3  по 5 равно 338
В период с 7  по 8 равно 338
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
Plague вне форума Ответить с цитированием
Старый 26.05.2017, 12:14   #3
Pavia
Лис
Старожил
 
Аватар для Pavia
 
Регистрация: 18.09.2015
Сообщений: 2,409
По умолчанию

1) Путаете равенство и присвоение. Видно отсутствие навыка программирования.
Поэтому ваш псевдокод никуда не годиться. Если логика у вас была бы правильная то и записано было-бы верно. Что в голове, то и на языке! Вам надо больше читать учить.
2) Таки да зависит от размера массива, но таки нет не линейная. Если бы вы записали алгоритм верно, и вспомнили определения "сложности алгоритма" то вы бы подсчитали число операция сложения и получили-бы T(n/2*(n-1)).
3) Тут задача не корректная. В том смысле, что к ней не применим термин жадный алгоритм. Вот если бы у вас было не число автомобилей которое всегда положительно, а дебет=прибыль-убытки, то можно было бы говорить что задача имеет жадный алгоритм, но таки ваш алгоритм не жадный, а ленивый.
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал .
Pavia вне форума Ответить с цитированием
Старый 26.05.2017, 12:19   #4
Alex11223
Старожил
 
Аватар для Alex11223
 
Регистрация: 12.01.2011
Сообщений: 19,500
По умолчанию

Цитата:
Сообщение от Time_for_Coffe Посмотреть сообщение
перед спецкурсом по анализу алгоритмов (неспрашивайте почему у меня этот курс)
почему?
Ушел с форума, https://www.programmersforum.rocks, alex.pantec@gmail.com, https://github.com/AlexP11223
ЛС отключены Аларом.
Alex11223 вне форума Ответить с цитированием
Старый 26.05.2017, 15:40   #5
Time_for_Coffe
 
Аватар для Time_for_Coffe
 
Регистрация: 26.05.2017
Сообщений: 4
По умолчанию

Цитата:
Сообщение от Plague Посмотреть сообщение
Правильно я понимаю Вашу задачу?
Код:
Введите N: 10
Массив А:
124 183 113 114 111 115 170 168 150 136
Ведите M: 338
Ответ:
В период с 3  по 5 равно 338
В период с 7  по 8 равно 338
Да, вот к этому частному случаю просят спроектировать жадный алгоритм O (n) для решения этой проблемы в целом и написать псевдокод.
Don't try to deny what you feel
Time_for_Coffe вне форума Ответить с цитированием
Старый 26.05.2017, 15:41   #6
Time_for_Coffe
 
Аватар для Time_for_Coffe
 
Регистрация: 26.05.2017
Сообщений: 4
По умолчанию

Цитата:
Сообщение от Pavia Посмотреть сообщение
1) Путаете равенство и присвоение. Видно отсутствие навыка программирования.
Поэтому ваш псевдокод никуда не годиться. Если логика у вас была бы правильная то и записано было-бы верно. Что в голове, то и на языке! Вам надо больше читать учить.
2) Таки да зависит от размера массива, но таки нет не линейная. Если бы вы записали алгоритм верно, и вспомнили определения "сложности алгоритма" то вы бы подсчитали число операция сложения и получили-бы T(n/2*(n-1)).
3) Тут задача не корректная. В том смысле, что к ней не применим термин жадный алгоритм. Вот если бы у вас было не число автомобилей которое всегда положительно, а дебет=прибыль-убытки, то можно было бы говорить что задача имеет жадный алгоритм, но таки ваш алгоритм не жадный, а ленивый.
Благодарю за ответ, все верно, навыками программирования не владею. Вот пытаюсь разобраться. Не отступать же.
Don't try to deny what you feel
Time_for_Coffe вне форума Ответить с цитированием
Старый 26.05.2017, 15:46   #7
Time_for_Coffe
 
Аватар для Time_for_Coffe
 
Регистрация: 26.05.2017
Сообщений: 4
По умолчанию

Цитата:
Сообщение от Alex11223 Посмотреть сообщение
почему?
Мой научный руководитель решил что мне пришла пора осваивать новые горизонты))
Don't try to deny what you feel
Time_for_Coffe вне форума Ответить с цитированием
Старый 26.05.2017, 18:46   #8
Pavia
Лис
Старожил
 
Аватар для Pavia
 
Регистрация: 18.09.2015
Сообщений: 2,409
По умолчанию

Time_for_Coffe
Раз запал остался. Тогда перепишете свой псевдо код, и не ленитесь пишите подробнее.
Потом можно заменить с ленивого алгоритма на жадный. А затем отыскать алгоритм со сложность O(n).
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал .
Pavia вне форума Ответить с цитированием
Старый 26.05.2017, 20:06   #9
Plague
Забанен
Форумчанин Подтвердите свой е-майл
 
Аватар для Plague
 
Регистрация: 01.11.2006
Сообщений: 420
По умолчанию

Что то сомневаюсь за O(n)
При n = 10 как минимум надо перебрать эти периоды что уже O(n^2)
Код:
(1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9) (1,10) 
(2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (2,10) 
(3,3) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9) (3,10) 
(4,4) (4,5) (4,6) (4,7) (4,8) (4,9) (4,10) 
(5,5) (5,6) (5,7) (5,8) (5,9) (5,10) 
(6,6) (6,7) (6,8) (6,9) (6,10) 
(7,7) (7,8) (7,9) (7,10) 
(8,8) (8,9) (8,10) 
(9,9) (9,10) 
(10,10)
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
Plague вне форума Ответить с цитированием
Старый 30.05.2017, 20:18   #10
Dekay
Пользователь
 
Регистрация: 21.06.2016
Сообщений: 65
По умолчанию

Можно за N log
Например, бинарный поиск
Можно за N log
Например, set
Можно за N, если ввести ограничения на сумму количества автомобилей. Мол, если она не больше 10^6, то обычный массив позволит решить за N.

Еще за N можно двумя указателями, чет сразу не подумал

Последний раз редактировалось Dekay; 31.05.2017 в 00:41.
Dekay вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


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