Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

Задача по информатике на собеседовании в 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);
        }
    }
}

Ещё одна схема для суммы 37 приведена на рисунке. Получается 24 комбинации.


Олимпиадная задача по информатике. Размен монет


На этом всё! Удачи!



11-02-2018 в 21:54:07





Похожая статья:

Задача по информатике. Шифр Цезаря.

Сегодня разберём самой простой тип шифрования текста - шифр Цезаря....

Категория: Алгоритмы  Подкатегория: Задачи
Дата: 15-01-2018 в 16:47:34 0



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



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота:

Ответ:


Последние
видео:



Шейкер-сортировка (С#)
ОГЭ по информатике. Задание 18


Подготовка к
ОГЭ


Подготовка к ОГЭ по информатике


Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy