Длинный корень Pascal - Помощь студентам

Street-Striker · 19.09.2015, 21:54

По заданному натуральному числу А требуется найти наибольшее число В такое, что B^2 <= A.
Во входном файле INPUT.TXT записано натуральное число A
(A <= 10^3000).
В выходной файл OUTPUT.TXT выведите максимальное натуральное число B, квадрат которого не превосходит A. Число B следует выводить без лидирующих нулей.

Например:

input: 234953211
output: 15328

Подскажите пожалуйста алгоритм, какие процедуры по длинной арифметике для этого нужны (сложения, вычитания, умножения или деления) и покажите его работу на конкретном числе (то есть, что происходит с ним на каждом шаге), а то никак не могу понять как это решить.

Poma][a · 19.09.2015, 22:00

старый добрый бинарный поиск..
Погугли как вручную высчитать числа после запятой у корня. Делается прикидкой.. Тут так же (ну я бы так делал)

Аватар · 19.09.2015, 22:01

В качестве идеи - вспомнить вычисление корня квадратного в столбик. Когда то в школе давали. И попробовать тот алгоритм запрограммировать

19.09.2015, 21:54	#1
Street-Striker Регистрация: 28.08.2015 Сообщений: 6	Длинный корень Pascal По заданному натуральному числу А требуется найти наибольшее число В такое, что B^2 <= A. Во входном файле INPUT.TXT записано натуральное число A (A <= 10^3000). В выходной файл OUTPUT.TXT выведите максимальное натуральное число B, квадрат которого не превосходит A. Число B следует выводить без лидирующих нулей. Например: input: 234953211 output: 15328 Подскажите пожалуйста алгоритм, какие процедуры по длинной арифметике для этого нужны (сложения, вычитания, умножения или деления) и покажите его работу на конкретном числе (то есть, что происходит с ним на каждом шаге), а то никак не могу понять как это решить.

19.09.2015, 22:01	#3
Аватар Старожил Регистрация: 17.11.2010 Сообщений: 18,922	В качестве идеи - вспомнить вычисление корня квадратного в столбик. Когда то в школе давали. И попробовать тот алгоритм запрограммировать Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Длинный параметр TIdMultipartFormDataStream	LomoCoder	Работа с сетью в Delphi	6	17.02.2014 17:23
Pascal ABC-построить график уравнения и найти корень (метод касательных)	Darik102rus	Помощь студентам	3	26.04.2013 17:46
toolStripStatusLabel и длинный текст	wm_leviathan	C# (си шарп)	2	29.03.2013 16:12
Кубический корень. Pascal	Dellc	Помощь студентам	15	28.03.2012 19:40
Длинный Case	Utkin	Общие вопросы Delphi	3	14.08.2009 10:38

19.09.2015, 22:00	#2
Poma][a Новичок Джуниор Регистрация: 11.10.2011 Сообщений: 3,882	старый добрый бинарный поиск.. Погугли как вручную высчитать числа после запятой у корня. Делается прикидкой.. Тут так же (ну я бы так делал)