Подсчет монет в APL - PullRequest
Новая
       35

Подсчет монет в APL

1 голос
/ 29 мая 2019

Функция Count ниже вычисляет минимальное количество монет, которое суммируется до заданной суммы. 

∇ R ← d AppendQuotRem qrs; oldR; q; r
    oldR ← 2 ⊃ (⍴qrs) ⊃ qrs
    q ← ⌊oldR ÷ d
    r ← oldR - d × q
    R ← qrs , ,⊂(q r)
∇

∇ R ← Count amount; ds; qrs; qs
    ds ← 1 5 10 25 50  ⍝ coin denominations in cents
    qrs ← ⊃AppendQuotRem/ ds , ⊂,⊂(0 amount)
    qs ← 1 ⊃¨ qrs
    R ← ds ,[0.5] ⌽1 ↓ qs
∇

Для каждой деноминации я вычисляю частное и остаток. Остальная часть используется в расчете с участием следующего номинала. Есть ли более короткий и / или более прямой способ решения проблемы?

1 Ответ

1 голос
/ 30 мая 2019

Проблема изменения на самом деле довольно сложная . Полный подход APL включен в рабочую область dfns .

Ваш алгоритм жадный, который дает неправильный результат для определенных наборов наборов монетных номиналов. Просто так получается, что вы работаете с набором, который вы используете в своем примере. Давайте изменим вашу Count функцию: 

∇ R ← Count134 amount; ds; qrs; qs
    ds ← 1 3 4  ⍝ coin denominations in cents
    qrs ← ⊃AppendQuotRem/ ds , ⊂,⊂(0 amount)
    qs ← 1 ⊃¨ qrs
    R ← ds ,[0.5] ⌽1 ↓ qs
∇
      Count134 6
1 3 4
2 0 1

Здесь используются три монеты, но правильный ответ - 3 цента: 

1 3 4
0 2 0

Тем не менее, общие системы чеканки разработаны так, что жадный алгоритм даст оптимальный результат. Вот, таким образом, упрощение вашего кода: 

∇ R ← d AppendQuotRem qrs; oldR; q; r
    oldR ← 1 ↑ qrs
    q ← ⌊oldR ÷ d
    r ← d | oldR
    R ← r , q , 1 ↓ qrs
∇

∇ R ← Count amount; ds
    ds ← 1 5 10 25 50  ⍝ coin denominations in cents
    R ← ds ,[0.5] ⊃AppendQuotRem/ 1 ↓ ds , amount
∇

Попробуйте онлайн!

...