powered by simpleCommunicator - 2.0.50     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничный треугольник
25 сообщений из 188, страница 4 из 8
Пятничный треугольник
    #39783164
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Типа log(x+1) ?
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783166
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneА вы попробуйте доказать, что за 7 невозможно :) для 15 ?
Первая попытка, схематично.
1) для измерения разбиваем на 2 мн-ва
2) разбиение на большее кол-во не уменьшит резалт (доказывать отдельно).
(А не потому, что никто не сумел быстрее ..)

1) Матем-ской индукцией по меньшему слагаемому
Имеем решение за 8. Например (8+7)--(4+4,4+3)--(2+2,2+2)--(1+1,1+1)
Уменьшение 7 до 6,5,...4 (т.е. до (10+5)) не уменьшает резальт. А переход от 8 к 9, наоборот увеличит.

2) ждём-с ... (просто слагаемые будут мельче, и добавляется новый ручеёк для проверки)


А насчёт помехоустойчивого кодирования (Хэмминга) ... боюсь, что сам код не оптимальный для С(N,2) вариантов, что не доказывает саму минимальность решения. И, блин, кто сюда принесёт типовые раскладки для Хэмминга с 2мя .... вот непонятно, обнаружениями или исправленями (ставлю на исправления).
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783178
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonТипа log(x+1) ? Нет.
Когда N = 2 к формула вроде как точная. Поправка должна учитывать некратность аргумента.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783183
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98, первое моё наивное решение содержало матрицу шаров типа 3х5
где я должен бы прикладывать измеритель к столбцам и строкам.
Неоптимально. Но очень похоже на выявление ошибок четности
в старых системах связи. Матричное кодирование типа.
Отсюда пошла и мысль о Хемминге как о более математически
верном пути.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783189
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, а я оч давно слышал вскользь, что колич-во измерений в похожих логических задачах можно дать ответ, построив оптимальный код (для хода измерений). Но как их строить и к чему применять, хз.
Даже в этой задаче не могу решить, по какому принципу разбивать мн-во. Например (8+1) ответ 5, (7+2)=6, (5+4)=7 ...

С другой стороны, есть задачи типа о выявлении лжеца, там больше самокоррекция напрашивается. Во всяк было что-то похожее на форуме в 12-13 г. Но загвоздка в том, какой код и с какими параметрами.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783194
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я подобные задачи обычно решаю отходя два шага назад. Тоесть чтобы глянуть как
задача выглядит не на 15 шарах а на 1500 например. И тогда будут более
очевидны. Или более "гладки". И "непрерывны" наши оценки. Ситуация с 1
шаром - тривиальна. Дихотомия. Два шара - сбивают с толку. Они дают некий
эффект который ломает дихтомию. Но не настолько чтоб сломать формулу.
Скорее просто вносит путаницу со старта для человека который решает шары
на малых значениях N.

По повод скриншота который я привел для 14 шаров. Я не удержался и заглянул вконец.
Пишут что 7 шагов достаточно. Это я не ради троллинга. А просто пишу видя что
интерес угас.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783195
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ИМХО mayton напутал и заставил искать подвох там где его нет, т.е. вместо нездорового числа 14 21824356 , которое решается за 7 измерений 21824574 вопреки общим оценкам, назвал число 15 где все банально и прозрачно.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783202
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну... прошу прощения. Эту задачу мне задал лет 15 назад один математик. И в той постановке звучало 15 шаров.

Вообще наверное суть не в этом.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783212
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я свожу к случаям 2-х мн-в и в каждом по 1метке. Каждая метка тогда стандартно находится делением/2, или даже можно сразу формулой. Поэтому я думаю, что общая формула д.б. 2-х ступенчатой, т.е. с 2-мя логарифмами.
Но разбиение пополам есть редко, а бОльшее слагаемое можно менять в больших пределах [2^k; 2*2^k), чем меньшее слагаемое. Тогда при подборе слагаемых результат для меньшего слаг-го меняется чаще, т.к. степень для него м.б. меньше. Поэтому мне видится 2-х ступенчатость общей суммы.
Это так, общие соображения.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783223
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98, проблема в том что формулы заточены на поиск одного [шара], а на два нет классических алгоритмов.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783225
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНу... прошу прощения. Эту задачу мне задал лет 15 назад один математик. И в той постановке звучало 15 шаров.

