Логин:Пароль:
FAQ по форумуНовые сообщения на Форуме
  • Страница 4 из 6
  • «
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • »
Форум Эрудитов » Логические задачи и головоломки » Математические задачи » Монеты (sml[theme])
Монеты
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
Высший разум
Сообщений: 3636
Награды: 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
Мудрец
Сообщений: 1488
Награды: 241
Совы: 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
Мудрец
Сообщений: 1488
Награды: 241
Совы: 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
Мудрец
Сообщений: 1488
Награды: 241
Совы: 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
 
Форум Эрудитов » Логические задачи и головоломки » Математические задачи » Монеты (sml[theme])
  • Страница 4 из 6
  • «
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • »
Поиск:

Интересная информация
Последние задачи Сообщество эрудитов ВКонтакте Рейтинг сообщений Совиный рейтинг
1.Цифра)))2
2.Бессмысленное и загадочно...9
3.Помощь с решением задачи1
4.Помогите решить ребус1
5.О времена, о нравы ...10
6.Случайная хорда3
7.Лучше9
8.Акула12
9.6 ребусов3
10.Головоломка без ключа1
1.Rostislav5379
2.Lexx4728
3.nebo3636
4.Иван3061
5.никник2735
6.Kreativshik2472
7.Гретхен1807
8.Vita1488
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Обратная связьКоллегиФорум Эрудитов