В этом примере мы обсудим оптимальное решение для решения проблемы размена денег с помощью жадного алгоритма.
Жадный алгоритм-это тот, который всегда выбирает лучшее решение в то время, без учета того, как этот выбор повлияет на будущие выборы. Здесь мы обсудим, как использовать жадный алгоритм для размена денег.
Было доказано, что оптимальное решение для размена денег всегда можно найти, используем для этого наши российские рубли в качестве монет монет
Например, предположим, вы покупаете некоторые предметы в магазине, и для сдача от вашей покупки составляет 63 рубля. Как продавец определяет сдачу, чтобы ее вам дать? Если продавец следует жадному алгоритму, он или она дает вам один полтинник, один червонец и три рубля. Это наименьшее количество монет, которое будет равно 63 рублям.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
using System; using System.Text; using System.Security.Cryptography; public class CsharpHashAlgo { static void MakeChange(double origAmount, double remainAmount, int[] coins) { if ((origAmount % 50) < origAmount) { coins[3] = (int)(origAmount / 50); remainAmount = origAmount % 50; origAmount = remainAmount; } if ((origAmount % 10) < origAmount) { coins[2] = (int)(origAmount / 10); remainAmount = origAmount % 10; origAmount = remainAmount; } if ((origAmount % 5) < origAmount) { coins[1] = (int)(origAmount / 5); remainAmount = origAmount % 5; origAmount = remainAmount; } if ((origAmount % 1) < origAmount) { coins[0] = (int)(origAmount / 1); remainAmount = origAmount % 1; } } static void ShowChange(int[] arr) { if (arr[3] > 0) Console.WriteLine("Количество 50 рублевых банкнот: " + arr[3]); if (arr[2] > 0) Console.WriteLine("Количество 10 рублевых монет: " + arr[2]); if (arr[1] > 0) Console.WriteLine("Количество 5 рублевых монет: " + arr[1]); if (arr[0] > 0) Console.WriteLine("Количество 1 рублевых монет: " + arr[0]); } static void Main() { Console.WriteLine("Введите сумму которую хотите разменять:"); double origAmount = Convert.ToDouble(Console.ReadLine()); double toChange = origAmount; double remainAmount = 0.0; int[] coins = new int[4]; MakeChange(origAmount, remainAmount, coins); Console.WriteLine("Лучше способ размена " + toChange + " в рублях: "); ShowChange(coins); Console.ReadKey(); } } |
Вывод:
Введите сумму которую хотите разменять:
63
Лучше способ размена 63 в рублях:
Количество 50 рублевых банкнот: 1
Количество 10 рублевых монет: 1
Количество 1 рублевых монет: 3