Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Object Pascal: кроссплатформенные технологии > Очень простая задача

Автор: Dr.Death 23.11.2004, 19:03

Дано натуральное число Х. Найдите такое максимальное целое число, квадрат которого не превышает Х.
Входные данные:
Число Х(1<=Х<=10^1000)
Выходные данные
Число, удовлетворяющее условию
Пример
Вх. данные|Выходные
16 4

Значит не знаю только как представить себе число 10^1000, такого типа данных помойму вообще нет, а длинной арифметикой очень долго. Знаю, что вроде легко решается, ну а как? smile

ограничения во времени 0,3с

Автор: Pakshin A. S. 23.11.2004, 19:14

Код


var
 b:boolean;
 x:integer;
 i:longint;
begin
 readln(x);
 b:=true;
 i:=1;
 while b and (i < Max_LongInt{сам заполнишь}) do
  begin
   b:=sqr(i) < x;
   if b
    then
     inc(i);
  end;
 if b
  then
   if i = MaxLongInt
    then
     writeln('Число очень большое!!!')
    else
     writeln('Числа нет') {хотя это не выполнится...}
  else
   writeln(i);
 readln;
end.

Вот-с....
Добавлено @ 19:20
А если подумав....

Код


var
 x:extended;
begin
 readln(x);
 writeln(Trunc(sqrt(x)));
 readln;
end.

Автор: dm9 25.11.2004, 22:16

Pakshin A. S., а если значащих цифр больше 20?

Возводим 111111111111111111111111111 в квадрат, полученное число скармливаем твоей программе.

Она его урезает до 20 цифр (ну или сколько там) и выдаёт ответ:
111111111111111111111111110 или 111111111111111111111111109.

Нет, без длинной арифметики никуда, имхо...
Добавлено @ 22:18
PS calc.exe именно так и урезал - до 111111111111111111111111109...

Автор: Pakshin A. S. 25.11.2004, 22:20

Нууу...
Паскаль же не принимает большие числа...

Автор: dm9 25.11.2004, 22:21

В данной постановке я бы посчитал, что задача нерешаема (с ограниченим времени) smile

Добавлено @ 22:27
В худшем случае придётся придётся перемножить около 1600 чисел (500/lg(2)) с 500 знаками. Столько же операций сравнения. Сколько это по времени? smile

Ну, это если использовать что-то типа деления отрезка пополам smile

Автор: Pakshin A. S. 25.11.2004, 22:40

А как сохранить примерно вот такое число, которое должно быть введено (Х):
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 - 1
Добавлено @ 22:40
Упс...
Добавлено @ 22:41
Это же сколько пямять выделить надо?

Автор: Pakshin A. S. 25.11.2004, 22:54

А что это мы с большими работам... давайте перейдем к бесконечно малым... Т. Е. будем работать с 1/х, где х - введённое с клавы число (надо придумать, как приобразовывать).
Тогда ответ будет таким: хнаменатель дроби 1/trunc(sqrt(x));
Теперь надо будет только реализовать... smile

Автор: Pakshin A. S. 25.11.2004, 23:13

Вот... кое-что...

Код


var
 c:char;
 i:integer;
 x:extended;
begin
 i:=10;
 read(c);
 x:=1/(ord(c) - ord('0'));
 read(c);
 while c <> #13 do
  begin
   x:=1/((1/x)*i + (ord(c) - ord('0')));
   read(c);
  end;
 writeln((sqrt(1/x)):20:1);
 readln;
 readln;
end.

Может и не верно... простите...

Автор: dm9 25.11.2004, 23:29

>Это же сколько пямять выделить надо?

String[1000]. Много? smile

Цитата(Pakshin @ 25.11.2004, 22:54)

А что это мы с большими работам... давайте перейдем к бесконечно малым

Та же фигня, разрядности не хватит...

Автор: cardinal 26.11.2004, 00:45

Цитата(Dr @ 23.11.2004, 18:03)

Входные данные

Вопрос: в каком виде они даны?

Автор: Dr.Death 26.11.2004, 18:12

Цитата(cardinal @ 26.11.2004, 00:45)

