ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы
25 сообщений из 208, страница 4 из 9
  4  все
Алгоритмы
    #39164945
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabа я тоже не поняла условие: например
УсловиеИзвестно, что среди башен во входном файле нет равных.

и далее даются башни файла

1 2 2 -> 1^2^2 = 1
1 3 2 -> 1^3^2 = 1
1 2 3 -> 1^2^3 =1
1 3 3 -> 1^3^3 = 1

что я неправильно делаю?

Возможно, имелось в виду, что нет двух башен, запись которых во входном потоке в виде строки совпадает?
...
Рейтинг: 0 / 0
07.02.2016, 02:24
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164949
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T,

терзают смутные сомнения, что и 4х уровней мало, завтра поэкспериментирую
...
Рейтинг: 0 / 0
07.02.2016, 02:44
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164956
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mini.weblabа я тоже не поняла условие: например
УсловиеИзвестно, что среди башен во входном файле нет равных.

и далее даются башни файла

1 2 2 -> 1^2^2 = 1
1 3 2 -> 1^3^2 = 1
1 2 3 -> 1^2^3 =1
1 3 3 -> 1^3^3 = 1

что я неправильно делаю?
первая цифра - количество степеней, или кол-во элементов в башне + 1, т.е.
1 2 2 -> 2^2
2 3 3 3 -> 3^3^3
...
Рейтинг: 0 / 0
07.02.2016, 07:15
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164992
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr SharahovDima T,

терзают смутные сомнения, что и 4х уровней мало, завтра поэкспериментирую

предчувствия его не обманули:

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
a1 = 99 40 3 1 1
a2 = 2 2 16 1 1
Result = 1 Expected = 1

a1 = 99 40 3 1 1
a2 = 2 2 2 4 1
Result = 1 Expected = 1

a1 = 99 40 3 1 1
a2 = 2 2 2 2 2
ERROR!!!           Result = -1 Expected = 1
...
Рейтинг: 0 / 0
07.02.2016, 11:33
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164995
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я вчера написал что 4 не помогло 18782630

Надо как-то 5-й добавить. Может понятно станет как 6й и т.д.

Похоже логарифмы тут не в тему. Надо какую-то другую зависимость искать.
...
Рейтинг: 0 / 0
07.02.2016, 11:45
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164997
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TЯ вчера написал что 4 не помогло 18782630

Надо как-то 5-й добавить. Может понятно станет как 6й и т.д.

Похоже логарифмы тут не в тему. Надо какую-то другую зависимость искать.

Я видел это. Надо хвост из единиц отсекать, а то и 6, и 7 не поможет ))

Выше я привел нормальный пример без единичного хвоста, когда не работает.
...
Рейтинг: 0 / 0
07.02.2016, 11:53
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165004
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Отсекал я хвосты. У меня меньшая добивается единицами до высоты большей. Дальше последние 4 от каждой.

Надо как-то к общему основанию или степени привести, чтобы эти правила заработали
Код: sql
1.
2.
3.
если a > b то
a^n > b^n 
n^a > n^b


только как?
...
Рейтинг: 0 / 0
07.02.2016, 12:18
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165010
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TОтсекал я хвосты. У меня меньшая добивается единицами до высоты большей. Дальше последние 4 от каждой.

Я о другом. В исходных данных могут подсунуть башни с длинными единичными хвостами.

Dima TНадо как-то к общему основанию или степени привести, чтобы эти правила заработали только как?

Проще подшаманить с последней парой элементов.
Если они в результате дают меньше 300,
то гарантированно переполнения не будет,
и можно сократить высоту.
 
типа такого
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
function ComparePowerTowers(const a1, a2: TPowerTower): integer;
const
  epsilon= 1.0e-9;
const
  MaxBaseForPower: array[2..8] of integer= (17,6,4,3,2,2,2);
var
  t1, t2: TPowerTower;
  i, len1, len2, pow: integer;
  x1, x2: extended;
