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

Откуда: Москва
Сообщений: 1730
Barlone,

терзают смутные сомнения, что для решения не всегда требуется делить пополам,
или что невозможно проскочить "плохой" уровень при поиске решения.
7 мар 19, 15:14    [21827419]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1137
kealon(Ruslan)
а вот конкретно для вашего алгоритма видно из примера, что формула log2(C(N,K)) к нему не подходит, он её не имплементирует
21827282
7 мар 19, 15:30    [21827449]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1137
Aleksandr Sharahov
Barlone,

терзают смутные сомнения, что для решения не всегда требуется делить пополам,
или что невозможно проскочить "плохой" уровень при поиске решения.
Проскочить? Можно ли одной проверкой, дающей ответ да/нет, найти один из трех шаров? У нас в результате одной проверки есть только два варианта, невозможно выдать один из трех разных ответов после одного теста. А после x тестов возможно только 2x вариантов ответа, их негде взять больше.
7 мар 19, 15:41    [21827473]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Dima T
Member

Откуда:
Сообщений: 13348
Barlone
Aleksandr Sharahov
Barlone,

терзают смутные сомнения, что для решения не всегда требуется делить пополам,
или что невозможно проскочить "плохой" уровень при поиске решения.
Проскочить? Можно ли одной проверкой, дающей ответ да/нет, найти один из трех шаров? У нас в результате одной проверки есть только два варианта, невозможно выдать один из трех разных ответов после одного теста. А после x тестов возможно только 2x вариантов ответа, их негде взять больше.

Для 14 шаров предлагали вариант с первым делением 4,4,4,2 21824574
7 мар 19, 15:45    [21827478]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1137
А насчет "пополам" - вот приведенный здесь алгоритм поиска 2 из 15 на первом шаге проверяя пять шаров, делит 105 вариантов на 60+45. Если проверять четыре шара, можно поделить на 50+55. Казалось бы, ближе к "пополам", но нет, эти 55 вариантов (а это найти 2 из 11) за 6 шагов не разделить.
7 мар 19, 15:50    [21827486]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1137
Dima T
Для 14 шаров предлагали вариант с первым делением 4,4,4,2 21824574
Так это 3 проверки, после них мы уже как-то разделили все возможные варианты пар (91) на 8 кучек. Получилось достаточно хорошо, в каждой кучке не больше 16 вариантов, чтобы за 4 оставшихся проверки найти единственный.
7 мар 19, 15:57    [21827495]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Barlone,

я как раз об этом
7 мар 19, 15:57    [21827496]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Aleksandr Sharahov
Barlone,

я как раз об этом


21827486
7 мар 19, 15:59    [21827501]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1137
Aleksandr Sharahov
Barlone,

я как раз об этом
О чем конкретно?
7 мар 19, 15:59    [21827505]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1137
А. Ну да, это же понятно, необязательно точно пополам, но каждая часть не должна превосходить соответствующую степень двойки.
7 мар 19, 16:01    [21827507]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Barlone
Aleksandr Sharahov
Barlone,

терзают смутные сомнения, что для решения не всегда требуется делить пополам,
или что невозможно проскочить "плохой" уровень при поиске решения.
Проскочить? Можно ли одной проверкой, дающей ответ да/нет, найти один из трех шаров? У нас в результате одной проверки есть только два варианта, невозможно выдать один из трех разных ответов после одного теста. А после x тестов возможно только 2x вариантов ответа, их негде взять больше.


У меня мысль в некотором роде обратная.

Из того, что по завершении совокупности x тестов мы должны
хотим найти 2 шара или даже из того, что хотим получить разбиение множества
на 2x примерно равных частей никак не следует, что каждый тест
последовательно делит множество на равные части.
7 мар 19, 16:53    [21827556]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
да, "деление" неподходящий термин
назовём "метод откусывания"
я так понимаю, что можно и снизу найти коэффициенты откусывания перебором

алгоритм бы только состряпать

путь функция откусывания Z(K, N), наша целевая функция F(K,N)

для упрощения возьмём случай K<=2

F(2, N) = 1 + Max[
F(2, N - Z(N)) - в откусанном кусочке нет ничего
... - в откусанном кусочке что-то есть вот тут как поступить пока непонятно
]

известные коэффициенты снизу:
F(2,2) = 0, Z(0,2) = 0
F(1,2) = 1, Z(1,2) = 1
F(0,2) = 0, Z(0,2) = 0