Вопрос: в каком виде они даны?

Ну как в каком?
Входные:16
Выходные:4
Там же все написано в начале - Число Х(1<=Х<=10^1000)

Автор: cardinal 26.11.2004, 18:15

Цитата(Dr @ 26.11.2004, 17:12)

Ну как в каком?
Входные:16
Выходные:4

Это и слону понятно, я имел в виду как они передаются процедуре, в виде массива или строки, как такое число передать функции? Тут идет речь о BigNumbers или нет?

Автор: Dr.Death 26.11.2004, 19:30

cardinal
Вообще по идее нам один чел говорил, который проверял задания, что он ее решит без BigNumbers. Насчет ввода я не знаю smile

. По идее должно просто в переменную, а вот как?

Автор: Pakshin A. S. 26.11.2004, 19:34

А может с памятью работать напрямую...
Не знаю о чем только что сказал... но....

Автор: dm9 26.11.2004, 20:02

Dr.Death, спроси этого человека потом, как он это решил smile

Автор: Pakshin A. S. 26.11.2004, 20:16

Млин... может тут какой-то подвох? smile

Автор: cardinal 26.11.2004, 22:15

Ладно расскажу в какую сторону мыслил (я просто думал, что может что поточнее узнаю, но как видно нет smile

).

Все числа от 1 до 10^1000 можно представить просто как значение их десятичного логарифма. То есть мы передаем функции не числа в диапазоне от 1 до 10^1000, а в диапазоне от 0 до 1000. Поделив число пополам мы и получим его корень smile

Все просто как никогда. Вопрос только в том, как добиться точности.

Рассматривая числа 2, 62, 862, 5862, мы получаем:
0 + log2 + 0 = 0,3010 (соответствует 2)
1 + log6 + log(62/60) = 1,7924 (соответствует 62)
2 + log8 + log(862/800) = 2,9355 (соответствует 862)
3 + log5 + log(5862/5000) = 3,7680 (соответствует 5862)
То есть наблюдается небольшая закономерность. Вопрос что делать дальше? smile

Ладно, думайте! ... а то мне в splinter cell охото порубиться smile

Автор: dm9 26.11.2004, 23:33

Математика, конечно, занимательная, но что отсюда следует - не пойму smile

Автор: cardinal 27.11.2004, 01:26

Цитата(dm9 @ 26.11.2004, 22:33)

Математика, конечно, занимательная, но что отсюда следует - не пойму

Ну с такими размышлениями можно добиться следующих результатов (четыре примера):

X = 832193569
Предстваляем X в виде: 8 + log8 + log(8.321/8) = 8.9201 (округляем вниз)
Корень X = 4.46005, то есть 10 ^ 4.46005 = 28843 (правильный ответ 28847)

X = 6358120356
Предстваляем X в виде: 9 + log6 + log(6.358/6) = 9.8033 (округляем вниз)
Корень X = 4.90165, то есть 10 ^ 4.90165 = 79735 (правильный ответ 79737)

X = 4352362436567456
Предстваляем X в виде: 15 + log4 + log(4.352/4) = 15,6386 (округляем вниз)
Корень X = 7,8193, то есть 10 ^ 7,8193 = 65962939 (правильный ответ 65972436)
А что делать? smile

Если увеличить 7,8193 на одну десятитысчную, то ответ уже будет больше корня 65972436 < 65978129.

X = 10 ^ 1000 = 10000000...
Предстваляем X в виде: 1000 + log1 + log(1.000/1) = 1000
Корень X = 500, то есть 10 ^ 500= 100000000... (правильный ответ именно такой же smile

)

На самом деле я думаю, что тут если еще немного покумекать, то можно какой-нибудь рекурсивный алгритм придумать, которую за n-ое выполнение самого себя, улучшит результат. smile

Автор: dm9 27.11.2004, 16:20

Просто всё равно мы приходим к логарифму, у которого 20 значащах цифр. Недостаточно для описания целого числа из 1000 знаков... Хотя, может, я чего не понял smile

Автор: cardinal 27.11.2004, 17:05

