Представление натурального числа в виде суммы квадратов 2-х чисел
Иногда встречаются задачи, в которых требуется определить, возможно ли представить число в виде суммы квадратов 2-х чисел. Как таковой математической формулы для установления этого факта нет. А потому приходится подбирать нужные числа. Конечно, для небольших чисел подбор возможных вариантов не займет много времени и машинных ресурсов. Но если речь идет о числах, кратных миллиону, то... Не сказать, что при нынешних условиях на такие вычисления уместно жаловаться , но, согласитесь, зачем тратить лишние "проценты" ЦП на вычисления, когда их можно использовать еще много для чего (это с учетом того, что расчеты надо делать не для одного числа, а для тех же родимых нескольких миллионов!).
Ну, в прочем, наша задача намного проще. Предположим, требуется функция, которая определит, можно ли представить данное число в виде суммы квадратов 2-х чисел, то есть в результате она должна "сказать" - "да" или "нет". Именно поэтому "наша задача намного проще"... В этом случае достаточно найти превое попавшееся подходящее сочетание чисел и все, этого хватит, чтобы сказать "да" или "нет". Кроме того, в данном случае, больше возможностей "обрезать" ненужные вычисления.
Рассмотрим алгоритм на примере. Пусть нам надо выяснить, разлагается число 10 на сумму квадратов 2-х чисел или нет. Чтобы не запутаться введем обозначения.
Пусть: x - число, которое надо проверить (в нашем случае это 10); i, j - числа которые при возведении в квадрат и дальнейшем сложении дадут x; i2= i*i (т. е. i в квадрате); j2= j*j (т. е. j в квадрате).
Таким образом, 10 можно представить как 1*1 + 3*3 = 10. Так как наша цель узнать первое возможное сочетание, прекращаем вычисление.
Теперь рассмотрим второй случай, когда число нельзя представить в виде суммы квадратов 2-х чисел. Тут стоит заранее отметить, что если i2 будет больше половины числа, которое раскладываем (т.е. i2 > x/2), то подбирать значения j далее нет смысла. Именно это и следует взять за второе условие конца перебора значений. Ну и теперь разберем алгоритм на примере числа 7.
Берем i = 3, тогда i2 = 9 (9 > 7, обрываем вычисления). Таким образом, 7 нельзя представить в виде суммы квадратов.
Теперь запишем этот алгоритм в виде функции.
int twoNumSquare(int x) { int i=0, j=1, c=0, x2; while ((c<1) && ((i*i)<= (x/2))) // здесь c - признак того, найден ответ или нет (1 - да, 0 - нет) { while ((i*i+j*j) < x) // пока сумма квадратов меньше нужного числа { c= 0; // не правильный вариант j++; } if ((i*i+j*j) == x) c= 1; // если сумма квадратов = нужному числу, то вариант верен (c=1) if ((i*i+j*j) > x) c= 0; // если сумма квадратов больше нужного числа, то вариант не верен i++; j=1; // возвращаем j (второе число) в первоначальное положение (!) } return(c); // возвращаем результат 1 или 0 }
А дальше после использования функции интерпретируете полученный 1 или 0 во что Вам удобно.
P.S. Замечания и предложения по этой функции, а так же обнаруженные баги описывайте в комментариях.
