Выплата заданной суммы денег

Опубликовано Mar 1, 2012 в Математика и логика | 6 коммент.

, , ,

Выплата заданной суммы денег

Имеются монеты достоинством 1, 2, 5, 10, 25, 50 копеек. Написать функцию, которая определяет, как любую заданную сумму денег представить наименьшим количеством монет указанного достоинства.

Код решения задачи на C#

 class Program
  {
    static void CoinsCount
       (int Money, int CoinIndex, int[] CoinsValues, int[] CoinsQty)
    {
      if (CoinIndex == CoinsValues.Length - 1)
      {
        CoinsQty[CoinIndex] = Money;
        return;
      }
      else{
        CoinsQty[CoinIndex] = Money / CoinsValues[CoinIndex];
        int RestOfMoney = Money % CoinsValues[CoinIndex];
        CoinIndex++;
        CoinsCount(RestOfMoney, CoinIndex, CoinsValues, CoinsQty);
      }
    }
    static void Main(string[] args)
    {
      int[] CoinsValues = new int[6]{50,25,10,5,2,1};
      int[] CoinsQty1 = new int[6];
      CoinsCount(345, 0, CoinsValues, CoinsQty1);
 
      int[] CoinsQty2 = new int[6];
      CoinsCount(50, 0, CoinsValues, CoinsQty2);
 
      int[] CoinsQty3 = new int[6];
      CoinsCount(111, 0, CoinsValues, CoinsQty3);
    }
  }

Вопросы

  • Как Вы предлагаете изменить сигнатуру метода CoinsCount? Почему?
  • Как переписать этот метод без рекурсии?

Автор публикации:

6 Коммент. : “Выплата заданной суммы денег”

  1. Вот набросал вариант решения без рекурсии. Немного упростил сигнатуру функции.

    struct CoinsCount
    {
    	int CoinValue;
    	int num;
    };
    void CountCoinsNumber(vector<CoinsCount>& numOfCoins, int money)
    {
    	for(int i = 0; i < numOfCoins.size(); i++)
    	{
    		if((money / numOfCoins[i].CoinValue) > 0)
    		{
    			numOfCoins[i].num = money / numOfCoins[i].CoinValue;
    			money = money % numOfCoins[i].CoinValue;
    		}
    	}
    }

    Работоспособность тестировал в следующем окружении:

    #include <vector>
    #include <string>
    #include <sstream>
    #include <algorithm>
    #include <iostream>
    using namespace std;
    struct CoinsCount
    {
    	int CoinValue;
    	int num;
    };
    ///////////
    template <typename T>
    std::string toString(T val)
    {
    	std::ostringstream oss;
    	oss<< val;
    	return oss.str();
    }
    template<typename T>
    T fromString(const std::string& s)
    {
    	std::istringstream iss(s);
    	T res;
    	iss >> res;
    	return res;
    }
    //////////
    inline int compareIntFunc(const int& n1, const int& n2) { return (n1 > n2); }
    void CountCoinsNumber(vector<CoinsCount>& numOfCoins, int money)
    {
    	for(int i = 0; i < numOfCoins.size(); i++)
    	{
    		if((money / numOfCoins[i].CoinValue) > 0)
    		{
    			numOfCoins[i].num = money / numOfCoins[i].CoinValue;
    			money = money % numOfCoins[i].CoinValue;
    		}
    	}
    }
    void ShowResult(vector<CoinsCount>& numOfCoins, int money)
    {
    	cout << "We'll give you " << money << " cents"
    		<< " using the smallest amount of coins this way:" << endl;
    	for(int i = 0; i < numOfCoins.size(); i++)
    	{
    		cout << "Coins with value " << numOfCoins[i].CoinValue
    			<<": " << numOfCoins[i].num << endl;
    	}
    }
    int main()
    {
    	cout << "Please, enter the sum of money: ";
    	unsigned int sumOfMoney = 0;
    	cin >> sumOfMoney; cin.get();
    	cout << endl << "Please, enter the values of coins putting space between them:" << endl;
    	vector<int> coins;
    	string strCoins;
    	getline(cin, strCoins);
    	char *wordPointer = strtok(const_cast<char*>(strCoins.c_str()), " ");
    	do
    	{
    		string temp = string(wordPointer);
    		coins.push_back(fromString<int>(temp));
    		wordPointer = strtok(NULL, " ");
    	}while(wordPointer != NULL);
    	sort(coins.begin(), coins.end(), compareIntFunc);
    	// sorting elements in decreasing order
    	vector<CoinsCount> numOfCoins(coins.size());
    	for(int i = 0; i < coins.size(); i++)
    	{
    		numOfCoins[i].CoinValue = coins[i];
    	}
    	CountCoinsNumber(numOfCoins, sumOfMoney);
    	ShowResult(numOfCoins, sumOfMoney);
    	cin.get();
    	return 0;
    }
  2. Юрий says:

    Дело в том Галина, что ваша функция работает некорректно(если я правильно понимаю что < именьшим количеством монет указанного достоинства> еквивалентно < рное количество монет будет минимальным>).
    Пример: представляем сумму 160 монетами а имеются монеты достоинством {50, 40, 1}
    Тогда ваш алгоритм выдаст {3, 0, 10}, число монет 13
    Минимальный же набор будет при {0, 4, 0} число монет 4

    • Галина says:

      Вы все поняли правильно и провели вполне разумный тест. Предложенный алгоритм работает для последовательнойтей номиналов монет, обладающих определенными свойствами – не случайно этот перечень (1, 2, 5, 10, 25, 50 копеек)явно приведен в условии. По крайней мере я строила алгоритм исходя из этих соображений – чтобы всегда было выгоднее брать максимально возможное количество монет самого большого достоинства.
      Вообще-то после вашего примера я подумаю над этой задачей еще. Интересно найти общее решение.

      • Это классическая задача на метод динамического программирования. Вот вариант решения на C++.

         
        #include <iostream>
        #include <vector>
        using namespace std;
         
        bool coinsCount(int money, const vector<int> &coins, vector<int> &qty) {
            const int inf = 1000000000;
            vector<int> minCoins(money + 1, inf);
            minCoins[0] = 0;
         
            for (int sum = 1; sum <= money; sum++)
                for (int coin = coins.size() - 1; coin >= 0; coin--)
                    if (sum >= coins[coin]
                        && minCoins[sum] > minCoins[sum - coins[coin]] + 1)
                        minCoins[sum] = minCoins[sum - coins[coin]] + 1;
         
            //Если заданную сумму нельзя представить
            if (minCoins[money] == inf) return false;
         
            for (int sum = money; sum > 0;)
                for (int coin = coins.size() - 1; coin >= 0; coin--)
                    if (sum >= coins[coin]
                        && minCoins[sum] == minCoins[sum - coins[coin]] + 1) {
                            sum -= coins[coin];
                            ++qty[coin];
                            break;
                        }
            return true;
        }
         
        void printSolution(int money, const vector<int> &coins, const vector<int> &qty) {
            cout << "Solution for value " << money << endl;
            for (int i = 0; i < coins.size(); i++)
                cout << coins[i] << " x " << qty[i] << endl;
            cout << endl;
        }
         
        int main()
        {
        	int c[6] = {1, 2, 5, 10, 25, 50};
            int money[3] = {345, 50, 111};
            int n = sizeof(c) / sizeof(int);
        	vector<int> coins(c, c + n);
         
        	for (int i = 0; i < sizeof(money) / sizeof(int); i++) {
        	    vector<int> qty(n, 0);
                if (coinsCount(money[i], coins, qty)) printSolution(money[i], coins, qty);
                else cout << "No solution for value " << money[i] << endl;
        	}
         
            return 0;
        }
    • class Program
          {
              enum Coins : int
              {
                  One = 1,
                  Two = 2,
                  Five = 5,
                  Ten = 10,
                  DventyFive = 25,
                  Fifty = 50
              }
       
              static void Main(string[] args)
              {
                  Dictionary<Coins, int> coinsCount = CoinsCount(150);
       
                  foreach (KeyValuePair<Coins, int> item in coinsCount)
                  {
                      Console.WriteLine("{0} - {1}", item.Key, item.Value);
                  }
       
                  Console.ReadKey();
              }
       
              static Dictionary<Coins, int> CoinsCount(int money)
              {
                  Dictionary<Coins, int> result = new Dictionary<Coins, int>();
                  IEnumerable<int> coins = ((IEnumerable<int>)Enum.GetValues(typeof(Coins))).OrderByDescending(x => x);
       
                  foreach (int c in coins)
                  {
                      int count = money / c;
                      if (count > 0)
                      {
                          result.Add((Coins)c, count);
                          money = money % c;
                      }
                      if (money == 0)
                          return result;
                  }
                  return result;
              }
          }
  3. #include <algorithm>
    #include <iostream>
    #include <vector>
    #include <map>
     
    //возвращать будем осациативный массив std::map
    std::map<int, int> give_me_money(std::vector<int> &coins, int summ) {
    	//сортируем массив (навсякий случай)
    	std::make_heap(coins.begin(), coins.end());
    	std::map<int, int> result;
    	int s = summ;
    	while(coins.size() != 0 && s != 0) {
    		//берём максимальную денежку
    		int coin = coins.front();
    		std::pop_heap (coins.begin(), coins.end());
    		coins.pop_back();
    		//если денюшка слишком большая
    		if(coin > s) {
    			continue;
    		}
    		int countCoins = s / coin;
    		s %= coin;
    		if(countCoins != 0) {
    			result[coin] = countCoins;
    		}
    	};
    	return result;
    }
     
    int main() {
    	int c[] = {1, 2, 5, 10, 25, 50};
    	std::vector<int> coins(c, c + 6);
    	std::map<int, int> res = give_me_money(coins, 1234);
    	for (std::map<int,int>::iterator it = res.begin(); it!=res.end(); ++it)
        	std::cout << it->first << " <= " << it->second << '\n';
    	return 0;
    }

    если нет нужного номинала возвращает количество близкое к сумме

Оставить комментарий

Ваш адрес email не будет опубликован.


*