Цитата(dm9 @ 27.11.2004, 15:20)

Просто всё равно мы приходим к логарифму, у которого 20 значащах цифр

У меня же нет 20 значащих цифр... Вопрос в точности...

Цитата(cardinal @ 27.11.2004, 00:26)

На самом деле я думаю, что тут если еще немного покумекать, то можно какой-нибудь рекурсивный алгритм придумать, которую за n-ое выполнение самого себя, улучшит результат.

Я о том и говорю, что "осталось лишь" придумать как улучшить это значение логарифма. Сейчас точность с 10-ти значными числами неплохая, но 16-ти значное число уже дает погрешность в 0.015 процента, что немного, но так как число большое, то от правильного результата мы улетаем далеко...

Автор: Fedor 29.11.2004, 18:48

Ребят... Почитал я тут... По-моему, вы не в ту сторону зашли. Есть же алгоритм извелечения квадратного корня из числа (я его правда не помню - сейчас поищу). Работает он со сложностью по-моему n, где n - количество разрядов. Берем тогда это число входное число, извлекаем из него корень "с остатком" и задача решена. Попробую сейчас найти алгоритм и наваять программу.

З.Ы. По-моему, этой теме место в Vingrad-колледж smile

Добавлено @ 18:53
Ну вот например Яндексом быстро нашел.
http://www.pspu.ac.ru/mirrors/computer-science/DL-AR/koren.html

Сейчас напишу программу.

Автор: Fedor 29.11.2004, 21:58

Фух. Весь вечер пропарился. Давно не программировал такие задачки...

Код

Type TLong = array[0..1002] of shortint;

var rivny:boolean;

procedure reversenumber(var na:word;var a:TLong);
var i:word;
    k:word;
begin
 for i:=1 to na div 2 do
  begin
   k:=a[i]; a[i]:=a[na-i+1]; a[na-i+1]:=k;
  end;
end;

procedure MoveRight(var na:word; var A:TLong; k:word);
var i:word;
begin
 for i:=na downto 1 do a[i+k]:=a[i];
 na:=na+k;
end;

function Less(na,nb:word;A,B:TLong):boolean; {if A<=B then true else false}
var
 i:word;
begin
 if na<nb then begin less:=true; exit; end;
 if na>nb then begin less:=false; exit; end;
 i:=na;
 while (i>0) and (a[i]=b[i]) do dec(i);
 if i=0 then begin less:=true; exit; end;
 if a[i]<b[i] then less:=true else less:=false;
end;

Procedure Multiplication(la,lb:word; A, B : TLong; var lc:word; Var C : TLong);
{la - length of A
 lb - length of B
 lc - length of C}
Var I, J : Integer; P : word; VspRez : word;
 Begin
  FillChar(C,sizeof(С),0);
  if (lb=1) and (B[1]=0) then begin lc:=1; exit; end;
  if (la=1) and (A[1]=0) then begin lc:=1; exit; end;
  For I := 1 To lA Do
  Begin P := 0;
        For J := 1 To lB Do
        Begin
          VspRez := A[I] * B[J] + P + C[I + J - 1];
            C[I + J - 1] := VspRez Mod 10;
            P := VspRez Div 10
          End;
        C[I + J] := P
   End;
  if C[la+lb]=0 then lc:=la+lb-1 else lc:=la+lb;
 End;

procedure longmin(na,nb:word; a,b:Tlong;var nc:word; var c: Tlong);
var i:word;
    tmp:shortint;
    p:byte;
begin
  FillChar(C,sizeof(С),0);
  for i:=1 to na do
   begin
    tmp:=a[i]-b[i];
    if tmp<0 then begin dec(a[i+1]); tmp:=tmp+10; c[i]:=tmp;end
    else c[i]:=tmp;
   end;
  i:=1000;
  while c[i]=0 do dec(i);
  nc:=i;
end;

function findmaxnumber(na,nb:word;a:TLong;BigA:TLong):longint;
{find such x that ax*x<A and }
var
 x:byte;
 C,D,E:TLong;
 nc,nd:word;
