|
Монеты
|
|
| Race | Дата: Ср, 21.02.18, 17:53 | Сообщение # 31 |
Просветленный  Сообщений: 459
| Я уже не знаю как расписать подробнее.
Делим девять монет на 3группы по 3 монеты в каждой. Называем группы А, В и С.
1-3 взвешивание
А>B>C
Дальше рассматриваем среднюю группу - В.
В ней возможно всего 3 комбинации монет
ттл => настоящая в тяжелой группе
тнл => настоящая в средней группе
тлл => настоящая в легкой группе.
в средней группе обзываем монеты 1,2 3, производим взвешивания:
1<2 1<3 2=3 =>настоящая монета в тяжелой группе
1<2 1<3 2<3 => настоящая монета в средней группе, это монета № 2.
1>2 1>3 2=3 => настоящая монета в легкой группе
Других комбинаций просто не может быть.
|
| |
| |
| nebo | Дата: Ср, 21.02.18, 18:29 | Сообщение # 32 |
Высший разум  Сообщений: 3639
| Вот теперь, наконец-то, Вы объяснили абсолютно понятно.
|
| |
| |
| zhekas | Дата: Ср, 21.02.18, 18:37 | Сообщение # 33 |
Гуру  Сообщений: 166
Совы: 6 
| Цитата Race (  ) 1<2 1<3 2<3 => настоящая монета в средней группе, это монета № 2.
В условии не сказано что легкие фальшивые как и тяжелые фальшивые весят одинаково
|
| |
| |
| Race | Дата: Ср, 21.02.18, 19:03 | Сообщение # 34 |
Просветленный Сообщений: 459
| zhekas,
это решение только для л=л=л=л и т=т=т=т.
Сообщение отредактировал Race - Ср, 21.02.18, 19:05 |
| |
| |
| Vita | Дата: Ср, 21.02.18, 19:04 | Сообщение # 35 |
Гений  Сообщений: 1524
| Race, 
Всё таки стоит поискать варианты оптимальнее. ИМХО.
Тем более если все фальшивые монеты разного веса. Т.е. мы должны упорядочить набор из 9 монет по весу.
Сообщение отредактировал Vita - Ср, 21.02.18, 19:15 |
| |
| |
| Race | Дата: Ср, 21.02.18, 19:21 | Сообщение # 36 |
Просветленный Сообщений: 459
| Цитата Vita ( ) Всё таки стоит поискать варианты оптимальнее. ИМХО.Тем более если все фальшивые монеты разного веса. Т.е. мы должны упорядочить набор из 9 монет по весу.
Имеется 9 предметов разного веса, требуется найти предмет X, такой что A<B<C<D<X<E<F<G<J.
1+2+...+8=(1+8)*8/2=36 но это максимальное кол-во взвешиваний, осталось каким либо образом оптимизировать.
Сообщение отредактировал Race - Ср, 21.02.18, 19:23 |
| |
| |
| Vita | Дата: Ср, 21.02.18, 19:28 | Сообщение # 37 |
Гений Сообщений: 1524
| нам нужно только 5 с любой стороны, но исключено ли равенство?
а я ещё подумала, почему в разделе математика такая задача...точно не решу!
Сообщение отредактировал Vita - Ср, 21.02.18, 19:41 |
| |
| |
| Race | Дата: Ср, 21.02.18, 19:40 | Сообщение # 38 |
Просветленный Сообщений: 459
| Равенство не исключено, в его случае ставим монеты рядом.
У меня получилось:
1+2+2+3+3+3+3+2=19 и это наверное не предел.
1|1 1
11|1 2
111|1 2
1111|1 3
11111|1 3
111111|1 3
1111111|1 3
11111111|1 2
Сообщение отредактировал Race - Ср, 21.02.18, 20:03 |
| |
| |
| Vita | Дата: Ср, 21.02.18, 20:33 | Сообщение # 39 |
Гений Сообщений: 1524
| Race, кажется сейчас учат в школе на информатике способы оптиматьной сортировки матрицы
Сортировка пузырьком (англ. Bubble sort) — для каждой пары индексов производится обмен, если элементы расположены не по порядку. Сложность алгоритма: {\displaystyle O(n^{2})} .Сортировка перемешиванием (англ. Cocktail sort). Сложность алгоритма: {\displaystyle O(n^{2})}.Сортировка вставками (Insertion sort) — определяем, где текущий элемент должен находиться в упорядоченном списке, и вставляем его туда. Сложность алгоритма: {\displaystyle O(n^{2})}.Гномья сортировка (Gnome sort; первоначально опубликована под названием «глупая сортировка» [stupid sort] за простоту реализации) — сходна с сортировкой вставками. Сложность алгоритма — {\displaystyle O(n^{2})}; рекурсивная версия требует дополнительно {\displaystyle O(n^{2})} памяти.Сортировка слиянием (Merge sort) — выстраиваем первую и вторую половину списка отдельно, а затем объединяем упорядоченные списки. Сложность алгоритма: {\displaystyle O(n\log n)} . Требуется {\displaystyle O(n)} дополнительной памяти.Сортировка с помощью двоичного дерева (англ. Tree sort). Сложность алгоритма: {\displaystyle O(n\log n)}. Требуется {\displaystyle O(n)} дополнительной памяти.Сортировка Timsort (англ. Timsort) — комбинированный алгоритм (используется сортировка вставками и сортировка слиянием). Сложность алгоритма: {\displaystyle O(n\log n)}. Требуется {\displaystyle O(n)} дополнительной памяти. Разработан для использования в языке Python[14].Сортировка подсчётом (Counting sort). Сложность алгоритма: {\displaystyle O(n+k)} . Требуется {\displaystyle O(n+k)} дополнительной памяти.Блочная сортировка (Корзинная сортировка, Bucket sort) — требуется {\displaystyle O(k)} дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций «переставить» и «сравнить». Сложность алгоритма: {\displaystyle O(n)}.Поразрядная сортировка (она же цифровая сортировка, Radix sort) — сложность алгоритма: {\displaystyle O(nk)} ; требуется {\displaystyle O(k)} дополнительной памяти.
Только я не уверена, что поняла задачу.
Сообщение отредактировал Vita - Ср, 21.02.18, 20:35 |
| |
| |
| Race | Дата: Чт, 22.02.18, 09:33 | Сообщение # 40 |
Просветленный Сообщений: 459
| Vita,
ну там явно без сто грамм не разберешься)))
Сейчас попробую графически изобразить, получается пирамида.
2| 1111111111
2| 11111111111
3| 111111111111
3| 1111111111111
3| 11111111111111.
2| 111111111111111
2| 1111111111111111
1| 11111111111111111
Вот что получилось:
1. Идем снизу вверх.
2. Синие предметы это потенциальное расположение не отсортированых
3. Красные максимально необходимое кол-во взвешиваемй для сортировки, учитывая что мы ищем именно 5й по весу предмет, считая от самого тяжелого или самого легкого.
4. Фиолетовые - предметы которые можно не сравнивать, так как они точно не могут быть 5м предметом.
5. Черные - предметы которые выбывают из взвешивания.
Алгоритм: когда отсортировано 3 и выше предмета, то взвешиваем сначала средний по положению, в итоге (n-1)/2 предметов нет необходимости взвешивать (если средний предмет делит правую или левую часть на 3 и больше предметов, то действуем так же, в итоге выигрываем еще немного взвешиваний, некое (m-1)/2, в нашем случае не пригодилось, так как оказалось выгоднее не взвешивать предметы которые потенциально не могут быть искомым), для n=2k, я всегда учитывал наиболее неблагоприятное распределение.
Итого имеем:
1+2+2+3+3+3+2+2=18 взвешиваний.
Если все легкие и тяжелые могут иметь разный вес, то другого варианта у меня не получилось найти.Добавлено (22.02.2018, 09:33)
---------------------------------------------
11111111X11111111
1111111XX1111111
111111XXO111111
11111XXXO11111
1111XXXOO1111
111ZXXXOZ111
11ZZXXOZZ11
1ZZZXXZZZ1
Вот так в ч/б. Может будет более наглядно.
1 - потенциальное расположение взвешенных предметов.
Х - взвешивание для распределения предметов
О - предметы которые нет необходимости взвешивать
Z - предметы которые не могут быть 5м предметом.
Сообщение отредактировал Race - Чт, 22.02.18, 09:27 |
| |
| |
