FAQ по форумуНовые сообщения на Форуме
  • Страница 4 из 6
  • «
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • »
Монеты
RaceДата: Ср, 21.02.18, 17:53 | Сообщение # 31
Просветленный
Сообщений: 459
Награды: 41
Совы: 12
Я уже не знаю как расписать подробнее.
Делим девять монет на 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
Награды: 350
Совы: 123
Вот теперь, наконец-то, Вы объяснили абсолютно понятно.
 
zhekasДата: Ср, 21.02.18, 18:37 | Сообщение # 33
Гуру
Сообщений: 166
Награды: 43
Совы: 6
Цитата Race ()
1<2 1<3 2<3 => настоящая монета в средней группе, это монета № 2.

В условии не сказано что легкие фальшивые  как и тяжелые фальшивые весят одинаково
 
RaceДата: Ср, 21.02.18, 19:03 | Сообщение # 34
Просветленный
Сообщений: 459
Награды: 41
Совы: 12
zhekas,
это решение только для л=л=л=л и т=т=т=т.


Сообщение отредактировал Race - Ср, 21.02.18, 19:05
 
VitaДата: Ср, 21.02.18, 19:04 | Сообщение # 35
Гений
Сообщений: 1578
Награды: 248
Совы: 13
Race, bravo
Всё таки стоит поискать варианты оптимальнее. ИМХО.
Тем более если все фальшивые монеты разного веса. Т.е. мы должны упорядочить набор из 9 монет по весу.


Вечность состоит из отчетных периодов


Сообщение отредактировал Vita - Ср, 21.02.18, 19:15
 
RaceДата: Ср, 21.02.18, 19:21 | Сообщение # 36
Просветленный
Сообщений: 459
Награды: 41
Совы: 12
Цитата Vita ()
Всё таки стоит поискать варианты оптимальнее. ИМХО.Тем более если все фальшивые монеты разного веса. Т.е. мы должны упорядочить набор из 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
 
VitaДата: Ср, 21.02.18, 19:28 | Сообщение # 37
Гений
Сообщений: 1578
Награды: 248
Совы: 13
нам нужно только 5 с любой стороны, но исключено ли равенство?
а я ещё подумала, почему в разделе математика такая задача...точно не решу!


Вечность состоит из отчетных периодов


Сообщение отредактировал Vita - Ср, 21.02.18, 19:41
 
RaceДата: Ср, 21.02.18, 19:40 | Сообщение # 38
Просветленный
Сообщений: 459
Награды: 41
Совы: 12
Равенство не исключено, в его случае ставим монеты рядом.
У меня получилось:
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
Гений
Сообщений: 1578
Награды: 248
Совы: 13
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
Награды: 41
Совы: 12
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
 
  • Страница 4 из 6
  • «
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • »
Поиск:

Интересная информация
Последние задачи Сообщество эрудитов ВКонтакте Рейтинг сообщений Совиный рейтинг
1.Арнольд, да не тот77
2.Простенький вопросик9
3.Гидродинамика14
4.Быстрая река.24
5.А попробуйте ещё это опро...6
6.Задача по логике7
7.Головоломка без ключа2
8.Задача о парадоксе Петров...11
9.Напрасно ли ожидание7
10.Чудо-Юдо и три головы12
1.Rostislav5379
2.Lexx4728
3.nebo3639
4.Иван3061
5.никник2770
6.Kreativshik2472
7.Гретхен1807
8.Vita1578
9.erudite-man1378
10.Valet937
1.nebo123
2.Kreativshik113
3.sovetnik49
4.MrCredo38
5.IQFun30
6.Pro100_Artyom27
7.marutand20
8.хан20
9.никник15
10.Фигаро15

ГлавнаяГостевая книгаFAQОбратная связьКоллегиФорум Эрудитов