begin;
  len1:=Length(a1);
  len2:=Length(a2);
  for i:=0 to len1-1 do if a1[i]<=1 then begin;
    len1:=i;
    break;
    end;
  for i:=0 to len2-1 do if a2[i]<=1 then begin;
    len2:=i;
    break;
    end;
  if len1 or len2=0 then begin;
    Result:=0;
    exit;
    end;
  t1:=Copy(a1, 0, len1);
  t2:=Copy(a2, 0, len2);
  if len1<len2 then begin;
    SetLength(t1, len2);
    for i:=len1 to len2-1 do t1[i]:=1;
    len1:=len2;
    end;
  if len2<len1 then begin;
    SetLength(t2, len1);
    for i:=len2 to len1-1 do t2[i]:=1;
    len2:=len1;
    end;
  if (t1[0]=1) or (t2[0]=1) then begin;
    Result:=t1[0]-t2[0];
    exit;
    end;
  if (len2>1)
  and (t1[len2-1]<=High(MaxBaseForPower)) and (t1[len2-2]<=MaxBaseForPower[t1[len2-1]])
  and (t2[len2-1]<=High(MaxBaseForPower)) and (t2[len2-2]<=MaxBaseForPower[t2[len2-1]])
  then begin;
    pow:=t1[len2-2]; for i:=2 to t1[len2-1] do pow:=pow*t1[len2-2]; t1[len2-2]:=pow;
    pow:=t2[len2-2]; for i:=2 to t2[len2-1] do pow:=pow*t2[len2-2]; t2[len2-2]:=pow;
    dec(len2);
    end;
  len1:=len2-4;
  if len1<0 then len1:=0;
  if len1+4=len2 then begin;
    x1:=ln(ln(t1[len1])) + ln(t1[len1+1]) * exp(ln(t1[len1+2])*t1[len1+3]);
    x2:=ln(ln(t2[len1])) + ln(t2[len1+1]) * exp(ln(t2[len1+2])*t2[len1+3]);
    end
  else if len1+3=len2 then begin;
    x1:=ln(ln(t1[len1])) + ln(t1[len1+1]) * t1[len1+2];
    x2:=ln(ln(t2[len1])) + ln(t2[len1+1]) * t2[len1+2];
    end
  else if len1+2=len2 then begin;
    x1:=ln(t1[len1]) * t1[len1+1];
    x2:=ln(t2[len1]) * t2[len1+1];
    end
  else begin;
    x1:=t1[len1];
    x2:=t2[len1];
    end;
  if abs(x1-x2)/(abs(x1)+abs(x2)+epsilon)>epsilon then begin;
    if x1<x2 then Result:=-1 else Result:=1;
    exit;
    end;
  for i:=len1-1 downto 0 do begin;
    Result:=t1[i]-t2[i];
    if Result<>0 then exit;
    end;
  Result:=0;
  end;

...
Рейтинг: 0 / 0
07.02.2016, 12:39
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165025
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov,

эксперименты показывают, что 300 - сильно заниженная оценка,
переполнения не происходит даже при 2470,
т.е. при вычислении 99^99^99^2470
...
Рейтинг: 0 / 0
07.02.2016, 13:21
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165032
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
 
добавил склейку верхних этажей, пока результат меньше 2470
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
function ComparePowerTowers(const a1, a2: TPowerTower): integer;
const
  epsilon= 1.0e-9;
const
  //MaxBaseForPower: array[2..8] of integer= (17,6,4,3,2,2,2);       //MaxBaseForPower[i]^i<300
  MaxBaseForPower: array[2..11] of integer= (49,13,7,4,3,3,2,2,2,2); //MaxBaseForPower[i]^i<2470
var
  t1, t2: TPowerTower;
  i, len1, len2, pow: integer;
  x1, x2: extended;
begin;
  len1:=Length(a1);
  len2:=Length(a2);
  for i:=0 to len1-1 do if a1[i]<=1 then begin;
    len1:=i;
    break;
    end;
  for i:=0 to len2-1 do if a2[i]<=1 then begin;
    len2:=i;
    break;
    end;
  if len1 or len2=0 then begin;
    Result:=0;
    exit;
    end;
  t1:=Copy(a1, 0, len1);
  t2:=Copy(a2, 0, len2);
  if len1<len2 then begin;
    SetLength(t1, len2);
    for i:=len1 to len2-1 do t1[i]:=1;
    len1:=len2;
    end;
  if len2<len1 then begin;
    SetLength(t2, len1);
    for i:=len2 to len1-1 do t2[i]:=1;
    len2:=len1;
    end;
  if (t1[0]=1) or (t2[0]=1) then begin;
    Result:=t1[0]-t2[0];
    exit;
    end;
  while (len2>1)
    and (t1[len2-1]<=High(MaxBaseForPower)) and (t1[len2-2]<=MaxBaseForPower[t1[len2-1]])
    and (t2[len2-1]<=High(MaxBaseForPower)) and (t2[len2-2]<=MaxBaseForPower[t2[len2-1]])
    do begin;
    pow:=t1[len2-2]; for i:=2 to t1[len2-1] do pow:=pow*t1[len2-2]; t1[len2-2]:=pow;
    pow:=t2[len2-2]; for i:=2 to t2[len2-1] do pow:=pow*t2[len2-2]; t2[len2-2]:=pow;
    dec(len2);
    end;
  len1:=len2-4;
  if len1<0 then len1:=0;
  if len1+4=len2 then begin;
    x1:=ln(ln(t1[len1])) + ln(t1[len1+1]) * exp(ln(t1[len1+2])*t1[len1+3]);
    x2:=ln(ln(t2[len1])) + ln(t2[len1+1]) * exp(ln(t2[len1+2])*t2[len1+3]);
    end
  else if len1+3=len2 then begin;
    x1:=ln(ln(t1[len1])) + ln(t1[len1+1]) * t1[len1+2];
    x2:=ln(ln(t2[len1])) + ln(t2[len1+1]) * t2[len1+2];
    end
  else if len1+2=len2 then begin;
    x1:=ln(t1[len1]) * t1[len1+1];
    x2:=ln(t2[len1]) * t2[len1+1];
    end
  else begin;
    x1:=t1[len1];
    x2:=t2[len1];
    end;
  if abs(x1-x2)/(abs(x1)+abs(x2)+epsilon)>epsilon then begin;
    if x1<x2 then Result:=-1 else Result:=1;
    exit;
    end;
  for i:=len1-1 downto 0 do begin;
    Result:=t1[i]-t2[i];
    if Result<>0 then exit;
    end;
  Result:=0;
  end;

...
Рейтинг: 0 / 0
07.02.2016, 13:39
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165036
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovЯ о другом. В исходных данных могут подсунуть башни с длинными единичными хвостами.
Эти тоже отсекал.

Aleksandr Sharahovэксперименты показывают, что 300 - сильно заниженная оценка,
переполнения не происходит даже при 2470,
т.е. при вычислении 99^99^99^2470
Скорее всего ты переполнение не заметил.
99^99 = 3,7 * 10^197
99^(10^197) ~ 10^(2 * 10^197) тут уже никаких стандартных типов не хватит.

Стандартный double (который в процессоре реализован) имеет предел 10^308.
...
Рейтинг: 0 / 0
07.02.2016, 13:50
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165041
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TСкорее всего ты переполнение не заметил.


Разумеется, я не вычислял башню непосредственно,
а вычислял двойной логарифм,
как это сделано и в твоем, и в моем исходниках.

Кроме того, я использую тип extended, а не double.
...
Рейтинг: 0 / 0
07.02.2016, 14:09
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165044
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Например, вот такой тест проходит сравнение 18783990

Код: pascal
1.
2.
3.
a1 = 99 98 99 99 99 99 99 99 99 2470
a2 = 98 99 99 99 99 99 99 99 99 2470
Result = -1 Expected = -1
...
Рейтинг: 0 / 0
07.02.2016, 14:15
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165115
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
оффтоп:

решил погуглить "сравнение числовых башен". прямого ответа не нашел, зато набрел на статью
http://lpgenerator.ru/blog/2014/12/10/zanimatelnaya-statistika-chast-vtoraya-gigantskaya/
в нем степенные башни с одинаковыми числами определяются как "тетрации".
Дочитал до места:
автор Операция пятого уровня — Пентация (^^^)

Пентация — это повторяющаяся тетрация, объединяет последовательности с двумя стрелками в одну операцию.
Гипероператор каждого последующего уровня сокращает последовательность предыдущего уровня, используя термин b для обозначения длины последовательности. Например:

пентация

Умножение сокращает последовательность сложения.
Возведение сокращает последовательность умножения.
Тетрация сокращает последовательность возведения в степень.

В каждом случае a — число в основании, b — длина последовательности.
Но что же сокращает пентация? Принцип работы этого гипероператора можно описать как «безумное поглощение степенных башен».

Представьте последовательность степенных башен в определенном порядке. Все они имеют одинаковое число в основании, отличаются только количеством уровней.

Вычисляем результат первой степенной башни и подставляем его вместо значения высоты (количества уровней) для следующей башни. Затем вычисляем и ее результат и подставляем его в количество уровней следующей степенной башни. И так далее. Каждая последующая башня «поглощает» результат предыдущей, используя её результат для собственного «безумного» роста... и голова начала болеть :)

во всяком случае, оставляю это здесь, вдруг кому пригодится :)
...
Рейтинг: 0 / 0
07.02.2016, 18:56
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165193
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Выше я уже описал возможно единственный способ решения данной задачи. Но способ неинтересный. Ибо ключевой вопрос такой: Можно ли сравнить 2 башни наверняка(даже если разница между ними 1-2 значения) ? Если нельзя, а скорее всего нельзя, то можно ли отсортировать множество башен не сравнивая их друг с другом ? При этом в данном конкретном случае bucket sort не подойдёт

Код ниже может быть решение, а может и нет (не разбирал). Сегодня совсем нет времени, да и задача мне пока не нравится.

 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
{$O-,Q+,R+}
uses SysUtils, Math;

const MaxK=9;
      inf=1e239;
      inf2=1e100;
      eps=1e-6;
      MaxN=50000;
      MaxA=99;

procedure readr (var x:integer; a, b:integer);
begin
  assert (not seekeoln); read (x); assert ((a<=x) and (x<=b));
end;

procedure readl;
begin
  assert (eoln); assert (not eof); readln
end;

type ip=record
       l, o:integer;
       x:extended;
     end;
     tow=array [0..MaxK] of integer;


         
function pseudoeval (s, k:integer; const t:tow):extended;
var i:integer;
begin
  assert (s<=k);
  Result:=t[k];
  for i:=k-1 downto s do begin
    if t[i]=1 then Result:=1 else
    if Result>1000 then Result:=inf else begin
      assert (Result=round (Result));
      Result:=IntPower (t[i], round (Result));
      if Result>inf then Result:=inf;
    end;
  end;
end;


procedure convert (k:integer; const t:tow; var r:ip);
begin
  r.l:=0; r.x:=pseudoeval (0, k, t);
  while r.x>=inf2 do begin
    inc (r.l); r.x:=pseudoeval (r.l, k, t)*ln (t[r.l-1]);
  end;
end;

function myln (x:extended):extended;
begin
  if x<=eps then myln:=-inf else myln:=ln (x);
end;


function less (var a, b:ip):boolean;
var l1, l2:extended;
    i:integer;
begin
  if a.o=b.o then begin Result:=false; exit end;
  l1:=a.x; l2:=b.x;
  for i:=a.l+1 to b.l do l1:=myln (l1);
  for i:=b.l+1 to a.l do l2:=myln (l2);
  assert (abs (l1-l2)>eps);
  less:=l1<l2;
end;

var A:array [1..MaxN] of ip;


procedure qsort (l, r:integer);
var i, j:integer;
    x, y:ip;
begin
  if l>=r then exit;
  i:=l; j:=r; x:=A[(l+r) shr 1];
  repeat
    while less (A[i], x) do inc (i);
    while less (x, A[j]) do dec (j);
    if i<=j then begin
      y:=A[i]; A[i]:=A[j]; A[j]:=y;
      inc (i); dec (j)
    end
  until i>j;
  qsort (l, j);
  qsort (i, r);
end;



var tmp:tow;
    i, j, K, N:integer;


begin
  reset (input, 'towers.in');
  rewrite (output, 'towers.out');
  readr (N, 1, MaxN); readl;
  for i:=1 to N do begin
    readr (K, 1, 9);
    for j:=0 to K do readr (tmp[j], 1, MaxA);
    convert (k, tmp, A[i]);
    A[i].o:=i;
    readl;
  end;
  assert (eof);
  qsort (1, N);

  for i:=1 to N-1 do
    assert (less (A[i], A[i+1]) and not less (A[i+1], A[i]));

  for i:=1 to N do write (A[i].o, ' ');
end.

...
Рейтинг: 0 / 0
08.02.2016, 01:54
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165194
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Интересно. Это задача на тему "Сортировки и последовательности" возможно я был не прав в части логарифмов и экспонент.
...
Рейтинг: 0 / 0
08.02.2016, 02:06
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165200
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonИнтересно. Это задача на тему "Сортировки и последовательности" возможно я был не прав в части логарифмов и экспонент.
Одно не исключает другое. Задача звучит так: "есть набор последовательностей (башен) и надо их отсортировать". Осталась мелочь: придумать алгоритм сравнения двух башен.
...
Рейтинг: 0 / 0
08.02.2016, 07:11
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165206
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryВыше я уже описал возможно единственный способ решения данной задачи. Но способ неинтересный.
Не нашел. Тут 18775760 мельком какое-то нечеткое сравнение упомянул, а дальше про сложность алгоритма.

