|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
01.04.2015, 19:02 | #1 |
Пользователь
Регистрация: 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 на любом языке программирования. |
01.04.2015, 19:02 | #2 |
Пользователь
Регистрация: 17.02.2009
Сообщений: 21
|
Пожалуйста, помогите!
|
01.04.2015, 20:54 | #3 |
Цифровой кот
Старожил
Регистрация: 29.08.2014
Сообщений: 7,629
|
Задавай вопросы, будем отвечать.
Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
|
02.04.2015, 10:06 | #4 | |
Форумчанин
Регистрация: 31.05.2009
Сообщений: 786
|
Цитата:
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Исходники програмы Банкомат | 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 |