Задача по информатике на собеседовании в IT-компанию. ''Размен монет''

Всем привет! Сегодня решим задачу по информатике, которую часто дают на собеседованиях в различные IT-компании (или похожую ей).

Задача: Напишите программу, которая определит количество различных комбинаций американских монет(1 цент, 5 центов, 10 центов, 25 и 50 центов), которые могут сложиться в определенную сумму, введённую с клавиатуры. Максимальная сумма 1000 центов.

Решение: Рассмотрим на примере. Пусть сумма будет равна 25 центов.

Сначала пытаемся использовать самые большие монеты. Монета в 50 центов в данном случае не пригодится. Поэтому берём в 25 центов. Это уже 1 вариант. Так же мы можем разбить сумму в 25 центов и без монеты в 25 центов (Т.е использовав монеты достоинством в 10, 5, 1). На рисунке показан этот случай стрелкой влево.

Число 25 можно разбить, использовав 10-ти центовые монеты, а можно и более мелкими монетами(5, 1). Поэтом от 25-ти на рисунке идут опять две стрелочки. Если мы используем монету достоинством в 10 центов, то мы кладём 10 и нам теперь необходимо разбить уже 15. Число 15 опять мы может разбить, использовав 10-ти центовые монеты, а можно 15 разбить и более мелкими монетами. И т.д. Продолжая эту логику у нас от каждого числа будет по 2 стрелочки. Продолжаем раскладывать, пока у нас не получатся элементарные варианты. Количество вариантов обозначены красным цветом.

Почему от некоторых чисел на рисунке идёт по 1-му варианту ? Это происходит из-за того, что мы в этих вариантах решили разбить число самыми маленькими монетами в 1 цент. Таким образом, даже большие числа вроде 20, будут раскладываться в этих случаях единственным образом 20 = 1 + ... + 1. А почему от 5 идёт два варианта ? Число пять можно разложить, как пяточком, так и по 1 центу.

Теперь просуммируем все числа красным цветом и получим количество вариантов. У нас получается число 13

Данный тип задач может попасться и на олимпиаде по информатике. Реализовывать будем на языке программирования C#!

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp18
{
    class Program
    {
        static void Main(string[] args)
        {
            int  n = Convert.ToInt32(Console.ReadLine());
            if (n > 1000) Console.WriteLine("Число слишком большое");
            else
                Console.WriteLine(getCountOfWays(n, 4));
            Console.ReadKey();

        }

        static int getCountOfWays(int money, int indexOfCoin)
        {
            int[] COINS_NOM = { 1, 5, 10, 25, 50 };
            if (money < 0 || indexOfCoin < 0) return 0;
            if (money == 0 || indexOfCoin == 0) return 1;
            return getCountOfWays(money, indexOfCoin - 1) + getCountOfWays(money - COINS_NOM[indexOfCoin], indexOfCoin);
        }
    }
}