F(2,3) = 2, Z(2,3) = 1
F(1,3) = 2, Z(1,3) = 1
F(0,3) = 0, Z(0,3) = 0
7 мар 19, 18:05    [21827631]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
Вы пока с этим разбиритесь, а я, коль пошла такая пьянка, вернусь вопросу с пересечением медиан. Все 100, что в шлоле я такое делал, сейчас уже не вспомнить.
Насчёт типового метода, о к-ром пишет Соколинский - наверняка это различные векторные равенства, других типовых не вспоминается.
Только мне кажется, что здесь можно без векторных уравнений.
Никогда не любил формулу Герона для площади тр-ка и не знаю как доказывается.
Пусть М - т. пересечения медиан. Берём один тр-к АМВ и угол при М.
Площадь = АМ*ВМ*Sin(М)/2 = здесь ф-ла Герона
Получили 2 неизвестных угол М и АВ
По теореме косинусов (ну или через разность векторов) АВ^2= m1^2 + m2^2 - 2*m1*m2*Cos(М)

Получили 2 ур-ния с 2-мя неизвечстными. Может они и тавтология, я не пробовал.
7 мар 19, 18:06    [21827633]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
Тут, кстати, 3-й угол считать необязательно,т.к. сумма 3-х=365град)
да, выше m1= АМ, m2=ВМ
7 мар 19, 18:11    [21827637]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
Трехмедианная задача - прекрасна. В ней что-то есть от начертательных
задач где есть циркуль и линейка и больше ничего.
7 мар 19, 18:18    [21827640]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
mayton, так её надо решить циркулем? "сомневаюсь я"(С)
7 мар 19, 18:23    [21827643]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
Нет конешно. Не надо. Я просто подчеркиваю ее простоту и в то-же время подкапотную глубину постановки.
7 мар 19, 18:28    [21827646]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1137
Aleksandr Sharahov

У меня мысль в некотором роде обратная.

Из того, что по завершении совокупности x тестов мы должны
хотим найти 2 шара или даже из того, что хотим получить разбиение множества
на 2x примерно равных частей никак не следует, что каждый тест
последовательно делит множество на равные части.
Ну как же, каждый тест так или иначе множество делит - часть возможных пар под условие теста попадает, часть нет.
7 мар 19, 19:16    [21827670]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Barlone
Aleksandr Sharahov
У меня мысль в некотором роде обратная.

Из того, что по завершении совокупности x тестов мы должны
хотим найти 2 шара или даже из того, что хотим получить разбиение множества
на 2x примерно равных частей никак не следует, что каждый тест
последовательно делит множество на равные части.
Ну как же, каждый тест так или иначе множество делит - часть возможных пар под условие теста попадает, часть нет.


Да, делит.
Но множества-то разные.
Могут содержать шары:
- ровно 2,
- ровно 1,
- ровно 0,
- от 1 до 2,
- от 0 до 1,
- от 0 до 2.
Почему они обязаны быть равными по размеру?
7 мар 19, 19:43    [21827687]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
Barlone
Member

Откуда:
Сообщений: 1137
Aleksandr Sharahov
Да, делит.
Но множества-то разные.
Могут содержать шары:
- ровно 2,
- ровно 1,
- ровно 0,
- от 1 до 2,
- от 0 до 1,
- от 0 до 2.
Почему они обязаны быть равными по размеру?
Не о тех множествах речь была.
7 мар 19, 20:09    [21827694]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
Barlone, миль пардон, а о каких тогда?
7 мар 19, 20:30    [21827704]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
В алгоритм 15 не вникал. Но хочу похвалить Барлона за вдумчивость, к-рую лично я упустил. Если правильно понимаю, то среди прочего в методе есть идея: после первого разбиения на 2 мн-ва (а наверное и в далнейшем тоже) не обязательно безусловно проводить 2 проверки, как я к примеру. После поверки одного мн-ва принимается решение проверять второе или дробить его на части и уж потом ....
Я правильно понял этот приём?
7 мар 19, 20:36    [21827709]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
А моя нечеткая логика? Не взлетит?
7 мар 19, 20:50    [21827719]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
exp98
Member

Откуда:
Сообщений: 1609
неч.логика для оценочной формулы или что иное?
Для оценки я бы подумал (не в смысле буквально думать).
7 мар 19, 21:10    [21827727]     Ответить | Цитировать Сообщить модератору
 Re: Пятничный треугольник  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
Ну это как томограф. Посмотрели на одномерную тень. Повернули наблюдаемый объект.
Посмотрели еще раз на тень. Повернули.

А потом - раз. И получили двумерный срез наблюдаемого объекта. Как колбасу срезали.

Вот я и думаю. Нечётким зрением посмотреть на шары. Только не на 14 шаров. А на 14 тысяч
например. Как-то так.
7 мар 19, 21:14    [21827730]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 [6] 7 8   вперед  Ctrl      все
Все форумы / Программирование Ответить