Подсчет монет в APL
Функция Считать ниже вычисляет минимальное количество монет, которое в сумме дает заданную сумму.
∇ 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
∇
Для каждого номинала я вычисляю частное и остаток. Остаток используется при расчете следующего номинала. Есть ли более короткий и/или более прямой способ решить проблему?
@DanBron Я так не думаю. {⍺←1 5 10 25 50 ⋄ ⍺⍪⍉⍪⌽⍵⊤⍨0,2÷/⌽⍺}дает 75=50+10+10+5 вместо 75=50+25.
Ответы 2
проблема внесения изменений на самом деле является довольно тяжело. Полный подход 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
∇
Жадный алгоритм, где денежная стоимость равна 100 50 20 10 5 1 единица.
∇r←Greedy w;i;d;k;x;l
r←⍬⋄i←1⋄d←100 50 20 10 5 1⋄l←≢d
r←r,k←⌊w÷x←d[i]⋄w-←k×x⋄→2×⍳l≥i+←1
r←2 l⍴d,r
∇
Prova←{+/⍵[1;]×⍵[2;]}
m←Greedy 125
m
100 50 20 10 5 1
1 0 1 0 1 0
Prova m
125
В Dyalog APL у вас есть Оператор кодировать
⊤, который предназначен для этого.