Тема: Zadachka (prosten'kaja) |
SivzevVrazhek
le acteur errants
|
|
elem
notre ami
|
Знаю, что никому не интересно, но всё равно напишу, ибо вредный я и капризный, и клал я на отсутствие интереса...
Итак, задача Номер Раз:
На столе (на полу, на любой поверхности) по кругу лежат 13 монет (то есть, у ряда монет нет начала и конца). Лежат они орлами кверху. А на решках у каждой монеты написана её масса в граммах (или в унциях, если кому-то не пофиг), и нет двух одинаковых по массе монет. Требуется найти алгоритм, с помощью которого можно совершенно точно указать на монету, масса которой больше массы каждой из своих соседок (А < В > С). При этом разрешается перевернуть (чтобы посмотреть на массу) только 6 монет.
Передвигать, менять местами и прочее нельзя. Алгоритм чёткий и точный, без выкрутасов.
|
---------------------- |
Папаша, закурить не найдётся? |
|
|
23 Марта 2007 11:35 |
|
|
elem
notre ami
|
|
PlintuS
le acteur errants
|
|
elem
notre ami
|
|
PlintuS
le acteur errants
|
elem пишет: А Вы - оптимист, батенька!
Я понял,это делается проше,как это делал Арxимед.Взвешиваешь монетку на воздухе.Сила измешения в какои нибудь жидкости,плотность которой известна,например вода - 1000 кг/м 3 равна V=V*ро(вода)*g приравниваешь к ....
Потом допишу,мне на уроки надо
|
|
|
26 Марта 2007 13:38 |
|
|
montag
le acteur errants
|
|
delesha
le acteur errants
|
вот написал, даже уже испробовал. знаю что примитивно, но всё же... (задача Номер Раз):
#include
int main(void)
{
int a, b, c, i=0, ret;
while(i < 13)
{
printf("a:");
scanf("%d", &a);
printf("b:");
scanf("%d", &b);
printf("c:");
scanf("%d", &c);
if(a < b)
ret = b;
else ret = a;
if(ret < c)
ret = c;
else ret = ret;
i++;
printf("ves moneti v grammax: %d n", ret);
}
return 0;
}
|
|
|
26 Марта 2007 15:08 |
|
|
delesha
le acteur errants
|
|
elem
notre ami
|
Цитата из Википедии:
«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.»
То Делеша: Ты это к чему написал?
Ответ скоро будет.
|
---------------------- |
Папаша, закурить не найдётся? |
|
|
26 Марта 2007 17:13 |
|
|
elem
notre ami
|
|
elem
notre ami
|
Решение задачи Номер Раз:
Общий принцип - нужно найти такие 3 монеты,
чтобы средняа была больше каждой из крайних,
а потом постепенно сжимать края.
Итак, у нас есть 13 монет. Обозначим их А Б Ц Д Е Ф Г Х И Й К Л М.
1. Переворачиваем монету А.
2. Переворачиваем монету Ф.
Возможные варианты: А > Ф, Ф > А
Эти варианты симметричны, т.е., нам без разницы,
куда двигаться, налево или направо. (смотри пояснения внизу).
Рассмотрим вариант Ф > А
3. Переворачиваем монету И.
Возможные варианты: А < И > Ф, И < Ф > А
Эти варианты тоже симметричны, поэтому
Рассмотрим вариант И < Ф > А
4. Переворачиваем монету Д.
Возможные варианты: А < Д > Ф, Д < Ф > И
Эти варианты тоже симметричны, поэтому
Рассмотрим вариант А < Д > Ф
5. Переворачиваем монету Ц.
Возможные варианты: А < Ц > Д, Ц < Д > Ф
Эти варианты тоже симметричны, поэтому
Рассмотрим вариант А < Ц > Д
6. Переворачиваем монету Б.
Если Б > Ц, то ответ Б
Если Ц > Б, то ответ Ц
Пояснения:
Если в самом начале получается, что А > Ф,
то мы просто идём в другом направлении, т.е.,
переворачиваем монету К.
|
---------------------- |
Папаша, закурить не найдётся? |
|
|
26 Марта 2007 17:39 |
|
|
elem
notre ami
|
Решение задачи Номер Два:
Итак, у нас есть 13 монет. Обозначим их А Б Ц Д Е Ф Г Х И Й К Л М.
1. Взвешиваем (сравниваем) монеты АБЦД и ЕФГХ.
Если АБЦД (или ЕФГХ - без разницы) перевесили то смотри пункт 2.1
Если весы оказались уравновешены, то смотри пункт 2.2
2.1 Мы знаем теперь, что фальшивая монета находиться среди этих 8-и монет.
Если она тяжелее настоящей, то она среди АБЦД, если легче, то среди ЕФГХ.
Сравниваем монеты АБЕ и ЦДФ.
Если АБЕ перевесили то фальшивая монета среди АБФ (либо А/Б тяжелее, либо Ф легче).
3.1 Сравниваем монеты А и Б.
Кто из них перевесил, тот и "выиграл". Если они равны, значит Ф - фальшивая.
Теперь рассмотрим другой вариант...
Мы знаем, что монеты АБЦДЕФГХ - настоящие.
Будем обозначать их звёздочкой *
2.2 Сравниваем монеты ИЙК и ***.
Если они равны, то перэодим к ЛМ (пункт 3.2.2).
Если ИЙК перевесили, то фальшивая монета среди них и она тяжелее настоящих (пункт 3.2.1).
3.2.1 Сравниваем И и Й
если равны, то ответ К, либо та, которая тяжелее.
3.2.2 Сравниваем Л и *
если равны, то ответ М, если нет, то Л.
Пояснения:
Если какая-то кучка монет не тяжелее, а легче, то задача решается аналогичо, поэтому я и не рассматривал абсолютно все варианты (я и так уже слегка одурел от этой писанины).
Если кого-то интересуют ответы на более ранние задачи - свистите.
|
---------------------- |
Папаша, закурить не найдётся? |
|
|
27 Марта 2007 10:10 |
|
|
montag
le acteur errants
|
[quote=delesha] инт а, б, ц, и=0, рет;
вхиле(и < 13)
{
принтф("а:");
сцанф("%д", &а);
принтф("б:");
[quote]
Сказали же- без выкрутасов.
|
|
|
27 Марта 2007 13:07 |
|
|
elem
notre ami
|
|
asde
le concierge
|
|
elem
notre ami
|
asde пишет: ...96
Браво!
Ты с помощью интегралов считал или подбором?
|
---------------------- |
Папаша, закурить не найдётся? |
|
|
22 Июня 2007 10:21 |
|
|
eklmn
Бывший океанец
|
|
asde
le concierge
|
|
eklmn
Бывший океанец
|
|