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

Откуда: Москва
Сообщений: 1730
Перечитал 21827271 и 21827278

На время праздничное помутнением покинуло мозг, и вновь я осознал и множества, и дихотомию )
Попробую сказать то же самое своими словами.

Для анализа алгоритма достаточно ограничиться рассмотрением пар чисел.
Нас интересует только пара-решение, ее мы ищем.
Все другие пары, даже если в них входит одно из звенящих чисел, нам безразличны.
Это важный момент, и он может сбивать с толку: в процессе решения мы часто ищем
каждое число из пары-решения по-отдельности, но для анализа это не важно.

Изначально пара-решение входит во все множество пар. В процессе решения
мы сокращаем это включающее множество. Когда размер включающего
множества сократится до 1 - мы нашли решение.

С этой точки зрения неважно, какие проверки мы делаем,
важно лишь, как при этих проверках сокращается включающее множество.
При любой проверке мы разбиваем множество пар на 2 части: включающую
и не влючающую. Мы всегда предполагаем худшее, а именно, что включающее
множество - большее из полученных. Очевидно, что если в х шагах от выдачи
результата размер включающего множества превышает 2х,
то решение найти не удастся. В силу дискретности задачи граница лежит ниже.

Удобно сначала построить последовательности проверок для меньших
количеств шаров. Эти построения можно использовать, если окажется,
что это множество ни разу не проверялось и оба шара лежат там.
8 мар 19, 11:28    [21827856]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
Aleksandr Sharahov, а можно интерпретировать это для бывших танкистов. Из такого объяснения понял только 1-й и последний абзацы.
П.С.
В связи с 1-м абзацем поздравляю всех наших жён с наступившей, бр-р-р, весной.
В связи с отсутствием их интереса к топику, предлагаю им пожелать скорректировать вектор интересов от "kinder, cookery, show" в средней или последней части.
8 мар 19, 16:51    [21828031]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
Может для общего языка ссылаться на случаи согласно типовой нумерации.
типа такого:
+
degree10,nn,       code,binary,           Hex,   Count(digits)
0,0,      0,0b000000000000000,0x0000,15
1,1,     11,0b000000000000011,0x0003,15
2,2,    101,0b000000000000101,0x0005,15
2,3,    110,0b000000000000110,0x0006,15
3,4,   1001,0b000000000001001,0x0009,15
3,5,   1010,0b000000000001010,0x000A,15
3,6,   1100,0b000000000001100,0x000C,15
4,7,  10001,0b000000000010001,0x0011,15

Вкладываю для 15.

К сообщению приложен файл (CodeHex.csv - 5Kb) cкачать
8 мар 19, 17:01    [21828034]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
Допустим оба тухлых яйца расположились как "....10001" (случай 7), но мы пока этого не знаем. Что дальше?.. Что за пары чисел, что и когда разбивает 105 случаев на включающую и не включающую части ?...
Хочется услышать как-нибудь поструктурнее.
8 мар 19, 17:13    [21828036]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
exp98
Aleksandr Sharahov, а можно интерпретировать это для бывших танкистов. Из такого объяснения понял только 1-й и последний абзацы.
П.С.
В связи с 1-м абзацем поздравляю всех наших жён с наступившей, бр-р-р, весной.
В связи с отсутствием их интереса к топику, предлагаю им пожелать скорректировать вектор интересов от "kinder, cookery, show" в средней или последней части.


Вообще-то это как раз и была интерпретация разъяснений Barlone )
Если интерпретировать интерпетацию она вырождается в нечто в роде такого:

Рассмотрим множество всевозможных пар шаров мощностью C(2,N).
Нас интерересует только один элемент этого множества - пара звенящих шаров.
Каждый тест, возвращая булевский результат, тем самым делит множество на 2 части.
И нет никакого способа найти нашу пару быстрее log(C(2,N)) ,
т.к. мы будем вредить, перенумеровывая шары перед каждым тестом,
но не нарушая результатов предыдущих тестов.
8 мар 19, 17:50    [21828050]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
exp98
Допустим оба тухлых яйца расположились как "....10001" (случай 7), но мы пока этого не знаем. Что дальше?.. Что за пары чисел, что и когда разбивает 105 случаев на включающую и не включающую части ?...
Хочется услышать как-нибудь поструктурнее.


В данном случае мы пытаемся только оценить количество шагов, а не построить алгоритм.
Поэтому анализ неконструктивный.
8 мар 19, 18:11    [21828057]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
Aleksandr Sharahov, спасибо за разъяснения. Поначалу я так же думал, что для кодирования 128 номеров необходимо 7 бит, потом у меня всё смешалось и таким остаётся.
Смущает, что С(12)=11*12/2=66 между (64; 128), и у меня для 12 раз за разом ответ 7. Но может я путаю, осталось убеждение, что все говорят для 12 ответ 6 или нет? ох, как неохота выискивать на страницах ...

Но с другой стороны, 7 бит - это когда номера произвольные. В задаче всё же номера имеют внутреннюю структуру ( 10101 - не м.б. и т.п.), и не все случаи равновероятны. Например при проверке кучек 6+1+1 не может получиться 002 или 111.
В общем какие-то ассоциации с частотным кодированием по Хэммингу. Может здесь эти ассоциации срабатывают? Лично я уже ни в чём не уверен.
8 мар 19, 18:19    [21828064]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
exp98
Aleksandr Sharahov, спасибо за разъяснения. Поначалу я так же думал, что для кодирования 128 номеров необходимо 7 бит, потом у меня всё смешалось и таким остаётся.
Смущает, что С(12)=11*12/2=66 между (64; 128), и у меня для 12 раз за разом ответ 7. Но может я путаю, осталось убеждение, что все говорят для 12 ответ 6 или нет? ох, как неохота выискивать на страницах ...

Но с другой стороны, 7 бит - это когда номера произвольные. В задаче всё же номера имеют внутреннюю структуру ( 10101 - не м.б. и т.п.), и не все случаи равновероятны. Например при проверке кучек 6+1+1 не может получиться 002 или 111.
В общем какие-то ассоциации с частотным кодированием по Хэммингу. Может здесь эти ассоциации срабатывают? Лично я уже ни в чём не уверен.


Для 12 ответ 7, см. 21827271.

Да, у нас не все случаи равновероятны. У нас с даже хуже.
Мы всегда предполагаем, что очередной тест дает результат,
который требует максимального количества дальнейших проверок.

З.Ы. В этой задаче такие ассоциации мне только мешают )
8 мар 19, 20:01    [21828107]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Полная проверка алгоритма Barlone (2 из 15) на Delphi без формочек:

+
function IsWhite(const balls, white: string; var calls: integer): boolean;
var
  i: integer;
begin;
  inc(calls);
  Result:=false;
  for i:=1 to Length(balls) do Result:=Result or (balls[i]=white[1]) or (balls[i]=white[2]);
  end;

function Find1(const balls, white: string; var calls: integer): char;
var
  half, count: integer;
begin;
  count:=Length(balls);
  half:=(count+1) shr 1;
  if count<=1
  then Result:=balls[1]
  else if IsWhite(copy(balls,1,half), white, calls)
       then Result:=Find1(copy(balls,1,half), white, calls)
       else Result:=Find1(copy(balls,1+half,count-half), white, calls);
  end;

function Find2(const balls, white: string; var calls: integer): string;
var
  i: integer;
begin;
  Result:='';
  for i:=1 to Length(balls)-1 do if IsWhite(balls[i], white, calls) then begin;
    Result:=Result+balls[i];
    if Length(Result)=2 then exit;
    end;
  Result:=Result+balls[Length(balls)];
  end;