begin
 FillChar(c,sizeof(С),0);
 FillChar(d,sizeof(d),0);
 x:=0;
 MoveRight(na,a,1);
 a[1]:=x;
 D[1]:=x;
 Multiplication(na,1,a,D,nc,C);
 while (x<9) and Less(nc,nb,C,BigA) do
  begin
   inc(x);
   a[1]:=x;
   D[1]:=x;
   Multiplication(na,1,a,D,nc,C);
  end;
 if (x=9) and (Less(nc,nb,C,BigA)) then findmaxnumber:=9
 else
  findmaxnumber:=x-1;
end;

var
 a,b:TLong;
 i:word;
 Smalla,BigA,TempLong,Long2:TLong;
 na,futurenb,nb:word;
 currentnumber:word;
 tmp:word;
 xx:word;
 c:char;
 err:integer;
 nexta:word;
 nba,nsa,ntl:word;
 res,res2:longint;
begin
 FillChar(TempLong,SizeOf(TempLong),0);
 FillChar(Long2,SizeOf(Long2),0);
 Long2[1]:=2;
 i:=0;
 while not EOLN do begin inc(i); read©; val(c,a[i],err); end;
 na:=i;
 reversenumber(na,A);

 if na<=4 then {if small number - count it immideately}
  begin
    res:=1000*a[4]+100*a[3]+10*a[2]+a[1];
    res2:=trunc(sqrt(res));
    if sqr(res2)=res then writeln(res2) else writeln(res2+1);
    exit;
  end;

 if na mod 2 = 0 then futurenb:=na div 2
 else futurenb:=na div 2 +1;

 if na mod 2 = 0 then begin tmp:=a[na]*10+a[na-1]; nexta:=na-2; end
 else begin tmp:=a[na]; nexta:=na-1; end;

 xx:=1;
 while ((xx<=9) and (xx*xx<=tmp)) do
 begin
  inc(xx);
 end;

 b[1]:=xx-1;

 xx:=tmp-b[1]*b[1];
 BigA[4]:=xx div 10;
 BigA[3]:=xx mod 10;
 BigA[2]:=a[nexta];
 BigA[1]:=a[nexta-1];
 if BigA[3]=0 then nba:=2 else if BigA[4]=0 then nba:=3 else nba:=4;
 nexta:=nexta-2;

 tmp:=b[1]*2;
 Smalla[2]:=tmp div 10;
 Smalla[1]:=tmp mod 10;
 if smalla[2]=0 then nsa:=1 else nsa:=2;

 b[2]:=b[1];
 b[1]:=findmaxnumber(nsa,nba,SmallA,BigA);
 nb:=2;
 for i:=3 to futurenb do
  begin
    MoveRight(nsa,SmallA,1);
    smalla[1]:=b[1];
    TempLong[1]:=b[1];
    ntl:=1;
    Multiplication(nsa,ntl,SmallA,TempLong,ntl,TempLong);
    LongMin(nba,ntl,BigA,TempLong,ntl,TempLong);
    MoveRight(ntl,tempLong,2);
    templong[2]:=a[nexta];
    templong[1]:=a[nexta-1];
    nexta:=nexta-2;

    nba:=ntl; BigA:=TempLong;
    Multiplication(nb,1,B,Long2,nsa,SmallA);
    MoveRight(nb,b,1);
    b[1]:=findmaxnumber(nsa,nba,SmallA,BigA);
  end;

 MoveRight(nsa,SmallA,1);
 smalla[1]:=b[1];
 TempLong[1]:=b[1];
 ntl:=1;
 Multiplication(nsa,ntl,SmallA,TempLong,ntl,TempLong);

 rivny:=true;
 if (ntl=nba) then
  begin
   for i:=1 to ntl do
    if TempLong[i]<>BigA[i] then begin rivny:=false; break; end;
  end
 else rivny:=false;

 i:=1;
 if not rivny then
  begin
    while b[i]=9 do inc(i);
    inc(b[i]);
    if i>nb then nb:=i;
  end;

 for i:=nb downto 1 do write(b[i]);

end.

