/*============================================================================== Лабораторна робота №6. Завдання 3. Варіант 19. Тема: многочлени, алгебраїчні операції над масивами коефіцієнтів. Умова (таблиця 6.1, завдання 19.3): увести з клавіатури цілі числа n, m (n > m) — степені двох многочленів, n > 2, m > 2. Увести або згенерувати у вказаному користувачем діапазоні значення коефіцієнтів двох многочленів n m f(x) = SUM a[i]*x^(n-i), g(x) = SUM b[i]*x^(m-i) i=0 i=0 Значення деяких коефіцієнтів можуть дорівнювати нулю. Визначити і вивести на екран вирази, що є: - часткою від ділення многочлена f(x) на многочлен g(x), використовуючи схему Горнера [3.5]; - остачею від ділення многочлена f(x) на многочлен g(x). Здійснити перевірку результату ділення многочленів, визначивши добуток частки на многочлен-дільник з додаванням остачі. ОБМЕЖЕННЯ УМОВИ: забороняється використовувати STL, std::vector, бібліотечні методи. Виконав: Одарчук Олексій, КНУ імені Тараса Шевченка, ФІТ, група ІПЗ-11. Компілятор: gcc -std=c17 ==============================================================================*/ #include #include #include #include /* Найбільший припустимий степінь многочлена. */ const int MAX_DEGREE = 20; /* Допуск, за яким коефіцієнт вважається нульовим під час виведення та порівняння многочленів. */ const double EPS = 1e-9; /*------------------------------------------------------------------------------ absValue — модуль дійсного числа. Реалізовано власними засобами, без функції fabs() з math.h: умова лабораторної роботи забороняє бібліотечні методи, тому заголовний файл math.h у програмі не підключається взагалі. Параметри: x [вхідний] — дійсне число. Повертає : модуль числа x. ------------------------------------------------------------------------------*/ double absValue(double x) { return x < 0.0 ? -x : x; } /*------------------------------------------------------------------------------ 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); } } /*------------------------------------------------------------------------------ readDouble — прочитати дійсне число з контролем введення. Параметри: prompt [вхідний], value [вихідний]. Повертає : true — число прочитано; false — вхідні дані вичерпано. ------------------------------------------------------------------------------*/ bool readDouble(const char *prompt, double *value) { for (;;) { printf("%s", prompt); const int scanned = scanf("%lf", value); if (scanned == EOF) return false; if (scanned == 1) return true; int c; /* очищення буфера */ while ((c = getchar()) != '\n' && c != EOF) { } printf("Помилка: очікується дійсне число.\n"); } } /*------------------------------------------------------------------------------ printPolynomial — вивести многочлен у звичному алгебраїчному вигляді. Коефіцієнти зберігаються у порядку спадання степенів: c[0] — коефіцієнт при x^degree, c[degree] — вільний член. Нульові коефіцієнти пропускаються, знак і одиничні коефіцієнти оформлюються природно. Параметри: name [вхідний] — назва многочлена (для заголовка); c [вхідний] — масив коефіцієнтів; degree [вхідний] — степінь многочлена. Локальні змінні: printed — чи вже виведено хоча б один доданок; power — степінь при поточному коефіцієнті; value — значення поточного коефіцієнта; magnitude — модуль поточного коефіцієнта. ------------------------------------------------------------------------------*/ void printPolynomial(const char *name, const double c[], int degree) { printf("%s = ", name); bool printed = false; for (int i = 0; i <= degree; ++i) { const double value = c[i]; const int power = degree - i; if (absValue(value) < EPS) continue; /* нульовий коефіцієнт не виводимо */ if (printed) printf(value < 0 ? " - " : " + "); else if (value < 0) printf("-"); const double magnitude = absValue(value); /* Коефіцієнт 1 перед змінною не пишеться, окрім вільного члена. */ if (absValue(magnitude - 1.0) > EPS || power == 0) printf("%.4g", magnitude); if (power > 0) { printf("x"); if (power > 1) printf("^%d", power); } printed = true; } if (!printed) printf("0"); /* усі коефіцієнти нульові */ printf("\n"); } /*------------------------------------------------------------------------------ fillPolynomial — заповнити масив коефіцієнтів многочлена. Параметри: c [вихідний] — масив коефіцієнтів; degree [вхідний] — степінь многочлена; name [вхідний] — назва многочлена (для запрошень); byHand [вхідний] — true: введення з клавіатури; false: генерація; low, high [вхідні] — межі діапазону для генерації. Повертає : true — заповнено; false — вхідні дані вичерпано. ------------------------------------------------------------------------------*/ bool fillPolynomial(double c[], int degree, const char *name, bool byHand, double low, double high) { if (byHand) { printf("Уведіть коефіцієнти многочлена %s від старшого до вільного члена " "(усього %d):\n", name, degree + 1); for (int i = 0; i <= degree; ++i) { char prompt[64]; snprintf(prompt, sizeof prompt, " коефіцієнт при x^%d = ", degree - i); if (!readDouble(prompt, &c[i])) return false; } } else { for (int i = 0; i <= degree; ++i) { /* Псевдовипадкове дійсне число у діапазоні [low; high], з одним десятковим знаком (решта цифр відкидається). */ const double t = (double)rand() / RAND_MAX; c[i] = low + t * (high - low); c[i] = (double)((int)(c[i] * 10.0)) / 10.0; } } return true; } /*------------------------------------------------------------------------------ dividePolynomials — поділити многочлен f на многочлен g за схемою Горнера. Узагальнена схема Горнера (синтетичне ділення). Робочий масив ініціалізується коефіцієнтами діленого. На кожному кроці старший коефіцієнт робочого масиву ділиться на старший коефіцієнт дільника — це черговий коефіцієнт частки; потім із робочого масиву віднімається дільник, помножений на цей коефіцієнт і зсунутий на відповідну позицію: q[i] = work[i] / b[0] work[i+j] = work[i+j] - q[i]*b[j], j = 0..m Після n-m+1 кроків у хвості робочого масиву лишаються коефіцієнти остачі. Кількість операцій множення з відніманням — (n-m+1)*(m+1). Схема оперує лише коефіцієнтами: степені x не обчислюються взагалі. Параметри: a [вхідний] — коефіцієнти діленого f(x), (n+1) штук; n [вхідний] — степінь многочлена f; b [вхідний] — коефіцієнти дільника g(x), (m+1) штук; m [вхідний] — степінь многочлена g; q [вихідний] — коефіцієнти частки, (n-m+1) штук; r [вихідний] — коефіцієнти остачі, m штук (степінь остачі < m). Передумова: n >= m, b[0] != 0 — перевіряється у викличній функції. Локальні змінні: work — робочий масив коефіцієнтів, що поступово перетворюється на остачу; i, j — індекси кроку ділення та коефіцієнта дільника. ------------------------------------------------------------------------------*/ void dividePolynomials(const double a[], int n, const double b[], int m, double q[], double r[]) { double work[MAX_DEGREE + 1]; for (int i = 0; i <= n; ++i) work[i] = a[i]; for (int i = 0; i <= n - m; ++i) { q[i] = work[i] / b[0]; for (int j = 0; j <= m; ++j) work[i + j] -= q[i] * b[j]; } /* Остача — останні m коефіцієнтів робочого масиву. */ for (int i = 0; i < m; ++i) r[i] = work[n - m + 1 + i]; } /*------------------------------------------------------------------------------ multiplyAndAdd — обчислити q(x)*g(x) + r(x) для перевірки результату ділення. Параметри: q [вхідний] — коефіцієнти частки; dq [вхідний] — степінь частки; b [вхідний] — коефіцієнти дільника; m [вхідний] — степінь дільника; r [вхідний] — коефіцієнти остачі (m штук, степінь m-1); out [вихідний] — коефіцієнти результату, (dq+m+1) штук. Локальні змінні: degree — степінь результату (dq + m); i, j — індекси коефіцієнтів співмножників. ------------------------------------------------------------------------------*/ void multiplyAndAdd(const double q[], int dq, const double b[], int m, const double r[], double out[]) { const int degree = dq + m; for (int i = 0; i <= degree; ++i) out[i] = 0.0; /* Добуток: коефіцієнт при x^((dq-i)+(m-j)) отримує доданок q[i]*b[j]. */ for (int i = 0; i <= dq; ++i) for (int j = 0; j <= m; ++j) out[i + j] += q[i] * b[j]; /* Додавання остачі: її коефіцієнти вирівнюються по молодших розрядах. */ for (int i = 0; i < m; ++i) out[degree - m + 1 + i] += r[i]; } /*------------------------------------------------------------------------------ Головна функція. Читає степені та коефіцієнти многочленів, виконує ділення за схемою Горнера, виводить частку й остачу та перевіряє результат. Локальні змінні: n, m — степені многочленів f та g; a, b — коефіцієнти многочленів f та g; q, r — коефіцієнти частки та остачі; check — коефіцієнти многочлена q*g + r; maxDiff — найбільше відхилення перевірки від вихідного многочлена. ------------------------------------------------------------------------------*/ int main() { printf("Лабораторна робота №6, завдання 3 (варіант 19)\n"); printf("Виконав: студент групи ІПЗ-11 Одарчук Олексій\n"); printf("Ділення многочленів за схемою Горнера\n\n"); int n = 0, m = 0; /* За умовою n > m > 2, тому найменший степінь діленого — 4. */ if (!readInt("Уведіть степінь n многочлена f(x) (4..20): ", &n, 4, MAX_DEGREE)) return 1; if (!readInt("Уведіть степінь m многочлена g(x) (3..n-1): ", &m, 3, n - 1)) return 1; printf("\nСпосіб задання коефіцієнтів:\n" " 1 - введення з клавіатури\n" " 2 - генерація псевдовипадкових чисел у заданому діапазоні\n"); int choice = 0; if (!readInt("Оберіть спосіб (1..2): ", &choice, 1, 2)) return 1; const bool byHand = (choice == 1); double low = 0.0, high = 0.0; if (!byHand) { if (!readDouble("Уведіть нижню межу діапазону коефіцієнтів: ", &low)) return 1; if (!readDouble("Уведіть верхню межу діапазону коефіцієнтів: ", &high)) return 1; if (low > high) { printf("Нижня межа більша за верхню.\n"); return 2; } srand((unsigned)time(NULL)); } double a[MAX_DEGREE + 1], b[MAX_DEGREE + 1]; if (!fillPolynomial(a, n, "f(x)", byHand, low, high)) return 1; if (!fillPolynomial(b, m, "g(x)", byHand, low, high)) return 1; /* Старший коефіцієнт дільника не може бути нульовим: інакше степінь многочлена g насправді менший за заявлений, і ділення за схемою Горнера дало б ділення на нуль. */ if (absValue(b[0]) < EPS) { printf("\nСтарший коефіцієнт многочлена g(x) дорівнює нулю —\n" "степінь дільника насправді менший за %d. Ділення неможливе.\n", m); return 2; } printf("\nВхідні многочлени\n"); printPolynomial(" f(x)", a, n); printPolynomial(" g(x)", b, m); double q[MAX_DEGREE + 1], r[MAX_DEGREE + 1]; dividePolynomials(a, n, b, m, q, r); const int dq = n - m; /* степінь частки */ printf("\nРезультат ділення f(x) на g(x)\n"); printPolynomial(" частка q(x)", q, dq); printPolynomial(" остача r(x)", r, m - 1); /* Перевірка: q(x)*g(x) + r(x) має тотожно дорівнювати f(x). */ double check[2 * MAX_DEGREE + 2]; multiplyAndAdd(q, dq, b, m, r, check); printf("\nПеревірка результату ділення\n"); printPolynomial(" q(x)*g(x) + r(x)", check, n); double maxDiff = 0.0; for (int i = 0; i <= n; ++i) { const double diff = absValue(check[i] - a[i]); if (diff > maxDiff) maxDiff = diff; } printf(" Найбільше відхилення від f(x) за коефіцієнтами: %.3e\n", maxDiff); printf(" %s\n", maxDiff < 1e-6 ? "Перевірку пройдено: q(x)*g(x) + r(x) тотожно дорівнює f(x)." : "УВАГА: перевірку не пройдено."); return 0; }