Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 6 7 [8]      все
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1137
kealon(Ruslan)
Aleksandr Sharahov
интересно, что тот же алгоритм с очевидными изменениями
находит 2 шара из 20 за 8 проверок, а вот что делать дальше неясно.
и 2 из 23 за 8 можно, должен быть масштабируемый алгоритм

Barlone прав, число возможных расстановок C(k,N) а значит минимально достаточно log2(C(k,N)) бит что бы описать любой из вариантов расстановки
не, эта оценка не всегда достижима 21827278 и 2 из 23 за 8 не получится
10 мар 19, 11:05    [21828662]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
Barlone
kealon(Ruslan)
пропущено...
и 2 из 23 за 8 можно, должен быть масштабируемый алгоритм

Barlone прав, число возможных расстановок C(k,N) а значит минимально достаточно log2(C(k,N)) бит что бы описать любой из вариантов расстановки
не, эта оценка не всегда достижима 21827278 и 2 из 23 за 8 не получится


и причина тут тот же закон сохранения информации
например 2 из 16 не получится

т.к. C(16,2) = 120

C(12,2) = 66 > 64
а С(11,2) = 55 и останется 120 - 55 = 65, что тоже >64

исходя из этого же следует что в вашем алгоритме ошика, нельзя откусить первым шагом 3, только 4 или 5
10 мар 19, 12:40    [21828675]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
Barlone,

с 4 довольно тривиально, а вот с 5 я кое как придумал
10 мар 19, 12:41    [21828676]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
Barlone,
поправлю
исходя из этого же следует что в вашем алгоритме ошибка, нельзя "откусить" от 15-ти первым шагом 3, только 4 или 5

т.к. C(12,2) = 66 > 64
10 мар 19, 12:45    [21828677]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
kealon(Ruslan), дык он ад хок делал для 15/2ш. Попутно могло подойти и для нек-х других.
А вообще, в теории алгоритмов известны примеры неразрешимых массовых алгоритммических проблем, к-рые тем не менее имеют решения для частных случаев.
Это может означать к примеру, что высказанный Бароном метод построения алгоритма не универсален, но если поработать над методом (или над высказыванием), мало ли, может и получится универсальный для N/2.
Вообще же, это математическая задача, не программистская.

П.С. ссылка хорошая, кто-то ею уже попользовался))
10 мар 19, 13:39    [21828690]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
kealon(Ruslan)
а значит минимально достаточно log2(C(k,N)) бит что бы описать любой из вариантов
Как осуществлять поиск 1 значения в массиве знают все. А вот как быстро искать 2 значения?
10 мар 19, 13:47    [21828692]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
exp98
kealon(Ruslan)
а значит минимально достаточно log2(C(k,N)) бит что бы описать любой из вариантов
Как осуществлять поиск 1 значения в массиве знают все. А вот как быстро искать 2 значения?


Так же )

Хитрости типа 2 из 15 имеют смысл только на малых массивах,
а на больших задача "найти 2" превращается в задачу "2 раза найти 1".
10 мар 19, 17:19    [21828734]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
Aleksandr Sharahov
exp98
пропущено...
Как осуществлять поиск 1 значения в массиве знают все. А вот как быстро искать 2 значения?


Так же )

Хитрости типа 2 из 15 имеют смысл только на малых массивах,
а на больших задача "найти 2" превращается в задачу "2 раза найти 1".

По сути на больших 2 из N мы можем улучшать только среднюю оценку
поиска. Но максимальную не улучшим.

Верно?
10 мар 19, 21:02    [21828788]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Например, надо найти 2 из 32.
Рассмотрим крайние случаи.

1. Проверяем левую половину, затем правую,
и числа сразу попадают в разные части.
Сокращаем размер каждой части: 8-4-2-1.
Итого 2+4*2=10 проверок.

2. Проверяем левую половину, затем правую,
и каждый раз числа попадают в правую часть:
16-8-4-2. Итого 4*2+1=9 проверок.

С(2,32)=496~512=2^9, т.е. мы в принципе
не могли затратить меньше 9 проверок.
10 мар 19, 21:14    [21828789]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Aleksandr Sharahov
Например, надо найти 2 из 32.
Рассмотрим крайние случаи.

1. Проверяем левую половину, затем правую,
и числа сразу попадают в разные части.
Сокращаем размер каждой части: 8-4-2-1.
Итого 2+4*2=10 проверок.

2. Проверяем левую половину, затем правую,
и каждый раз числа попадают в правую часть:
16-8-4-2. Итого 4*2+1=9 проверок.

С(2,32)=496~512=2^9, т.е. мы в принципе
не могли затратить меньше 9 проверок.


Сорри скопипастил сдуру,
во втором случае, конечно, всего 4 проверки.

В худшем случае мы тратим всего 1 лишнюю проверку
10 мар 19, 21:23    [21828790]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Относительно средней оценки все выглядит так,
будто она мало зависит от алгоритма.
Плюс-минус одна проверка не имеет значения,
если их десятки.
10 мар 19, 21:31    [21828795]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
ну вот, пришёл Александ и всё опошлил :-)
11 мар 19, 06:33    [21828852]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
вариант с первоначальным "откусыванием" 5 (без трививальной части )

+
program SetTest;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  SysUtils;

type
  TSetNum = 1..15;
  TSet = set of TSetNum;

  TTest = function(A: TSet): Boolean of object;


function BinS(m: TTest; a, b: Integer): TSet;
var
  l, i: Integer;
  v: TSet;
begin
  repeat
    l := a + (b - a) div 2;
    v := [];
    for i := a to l do
      v := v + [i];
    if m(v) then begin
      b := l;
      if l = a then
        Exit([a]);
    end else
    begin
      if a = l then
        Exit([b]);
      a := l + 1;
    end;
  until False;
end;

function Alg(m: TTest): TSet;
begin
  // Всего С(2,15) = 105
  if m([1..5]) then begin
    // C(2,5) + 5 * 10 =   60
    if m([4,5,6]) then begin
      // C(2,6) - C(2,3)  + 2 * 9 = 30
      if m([8..15]) then begin
        // 2 *  8 = 16
        Result := BinS(m, 4, 5) + BinS(m, 8, 15);
      end else begin
        // C(2,6) - C(2,3)  + 2 * 1 = 14
        if m([1, 6]) then begin
          // 3 + 4 = 7
          if m([1]) then begin
            // 3
            Result := [1] + BinS(m, 4, 6);
          end else begin
            // 4
            Result :=  [6] + BinS(m, 2, 5);
          end;
        end else begin
          // C(2,4) -1 + 2 = 7
          if m([2,3]) then begin
            // C(2,3) = 4
            Result := BinS(m, 2, 3) + BinS(m, 4, 5);
          end else begin
            // 3
            if m([7]) then
              Result := [7] + BinS(m, 4, 5)
            else
              Result := [4,5];
          end;
        end;
      end;
    end else begin
      // C(2,3) + 3* 9 = 30
      if m([3,7,8]) then begin
        // C(2, 5) - 2 {без [1,2] и [7,8]} + 1 * 7 = 15
        if m([9..15]) then begin
          // 7
          Result := [3] + BinS(m, 9, 15);
        end else begin
          // C(2, 5) - 2 = 8
          if m([3]) then begin
            // 4
            if m([7,8]) then begin
              if m([7]) then
                Result := [7]
              else
                Result := [8];
            end else begin
              if m([1]) then
                Result := [1]
              else
                Result := [2];
             end;
            Result := Result + [3];
          end else begin
            // 2 * 2 = 4
            if m([1]) then
              Result := [1]
            else
              Result := [2];
            if m([7]) then
              Result := Result + [7]
            else
              Result := Result + [8]
          end;
        end;
      end else begin
        // C(2,2) + 2 * 7 = 15
        if m([12..15]) then begin
          // 2 * 4 = 8
          Result := BinS(m, 1, 2) + BinS(m, 12, 15);
        end else begin
          // C(2,2) + 2 * 3 = 7
          if m([10,11]) then begin
            // 2 * 2
            Result := BinS(m, 1, 2) + BinS(m, 10, 11);
          end else begin
            //C(2,2) + 2 * 1 = 3
            if (m([9])) then begin
              Result := BinS(m, 1, 2) + [9];
            end else begin
              Result := [1,2];
            end;
          end;
        end;
      end;
    end;
  end else begin
    // С(2, 10) = 45   - тривиальный, не буду рассматривать
    Result := [];
  end;
end;

type
  TSetTest = record
    v: TSet;
    c: Integer;
    constructor create(i,j: Integer);
    function Con(A: TSet): Boolean;
  end;

function TSetTest.Con(A: TSet): Boolean;
begin
  Inc(c);
  Result := (v * A <> []);
end;

constructor TSetTest.Create(i, j: Integer);
begin
  c := 0;
  v := [i,j];
end;

var
  i,j: Integer;
  TestM: TSetTest;
  s: TSet;
begin
  try
    for i := 1 to 5 do
      for j := i + 1 to 15 do begin
        TestM := TSetTest.create(i,j);
        s := Alg(TestM.Con);
        if (TestM.v <> s)or(TestM.c > 7) then begin


          TestM := TSetTest.Create(i,j);
          s := Alg(TestM.Con);

          raise Exception.Create('Error Message');
        end;
      end;
    Writeln('Ok');
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.
11 мар 19, 10:51    [21828949]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 6 7 [8]      все
Все форумы / Программирование Ответить