Логин:Пароль:
FAQ по форумуНовые сообщения на Форуме
  • Страница 4 из 6
  • «
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • »
Форум Эрудитов » Логические задачи и головоломки » Математические задачи » Монеты (sml[theme])
Монеты
RaceДата: Среда, 21.02.2018, 17:53 | Сообщение # 31
Гуру
Сообщений: 444
Награды: 35
Совы: 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.2018, 18:29 | Сообщение # 32
Высший разум
Сообщений: 3487
Награды: 323
Совы: 115
Вот теперь, наконец-то, Вы объяснили абсолютно понятно.
 
zhekasДата: Среда, 21.02.2018, 18:37 | Сообщение # 33
Гуру
Сообщений: 166
Награды: 43
Совы: 6
Цитата Race ()
1<2 1<3 2<3 => настоящая монета в средней группе, это монета № 2.

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


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


Сообщение отредактировал Vita - Среда, 21.02.2018, 19:15
 
RaceДата: Среда, 21.02.2018, 19:21 | Сообщение # 36
Гуру
Сообщений: 444
Награды: 35
Совы: 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.2018, 19:23
 
VitaДата: Среда, 21.02.2018, 19:28 | Сообщение # 37
Мыслитель
Сообщений: 961
Награды: 176
Совы: 10
нам нужно только 5 с любой стороны, но исключено ли равенство?
а я ещё подумала, почему в разделе математика такая задача...точно не решу!


Сообщение отредактировал Vita - Среда, 21.02.2018, 19:41
 
RaceДата: Среда, 21.02.2018, 19:40 | Сообщение # 38
Гуру
Сообщений: 444
Награды: 35
Совы: 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.2018, 20:03
 
VitaДата: Среда, 21.02.2018, 20:33 | Сообщение # 39
Мыслитель
Сообщений: 961
Награды: 176
Совы: 10
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.2018, 20:35
 
RaceДата: Четверг, 22.02.2018, 09:33 | Сообщение # 40
Гуру
Сообщений: 444
Награды: 35
Совы: 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.2018, 09:27
 
Форум Эрудитов » Логические задачи и головоломки » Математические задачи » Монеты (sml[theme])
  • Страница 4 из 6
  • «
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • »
Поиск:

Интересная информация
Последние задачи Сообщество эрудитов ВКонтакте Рейтинг сообщений Совиный рейтинг
1.Утомление от позирования4
2.Секретный ингредиент5
3.Гомеоморфизм.4
4.Забугорный сайт с решенем...0
5.задачки на смекалку6
6.Конем ходи)5
7.Антифразы65
8.ПОМОГИТЕ РЕШИТЬ РЕБУС17
9.Театр одного зрителя3
10.Сигнал для управления7
1.Rostislav4885
2.Lexx4728
3.nebo3487
4.Иван3061
5.Kreativshik2472
6.никник2271
7.Гретхен1807
8.erudite-man1335
9.Vita961
10.Valet937
1.nebo115
2.Kreativshik113
3.sovetnik49
4.IQFun30
5.Pro100_Artyom27
6.MrCredo26
7.marutand20
8.хан20
9.slltllnll12
10.никник12


ГлавнаяГостевая книгаFAQНаписать админуКоллегиФорум ЭрудитовХостинг от uCoz