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

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

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 01.04.2015, 19:02   #1
andronova
Пользователь
 
Аватар для andronova
 
Регистрация: 17.02.2009
Сообщений: 21
По умолчанию Задача про банкомат

Задача
Имеется банкомат, в котором есть почти неограниченное количество купюр Y1, Y2, …, Yn разных достоинств некоторой валюты. Выдавая, запрошенную клиентом сумму, банкомат выполняет циклически следующий алгоритм:
Пусть необходимо выдать сумму X.
1. Банкомат выдает 1 купюру достоинства Yi, такую, что Yi ≤ X и Yi максимально;
2. Из X вычитается Yi;
3. Если X стало равно 0, то алгоритм завершается;
4. Иначе, выполнение алгоритма продолжается с шага 1.
Пример - алгоритм:
Пусть необходимо выдать сумму 31. В распоряжении банкомата имеются купюры следующих достоинств: 1, 7, 16. Банкомат выполнит 4 действия:
1. Банкомат выдаст купюру достоинства 16. Останется выдать сумму 15;
2. Банкомат выдаст купюру достоинства 7. Останется выдать сумму 8;
3. Банкомат выдаст купюру достоинства 7. Останется выдать сумму 1;
4. Банкомат выдаст купюру достоинства 1 и на этом закончит выдачу.
Задания:
1. Напишите программный код приведенного выше алгоритма на любом языке программирования.
2. Пусть задан бесконечный набор купюр в виде степеней двойки, т.е. 1, 2, 4, 8, 16, … и необходимо выдать купюры на сумму X.
Необходимо дать обоснованный ответ: в какой степени возрастет количество действий банкомата при выполнении алгоритма в худшем случае, если сумма станет равна
a) 2X
б) X2.
3. Предположим, что клиенту хотелось бы получить запрошенную сумму в минимальном количестве купюр (на самом деле приведенный выше алгоритм не всегда выдает такое количество).
Приведите пример, при каких достоинствах купюр и какой запрашиваемой сумме алгоритм выдаст купюр больше, чем может быть.
4. Предложите идею, как можно модифицировать алгоритм, чтобы банкомат всегда выдавал минимальное количество купюр.
5. Реализуйте идею из пункта 5 на любом языке программирования.
andronova вне форума Ответить с цитированием
Старый 01.04.2015, 19:02   #2
andronova
Пользователь
 
Аватар для andronova
 
Регистрация: 17.02.2009
Сообщений: 21
По умолчанию

Пожалуйста, помогите!
andronova вне форума Ответить с цитированием
Старый 01.04.2015, 20:54   #3
min@y™
Цифровой кот
Старожил
 
Аватар для min@y™
 
Регистрация: 29.08.2014
Сообщений: 7,656
По умолчанию

Задавай вопросы, будем отвечать.
Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
min@y™ вне форума Ответить с цитированием
Старый 02.04.2015, 10:06   #4
alexcoder
Форумчанин
 
Регистрация: 31.05.2009
Сообщений: 786
По умолчанию

Цитата:
5. Реализуйте идею из пункта 5 на любом языке программирования.
Рекурсия-с, однако.
Помощь с программами:
vk.com/alexcoder1
e-mail: informatik101@mail.ru
alexcoder вне форума Ответить с цитированием
Ответ


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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Исходники програмы Банкомат chopa Общие вопросы по Java, Java SE, Kotlin 0 14.02.2013 04:25
банкомат. выдача денег fineleave Помощь студентам 3 29.04.2011 14:55
банкомат isxaker Общие вопросы C/C++ 2 09.12.2009 21:19
Банкомат делаем.. Andrey_andrey Microsoft Office Access 1 24.05.2009 16:18