Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Статья: Обобщённая задача о фальшивых монетах

Название: Обобщённая задача о фальшивых монетах
Раздел: Рефераты по математике
Тип: статья Добавлен 07:41:04 04 марта 2007 Похожие работы
Просмотров: 654 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

М. Мамикон

Многим читателям хорошо известна следующая классическая задача о фальшивых монетах, поражающая тем, что она разрешима:

Задача о мешке с фальшивыми монетами

Имеются N мешков и в каждом из них достаточное количество монет. Все мешки, кроме одного, содержат одинаковые «нормальные» монеты, в одном же мешке все монеты фальшивые. Известен вес нормальной монеты и известно, что фальшивая монета на 1 грамм легче нормальной. Требуется при помощи одного взвешивания на весах с разновесками обнаружить мешок с фальшивыми монетами.

Вот как решается эта задача. Мешки последовательно нумеруются и из каждого мешка берется количество монет, равное номеру этого мешка. Суммарный вес всех взятых таким образом монет будет «не дотягивать» до веса такого же количества нормальных монет (который нам известен) на количество граммов, равное номеру именно того мешка, который содержит фальшивые монеты. (Эта задача решается – правда, хитрее – и в том случае, когда вес нормальной монеты неизвестен и разновесков нет. Подумайте, как.)

Раздумывая над этой задачей, я пришёл к более удивительному выводу о том, что одним взвешиванием может быть решена и более сложная задача:

Задача о нескольких мешках с фальшивыми монетами

Пусть в условиях предыдущей задачи имеется не один, а несколько мешков с фальшивыми монетами, причём их количество неизвестно. Требуется при помощи одного взвешивания на весах с разновесками обнаружить все эти мешки.

Решив и эту задачу, я осмелился на дальнейшие усложнения. Задача оказалась разрешимой при ещё более удивительных условиях:

Задача о мешках с тяжёлыми и лёгкими монетами

Среди N мешков имеются некоторое (неизвестное) количество мешков с тяжёлыми и некоторое (тоже неизвестное) количество мешков с лёгкими монетами. Лёгкая монета на 1 г легче нормальной, а тяжёлая, наоборот, на 1 г тяжелее нормальной. Требуется при помощи одного взвешивания на весах с разновесками узнать, какие мешки содержат нормальные монеты, какие – тяжёлые, а какие – лёгкие. (Напомним, что внутри данного мешка все монеты одинакового веса и что вес нормальной монеты известен.)

Разрешимость и этой задачи вдохновила меня на дальнейшее обобщение, которое уже напрашивалось само собой. До сих пор мы фактически рассматривали задачи о двух или трёх сортах (типах) монет, поэтому естественна следующая

Задача о мешках с разносортными монетами

Пусть имеются N мешков и в каждом достаточное количество монет. Имеются монеты разных сортов, но в каждом мешке содержатся монеты только одного сорта. Количество мешков с монетами данного сорта произвольное, и нам оно неизвестно. Монеты разных сортов отличаются друг от друга по весу, причём на целое число граммов. Вес монеты каждого сорта нам известен. Требуется при помощи одного взвешивания на весах с разновесками определить, к какому сорту принадлежат монеты в каждом мешке.

Мы предлагаем читателю попробовать самостоятельно решить предыдущие задачи, прежде чем перейти к излагаемому ниже решению обобщённой задачи о фальшивых монетах.

Решение задачи о мешках с разносортными монетами

Перенумеруем последовательно мешки от 0 до N – 1. Обозначим вес самой лёгкой монеты через m. Пусть мешок под номером j содержит монеты веса m + Δj, то есть Δj определяет сорт монеты в j-м мешке. Пусть в зависимости от сорта монеты величины Δ могут принимать (целые) значения 0, 1, 2, ..., меньшие k, то есть количество сортов монет равно k.

Теперь возьмем из мешка с номером j количество монет, равное k j, то есть из первого мешка – одну монету, из второго – k, ..., из последнего – kN–1 монет. Всего взятых монет будет

N–1
M = k j = 1 + k + k2 + ... + kN–1 =

kN – 1

k – 1

.
j=0

Их суммарный вес S на весах будет равен

N–1 N–1
S = (m + Δj )k j = m·M + Δj k j.
j=0 j=0

Поскольку всегда Δj < k, вторая сумма в правой части

N–1
Δ = Δj k j = Δ0 + Δ1 k + Δ2 k2 + ... + ΔN–1kN–1
j=0

представляет собой перевод числа Δ из десятичной системы счисления (в которой работают весы) в систему счисления с основанием, равным k. В этой системе Δ записывается в виде числа со следующей последовательностью цифр:

Δ → ΔN–1 ΔN–2 ... Δ2 Δ1 Δ0 .
(*)

Мы видим, что каждая цифра этой записи показывает сорт монеты в последовательности мешков, взятой в обратном порядке. В этом состоит суть нашего решения.

Итак, из суммарного веса S всех выбранных M монет вычитаем величину Mm – вес того же количества монет наилегчайшего сорта и оставшееся число Δ = S – Mm переводим в систему счисления с основанием k (разлагаем по степеням k, начиная со старшей). Тогда мы получим число вида (*). Его j-я цифра с конца (счёт ведётся от нуля) показывает сорт монеты Δj в мешке под номером j.

Пример

В приводимой ниже таблице указаны веса монет, содержащихся в пяти мешках. Сверху дана нумерация мешков справа налево (это и есть обратный порядок), а под мешками указаны сорта монет. Они являются искомыми.

4 3 2 1 0 номер мешка j
11 г 12 г 10 г 12 г 10 г содержимое мешка m + Δj
1 2 0 2 0 сорт монеты Δj
81 27 9 3 1 количество взятых монет kj

В этом случае k = 3 и количество взятых монет соответствует степеням тройки, как показано в последней строчке таблицы. Всего мы взяли M = 121 монету. Их общий вес на весах будет равен S = 1351 г. Вычитая величину M·m = 121·10, получим Δ = 141 г. Переводя Δ в троичную систему

Δ = 1·34 + 2·33 + 0·32 + 2·31 + 0·30,

получим число 12020, последовательность цифр которого совпадает с исходной последовательностью сортов, приведённой в таблице.

Если k = 10, то надобность перевода Δ из одной системы счисления в другую отпадает. Для случая k = 3 существует несколько отличная от нашей интерпретация решения задачи. Найти её мы предоставляем читателю.

Немного истории

Классическую задачу об одном мешке с фальшивыми монетами можно найти во многих популярных книжках по математике. Говорят, что во время второй мировой войны англичане «сбросили» эту задачу над немецкими солдатами с целью их дезорганизации и что те потеряли над её решением более 40 000 человеко-часов.

В книге Д. Бизама и Я. Герцега «Многоцветная логика» (М., «Мир», 1978 г.) рассматривается также случай двух мешков с фальшивыми монетами и приводится решение этой задачи при помощи двух взвешиваний.

Классическая задача о фальшивых монетах в последнее время нашла применение в теории кодирования и информации – для обнаружения ошибки в коде.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:57:44 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:55:01 24 ноября 2015

Работы, похожие на Статья: Обобщённая задача о фальшивых монетах

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150580)
Комментарии (1836)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru