|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
22.11.2009, 15:06 | #1 |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
сложность алгоритма
задача о размене монет с номиналами 25,10,5,1 вот алгоритм
Код:
затем из N вычитается номинал этой монеты. Таким образом получается размен монет Код:
кол-во итераций вложенного цикла всегда равно coins.size-1 = 3 как расчитать зависимость от N кол-во итераций первого цикла ? Последний раз редактировалось NiCola999; 22.11.2009 в 15:09. |
22.11.2009, 15:23 | #2 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Зачем ерундой голову себе забивать? Сделать одним общим формализатором и все. Тогда сложность равна количеству монет, которые входят в итоговый размен. А если не сохранять сами монеты, а только количество, то алгоритм O(1).
|
22.11.2009, 15:26 | #3 |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
дело в том, что в задании сказано использовать жадный алгоритм, вот я его и написал.
допустим I кол-во итераций первого цикла, тогда получается a = [25,10,5,1] I = Sum(k=N, 0 ) k /= max(a[k]) max(a[k]) = максим номинал монеты, который не больше k как теперь вычислить сложность всего алгоритма ? Последний раз редактировалось NiCola999; 22.11.2009 в 15:32. |
22.11.2009, 15:32 | #4 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Так и пишите жадный алгоритм. Только по-человечески, по принципу
Код:
Последний раз редактировалось LeBron; 22.11.2009 в 15:53. |
22.11.2009, 15:49 | #5 | |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
я паскаль не знаю, что это значит?
for t:=1 to n div 25 do begin inc(i);ar[i]:=25;end; цикл от 1 до n/25 a[i] = 25 i+=1 ? Цитата:
Последний раз редактировалось NiCola999; 22.11.2009 в 15:52. |
|
22.11.2009, 15:55 | #6 | |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
Код:
|
|
22.11.2009, 17:37 | #7 |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
так у меня получается тоже самое что и у тебя, просто вместо 25 идут элменты массива.Только кол-во итераций получается 3+кол-во монет
Последний раз редактировалось NiCola999; 22.11.2009 в 17:49. |
22.11.2009, 17:49 | #8 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
По сути да, но мой вариант более общий - такое используют, если надо просто подсчитать количество монет, не разменивая. Или, например, если можно написать так: 12*25+4*10+1*5+2*1 В конкретно взятом случае да, оба решения одинаково хорошие.
|
22.11.2009, 17:51 | #9 |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
так как расчитать O(n) ?=)
|
22.11.2009, 17:56 | #10 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Рассчитать - разложить? Это и есть решение за О(n). И Ваше, и мое решение, при увеличении числа N, скажем, с миллиона до 2 миллионов, станут работать в 2 раза дольше.
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Сложность с запросом БД | k1r1ch | БД в Delphi | 4 | 27.09.2009 18:50 |
Сложность взлома XLS | Alex Cones | Свободное общение | 13 | 29.08.2009 15:13 |
Требуется дописать программу на QT. За деньги, сложность низкая. | Static2 | Фриланс | 4 | 27.02.2009 14:32 |
Уже не студент, и не могу преодолеть сложность (строки, *.txt) | SarahConner | Помощь студентам | 6 | 13.01.2009 16:24 |
Сложность Алгоритма | PChEL@ | Помощь студентам | 3 | 26.05.2007 07:56 |