Надеюсь, что-то поймете. Я позже прокомментирую строчки. Чтоб понятнее было. Сейчас просто времени уже не осталось.

На максимальном тесте работает около секунды. Хотя уверен можно оптимизировать (например хранить длинные числа не по одному разряду, а по два или больше. А может и сам алгоритм подправить)

Автор: cardinal 29.11.2004, 22:00

Morpheus, все это хорошо, но во-первых как решить задачу в заданное время, а во-вторых как ты представишь корень числа 10^1000? Я пока это не понимаю...

Автор: Fedor 29.11.2004, 22:18

Цитата(cardinal @ 29.11.2004, 21:00)

а во-вторых как ты представишь корень числа 10^1000

Он хранится в массиве b по-разрядно. Ихсодное число хранится в массиве a. Тоже по-разрядно. И соотв я выполняю действия - умножение в столбик, вычитание. И алгоритм нахождения корня по-разрядно.

Цитата(cardinal @ 29.11.2004, 21:00)

но во-первых как решить задачу в заданное время

Именно этим способом. Я уверен. Только нужно немного упростить мое решение. А то сейчас оно у меня тупо в лоб делает арифметические действия. Скорее всего, можно упростить где-то.

Автор: cardinal 29.11.2004, 22:27

Цитата(Morpheus @ 29.11.2004, 21:18)

Я уверен.

Ну тогда держи +. Как говорится все гениальное просто - мне понравился алгоритм (см. ссылка) smile

Круто! Будет время перепишу код на VB и посмотрю что и как smile

Автор: dm9 29.11.2004, 23:24

Morpheus, ты каким компилятором пользовался? У меня в трёх местах английская "С" заменена на русскую...

При вводе (10^n)^2, где n - любой целое (например, 10000) - Access violation...

Может, дело в том, что я Delphi использую...

А вообще, идея интересная smile

Автор: cardinal 29.11.2004, 23:35

Цитата(dm9 @ 29.11.2004, 22:24)

При вводе (10^n)^2, где n - любой целое (например, 10000) - Access violation...

Ограничение в 10^1000, ты о чем?

Автор: dm9 29.11.2004, 23:57

Я о том, что когда я пытаюсь скормить программе число, корень из которого - единица с последующими нулями, у меня вылетает AV...

Это Borland Pascal был? Надо будет в нём попробовать запустить...

Автор: S.A.P. 29.11.2004, 23:58

Может не обязательно число представлять с высокой точностью, а в виде 2-х воставляющих как в условии. Например число 10 - как 10 и 1, а число 5^100 как 5 и 100?

Автор: dm9 30.11.2004, 00:09

Perchilla, так не интересно smile

Автор: cardinal 30.11.2004, 00:09

Цитата(dm9 @ 29.11.2004, 22:24)

При вводе (10^n)^2, где n - любой целое (например, 10000)

То есть корень от (10^10000)^2 это единица с последующими нулями smile

Perchilla, ты еще идею не понял см. еще раз http://www.pspu.ac.ru/mirrors/computer-sci...L-AR/koren.html

Автор: dm9 30.11.2004, 00:13

cardinal, там пример не совсем корректен smile

10000 - это не n.
n здесь равно двум smile

(10^2)^2 = 10000 - корень из этого числа равен 100, то есть единица с нулями smile

Вот ввожу я 10000, 1000000, 1000000000000000000000000000000000000 и получаю AV...

Автор: cardinal 30.11.2004, 00:48

Теперь понятно, а то n, n... smile

Автор: Fedor 30.11.2004, 01:11

dm9 Прав.... Молодец. Я то и не тестировал почти совсем. Обрадовался было уже, что на рендомических тестах работает. Забыл уже, как на олимпиадах заваливают. Ну, я подправил в некоторых местах. Начал тестировать - еще нашел неправильный ответ. Исправил вроде (я неправильно единицу к числу прибавлял в самом конце, например).

Насчет русских букв C - это форум позаменял © на значки копирайтов. Ну, я их обратно редактировал да видно раскладку клавиатуры забыл поменять. Сорри.

В общем, ловите: