Боцманок Брач Владислав Альбертович : другие произведения.

Алгоритм извлечения квадратного корня

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:
Школа кожевенного мастерства: сумки, ремни своими руками
Оценка: 4.61*16  Ваша оценка:
  • Аннотация:
    У нас происходит нечто странное и чудовищное. Школьников не учат извлекать квадратный корень. В программе нет!Решил восполнить этот пробел в образовании молодёжи. Пользуйтесь на здоровье!

  ИЗВЛЕЧЕНИЕ КВАДРАТНОГО КОРНЯ
  Квадратным корнем из любого, данного, положительного числа называется число, которое будучи возведённым во вторую степень даст данное число. Положительное значение корня называется арифметическим квадратным корнем. Квадратный корень извлекается только из любого, данного, положительного числа. Квадратный корень из нуля есть ноль! Действие извлечения квадратного корня обратно действию возведения в квадрат. В основе алгоритма (схемы) извлечения корня лежат следующие математические факты: десятичная запись любого числа, например ab.cd , где a, b, c, d есть десятичные цифры, можно представить как ab.cd = 10 * a + b + 0.1 * c + 0.01 * d ; квадрат любой цифры от 1 до 9 находится в промежутке чисел от 1 до 99, то есть требует для записи два разряда. Квадрат 1 = 1 * 1 = 1. Квадрат 9 = 9 * 9 = 81. Квадрат любой десятичной дроби от 0,1 до 0,9 находится в промежутке чисел от 0,01 до 0,99, то есть требует для записи два разряда. Квадрат 0,1 = 0,1 * 0,1 = 0,01. Квадрат 0,9 = 0,9 * 0,9 = 0,81. В алгоритме используется формула
   ( 10 * a + b ) ^ 2 = 100 * a ^ 2 + 20 * a * b + b ^ 2 = 100 * a ^ 2 + ( 20 * a + b ) * b.
  Алгоритм.
  1. Разбиваем цифры исходного числа на пары: те, что стоят слева от десятичной запятой, группируем по две справа налево, а те, что правее - по две слева направо.
  2. Затем первый раз подбором вычисляем квадрат старшей цифры корня, чтобы он не превосходил числового значения крайней левой пары цифр исходного числа, но был к нему наиболее близок, и вычитаем его из этого числового значения. Записываем в результат первую цифру корня.
  3. Далее мы приписываем две, следующие слева направо в исходном числе, десятичные цифры к остатку вычитания. Отсюда понятно разбиение на пары (видно из формулы).
  4. Выбираем 2 * a - удвоенное число, образованное цифрами известного на данный момент результата извлечения корня.
  5. Сдвигаем 2 * a на разряд влево (умножаем на 10) и прибавляем к нему подбором следующую цифру корня b так, чтобы число ( 20 * a + b ) * b не превосходило числового значения остатка с приписанной к нему парой цифр исходного числа, но было к нему наиболее близко.
  6. Для этого выбираем перебором очередную цифру из цифр от 0 до 9 и образуем число 20 * a + b .
  7. Умножаем 20 * a + b на эту же самую цифру b, получаем число ( 20 * a + b ) * b.
  8. Вычитаем число ( 20 * a + b ) * b из числа, образованного остатком и приписанной к нему справа парой цифр исходного числа.
  9. Сравниваем остаток с числом ( 20 * a + b ) * b .
  10. Остаток больше числа ( 20 * a + b ) * b. Переход к пункту 6.
  11. Приписываем цифру b справа к результату извлечения корня, то есть к числу за знаком корня.
  12. Все пары цифр исходного числа обработаны?
  13. Нет. Переход к пункту 3.
  14. Да. Конец.
  
  Пример извлечения корня с описанием выполняемых действий из числа 57240.5625.
  Квадратный корень из 5'72'40.56'25 = 239.25......................
  --------------------------4....................................
  .......................................1'72..................................
  --------------------------1 29...................43 * 3 = 129
  ......................................... 43'40.................................
  ----------------------------42 21..................469 * 9 = 4221
  ............................................1 19'56..............................
  --------------------------------95 64...............4782 * 2 = 9564
  ................................................23 92'25............................
  --------------------------------23 92 25............47845 * 5 = 239225
  ................................................00 00 00
  1. Разбиваем цифры числа 57240.5625 на пары: те, что стоят слева от десятичной запятой, группируем по две справа налево, а те, что правее - по две слева направо. Получаем 5'72'40.56'25.
  2. Определяем квадратный корень из числа, соответствующего первой группы цифр слева - в нашем случае это 5 (ясно, что точно корень может не извлекаться, берем число, квадрат которого максимально близок к нашему числу, образованному первой группой цифр, но не превосходит его). В нашем случае это будет число 2. Записываем 2 в ответ - это старшая цифра корня.
  3. Возводим число, которое стоит уже в ответе, а это 2, в квадрат, и вычитаем его из числа, соответствующего первой слева группы цифр - из числа 5. В остатке остается 1.
  4. Приписываем к остатку справа следующую группу из двух цифр - 72 и получаем число 172. Число 2, которое уже стоит в ответе, умножаем на 2 и получаем 4.
  5. Теперь следите внимательно. Нам нужно число 4 сдвинуть на разряд влево (умножить на 10) и справа приписать (прибавить) одну цифру b, и число 4b умножить на b, то есть на ту же самую приписанную цифру. Результат должен быть как можно ближе к 172, но опять-таки не больше этого числа. В нашем случае, в результате подбора, это будет цифра 3. Её записываем в ответ рядом с цифрой 2, справа. Это следующая цифра в десятичной записи нашего квадратного корня.
  6. Из 172 вычитаем произведение 43 * 3 = 129, получаем в остатке 43.
  7. Повторяем предыдущие операции. Приписываем к 42 справа следующую группу цифр 40. Получаем число 4240. Число 23 в ответе умножаем на 2 и сдвигаем влево. К полученному числу 46_ после подбора приписываем справа (прибавляем к 460) одну цифру, такую, чтобы при умножении на нее получилось число, меньшее 4240, но наиболее близкое к нему. Это цифра 9 - следующая цифра в ответе, в десятичной записи квадратного корня, а число 4221.
  8. Далее у нас в числе стоит десятичная точка, ставим такую же точку в ответе после цифры 9. Продолжаем процесс, снося по две цифры после точки. Так же, как и ранее получаем две цифры корня после десятичной точки. Это 2 и 5. Понятно, что в общем случае, если остаток не равен нулю, можно сносить и два нуля, чтобы достичь желаемой точности извлечения корня.
  
Оценка: 4.61*16  Ваша оценка:

Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список

Кожевенное мастерство | Сайт "Художники" | Доска об'явлений "Книги"