В массиве K(n) в порядке убывания представлены достоинства денежных знаков (купюр и монет)

@kiryagos · Регистрация: 27.02.2020

Студворк — интернет-сервис помощи студентам

В массиве K(n) в порядке убывания представлены достоинства денежных знаков (купюр и монет) валютной системы некоторой страны. Реализовать выдачу в этой системе заданной суммы m минимальным числом денежных знаков. Разработать блок-схему и программу для решения этой задачи.
Помогите, пожалуйста, с решением.

@u235 · 27.02.2020, 18:27

Python
1
2
3
4
5
K=[5000, 2000, 1000, 500, 200, 100, 50, 10, 5, 2, 1]
n=11357
for i in K:
    m,n=divmod(n, i)
    print(m,'купюры/чеканной монеты по ', i,'у.е.')

@palva · 27.02.2020, 20:25

Это так называемый жадный алгоритм. Но при виде денег не нужно жадничать. Например,

Python
1
2
K=[4, 3, 1]
n=6

Алгоритм предложит 3 купюры: 6 = 4 + 1 + 1. Но можно обойтись двумя купюрами 6 = 3 + 3.
Наверно, пока я набираю этот текст, кто-то уже предложит правильный алгоритм.

Добавлено через 35 минут
Вот так на моих данных печатает правильно. Может, ошибся где...

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
K = [4, 3, 1]
m = 6
A = [0]*(m+1)
for s in range(1, m+1):
    mn = -1
    for i in K:
        ind = s - i
        p = 0 if ind < 0 else A[ind]
        if mn < 0:
            mn = p
        else:
            mn = min(mn, p)
    A[s] = 1 + mn
print(A[m], "banknotes.")

Добавлено через 8 минут
Да, ошибся. Не обработал случаи, когда разменять невозможно. Надо поправлять.

Добавлено через 41 минуту
Встрял в обсуждение -- придется делать.
A[s] это минимальное число купюр для размена s единиц или -1, если размен невозможен.
Полагаем, что A[0] = 0 и заполняем список A слева направо. Где-то в середину нужно вставить append для накопления списка выплаченных купюр. Но это уже в качестве упражнения.
И опять не исключено, что остались ошибки. Не особо тестировал.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
K = [4, 2, 1]
m = 10
A = [0]*(m+1)
for s in range(1, m+1):
    mn = -1
    for i in K:
        ind = s - i
        p = -1 if ind < 0 else A[ind]
        if p >= 0:
            if mn < 0:
                mn = p
            else:
                mn = min(mn, p)
    if mn == -1:
        A[s] = -1
    else:
        A[s] = 1 + mn
print(A)

Новые блоги и статьи Все статьи Все блоги /
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .

@kiryagos 0 / 0 / 0 Регистрация: 27.02.2020 Сообщений: 2

	В массиве K(n) в порядке убывания представлены достоинства денежных знаков (купюр и монет) 27.02.2020, 18:00. Показов 3732. Ответов 2 Метки python, массив (Все метки) В массиве K(n) в порядке убывания представлены достоинства денежных знаков (купюр и монет) валютной системы некоторой страны. Реализовать выдачу в этой системе заданной суммы m минимальным числом денежных знаков. Разработать блок-схему и программу для решения этой задачи. Помогите, пожалуйста, с решением. 0