/*============================================================================== Лабораторна робота №5. Завдання 2. Варіант 19. Тема: рекурсивна обробка послідовностей. Умова (таблиця 5.2, варіант 19): потрібно сплатити поштове відправлення, вартість котрого складає m копійок, а в наявності тільки поштові марки номіналом x, y, z копійок. Скількома різними способами можна сплатити поштове відправлення? Розробити рекурсивну функцію для обчислення кількості зображень числа m у вигляді суми певних фіксованих чисел з використанням рекурентних співвідношень. Використати рекурентне співвідношення для чисел Фібоначчі: | 1, n = 0 f(n) = | 1, n = 1 | f(n-1) + f(n-2), n > 2 ОБМЕЖЕННЯ УМОВИ: забороняється використовувати масиви і рядки. Використання рекурсії обов'язкове. Виконав: Одарчук Олексій, КНУ імені Тараса Шевченка, ФІТ, група ІПЗ-11. Компілятор: gcc -std=c17 ==============================================================================*/ #include #include /* Найбільша вартість відправлення. Рекурсія без запам'ятовування проміжних результатів має експоненційну трудомісткість, а масиви для запам'ятовування умова забороняє. Найгірший випадок — найдрібніші номінали 1, 2, 3: тоді при m = 30 виконується близько 1,9*10^8 викликів (частки секунди), при m = 35 — 4*10^9 (секунди), а при m = 40 програма вже не завершується за прийнятний час. Тому межу встановлено на рівні 30. */ #define MAX_COST 30 /* Найбільший номінал марки: більший за вартість відправлення номінал використати неможливо, тому межа збігається з MAX_COST. */ #define MAX_STAMP 30 /* Лічильник викликів рекурсивної функції — характеристика трудомісткості. Оголошений глобально, щоб не додавати службовий параметр до функції, яка має відповідати рекурентному означенню з умови. */ unsigned long long g_calls = 0; /* Поточна та максимальна глибина вкладеності рекурсивних викликів. */ int g_currentDepth = 0; int g_maxDepth = 0; /*------------------------------------------------------------------------------ countWays — кількість різних способів набрати суму m марками номіналом x, y, z копійок. Рекурентне співвідношення. Будь-який спосіб оплати починається з наклеювання однієї марки — котроїсь із трьох. Після цього лишається сплатити суму, меншу на її номінал. Отже: w(m) = w(m - x) + w(m - y) + w(m - z), w(0) = 1 (сума набрана — це один завершений спосіб), w(m) = 0 при m < 0 (перевитрата — спосіб не існує). Це співвідношення має ту саму будову, що й означення чисел Фібоначчі з умови варіанта: значення в точці визначається через значення в кількох попередніх точках, а базові випадки зупиняють рекурсію. При x = 1, y = 2 і третьому номіналі, більшому за m, воно вироджується точно у Фібоначчі. Способи вважаються різними, якщо відрізняється ПОСЛІДОВНІСТЬ наклеювання марок: 1+2 і 2+1 — це два різних способи. Саме таку інтерпретацію задає співвідношення Фібоначчі, вказане в умові варіанта. Параметри: m [вхідний] — сума, яку лишилось сплатити, копійок; x, y, z [вхідні] — номінали наявних марок, копійок. Повертає: кількість способів сплатити суму m. Умови завершення рекурсії: m = 0 (успіх) та m < 0 (глухий кут). Локальні змінні: ways — накопичувана кількість способів. Однакові номінали враховуються лише один раз: інакше один і той самий спосіб було б підраховано двічі. ------------------------------------------------------------------------------*/ unsigned long long countWays(int m, int x, int y, int z) { ++g_calls; ++g_currentDepth; if (g_currentDepth > g_maxDepth) g_maxDepth = g_currentDepth; unsigned long long ways; if (m == 0) { ways = 1; /* сума набрана точно */ } else if (m < 0) { ways = 0; /* перевитрата — глухий кут */ } else { ways = countWays(m - x, x, y, z); if (y != x) ways += countWays(m - y, x, y, z); if (z != x && z != y) ways += countWays(m - z, x, y, z); } --g_currentDepth; return ways; } /*------------------------------------------------------------------------------ readInt — прочитати ціле число з контролем коректності введення. Параметри: prompt [вхідний] — текст запрошення; value [вихідний] — адреса змінної для введеного числа; low [вхідний] — найменше припустиме значення; high [вхідний] — найбільше припустиме значення. Повертає: true — число прочитано; false — вхідні дані вичерпано. ------------------------------------------------------------------------------*/ bool readInt(const char *prompt, int *value, int low, int high) { for (;;) { printf("%s", prompt); const int scanned = scanf("%d", value); if (scanned == EOF) return false; if (scanned == 1 && *value >= low && *value <= high) return true; if (scanned != 1) { int c; /* очищення буфера */ while ((c = getchar()) != '\n' && c != EOF) { } } printf("Помилка: потрібне ціле число від %d до %d.\n", low, high); } } /*------------------------------------------------------------------------------ Головна функція. Читає вартість відправлення та номінали марок, обчислює кількість способів оплати й виводить характеристики рекурсії. Локальні змінні: m — вартість поштового відправлення, копійок; x, y, z — номінали марок, копійок; ways — кількість способів оплати. ------------------------------------------------------------------------------*/ int main() { printf("Лабораторна робота №5, завдання 2 (варіант 19)\n"); printf("Виконав: студент групи ІПЗ-11 Одарчук Олексій\n"); printf("Кількість способів сплатити m копійок марками номіналом x, y, z\n\n"); printf("Способи вважаються різними, якщо відрізняється послідовність\n" "наклеювання марок (1+2 і 2+1 — два різних способи).\n\n"); int m = 0, x = 0, y = 0, z = 0; /* Верхня межа вартості обмежена: трудомісткість рекурсії без запам'ятовування зростає експоненційно з ростом m. */ if (!readInt("Уведіть вартість відправлення m (1..30): ", &m, 1, MAX_COST)) return 1; if (!readInt("Уведіть номінал першої марки x (1..30): ", &x, 1, MAX_STAMP)) return 1; if (!readInt("Уведіть номінал другої марки y (1..30): ", &y, 1, MAX_STAMP)) return 1; if (!readInt("Уведіть номінал третьої марки z (1..30): ", &z, 1, MAX_STAMP)) return 1; if (x == y || x == z || y == z) printf("\nУвага: серед номіналів є однакові — повторні враховуються\n" "один раз, інакше однакові способи рахувалися б двічі.\n"); g_calls = 0; g_currentDepth = 0; g_maxDepth = 0; const unsigned long long ways = countWays(m, x, y, z); printf("\nВартість відправлення: %d коп.\n", m); printf("Номінали марок: %d, %d, %d коп.\n", x, y, z); printf("\nКількість способів оплати: %llu\n", ways); if (ways == 0) printf("Сплатити цю суму наявними номіналами неможливо.\n"); printf("\nХарактеристики рекурсії\n"); printf(" Викликів рекурсивної функції: %llu\n", g_calls); printf(" Глибина рекурсії: %d\n", g_maxDepth); return 0; }