Нет, не из тестов. Нарыл старые условия математического кружка, в который я когда-то ходил. Условие задачи выглядит именно так, чего-то типа "Если возможно, то приведите пример, если невозможно, то докажите что невозможно" там не было.
Какие весы написано - "За одно взвешивание можно узнать вес одной монеты."
Нет, не из тестов. Нарыл старые условия математического кружка, в который я когда-то ходил. Условие задачи выглядит именно так, чего-то типа "Если возможно, то приведите пример, если невозможно, то докажите что невозможно" там не было.
На вопрос как можно ответить никак и уже доказать почему
примем обозначения: Мn - монета подлежащая взвешиванию. ∨М - монета, вес которой наибольший среди уже взвешенных. а→х - количество невзвешенных монет (а) отсчитываемых в сторону наибольшего шага (→х) от ∨М. Шагом является расстояние(измеряемое в монетах) между двумя ближайшими взвешенными монетами. Теперь можем найти требуюмую "тяжелую" монету по формуле: Мn=∨М+а→х следующим образом: 1) Определяем любую М1 2) М2=М1+5→х 3) М3=∨М+3→х 4) М4=∨М+2→х 5) М5=∨М+1→х 6) М6=∨М+1→х 7) Определяем из взвешенных ∨М , она и будет решением задачи.
Сообщение отредактировал Kreativshik - Ср, 19.06.13, 01:28
Итак, судя по условию у нас весы которые показывают вес, пусть это будут электронные весы. Единственная "непонятка" это ограничение, что можно взвешивать только одну монету - оно явно нелогичное, поэтому его игнорируем. Если все же, это не ошибка формулировки, тогда нужно думать еще.
Монеты имеют разный вес, а значит решений может быть несколько, все зависит от взаимного расположения монет, и искать их всех мы не собираемся. Нас интересует основное решение - нужно найти самую тяжелую монету, и она будет одним из возможных ответов. Нам это достаточно. Поиск.
пронумеруем все монеты по порядку, от 1 до 13. Взвещивание №1. взвешиваем монеты №№ 1 ...7 (фиксируем вес) Взвещивание №2. взвешиваем монеты №№ 7 ...13 (фиксируем вес) Определяем какая куча тяжелее и откидываем заведомо легкие монеты. (например пусть первая куча легче и мы отбрасываем монеты 1..6) Взвещивание №3. взвешиваем монеты №№ 7,8,9,10 (фиксируем вес) Взвещивание №4. взвешиваем монеты №№ 10,11,12,13 (фиксируем вес) Опять же определяем какая куча тяжелее и откидываем заведомо легкие монеты (например пусть первая куча легче и мы отбрасываем монеты 7,8,9). Также нам стал известен вес (или масса , кому как нравится) монеты №10 (Взвеш.№4 + Взвеш№3 - Взвеш.№2). Взвещивание №5. взвешиваем монеты №№ 11,12 (фиксируем вес) Взвещивание №6. взвешиваем монеты №№ 12,13 (фиксируем вес) После этого взвешивания нам известны массы всех оставшихся монет ( 10,11,12,13) выбираем самую тяжелую.
Ну где-то так.
Сообщение отредактировал freews - Пт, 28.06.13, 21:06
Нас интересует основное решение - нужно найти самую тяжелую монету,
Афигенно классный подход к решению!!!
С меня наградка, и очень надеюсь, что Уважаемая Администрация тоже расщедрится на ножки и крылышки за ну вот безусловно явное мозго-шевеление в стиле ФЭ
freews, Вам сразу хочеться задать вопрос,- а Вы какую задачу решаете?)) В задаче русским по белому написано, что за одно взвешивание можно определить вес ОДНОЙ монеты! К тому же условия требуют однозначно определить монету, которая тяжелее любой соседней! Ваш алгоритм не удовлетворяет ни то ни другое! Собственно на этом можно было бы и закончить данный комментарий, но подозреваю, что без подробной экспликации выше сказанного, будут попытки навязать мне чьи то заблуждения. Поэтому далее будет предложен контраргумент: Допустим мы пронумеровали монеты от 1 до 13. Вес монет с номерами от 1 до 7 составляет 35г. (7...13) = 69г. (7...10)=33г. (10...13)=46г (11,12)=23г. (12,13)=25г. В итоге мы получаем следующие веса монет с номерами 10, 11, 12, 13. (10)=(33+46)-69=10г. (11)=23-(25-(46-10-23))=11г. (12)=23-11=12г. (13)=25-12=13г. Очевидно, что монета номер 13 весит больше чем любая из монет с номерам 10, 11, 12. Тринадцатая монета естественно тяжелее одной из своих соседок,- монеты номер 12. Но тяжелее ли она другой соседки (монета номер 1) определенно сказать невозможно. Ведь согласуясь с выше изложенным веса монет могу быть распределены например так: (1)=14г (2)=1г (3)=2г (4)=3г (5)=4г (6)=5г (7)=6г (8)=8г (9)=9г (10)=10г (11)=11г (12)=12г (13)=13г Недоразуменице получается, неправда ли?!)))) P.S. Решение данной задачи найдено в посте #17. От туда можно вывести и общее решение для любого количества монет. Если решение не понятно, то я могу разъяснить его подробней.
Сообщение отредактировал Kreativshik - Сб, 29.06.13, 16:37
