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

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

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

Рассматривая числа 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)
То есть наблюдается небольшая закономерность. Вопрос что делать дальше?

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

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

Цитата(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)
А что делать? Если увеличить 7,8193 на одну десятитысчную, то ответ уже будет больше корня 65972436 < 65978129.

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

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

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

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

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

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

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

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

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

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

З.Ы. По-моему, этой теме место в Vingrad-колледж
Добавлено @ 18:53
Ну вот например Яндексом быстро нашел.
http://www.pspu.ac.ru/mirrors/computer-sci...L-AR/koren.html

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

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

Код

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.

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

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

Это сообщение отредактировал(а) Morpheus - 29.11.2004, 22:14

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

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

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

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

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

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

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

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

Я уверен.

Ну тогда держи +. Как говорится все гениальное просто - мне понравился алгоритм (см. ссылка) Круто! Будет время перепишу код на VB и посмотрю что и как

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

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

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

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

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

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

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

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

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

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