function Find2From15(const balls, white: string; var calls: integer): string;
begin;
  if IsWhite('12345',white,calls)
  then if IsWhite('12f',white,calls)
       then if IsWhite('16',white,calls)
            then if IsWhite('89abcdef',white,calls)
                 then Result:='1'+Find1('89abcdef',white,calls)
                 else if IsWhite('3457',white,calls)
                      then Result:='1'+Find1('3457',white,calls)
                      else Result:=Find2('126',white,calls)
            else if IsWhite('cdef',white,calls)
                 then if IsWhite('f',white,calls)
                      then Result:=Find1('2345',white,calls)+'f'
                      else Result:='2'+Find1('cde',white,calls)
                 else Result:='2'+Find1('345789ab',white,calls)
       else if IsWhite('367',white,calls)
            then if IsWhite('4567',white,calls)
                 then if IsWhite('3',white,calls)
                      then Result:='3'+Find1('4567',white,calls)
                      else Result:=Find1('45',white,calls)+Find1('67',white,calls)
                 else Result:='3'+Find1('89abcde',white,calls)
            else if IsWhite('4',white,calls)
                 then Result:='4'+Find1('589abcde',white,calls)
                 else Result:='5'+Find1('89abcde',white,calls)
  else if IsWhite('6789',white,calls)
       then if IsWhite('abcd',white,calls)
            then Result:=Find1('6789',white,calls)+Find1('abcd',white,calls)
            else if IsWhite('ef',white,calls)
                 then Result:=Find1('6789',white,calls)+Find1('ef',white,calls)
                 else Result:=Find2('6789',white,calls)
       else if IsWhite('abcd',white,calls)
            then if IsWhite('ef',white,calls)
                 then Result:=Find1('abcd',white,calls)+Find1('ef',white,calls)
                 else Result:=Find2('abcd',white,calls)
            else Result:='ef';
  end;

function Validate: string;
const
  hex: array[0..15] of char= '0123456789abcdef';
var
  white, sol, maxsol: string;
  ch1, ch2: char;
  i, j, i1, i2, calls, maxcalls: integer;
begin;
  maxcalls:=0;
  for i2:=2 to 15 do begin;
    for i1:=1 to i2-1 do begin;
      white:=hex[i1]+hex[i2];
      calls:=0;
      sol:=Find2From15('abcd',white,calls);
      if maxcalls<calls then begin;
        maxcalls:=calls; maxsol:=sol;
        end;
      if white<>sol then begin;
        Result:=Format('Тест завален, неверное определение %s<>%s', [sol, white]);
        exit;
        end;
      end;
    end;
  Result:=Format('Тест пройден, максимум проверок %d для шаров %s', [maxcalls, maxsol]);
  end;
9 мар 19, 00:48    [21828222]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1137
По похожему принципу решаются задачи на взвешивания типа "найти две фальшивых монеты из 13", только делить надо на 3 части.
(известно что фальшивые монеты одинакового веса и тяжелее настоящих, у нас есть рычажные весы без гирь...)
9 мар 19, 06:42    [21828251]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
Barlone, и так же тухлые яйца,помидоры и т.п., только их не взвешивают, а вонь проверяют))

Э-э, вопрос был к дельфам: а) где ж её взять или хотя бы интерпретатор;
б) недопонял это
  if IsWhite('12f',white,calls).......
и подобное.
Это повторная проверка шаров 1 и 2? для чего? ведь перед этим
  IsWhite('12345',......

Ведь судя по самой последней проверке
            then if IsWhite('ef',white,calls)
then Result:=Find1('abcd',white,calls)+Find1('ef',white,calls)
else Result:=Find2('abcd',white,calls)
else Result:='ef';
ф-ция IsWhite() проверяет отсутствие. Или наоборот?
9 мар 19, 14:17    [21828381]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
exp98
Barlone, и так же тухлые яйца,помидоры и т.п., только их не взвешивают, а вонь проверяют))

Э-э, вопрос был к дельфам: а) где ж её взять или хотя бы интерпретатор;
б) недопонял это
  if IsWhite('12f',white,calls).......
и подобное.
Это повторная проверка шаров 1 и 2? для чего? ведь перед этим
  IsWhite('12345',......

Ведь судя по самой последней проверке
            then if IsWhite('ef',white,calls)
then Result:=Find1('abcd',white,calls)+Find1('ef',white,calls)
else Result:=Find2('abcd',white,calls)
else Result:='ef';
ф-ция IsWhite() проверяет отсутствие. Или наоборот?


a) скачать стартовую версию бесплатно у производителя

