Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Содержание сайт... 65535
Вызов хранимых ... 65535
Эмулятор микроп... 65535
Приложение «Про... 64168
Организация зап... 62783
Оператор выбора... 62626
Invision Power ... 62200
Подключение Mic... 61005
Модуль Forms 59911
Создание отчето... 59836
ТЕХНОЛОГИИ ДОСТ... 56037
Программируемая... 55541
Пример работы с... 53153
Имитационное мо... 51427
21 ошибка прогр... 46413
Реклама
Сейчас на сайте
Гостей: 12
На сайте нет зарегистрированных пользователей

Пользователей: 13,057
новичок: Aidar
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Моделирование регулировочного участка цеха на GPSS + Пояснительная записка
Игра Sokoban на Delphi + Блок схемы
База данных склада на Delphi + Схема БД

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Алгоритмы поиска и задачи на взвешивания
Появление подобных задач, например задачи определения фальшивой монеты, в контексте рассмотрения алгоритмов поиска не случайно. Во-первых, поиск и в этом случае осуществляется путем операций сравнения, правда, уже не только одиночных элементов, но и групп элементов между собой. Во-вторых, как будет показано ниже, задачи на взвешивания вполне можно решать конструктивно.
В качестве примера рассмотрим задачу, предлагавшуюся на теоретическом туре одной из региональных олимпиад по информатике. Пусть у нас имеется 12 монет, одна из которых фальшивая, по весу отличающаяся от остальных монет, причем неизвестно, легче она или тяжелее. Требуется за три взвешивания определить номер фальшивой монеты (попробуйте решить эту задачу самостоятельно и вы убедитесь, что это совсем не просто, а порой вообще кажется невозможным). Введем следующие обозначения. Знаком “+” будем обозначать монеты, которые во время текущего взвешивания следует положить на весы, причем, если монета на весах уже была, то на ту же самую чашу, на которой эта монета находилась во время своего предыдущего взвешивания. Знаком “-“ будем обозначать монеты, которые следует переложить на противоположную чашу весов, по отношению к той, на которой они находились (каждая в отдельности), заметим, что если монета на весах еще не была, то знак “-“ к ней применен быть не может. Наконец, знаком “0” — монеты, которые в очередном взвешивании не участвуют. Тогда, существует 14 различных способов пометки монет для трех взвешиваний:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
+ + + + + + + + + 0 0 0 0 0 — первое взвешивание
+ + + - - - 0 0 0 + + + 0 0 — второе взвешивание
+ - 0 + - 0 + - 0 + - 0 + 0 — третье взвешивание



