Просмотр полной версии : Кто решает эту задачу за 2 часа принимаются на Лондонскую биржу
Есть 12 шаров, 11 одинаковых, 12-й либо тяжелее, либо легче (это неизвестно)
Есть весы, которые бывают в 3-х положениях "больше", "меньше" и "поровну"
Есть 3 взвешивания, которые можно сделать
Необходимо определить какой из шаров - имеет аномальную массу
12 шаров в 2 кучи=1 куча тяжелей
берем тяжелую кучу
и взвешиваем по 2, пока один из них не окажется тяжелей...
шар может быть и легче
если бы только тяжелее- все проще
тут неизвестно тяжелее или легче 12 шар
Решил задачу в 4 взвешивания. 4ыйбыл нужен для проверки. Три это очень мало
MuXaJIbI4
06.03.2009, 18:34
1. делим 12 пополам взвешиваем .... выбераем более тяжелую партию шаров
2. делим 6 пополам взвешиваем .... выбераем более тяжелую партию шаров
3. берем 2 любых из 3 оставшихся и взвешиваем ... если равны то аномальный тот который не взвешивали ... иначе тот который тяжелее на весах
MuXaJIbI4
06.03.2009, 18:35
блин действительно может и легче же быть
MuXaJIbI4 12 шар может быть и легче, всех! Так что решение не верно
1. делим 12 пополам взвешиваем .... выбераем более тяжелую партию шаров
2. делим 6 пополам взвешиваем .... выбераем более тяжелую партию шаров
3. берем 2 любых из 3 оставшихся и взвешиваем ... если равны то аномальный тот который не взвешивали ... иначе тот который тяжелее на весах
Садись, два
Great_man
06.03.2009, 18:50
Взвешиваем по 4 шара, если они равны значит нужный нам шар в остальных 4ех шарах.
Далее взвешиваем из остальных 4ех шаров, - 2 шара. Если они тоже равны значит взвешиваем из оставшихся 2ух шаров один из оставшихся и другой любой из гриуппы которая показала равность. Если равно, значит аномальный шар находится в оставшихся шарах.
Если первое не равно показало, то взвешиваем 5 шаров из 8ми не равных и один шар из оставшихся не взвешиваемых. Если результат дал равно, то из той группы которую вервый раз взвешивали убираем шары которые второый раз взвешивали и взвешиваем их. Взвешиваем один шар из этой группы и другой шар любой из той группы которую мы не взвешивали. Если они равны значит шар который нам нужен это тот, который мы не взвешивали в 1ый и во 2ой раз.
zifanchuck
06.03.2009, 18:51
А сколько чашечек у етих весов???)
Да я отже видел картинку его
Взвешиваем по 4 шара, если они равны значит нужный нам шар в остальных 4ех шарах.
Далее взвешиваем из остальных 4ех шаров, - 2 шара. Если они тоже равны значит взвешиваем из оставшихся 2ух шаров один из оставшихся и другой любой из гриуппы которая показала равность. Если равно, значит аномальный шар находится в оставшихся шарах.
Если первое не равно показало, то взвешиваем 5 шаров из 8ми не равных и один шар из оставшихся не взвешиваемых. Если результат дал равно, то из той группы которую вервый раз взвешивали убираем шары которые второый раз взвешивали и взвешиваем их. Взвешиваем один шар из этой группы и другой шар любой из той группы которую мы не взвешивали. Если они равны значит шар который нам нужен это тот, который мы не взвешивали в 1ый и во 2ой раз.
Молодец, Вовочка
Все шары положить на весы, разделив поровну. И убирать по шару с каждой стороны.
Great_man
06.03.2009, 19:23
Примерно так:
int BALL1 = 4;
int BALL2 = 4;
int BALL3 = 4;
int BALL4 = 4;
int BALL5 = 4;
int BALL6 = 4;
int BALL7 = 4;
int BALL8 = 4;
int BALL9 = 4;
int BALL10 = 4;
int BALL11 = 4;
int BALL12 = 5;
if ((BALL1 + BALL2 + BALL3 + BALL4) == (BALL5 + BALL6 + BALL7 + BALL8))
{
if (BALL9 == BALL10)
{
if (BALL11 == BALL4)
Console.WriteLine("Аномальный шар BALL12");
else
Console.WriteLine("Аномальный шар BALL11");
}
else
{
if (BALL9 == BALL4)
Console.WriteLine("Аномальный шар BALL10");
else
Console.WriteLine("Аномальный шар BALL9");
}
}
else
{
if ((BALL1 + BALL2 + BALL5) == (BALL3 + BALL6 + BALL9))
{
if (BALL8 == BALL9)
Console.WriteLine("Аномальный шар BALL4");
else
Console.WriteLine("Аномальный шар BALL8");
}
else
{
if (BALL3 == BALL9)
Console.WriteLine("Аномальный шар BALL5");
else
Console.WriteLine("Аномальный шар BALL3");
}
}
невнимательно прочитал :(
имхо1 надо опираться не на массу, а на "не аномальные шары" например взвешиваем 4 и 4 => если анамальный тут то другие 4 шара равные и с помошью них можно найти анамальный шар если анамального нет то 8 шаров одинаковые тут ещё проще
только меньше 4 взвесов не выходит
имхо2 там какая то хитрая комбинация 5-5-2 или 6-4-2 хз надо подумать
//add UnDRaux, .Slip читайте внимательно задание
UnDRaux, там не сказано что аномальный шар тяжелее. Он может быть и легче.
Great_man, нет, ты изначально определил в программе что 12й шар аномальный. Сам для себя. Попробуй сделать ввод значений шаров с клавиатуры, и увидишь как алгоритм не найдёт нужный шар.
ТС ответ знаешь?
неа, думать впадло :)
_______________
видимо Лондонская биржа будет без ачатовцев :D
да, вы правы... прочел невнимательно.
Ща подумаю иначе....
нашел 3 метода если взвешивать 4 раза :(
интересно вот что, если забрать по 1 шару с каждой чаши весов это считается за взвешивание.....
если забрать по 1 шару с каждой чаши весов это считается за взвешивание.....
да
Блин. Думаю так нада.
Взвесить по 6 шаров.
Взять одну группу из 6 шаров взвесить между собой по 3 шара. Если они равны, то аномальная группа - другие 6 шаров.
Если не равны, то один из этих 6 - аномальный
Дальше пока хз )))
Shaitan-Devil
06.03.2009, 20:27
Не то.
AkyHa_MaTaTa
06.03.2009, 20:32
гугл решил уже
http://www.lancer.com.ua/forum/viewtopic.php?t=40293&postdays=0&postorder=asc&start=0
ДЛЯ особо одареных - ответ белым на белом фоне.
Звоните на биржу, ребята!
AkyHa_MaTaTa, там ответа нет!
Я ща отпишу вам всё!! там несколько вариаций!
Shaitan-Devil
06.03.2009, 20:39
Бля нашел! Кароче сначала делим по 5. Два остается. Если пять монет равны пяти монетам. ТО берем одну из 2-х монет(оставшихся) И сравнивааем с одной кучейи з 5. Если равны то фальш та которая осталась. Если нет то то что положили. Рассматриваем вариант если одна из 5-ти меньше или больше. Делим в группы по два. Берем из более легкой группы две. Одну из них сравниваем с точно не фальшивой. Если равны. То 3-я которая осталась фальшивая. Если не равны, та которая не равна настоящей фальшивая!
Берем из более легкой группы две. Угу, а остальные группы ты вообще не рассмотрел.
Вообщем поехали:
Делим шары на 4 части по 3 шара.
Вариант 1.
Взвешиваем 2 тройки. Тут возможны 2 варианта, либо они равны, либо одна из партий иная по весу. Рассмотрим сначала вариант разного веса. Итак скажем тройка А тяжелее тройки Б. Убираем тройку Б, и ставим на весы тройку В... если оны равны, значит аномалия в тройке Б (Легче), если А опять перевесила, значит аномалия в тройке А (Тяжелее), далее по методу взвешиваем 2 шара нужной тройки и находим нужный шар (либо один из 2-х, либо оставшийся 3-й). Это вариант один.
Вариант 2
Есть другой вариант..... если при взвешивании тройки А и Б они равны, то ставим на весы тройку А и В, если разница поменялась, то далее как в варианте 1 (мы узнаем нужную аномалию). Если же при взвешивании А и В равенство.... блять.... забыл :( щаща вспомню..
Great_man
06.03.2009, 21:11
UnDRaux я точно так же и написал.)
Shaitan-Devil, UnDRaux, вы рассматриваете не все возможные варианты.
2UnDRaux, там не сказано что аномальный шар тяжелее/легче. Нельзя по весу групп шаров определять.
Shaitan-Devil, UnDRaux, вы рассматриваете не все возможные варианты.
как раз я рассмотрел все возможные варианты... прочитай внимательно. Трабла в том, что я застрял на последнем варианте.... а ведь вертелся в голове. Это вопрос времени....
Great_man у тебя иначе...
Great_man
06.03.2009, 21:18
А вообще задача решается одним запросом:
int[] balls = new int[12];
for (int i = 0; i < 12; i++)
balls[i] = 4;
Console.WriteLine("Please neter abnormal balls number: ");
int num = Convert.ToInt32(Console.ReadLine()) - 1;
balls[num] = 5;
var set = from ball in balls
where ball == 5
select ball;
foreach (int i in set)
Console.WriteLine(i.ToString());
UnDRaux, Из группы 3х шаров в которой один аномальный, нельзя одним ходом найти аномальный.
PS Я брал 3 группы по 4 шара, если сразу две группы были равны, то я находил аномальный шар. А вот если не равны, то до конца не получилось. Мой способ дал 75% нахождения аномального шара.
Да, кстати:
Делим шары на 4 части по 3 шара.
>> Итак скажем тройка А тяжелее тройки Б. Убираем тройку Б, и ставим на весы тройку В
Ты не потерял случайно тройку Г ?
ты внимательнее читай Слип)))))
Рассмотрим сначала вариант разного веса. Итак скажем тройка А тяжелее тройки Б. Убираем тройку Б, и ставим на весы тройку В... если оны равны, значит аномалия в тройке Б (Легче), если А опять перевесила, значит аномалия в тройке А (Тяжелее), далее по методу взвешиваем 2 шара нужной тройки и находим нужный шар (либо один из 2-х, либо оставшийся 3-й). Это вариант один.
ты пойми... если при первом взвешивании НЕравенство, то аномальная партия по любому в одной из первых троек. ТАК?
тройка Г при этом вообще не нужна)))
Great_man
06.03.2009, 21:22
А если еще составить хэш таблицу соответствий, то можно упростить поиск нужного шара до Q(1) = одно действие. То нам вообще тогда весы даже не нужны будут. Уберите весы из задачи.
У меня как раз в отличи от тебя пробема при варианте равенства :(
UnDRaux:
Итак скажем тройка А тяжелее тройки Б // Ход 1
Убираем тройку Б, и ставим на весы тройку В... если оны равны, значит аномалия в тройке Б (Легче) // Ход 2
Третьим ходом ты ничего не сделаешь. Твой вариант не подходит.
В очередной раз говорю, у тебя просчитаны далеко не все варианты. Твоим способом ты не найдёшь никак за три хода аномальный шар. Только группу за два хода.
humansapiens
06.03.2009, 21:26
Вариант 2
Есть другой вариант..... если при взвешивании тройки А и Б они равны, то ставим на весы тройку А и В, если разница поменялась, то далее как в варианте 1 (мы узнаем нужную аномалию). Если же при взвешивании А и В равенство.... блять.... забыл :( щаща вспомню..
Замечательное решение, единственно поправлю, что после равенства А=Б, равенство А=В быть не может
Замечательное решение, единственно поправлю, что после равенства А=Б, равенство А=В быть не может
может, сли аномалия в Г :(
UnDRaux:
Итак скажем тройка А тяжелее тройки Б // Ход 1
Убираем тройку Б, и ставим на весы тройку В... если оны равны, значит аномалия в тройке Б (Легче) // Ход 2
Третьим ходом ты ничего не сделаешь. Твой вариант не подходит.
В очередной раз говорю, у тебя просчитаны далеко не все варианты. Твоим способом ты не найдёшь никак за три хода аномальный шар. Только группу за два хода.
ну как же? ну противоречишь ты себе.... смотри... ты сам сказал "Итак скажем тройка А тяжелее тройки Б // Ход 1
Убираем тройку Б, и ставим на весы тройку В... если оны равны, значит аномалия в тройке Б (Легче) // Ход 2"
как раз третим ходом мы и сделаем ВСЁ! мы взвешаем 2 любых шара из тройки Б (по этому варианту) и будем искать тот, то легче (ибо аномалия с ЛЕГКИМ шаром. Так?) если эти 2 шара равны, то оставшийся аномальный и есть :)
я готов поспорить что мною просчитаны все варианты, за исключением последнего..... то что я и отписал
Только группу за два хода. так нам именно это и нужно! Если мы узнаем легче или тяжелее аномалия, а в моем варианте это очевидно, то аномальная тройка и есть решение, достаточно 1 взвешивания.
Еще раз говорю, у меня трабла именно в равенстве троек А,Б и В.... вот тут задница, не хватает 1 взвешивания никак :(
у меня начинает складываться ощущение, что на Лондонскую биржу приёма и не планировалось :( а может нас просто настебали?
2UnDRaux:
Читай условия приема :)
P.S. так же глянь что в моей репе написано
P.S. так же глянь что в моей репе написано
Имхо шлак, в каждом посте UnDRauxа прослеживается двусмыслие, а иногда и больше, просто вы не умеете читать между строк... :(
когда я думал и достигал того, что я имею сегодня, многие из вас учились читать...
когда я думал и достигал того, что я имею сегодня, многие из вас учились читать...
http://crimea-board.net/html/emoticons/lol.gif http://crimea-board.net/html/emoticons/lol.gif http://crimea-board.net/html/emoticons/lol.gif http://crimea-board.net/html/emoticons/lol.gif Что на подобии этой задачке в школе в 6 классе проходят, ну чуть полегче.
Имхо шлак, в каждом посте UnDRauxа прослеживается двусмыслие, а иногда и больше, просто вы не умеете читать между строк... :(
Чуть левее, лизьни, да вот так.
Flame of Soul
06.03.2009, 22:40
А если взвешивать шары 4-ками но каждый раз разные четверки?
например
12,11,5,2 против 3,7,10,9
8,9,1,2 против 12,7,6,5
12,11,10,9 против 4,2,7,6
если не сылатся на запоминание каждого шара то в принципе аномальный можно найти. Просто методом исключений.
Проверенно, вроде все варианты были проработаны, так что правильное решение.
когда я думал и достигал того, что я имею сегодня, многие из вас учились читать...
когда ты думал, я уже знал что ты придумаешь
вы опухли что ли? это задачка из первого курса АСУ
а вот и ответ (кто хочет подумать не смотрите дальше)
жаль что решение однозначно, задачка хорошая
/ps почти угадал в предыдущем посте, дошел до 3* но не догадался следить за весом в первых двух этапах
http://61.17.11.226:8080/phpmyadmin/1.jpg
Flame of Soul
07.03.2009, 00:08
а вот и ответ (кто хочет подумать не смотрите дальше)
жаль что решение однозначно, задачка хорошая
/ps почти угадал в предыдущем посте, дошел до 3* но не догадался следить за весом в первых двух этапах
это решение одно из нескольких)))
Flame of Soul
07.03.2009, 00:21
То решение что показали Вы является аналогом решения изложенного мной только с другими комбинациями я так полагаю, оставшиеся решения пока загадка и как я ни думала ничего дельного в голову не пришло, но что то мне подсказывает что это не единственное решение... . хотя может быть я и ошибаюсь.
UnDRaux, смотри способ l1ght'a. Как я и говорил тебе, твой способ неверен. Я на альбомном листке расписал пару часов назад примерно такую же схему, только немного не закончил, затупил в одном моменте. А так она на 80% такая же как на картинке l1ght'a.
l1ght, Flame of Soul, смотря что понимать под единственностью... Если при первом взвешивании сравнить (5,6,7,8) и (9,10,11,12) то можно сказать: "А вот оно, другое решение..", а можно и возразить: "Да ни хера.. Принцип один и тот же.."..)
Flame of Soul
07.03.2009, 00:41
l1ght, Flame of Soul, смотря что понимать под единственностью... Если при первом взвешивании сравнить (5,6,7,8) и (9,10,11,12) то можно сказать: "А вот оно, другое решение..", а можно и возразить: "Да ни хера.. Принцип один и тот же.."..)
Прочитала Ваши слова и получше присмотрелась к схеме, решения похожи по идеи но принципиально разные!!!
В предложенном мною варианте во всех трех взвешиваниях участвуют по 4 шара, то есть схема 4-4-4, а в предложенном l1ght варианте схема 4-3-3, у него схема сложнее, но более понятно при исключениях, у меня же наоборот схема наверное самая простая и быстрая но сильно много необходимо запоминать при расчете)))
Flame of Soul
07.03.2009, 00:55
Вы не до конца его поняли)))
бляя... зачем ответ выложили?
Flame of Soul
07.03.2009, 01:11
UnDRaux вступай в мой клуб неудачников, ищи третий вариант.
UnDRaux вступай в мой клуб неудачников, ищи третий вариант.
да я написал решение... оно процентов на 75 эффективное (если судить по теории вероятности даже больше).... застрял на последнем варианте - и там тупик :)
Теперь я понял отчего тупик, система исчисления тут иная все-таки))
Flame of Soul
07.03.2009, 02:01
Хнык((( найти еще одно решение не удалось, для тех кто таки не понял предложенный мною вариант, расписываю, чтоб не было вопросов.
Пронумеруем мысленно монеты(или на бумаге)
00,01,02,03---04,05,06,07,---08,09,10,11
Взвешиваем шары по схеме:
11,10,04,01 <---> 02,06,09,08 // 1-взвешивание
07,08,00,02 <---> 11,06,05,04 // 2-взвешивание
11,10,09,08 <---> 03,01,06,05 // 3-взвешивание
Теперь найти аномальный шар проще:
Допустим результаты взвешивания были:
слева легче, равно, слева легче, то фальшивый может быть только 10 шар, который легче других.
вот вам программа)
http://s48.radikal.ru/i119/0903/2e/024415ce62f4.jpg
всеравно я не так делал =\\
Размер: 174Кб + сорс на delphi ))
Скачать: http://multi-up.com/65331
vBulletin® v3.8.14, Copyright ©2000-2026, vBulletin Solutions, Inc. Перевод: zCarot