Логин:Пароль:
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
Высший разум
Сообщений: 3484
Награды: 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
Мыслитель
Сообщений: 921
Награды: 164
Совы: 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
Мыслитель
Сообщений: 921
Награды: 164
Совы: 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
Мыслитель
Сообщений: 921
Награды: 164
Совы: 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.Конем ходи)2
2.ОНИ тремя словами3
3.Два персонажа5
4.задачки на смекалку5
5.ПОМОГИТЕ РЕШИТЬ РЕБУС17
6.Театр одного зрителя3
7.Сигнал для управления7
8.Простой парадокс35
9.Можно ли на 4-м ходу парт...2
10.Антифразы54
1.Rostislav4848
2.Lexx4728
3.nebo3484
4.Иван3061
5.Kreativshik2472
6.никник2258
7.Гретхен1802
8.erudite-man1323
9.Valet937
10.Vita921
1.nebo115
2.Kreativshik113
3.sovetnik49
4.IQFun30
5.Pro100_Artyom27
6.MrCredo26
7.marutand20
8.хан20
9.slltllnll12
10.никник12


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