Из полученной таблицы вычеркнем 2 столбца так, чтобы в каждой из трех строк количество ненулевых элементов оказалось четным (ведь мы не можем во время одного взвешивания положить на две чаши весов нечетное число монет). Это могут быть, например, столбцы 4 и 14. Теперь будем взвешивать 12 монет так, как это записано в оставшихся 12 столбцах. То есть, в первом взвешивании будут участвовать 8 произвольных монет, во втором — три монеты следует с весов убрать, две — переложить на противоположные по отношению к первому взвешиванию чаши весов и три монеты положить на весы впервые (на свободные места так, чтобы на каждой из чаш вновь оказалось по 4 монеты). Согласно схеме проведем и третье взвешивание, опять располагая на каждой чаше весов по 4 монеты. Результат каждого взвешивания в отдельности никак не анализируется, а просто записывается. При этом равновесие на весах всегда кодируется нулем, впервые возникшее неравновесное состояние — знаком плюс, если при следующем взвешивании весы отклонятся от равновесия в ту же самую сторону, то результат такого взвешивания также кодируется плюсом, а если в другую сторону — то минусом. Например, записи “=<<” и “=>>” кодируются как “0++”, а записи “<=>” и “>=<” —
как “+0-“. Так как мы не знаем, легче или тяжелее остальных монет окажется фальшивая, то нам важно как изменялось состояние весов от взвешивания к взвешиванию, а не то какая именно чаша оказывалась тяжелее, а какая легче. Поэтому два, на первый взгляд, различных результата трех взвешиваний в этом случае кодируются одинаково. После подобной записи результатов взвешиваний фальшивая монета уже фактически определена. Ею оказывается та, которой соответствует такой же столбец в таблице, как и закодированный нами результат трех взвешиваний. Для первого из примеров это монета, которая участвовала во взвешиваниях по схеме, указанной в 10-м столбце таблицы, а для второго — в 8-м. В самом деле, состояние весов в нашей задаче меняется в зависимости от того, где оказывается фальшивая монета во время каждого из взвешиваний. Поэтому монета, “поведение” которой согласуется с записанным результатом взвешиваний, такой результат и определяет.
Анализ таблицы показывает, что эту задачу можно решить не только для 12, но и для 13 монет. Для этого следует исключить из рассмотрения любой не содержащий нулей столбец, например, все тот же четвертый. В остальном все действия остаются неизменными. Для произвольного числа монет N>2 количество взвешиваний при определяется по формуле [log3(2*N + 1)] (за одно взвешивание задача не разрешима ни для какого количества монет!!!), но подход к решению задачи при этом не изменится.
Попробуйте теперь решить задачу, которая предлагалась в 1998 году на уже упоминавшемся выше полуфинале чемпионата мира по программированию среди студенческих команд вузов. В ней также требовалось определить номер фальшивой монеты, вес которой отличался от остальных. Но все взвешивания уже были проведены, а их результаты записаны. Число взвешиваний являлось входным параметром в задаче (оно могло быть и избыточным по сравнению с описанным выше оптимальным алгоритмом определения номера фальшивой монеты). При этом в каждом из взвешиваний могло участвовать любое четное количество имеющихся монет (сколько и какие именно — известно). Результаты записывались с помощью символов “<”, “>” и “=”.
Еще одна задача на взвешивания рассмотрена в [8]. В общем случае в ней требуется найти набор из минимального количества гирь такой, что с его помощью можно взвесить любой груз, весящий целое число килограмм, в диапазоне от 1 кг до N кг. При необходимости гири можно располагать на обеих чашах весов. Так, для N=40 это гири 1, 3, 9 и 27 кг.




Опубликовал Kest February 25 2010 22:34:13 · 0 Комментариев · 9824 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
EditButton
Работа с картотеками
Медиа комбайн
AID антивирус
45 уроков по дельфи
Учебник для продв...
Синтаксический ан...
Игра Car [Исходни...
БД студентов
Gold Submitter II...
Visual Studio 200...
Preview
Error mod
Ehlib
Пятнашки и крести...
DelphiXIsoDemo1
Векторный редакто...
PHP/MySQL для нач...
TelBook
CwstatusBar

Топ загрузок
Приложение Клие... 100366
Delphi 7 Enterp... 82142
Converter AMR<-... 20046
Borland C++Buil... 11045
GPSS World Stud... 10405
Borland Delphi ... 8032
Turbo Pascal fo... 6959
Visual Studio 2... 4961
Калькулятор [Ис... 4259
FreeSMS v1.3.1 3508
Случайные статьи
Целевые страницы
СПИСКИ ПОЛЬЗОВАТЕЛЯ
Игровые автоматы с...
Устранение дребезг...
зательно
функции-члены
брандмауэре
Обработка исключит...
Код сообщения втор...
Внешний DNS-сервер...
пользователям
Иерархии настраива...
Иногда поддерживаю...
Запуск программ на...
Оценка рисков безо...
Открытие потока
Листинг 17.2. Сайт...
Вывод результатов ...
Экспертные системы...
Определить инициал...
Программа рассчиты...
При хакинге Xbox п...
Программа перечисл...
Правила оптимизаци...
Системный вызов ехес
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?