перевод статьи https://www.java67.com/2022/05/solved-how-to-solve-coin-change-problem.html
Проблема размена монет - один из популярных вопросов на собеседовании по программированию, и знание того, как решить эту проблему, может помочь вам во время собеседования. Также полезно изучить пару приемов и структуру данных. Эта проблема в какой-то степени связана с массивами, поэтому мы обсудим, что такое массив, но прежде чем мы углубимся, нам нужно понять проблему. Мы собираемся решить проблему с монетами, определив, сколькими возможными способами может быть выплачена сумма. Предположим, Мэри - деловая женщина, которая занимается разменом монет.
Итак, клиент приходит, чтобы разменять определенное количество монет с монетами, которые есть у Мэри, сколько возможных способов она может обменять монеты клиентов? Если у Мэри есть следующие монеты 1,2,3,4,5, и клиент хочет поменять 16. Возможные способы, которыми Мэри могла бы разменять монету, таковы:
Пример 1 :
Input: [1,2,3,4,5]
Sum: 16
Output: 4
Пояснение: Для получения желаемой суммы, равной 16, требуется четыре монеты: [5,5,5,1]
Пример 2:
input: [2, 4, 6, 8]
Sum: 15
Output: -1
Пояснение: Комбинация с суммой 15 отсутствует.
Пример 3:
Input: [1,2,5,9,8]
Sum: 17
Output: 2
Пояснение: Для получения желаемой суммы, которая составляет 17, требуется две монеты: [9,8]
В таком случае мы можем использовать рекурсию для решения этой проблемы, поскольку мы должны перебирать все возможные комбинации монет, которые равны заданной сумме, каждый раз, обновляя минимальное количество монет, необходимое для создания этой суммы.
Теперь давайте посмотрим на пример кода:
public class Main
{
public static int count(int[] coins, int number, int target)
{
if (target == 0) {
return 1;
}
if (target < 0 || number< 0) {
return 0;
}
int first= count(coins, number, target - coins[number]);
int second= count(coins, number - 1, target);
return first + second;
}
public static void main(String[] args)
{
int[] coinArray = { 1, 2, 3 };
int target = 4;
System.out.print("The total number of ways to get the desired change is "
+ count(coinArray, coinArray.length - 1, target));
}
}
В такой реализации кода, у нас есть метод с именем count() в строке 3, который принимает 3 параметра, во-первых, массив coin типа int, во-вторых, число типа int, а также цель типа int. (Цель - это то конкретное число, на которое мы обращаем внимание).
Первое условие в строке 4 гласит, что если цель равна 0, то должно быть возвращено 1. таким образом, программа завершается на этом, но если нет, она переходит к следующей строке и проверяет условие в строке 8. то есть, если цель меньше 0 или число меньше 0, оно должно возвращать 0. и заканчивается там, если условие истинно.
Но если первое и второе условие равно false, то оно переходит к строке 11 и начинает выполнение оттуда. Это рекурсивный вызов, метод, вызывающий себя сам по себе.
Итак, метод был вызван дважды и сохранен в двух разных переменных, названных first и second соответственно. таким образом, первый вызов метода принял coins, который является массивом в качестве первого аргумента, второй аргумент - это число, а третий аргумент - это цель минус массив монет с номером, т.е. coin[number].
Во втором вызове метода он принимает массив монет[number - 1] и цель соответственно. и он возвращает сумму первого и второго в строке 13.
Строка 16 - это основной метод. В строке 18 создается и инициализируется массив монет.
Строка 19 - целевая переменная типа int, инициализируется значением 4
Line 20 выводит результат и значения переменных: массив монет, его длину - 1, и цель.
КАК РАБОТАЮТ МАССИВЫ
массив - это набор элементов с одинаковым типом. Это означает, что вы не можете найти там различные типы элементов или типов данных. Вы можете видеть выше, что у нас есть только массив целых чисел, это числа. В java, когда вы создаете массив заново, вы должны сделать две важные вещи:
Во-первых, вы должны указать тип поступающего элемента. будь то целое число, строка, логическое значение и т.д. Хорошо то, что после того, как вы указали тип данных, вы не можете его изменить. Вы не можете объявить массив int и теперь заполнить его строковым элементом, нет!, это так не работает. Это приводит к ошибке компиляции.
Во-вторых, при объявлении массива в java вы должны указать ожидаемую длину. И она тоже никогда не изменится. Ниже показано, как объявить массив:
int [] numbers= new int [10];
Заключение
В этой статье вы узнали, как решить проблему с разменом монет. Кроме того, помните, что любая попытка добавить больше, чем вы указали в конкретном массиве, приводит к исключению индекса массива за пределами границ. Вы не можете сказать, что длина элементов, поступающих при создании, равна 10, и в итоге вы добавляете 11 элементов, извините, это не сработает!.
#java #перевод