б) IsWhite('12345', '37', calls) проверяет светимость группы шаров 12345,
если по условию дано, что светятся шары 37,
т.е. вхождение одного из шаров 3 или 7 в группу 12345.
При этом инкрементируется счетчик проверок calls

Да эта проверка повторно затрагивает шары 1 и 2, таков алгоритм.

IsWhite() проверяет наличие светимости
9 мар 19, 14:45    [21828392]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
интересно, что тот же алгоритм с очевидными изменениями
находит 2 шара из 20 за 8 проверок, а вот что делать дальше неясно.
9 мар 19, 15:26    [21828400]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
Так получилось, что сам только что заглянул, поэтому спрашиваю.
Непонятна цель повторной проверки. Скорее всего просто так родилось, ну и оставили.
Умозрительно кажется, что
  if IsWhite('12f',white,calls).......
можно заменить на проверку только "f".
9 мар 19, 15:35    [21828403]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
Aleksandr Sharahov
дальше неясно.
Дальше переходить на полный бэктрекинг и генерацию подмножеств 2^21 ...
Вообще, стоит покопаться в работах по обнаружению ошибок.
9 мар 19, 15:40    [21828405]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
exp98
Так получилось, что сам только что заглянул, поэтому спрашиваю.
Непонятна цель повторной проверки. Скорее всего просто так родилось, ну и оставили.
Умозрительно кажется, что
  if IsWhite('12f',white,calls).......
можно заменить на проверку только "f".


Нет, нельзя. Смысл изменится.
Там каждая циферка играет свою роль.
9 мар 19, 15:41    [21828406]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
Ни фига не понимаю почему. Ведь если '12345' не пахнут, почему '12f' могут отличаться от 'f'? Ведь первые 2 ифа работают по этой логике.
9 мар 19, 15:49    [21828407]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
У меня сведения старые, по автоматическому синтезу алгоритмов можно ещё почитать. У нас давно ещё направление развивал Лупанов ОБ., ну и другие менее тогда известные.
9 мар 19, 15:59    [21828408]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1137
exp98
Ни фига не понимаю почему. Ведь если '12345' не пахнут, почему '12f' могут отличаться от 'f'? Ведь первые 2 ифа работают по этой логике.
нет, вторая проверка в 'true' ветке. Среди 12345 есть меченый, но это может быть и не 12.
9 мар 19, 16:09    [21828409]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
exp98
Ни фига не понимаю почему. Ведь если '12345' не пахнут, почему '12f' могут отличаться от 'f'? Ведь первые 2 ифа работают по этой логике.


тут надо узнать как можно больше про пару 12, а f подмешиваем, чтобы использовать знание о нем ниже
логика такая: если 12f не пахнут, то 12 не пахнут, и значит пахнут 345
а в нижних else-ветках мы уже знаем, что и f не пахнет
9 мар 19, 16:10    [21828411]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
Хорошо, вам лучше знать,
IsWhite() == тру, при наличии метки
IsWhite() == фолс, при отсутствии метки.
Раньше я думал что IsWhite() действует наоборот.

Тогда "все сходится, ребёночек не наш"(с).
Спасибо за разъяснения.
9 мар 19, 20:40    [21828501]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
exp98
У меня сведения старые, по автоматическому синтезу алгоритмов
ошибся, вроде д.б. по автоматическому синтезу логических схем.
9 мар 19, 20:43    [21828502]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
exp98
Э-э, вопрос был к дельфам: а) где ж её взять или хотя бы интерпретатор;

тынц
9 мар 19, 22:02    [21828545]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

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

Barlone прав, число возможных расстановок C(k,N) а значит минимально достаточно log2(C(k,N)) бит что бы описать любой из вариантов расстановки
9 мар 19, 22:05    [21828547]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
вселенная с этим не согласна
9 мар 19, 23:09    [21828575]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 6 [7] 8   вперед  Ctrl      все
Все форумы / Программирование Ответить