04-strings1 (1238875), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Размен монет•Приложение к размену монет: пусть есть монеты номиналами 1 , 2 , 3 инеобходимо разменять сумму •Заведём таблицу от 0 до и протабулируем оптимальные размены.Пусть есть номиналы 1,3,4 и надо разменять 10 используя минимальноеколичество монетk12V12345678910Размен монет•Приложение к размену монет: пусть есть монеты номиналами 1 , 2 , 3 инеобходимо разменять сумму •Заведём таблицу от 0 до и протабулируем оптимальные размены.Пусть есть номиналы 1,3,4 и надо разменять 10 используя минимальноеколичество монетk1234V12125678910Размен монет•Приложение к размену монет: пусть есть монеты номиналами 1 , 2 , 3 инеобходимо разменять сумму •Заведём таблицу от 0 до и протабулируем оптимальные размены.Пусть есть номиналы 1,3,4 и надо разменять 10 используя минимальноеколичество монетk12345V12122678910Размен монет•Приложение к размену монет: пусть есть монеты номиналами 1 , 2 , 3 инеобходимо разменять сумму •Заведём таблицу от 0 до и протабулируем оптимальные размены.Пусть есть номиналы 1,3,4 и надо разменять 10 используя минимальноеколичество монетk12345678910V1211222233Problem MC – размен монет•Вам необходимо написать программу, которая считывая со стандартноговвода:•Сумму размена•Число монет для размена•Номиналы монет для размена•Выдавала бы на стандартный вывод минимальное количество монет дляразменаProblem BP – задача о рюкзаке•Вам необходимо написать программу, которая считывая со стандартноговвода:•Количество вещей•Вес каждой вещи•Общий вес входящий в рюкзак•Выдавало бы наибольшее количество вещей которые можно положить врюкзак•Например для: 4, {1, 3, 3, 4}, 10 ответ будет 3Расстояние редактирования•Как перейти от слова spoon к слову sponge?•Что можно делать:••••Вставлять букву в любое место (цена == 1)Удалять любую букву (цена == 1)Изменять любую букву (цена == 2)Нужно найти последовательность действий с минимальной ценойspoon → sponn (+2) → spong (+2) → sponge (+1), cost = 5spoon → spon (+1) → spong (+1) → sponge (+1), cost = 3•Можем ли мы применить динамическое программирование?Динамическое программирование•Любая часть оптимальной траектории является оптимальной траекторией − 1, + 1 , − 1 + 1 , = ൞ − 1, − 1 + (, )0, 1 = 2 , = ቊ2, 1 ≠ 2 ••Задача теперь сводится к тому,чтобы найти 5, 6Потренируемся заполнять таблицу#SPONGE#0123456S1(1,1)P2O3O4N5(5,6)Динамическое программирование•Любая часть оптимальной траектории является оптимальной траекторией − 1, + 1 , − 1 + 1 , = ൞ − 1, − 1 + (, )0, 1 = 2 , = ቊ2, 1 ≠ 2 ••Задача теперь сводится к тому,чтобы найти 5, 6Потренируемся заполнять таблицу#SPONGE#0123456S1012345P2101234O3210123O4321234N5432123Problem ED – расстояние редактирования•Реализуйте программу, которая считывает со стандартного ввода••••••••стоимость добавлениястоимость удалениястоимость заменыдлину первой строкипервую строкудлину второй строкивторую строкуИ выводит на стандартный вывод минимальное расстояние редактированияЛитература•С11 ISO/IEC – "Information technology – Programming languages – C",2011•& Brian W.

Kernighan, Dennis Ritchie – The C programming language,1988•• Joel Spolsky – Back to Basics, 2001 Peter van der Linden – Expert C Programming: Deep C Secrets ,1994• Richard Bellman – Dynamic Programming, 1957• Thomas H. Cormen – Introduction to Algorithms, 2009• Donald E. Knuth – The Art of Computer Programming, 2011• Robert Sedgewick Algorithms, 4th edition, 2011.

Характеристики

Список файлов лекций