|
|
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Barlone, терзают смутные сомнения, что для решения не всегда требуется делить пополам, или что невозможно проскочить "плохой" уровень при поиске решения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 15:14 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)а вот конкретно для вашего алгоритма видно из примера, что формула log2(C(N,K)) к нему не подходит, он её не имплементирует 21827282 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 15:30 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Aleksandr SharahovBarlone, терзают смутные сомнения, что для решения не всегда требуется делить пополам, или что невозможно проскочить "плохой" уровень при поиске решения.Проскочить? Можно ли одной проверкой, дающей ответ да/нет, найти один из трех шаров? У нас в результате одной проверки есть только два варианта, невозможно выдать один из трех разных ответов после одного теста. А после x тестов возможно только 2 x вариантов ответа, их негде взять больше. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 15:41 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
BarloneAleksandr SharahovBarlone, терзают смутные сомнения, что для решения не всегда требуется делить пополам, или что невозможно проскочить "плохой" уровень при поиске решения.Проскочить? Можно ли одной проверкой, дающей ответ да/нет, найти один из трех шаров? У нас в результате одной проверки есть только два варианта, невозможно выдать один из трех разных ответов после одного теста. А после x тестов возможно только 2 x вариантов ответа, их негде взять больше. Для 14 шаров предлагали вариант с первым делением 4,4,4,2 21824574 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 15:45 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
А насчет "пополам" - вот приведенный здесь алгоритм поиска 2 из 15 на первом шаге проверяя пять шаров, делит 105 вариантов на 60+45. Если проверять четыре шара, можно поделить на 50+55. Казалось бы, ближе к "пополам", но нет, эти 55 вариантов (а это найти 2 из 11) за 6 шагов не разделить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 15:50 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Dima TДля 14 шаров предлагали вариант с первым делением 4,4,4,2 21824574 Так это 3 проверки, после них мы уже как-то разделили все возможные варианты пар (91) на 8 кучек. Получилось достаточно хорошо, в каждой кучке не больше 16 вариантов, чтобы за 4 оставшихся проверки найти единственный. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 15:57 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Barlone, я как раз об этом ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 15:57 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Aleksandr SharahovBarlone, я как раз об этомО чем конкретно? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 15:59 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
А. Ну да, это же понятно, необязательно точно пополам, но каждая часть не должна превосходить соответствующую степень двойки. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 16:01 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
BarloneAleksandr SharahovBarlone, терзают смутные сомнения, что для решения не всегда требуется делить пополам, или что невозможно проскочить "плохой" уровень при поиске решения.Проскочить? Можно ли одной проверкой, дающей ответ да/нет, найти один из трех шаров? У нас в результате одной проверки есть только два варианта, невозможно выдать один из трех разных ответов после одного теста. А после x тестов возможно только 2 x вариантов ответа, их негде взять больше. У меня мысль в некотором роде обратная. Из того, что по завершении совокупности x тестов мы должны хотим найти 2 шара или даже из того, что хотим получить разбиение множества на 2 x примерно равных частей никак не следует, что каждый тест последовательно делит множество на равные части. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 16:53 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
да, "деление" неподходящий термин назовём "метод откусывания" я так понимаю, что можно и снизу найти коэффициенты откусывания перебором алгоритм бы только состряпать путь функция откусывания 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 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 18:05 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Вы пока с этим разбиритесь, а я, коль пошла такая пьянка, вернусь вопросу с пересечением медиан. Все 100, что в шлоле я такое делал, сейчас уже не вспомнить. Насчёт типового метода, о к-ром пишет Соколинский - наверняка это различные векторные равенства, других типовых не вспоминается. Только мне кажется, что здесь можно без векторных уравнений. Никогда не любил формулу Герона для площади тр-ка и не знаю как доказывается. Пусть М - т. пересечения медиан. Берём один тр-к АМВ и угол при М. Площадь = АМ*ВМ*Sin(М)/2 = здесь ф-ла Герона Получили 2 неизвестных угол М и АВ По теореме косинусов (ну или через разность векторов) АВ^2= m1^2 + m2^2 - 2*m1*m2*Cos(М) Получили 2 ур-ния с 2-мя неизвечстными. Может они и тавтология, я не пробовал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 18:06 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Тут, кстати, 3-й угол считать необязательно,т.к. сумма 3-х=365град) да, выше m1= АМ, m2=ВМ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 18:11 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Трехмедианная задача - прекрасна. В ней что-то есть от начертательных задач где есть циркуль и линейка и больше ничего. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 18:18 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
mayton, так её надо решить циркулем? "сомневаюсь я"(С) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 18:23 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Нет конешно. Не надо. Я просто подчеркиваю ее простоту и в то-же время подкапотную глубину постановки. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 18:28 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov У меня мысль в некотором роде обратная. Из того, что по завершении совокупности x тестов мы должны хотим найти 2 шара или даже из того, что хотим получить разбиение множества на 2 x примерно равных частей никак не следует, что каждый тест последовательно делит множество на равные части.Ну как же, каждый тест так или иначе множество делит - часть возможных пар под условие теста попадает, часть нет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 19:16 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
BarloneAleksandr SharahovУ меня мысль в некотором роде обратная. Из того, что по завершении совокупности x тестов мы должны хотим найти 2 шара или даже из того, что хотим получить разбиение множества на 2 x примерно равных частей никак не следует, что каждый тест последовательно делит множество на равные части.Ну как же, каждый тест так или иначе множество делит - часть возможных пар под условие теста попадает, часть нет. Да, делит. Но множества-то разные. Могут содержать шары: - ровно 2, - ровно 1, - ровно 0, - от 1 до 2, - от 0 до 1, - от 0 до 2. Почему они обязаны быть равными по размеру? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 19:43 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Aleksandr SharahovДа, делит. Но множества-то разные. Могут содержать шары: - ровно 2, - ровно 1, - ровно 0, - от 1 до 2, - от 0 до 1, - от 0 до 2. Почему они обязаны быть равными по размеру?Не о тех множествах речь была. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 20:09 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Barlone, миль пардон, а о каких тогда? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 20:30 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
В алгоритм 15 не вникал. Но хочу похвалить Барлона за вдумчивость, к-рую лично я упустил. Если правильно понимаю, то среди прочего в методе есть идея: после первого разбиения на 2 мн-ва (а наверное и в далнейшем тоже) не обязательно безусловно проводить 2 проверки, как я к примеру. После поверки одного мн-ва принимается решение проверять второе или дробить его на части и уж потом .... Я правильно понял этот приём? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 20:36 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
А моя нечеткая логика? Не взлетит? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 20:50 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
неч.логика для оценочной формулы или что иное? Для оценки я бы подумал (не в смысле буквально думать). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 21:10 |
|
||
|
Пятничный треугольник
|
|||
|---|---|---|---|
|
#18+
Ну это как томограф. Посмотрели на одномерную тень. Повернули наблюдаемый объект. Посмотрели еще раз на тень. Повернули. А потом - раз. И получили двумерный срез наблюдаемого объекта. Как колбасу срезали. Вот я и думаю. Нечётким зрением посмотреть на шары. Только не на 14 шаров. А на 14 тысяч например. Как-то так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.03.2019, 21:14 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=39783761&tid=1339982]: |
0ms |
get settings: |
11ms |
get forum list: |
12ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
158ms |
get topic data: |
12ms |
get forum data: |
3ms |
get page messages: |
68ms |
get tp. blocked users: |
2ms |
| others: | 278ms |
| total: | 552ms |
| 0 / 0 |
