адання, тоді при N = i2 + j2 + k2 + l2 виконується i Ві j Ві k Ві l. Тоді вірно i2 ВЈ N і i2 Ві N/4, тобто i належить відрізку [/ 2,]. Оскільки j, k і l не перевищує i, загальне число комбінацій можна оцінити зверху Точну оцінку дає формула
Наведемо тепер алгоритм, що дозволяє отримати всі впорядковані розкладання даного числа.
квадрата.
К1. для всіх i від до/2 виконати К2-К8.
К2. S1 В¬ i2. Якщо N = S1, то вивести (i). p> КЗ. для j від i до 0 виконати К4-К8.
К4. S2 В¬ S1 + j2, Якщо N = S2, то вивести (i, j).
К5. для k від j до 0 виконати КБ-К8.
К6. S3 В¬ S2 + k2, Якщо N = S3, то вивести (i, j, k). p> К7. для l від k до 0 виконати К8.
К8. Якщо N = S3 + l2 то вивести (i, j, k, 1} і перейти до К5 з наступним значенням k. p> У цьому алгоритмі i, j, k і I пробігають цілі значення в відповідних інтервалах. S1, S2, S3 введені для скорочення обсягу обчислень. Виконання кроку К8 можна припиняти при знаходженні першого значення, що задовольняє умові, оскільки не може бути двох розкладань, відрізняються тільки останнім числом. Невелика модифікація алгоритму дозволяє організувати роботу до знаходження першого розкладання. Ця програма може бути використана для чисельного вирішення багатьох статистичних завдань: розподіл чисел, що представляються у вигляді суми 1, 2, 3, 4 квадратів, як функція N, число різних уявлень в необхідному вигляді, а також перевірити наведену нами оцінку числа комбінацій.
3. Рішення алгебраїчних рівнянь з раціональними коефіцієнтами. Зазвичай у шкільній практиці рівняння виду аоxn + a1 xn-1 + + ... + an = 0 мають раціональні коефіцієнти. У цьому випадку мається ефективний алгоритм знаходження всіх раціональних коренів. Перш ніж розбирати його, відзначимо, що множення на НОК знаменників коефіцієнтів дозволяє зробити їх цілими числами. Якщо старший коефіцієнт відмінний від одиниці, то помножимо рівняння на a0n-1та зробимо підстановку у = АОХ. Таким чином, ми завжди можемо вважати всі коефіцієнти цілими, а став рівним 1.
У алгебрі доводиться, що всі раціональні рішення такого рівняння є цілими числами, і при тому дільниками вільного члена. Зрозуміло, у рівняння можуть бути і ірраціональні корені.
Роботу можна істотно скоротити, якщо скористатися модифікацією схеми Горнера.
Нехай а - корінь рівняння, тоді по теоремі Безу
xn + a1xn-1 + ... + an = (x-a) (xn-1 + c1xn-2 + ... + cn-1). p> Запишемо це тотожність у вигляді
xn + a1xn-1 + ... + an = (xa) (-b0xn-1-b1xn-2-...-bn-1)
і прирівняємо коефіцієнти при однакових ступенях:
an = abn-1; an-1 = abn-2-bn-1; ...; a1 = ab0-b1; 1 =-b0
Всі числа ai і bi є цілими, тому an, an-1 + bn-1, ... діляться на а. Значить, якщо хоч один з коефіцієнтів bi виявиться нецілим, то проверяемое числа не може бути коренем. Відзначимо також, що за теоремою Безу при x = 1 і х = -1 a0 + a1 + ... + an ділиться на а-1, а ao-a1 + ... + (В±) a...