Вообще наверное суть не в этом.
Может в этом есть верх троллинга над студентами: найди подвох там где его нет. Сложно признать что подвоха нет если ты участник олимпиад и привык искать (и находить) подвох.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783227
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кажется, найти 2 из 15 таки можно за 7 измерений.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783230
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneКажется, найти 2 из 15 таки можно за 7 измерений.
Можно за одно 21823737 , но не всегда. Решение огласи
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783234
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TBarloneКажется, найти 2 из 15 таки можно за 7 измерений.
Можно за одно 21823737 , но не всегда. Решение огласиНачинается с проверки первых пяти шаров. Если там пусто, то из оставшихся 10 можно найти два за 6 проверок.
Если не пусто, меряем например 1,2,15. Каждый следующий шаг зависит от предшествующих результатов. Получается много веток. Я просто выписал все возможные варианты пар, и каждым измерением делил их на две равные части.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783239
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Челлендж: написать генератор решений. Ну то есть генератор алгоритмов в виде псевдокода или даже программы, выполняющей нужную последовательность проверок.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783272
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneЧеллендж: написать генератор решений. Ну то есть генератор алгоритмов в виде псевдокода или даже программы, выполняющей нужную последовательность проверок.

полная проверка алгоритма 21824574
Код: 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.
function IsWhite(p: pInteger; count: integer; var calls: integer): boolean;
begin;
  inc(calls);
  Result:=false;
  while count>0 do begin;
    Result:=Result or (p^>=0);
    inc(p);
    dec(count);
    end;
  end;

function FindOne(p: pInteger; count: integer; var calls: integer): integer;
begin;
  if count>1 then begin;
    count:=count shr 1;
    if not IsWhite(p, count, calls) then inc(p, count);
    Result:=FindOne(p, count, calls);
    end
  else Result:=p^;
  end;

procedure TForm1.Button1Click(Sender: TObject);
var
  x: array[0..13] of integer;
  sol: array[0..1] of integer;
  group: array[0..1] of integer;
  i, j, i1, i2, calls, gcount, maxcalls, maxi1, maxi2: integer;
begin;
  maxcalls:=0; maxi1:=0; maxi2:=0;
  for i2:=1 to Length(x)-1 do begin;
    for i1:=0 to i2-1 do begin;
      for i:=0 to Length(x)-1 do x[i]:=-1;
      x[i1]:=i1;
      x[i2]:=i2;
      calls:=0;
      gcount:=0;
      if IsWhite(@x[0],4,calls) then begin; group[gcount]:=0; inc(gcount); end; //0..3
      if IsWhite(@x[4],4,calls) then begin; group[gcount]:=4; inc(gcount); end; //4..7
      if (gcount<2) and IsWhite(@x[8],4,calls) then begin; group[gcount]:=8; inc(gcount); end; //8..11

      if gcount>=2 then for i:=0 to 1 do sol[i]:=FindOne(@x[group[i]],4,calls)
      else if gcount=0 then begin;
        sol[0]:=x[12];
        sol[1]:=x[13];
        end
      else begin; //gcount=1
        if IsWhite(@x[12],2,calls) then begin;
          sol[0]:=FindOne(@x[group[0]],4,calls);
          sol[1]:=FindOne(@x[12],2,calls);
          end
        else begin;
          i:=0; j:=0;
          while (i<2) and (j<3) do begin;
            if IsWhite(@x[group[0]+j],1,calls) then begin; sol[i]:=x[group[0]+j]; inc(i); end;
            inc(j);
            end;
          if i=1 then sol[1]:=x[group[0]+3];
          end;
        end;

      if maxcalls<calls then begin;
        maxcalls:=calls; maxi1:=i1; maxi2:=i2;
        end;
      if (i1<>sol[0]) or (i2<>sol[1])
      then Memo1.Lines.Add(Format('Неверное определение %d %d <> %d %d', [i1, i2, sol[0], sol[1]]));
      end;
    end;
  Memo1.Lines.Add(Format('Максимум проверок %d для шаров %d %d', [maxcalls, maxi1, maxi2]));
  end;

...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783304
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Поиск 2 из 15 за 7 проверок. Как уже говорил, первая проверка все 1-5.
Если пусто, то вроде бы все согласны, что из оставшихся 10 можно найти 2 за 6 проверок. Эту часть расписывать не буду.

У нас осталось 60 вариантов пар, в которых присутствует хотя бы один из шаров 1-5.
Теперь проверяем 1,2,15. При положительном результате проверяем 1 и 6, иначе 3, 6 и 7.
Получилось 4 ветки, в каждую попадают по 15 вариантов пар.
В каждой за 4 проверки можно выбрать одну правильную. Сейчас все распишу.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783305
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Первый случай. check(1,2,15)=true, check(1,6)=true
Проверяем 8-15
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
check(8,9,10,11,12,13,14,15)
 1,8         |
 1,9         |  (1,3) (1,4)
 1,10        |  (1,5) (1,7)
 1,11        |
 1,12        |-check(3,4,5,7)-
 1,13        |
 1,14        | (1,2) (1,6) (2,6)
 1,15        |
