Поиск целочисленного квадратного корня - C (СИ)
Формулировка задачи:
Есть программа, которая должна искать целочисленные квадратные корни из целого числа методом деления отрезка пополам. Вот её код:
Вроде всё правильно, но для многих чисел, из которых извлекается целый корень (16, 25, 36, 64, 81, 100) она выдаёт результат - 0. Помогите, пожалуйста, найти ошибку.
/* Максимальное unsigned long число */ #define MAXINT (~0L) /* Определим имя-синоним для типа unsigned long */ typedef unsigned long ulong; /* Функция, корень которой мы ищем: */ #define FUNC(x, arg) ((x) * (x) - (arg)) /* тогда x*x - arg = 0 означает x*x = arg, то есть * x = корень_квадратный(arg) */ /* Начальный интервал. Должен выбираться исходя из * особенностей функции FUNC */ #define LEFT_X(arg) 0 #define RIGHT_X(arg) (arg > MAXINT)? MAXINT : (arg/2)+1; /* КОРЕНЬ КВАДРАТНЫЙ, округленный вниз до целого. * Решается по методу деления отрезка пополам: * FUNC(x, arg) = 0; x = ? */ ulong i_sqrt( ulong arg ) { register ulong mid, /* середина интервала */ rgt, /* правый край интервала */ lft; /* левый край интервала */ lft = LEFT_X(arg); rgt = RIGHT_X(arg); do{ mid = (lft + rgt + 1 )/2; /* +1 для ошибок округления при целочисленном делении */ if( FUNC(mid, arg) > 0 ){ if( rgt == mid ) mid--; rgt = mid ; /* приблизить правый край */ } else lft = mid ; /* приблизить левый край */ } while( lft < rgt ); return mid; } void main(){ ulong i; for(i=0; i <= 100; i++) printf("%ld -> %lu\n", i, i_sqrt(i)); }
Да и для всех остальных значений должен выдаваться результат округлённый вниз до целого, а не 0.
Решение задачи: «Поиск целочисленного квадратного корня»
textual
Листинг программы
#include <stdio.h> /* Максимальное unsigned long число */ #define MAXINT (~0L) /* Определим имя-синоним для типа unsigned long */ typedef unsigned long ulong; /* Функция, корень которой мы ищем: */ #define FUNC(x, arg) ((x) * (x) - (arg)) /* тогда x*x - arg = 0 означает x*x = arg, то есть * x = корень_квадратный(arg) */ /* Начальный интервал. Должен выбираться исходя из * особенностей функции FUNC */ #define LEFT_X(arg) 0 #define RIGHT_X(arg) ((arg/2)+1); /* КОРЕНЬ КВАДРАТНЫЙ, округленный вниз до целого. * Решается по методу деления отрезка пополам: * FUNC(x, arg) = 0; x = ? */ ulong i_sqrt( int arg ) { register int mid, /* середина интервала */ rgt, /* правый край интервала */ lft; /* левый край интервала */ lft = LEFT_X(arg); rgt = RIGHT_X(arg); do{ mid = (lft + rgt + 1 )/2; /* +1 для ошибок округления при целочисленном делении */ if( FUNC(mid, arg) > 0 ){ if( rgt == mid ) mid--; rgt = mid ; /* приблизить правый край */ } else lft = mid ; /* приблизить левый край */ } while( lft < rgt ); return mid; } int main(){ int i = 0; for (; i< 50; i++) printf("%i -> %i\n", i, i_sqrt(i)); return 0; }
Объяснение кода листинга программы
- Включаем заголовочный файл stdio.h для использования функций ввода-вывода.
- Определяем максимальное значение типа unsigned long с помощью #define MAXINT (~0L).
- Создаем синоним для типа unsigned long, используя typedef.
- Определяем функцию FUNC(x, arg), которую мы хотим найти квадратный корень.
- Задаем начальный интервал для поиска корня с помощью #define LEFT_X(arg) 0 и #define RIGHT_X(arg) ((arg/2)+1).
- Создаем переменные left и right для хранения левой и правой границы интервала.
- Используем do-while цикл для деления интервала пополам и проверки, является ли значение функции FUNC(mid, arg) положительным.
- Если значение функции FUNC(mid, arg) больше нуля, то приближаем правую границу интервала, иначе приближаем левую границу.
- Возвращаем найденное значение mid в качестве результата функции i_sqrt(arg).
- В функции main() создаем переменную i и используем цикл for для вызова функции i_sqrt(i) и вывода результата на экран.
- Задаем начальное значение i = 0 и выполняем цикл 50 раз.
- Выводим на экран значения i и i_sqrt(i).
- Возвращаем 0 в конце программы, чтобы указать, что программа успешно завершилась.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д