Я уже не знаю как расписать подробнее. Делим девять монет на 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 => настоящая монета в легкой группе
Race, Всё таки стоит поискать варианты оптимальнее. ИМХО. Тем более если все фальшивые монеты разного веса. Т.е. мы должны упорядочить набор из 9 монет по весу.
Сообщение отредактировал Vita - Ср, 21.02.18, 19:15
Всё таки стоит поискать варианты оптимальнее. ИМХО.Тем более если все фальшивые монеты разного веса. Т.е. мы должны упорядочить набор из 9 монет по весу.
Да... zhekas прав, похоже мы решали совсем не ту задачу. Имеется 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
Равенство не исключено, в его случае ставим монеты рядом. У меня получилось: 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
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
Вот что получилось: 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 взвешиваний. Если все легкие и тяжелые могут иметь разный вес, то другого варианта у меня не получилось найти.
Вот так в ч/б. Может будет более наглядно. 1 - потенциальное расположение взвешенных предметов. Х - взвешивание для распределения предметов О - предметы которые нет необходимости взвешивать Z - предметы которые не могут быть 5м предметом.
Сообщение отредактировал Race - Чт, 22.02.18, 09:27
.
. Требуется {\displaystyle O(n)}
дополнительной памяти.
. Требуется {\displaystyle O(n+k)}
дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций «переставить» и «сравнить». Сложность алгоритма: {\displaystyle O(n)}
; требуется {\displaystyle O(k)}
