Question

Є 10 монет по 2 євро та 15 монет по 1 євро. Скількома різними способами можна сплатити 17 євро, використовуючи лише ці монети? (Порядком монет при виплаті знехтувати.)​

Answer 1

Ответ:

Пошаговое объяснение:

15×1+2=17

8×2+1=17

7×2+3×1=17

6×2+5×1=17

5×2+7=17; 4×2+9=17 ; 3×2+11×1=17; 2×2+13×1=17

8 способов

Answer 2

Для вирішення цієї задачі можна скористатися методом динамічного програмування. Спочатку розглянемо випадок, коли використовується лише монети по 2 євро. Знайдемо всі можливі комбінації, якими можна сплатити 17 євро за допомогою 10 монет по 2 євро.

Використання лише монет по 2 євро

Для цього використаємо метод динамічного програмування. Створимо масив dp, де dp[i] буде містити кількість способів, якими можна сплатити суму i євро за допомогою монет по 2 євро. Початково всі елементи масиву dp будуть дорівнювати 0.

1. Ініціалізуємо dp[0] = 1, оскільки єдиний спосіб сплатити суму 0 євро - не використовувати жодну монету. 2. Проходимо по всім монетам по 2 євро і для кожної монети оновлюємо значення dp. Для кожної монети ми розглядаємо всі можливі суми від 2 євро до 17 євро і додаємо кількість способів, якими можна сплатити суму (сума - монета), до dp[сума]. 3. Після проходження по всім монетам dp[17] буде містити кількість способів, якими можна сплатити 17 євро за допомогою монет по 2 євро.

Аналогічно можна розглянути випадок, коли використовуються лише монети по 1 євро. Знайдемо всі можливі комбінації, якими можна сплатити 17 євро за допомогою 15 монет по 1 євро.

Використання лише монет по 1 євро

Також використаємо метод динамічного програмування. Створимо масив dp, де dp[i] буде містити кількість способів, якими можна сплатити суму i євро за допомогою монет по 1 євро. Початково всі елементи масиву dp будуть дорівнювати 0.

1. Ініціалізуємо dp[0] = 1, оскільки єдиний спосіб сплатити суму 0 євро - не використовувати жодну монету. 2. Проходимо по всім монетам по 1 євро і для кожної монети оновлюємо значення dp. Для кожної монети ми розглядаємо всі можливі суми від 1 євро до 17 євро і додаємо кількість способів, якими можна сплатити суму (сума - монета), до dp[сума]. 3. Після проходження по всім монетам dp[17] буде містити кількість способів, якими можна сплатити 17 євро за допомогою монет по 1 євро.

Загальна кількість способів

Щоб знайти загальну кількість способів, якими можна сплатити 17 євро, використовуючи лише ці монети, потрібно просумувати dp[17] для випадку з монетами по 2 євро та dp[17] для випадку з монетами по 1 євро.

Отже, загальна кількість способів, якими можна сплатити 17 євро, використовуючи лише ці монети, дорівнює сумі dp[17] для випадку з монетами по 2 євро та dp[17] для випадку з монетами по 1 євро.

Застосуємо описаний алгоритм для знаходження кількості способів сплатити 17 євро за допомогою монет по 2 євро та 15 монет по 1 євро.