При положительном результате (слева) всегда 1 + один из 8-15, который выберем за 3 шага делением пополам.
При отрицательном результате (справа) проверяем 3,4,5,7. Сверху + снизу -. Дальше вроде понятно.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783306
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Второй случай. check(1,2,15)=true, check(1,6)=false
Проверяем 3,4,5,7,8,9,10,11
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
check(3,4,5,7,8,9,10,11)
2,3          |
2,4          |  (2,15) (3,15)
2,5          |  (4,15) (5,15)
2,7          |
2,8          |---check(15)---
2,9          |
2,10         | (2,12) (2,13) (2,14)
2,11         |
При положительном результате (слева) всегда 2 + один из 3,4,5,7,8,9,10,11, который выберем за 3 шага делением пополам.
При отрицательном результате (справа) проверяем 15. Сверху + снизу -. Дальше понятно.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783307
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Третий случай. check(1,2,15)=false, check(3,6,7)=true
Проверяем 7-14
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
check(7,8,9,10,11,12,13,14)
3,7          |
3,8          | (3,4) (3,5) (3,6)
3,9          |
3,10         |---check(3)---
3,11         |
3,12         |  (4,6) (4,7)
3,13         |  (5,6) (5,7)
3,14         |
При положительном результате (слева) всегда 3 + один из 7-14, который выберем за 3 шага делением пополам.
При отрицательном результате (справа) проверяем 3. Сверху + снизу -. Дальше понятно.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783308
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Последний случай. check(1,2,15)=false, check(3,6,7)=false
Проверяем 4
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
check(7,8,9,10,11,12,13,14)
check(4)
4,5          |  5,8
4,8          |  5,9
4,9          |  5,10
4,10         |  5,11
4,11         |  5,12
4,12         |  5,13
4,13         |  5,14
4,14         |
При положительном результате (слева) всегда 4 + один из ... ну думаю вы поняли
При отрицательном результате (справа) всегда 5 + один из ...
Модератор: Поправил 21826905
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783310
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну вот, в самом конце опечатка. check(4) должно быть вместо check(7,8,9,10,11,12,13,14)
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783340
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneВторой случай. check(1,2,15)=true, check(1,6)=false
Проверяем 3,4,5,7,8,9,10,11
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
check(3,4,5,7,8,9,10,11)
2,3          |
2,4          |  (2,15) (3,15)
2,5          |  (4,15) (5,15)
2,7          |
2,8          |---check(15)---
2,9          |
2,10         | (2,12) (2,13) (2,14)
2,11         |
При положительном результате (слева) всегда 2 + один из 3,4,5,7,8,9,10,11, который выберем за 3 шага делением пополам.
Еще возможно 15 и один из 3,4,5.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783345
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
21826945 Если первый один из 3,4,5, то нужен 8-й замер чтобы понять где второй: 2 или 15.

В 7 замеров не уложился.
...
Рейтинг: 0 / 0
Пятничный треугольник
    #39783349
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TBarloneВторой случай. check(1,2,15)=true, check(1,6)=false
Проверяем 3,4,5,7,8,9,10,11
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
check(3,4,5,7,8,9,10,11)
2,3          |
2,4          |  (2,15) (3,15)
2,5          |  (4,15) (5,15)
2,7          |
2,8          |---check(15)---
2,9          |
2,10         | (2,12) (2,13) (2,14)
2,11         |
При положительном результате (слева) всегда 2 + один из 3,4,5,7,8,9,10,11, который выберем за 3 шага делением пополам.
Еще возможно 15 и один из 3,4,5.
Упс, косяк, исправляем... check на самом другой, запутался своих в пометках.
Проверяем 12,13,14,15
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
check(12,13,14,15)
2,3          |
2,4          |  (2,15) (3,15)
2,5          |  (4,15) (5,15)
2,7          |
2,8          |---check(15)---
2,9          |
2,10         | (2,12) (2,13) (2,14)
2,11         |
При отрицательном результате слева всегда 2 + один из 3,4,5,7,8,9,10,11, который выберем за 3 шага делением пополам.
...
Рейтинг: 0 / 0
25 сообщений из 188, страница 4 из 8
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничный треугольник
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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