SashaMercury Ибо ключевой вопрос такой: Можно ли сравнить 2 башни наверняка(даже если разница между ними 1-2 значения) ? Если нельзя, а скорее всего нельзя, то можно ли отсортировать множество башен не сравнивая их друг с другом ?
Нельзя отсортировать если невозможно сравнить. Раз есть правильные решения - задача решаема.

SashaMercuryКод ниже может быть решение, а может и нет (не разбирал). Сегодня совсем нет времени, да и задача мне пока не нравится.
Много букав на непонятном паскале, магические числа (1e239, 1e100) и ни одного камента.

Ты бы лучше словами описал свой алгоритм сравнения двух башен.
...
Рейтинг: 0 / 0
08.02.2016, 07:33
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165217
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Использование bucket sort позволит провести сортировку не сравнивая элементы исходного множества друг с другом. Однако, в данном конкретном случае, такая сортировка не подойдёт. Может быть существует другой вариант по сортировке без сравнения элементов непосредственно друг с другом ?

Алгоритм такой:
Использовать быстрое возведение в степень, и свой формат хранения больших чисел. Но данный алгоритм не позволит сравнить две башни, разница между которыми очень маленькая. Тут аналогичная ситуация как с диапазоном long double, и покрытием множества действительных чисел. Асимптотика алгоритма O(nlgn), коэффициент перед функцией будет порядка 10^3
...
Рейтинг: 0 / 0
08.02.2016, 07:49
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165239
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryИспользование bucket sort позволит провести сортировку не сравнивая элементы исходного множества друг с другом. Однако, в данном конкретном случае, такая сортировка не подойдёт. Может быть существует другой вариант по сортировке без сравнения элементов непосредственно друг с другом ?
Не знаю почему ты решил что bucket sort не требует сравнения. Там элементы не сравниваются меж собой на первом шаге, но сравнивается элемент с границами корзины. На втором шаге каждая корзина сортируется обычной сортировкой, т.е. со сравнением элементов. ИМХУ это просто специфичный вид сортировки для очень больших последовательностей: сначала разбиваем на куски, которые гарантированно поместятся в памяти, затем сортируем каждый кусок.

SashaMercuryАлгоритм такой:
Использовать быстрое возведение в степень, и свой формат хранения больших чисел. Но данный алгоритм не позволит сравнить две башни, разница между которыми очень маленькая. Тут аналогичная ситуация как с диапазоном long double, и покрытием множества действительных чисел. Асимптотика алгоритма O(nlgn), коэффициент перед функцией будет порядка 10^3
Думаю тут достаточно порядок результата прикинуть с точностью до первых 10-15 десятичных разрядов. Но и порядок хранить проблематично:
99^99 = 3,7 * 10^197
99^(10^197) ~ 10^(2 * 10^197)
...
Рейтинг: 0 / 0
08.02.2016, 09:01
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165312
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Если правильно вижу, то решение 18785435 отличается от 18783990 следующим:

1) хранит башню в виде:
- количество уровней до шапки
- шапка
(а не только шапку)

2) вычисляет шапку,
2а) склеивая верхние уровни в один до тех пор, пока ее величина остается меньше 1000 (а не 2470)
2б) логарифмируя полученное значение и умножая его на значение предыдущего уровня,
чтобы учесть в шапке на 1 уровень больше (а не на 3 уровня)

3) для всех неучтенных уровней хранит их количество

4) для сравнения башен сравниваются их шапки,
однако, если уровни башен до шапок не совпадают,
то перед сравнением шапка меньшей логарифмируется
столько раз, какова разность уровней.
...
Рейтинг: 0 / 0
08.02.2016, 10:52
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165317
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
не совсем понимаю, как оно заметит разницу между
99 99 99 99 99 99 99 99 99 и
98 99 99 99 99 99 99 99 99
...
Рейтинг: 0 / 0
08.02.2016, 11:00
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165323
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Идея с логарифмированием на разность уровней очень хороша, можно своровать ))
И для большей строгости использовать правильное основание, а не просто e.
...
Рейтинг: 0 / 0
08.02.2016, 11:05
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165335
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, логарифм по правильному основанию всё равно
расчитывается через натуральные. Строгость мы получаем только
в суждениях но в численном методе остаётся тоже что и было.
...
Рейтинг: 0 / 0
08.02.2016, 11:12
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165345
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

я это типа знаю,
но почему бы не учесть множитель, если он сам идет в руки ))
...
Рейтинг: 0 / 0
08.02.2016, 11:16
| Ответить | Цитировать | Написать  
25 сообщений из 208, страница 4 из 9
  4  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]