Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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


Донат для форума - использовать для поднятия настроения себе и модераторам

А ещё здесь можно купить рекламу за 25 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

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

Задача
Имеется банкомат, в котором есть почти неограниченное количество купюр 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, 20:02   #2
andronova
Пользователь
 
Аватар для andronova
 
Регистрация: 17.02.2009
Сообщений: 21
Репутация: 10
По умолчанию

Пожалуйста, помогите!
andronova вне форума   Ответить с цитированием
Старый 01.04.2015, 21:54   #3
min@y™
Цифровой кот
Профессионал
 
Аватар для min@y™
 
Регистрация: 29.08.2014
Адрес: 1600, пенсильвания-авеню, п.г.т. верхний Вашингтонск, 8126 км от МКАД, от поста ГАИ - налево.
Сообщений: 7,664
Репутация: 2449

icq: 100500
skype: kick-ass
По умолчанию

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

skype: alexcoder1
По умолчанию

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Исходники програмы Банкомат 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 22:19
Банкомат делаем.. Andrey_andrey Microsoft Office Access 1 24.05.2009 16:18


05:19.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.