Олимпиада

В России появились б...

Четверг, 30 Август 2012
Компания HEC/COMPUCASE Europe GmbH объявляет о начале продаж в России блоков питания марки COUGAR серии CMX. Новые БП мощные и тихие, с модульным подключением кабелей. Линейка состоит из 4 моделей мощностью 550,...
Читать полностью

ЧП добровольно выпла...

Вторник, 28 Август 2012
Днепропетровска компания "Безопасность, охрана, гарантия", предоставляющая услуги по охране, использовала 14 компьютеров с установленными, на каждом из них, пиратскими копиями операционных систем и офисных приложений Microsoft. Согласно действующего законодательства, за хранение...
Читать полностью

«SMS XL» от «Киевста...

Суббота, 25 Август 2012
До 15 июня 2011 года абоненты предоплаченной связи Киевстар могут воспользоваться новым акционным предложением SMS XL с включенным объемом SMS для отправки на номера сети Киевстар и DJUICE. Киевстар вводит новое акционное...
Читать полностью

Вредоносные программ...

Четверг, 23 Август 2012
Согласно данным мониторинга, абсолютным лидером по количеству заражений в Интернете в этом месяце стал размещаемый на порно-сайтах скрипт из семейства FakeUpdate - Trojan.JS.FakeUpdate.bp. Он предлагает скачать видео соответствующего содержания, однако для...
Читать полностью

Samsung анонсировала...

Понедельник, 20 Август 2012
Компания Samsung Mobile Display анонсировала выход семидюймовых дисплеев, изготовленных по ее технологии Super-AMOLED, пишет ресурс OLED-Display.net со ссылкой на корейское издание Etnews Новые дисплеи имеют разрешение 1200 на 600 пикселей.
Календарь
< Август 2012 >
П В С Ч П С В
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    
Анонсы новостей

Современные возможности программирования и качественный ламинат в интернет магазине

На сегодня в интернете есть немало сайтов, на которых можно приобрести отличные строительные материалы для отделочных работ.

Читать полностью
Яндекс.Метрика


Появление подобных задач например задачи определения фальшивой...

Появление подобных задач, например задачи определения фальшивой монеты, в контексте рассмотрения алгоритмов поиска не случайно. Во-первых, поиск и в этом случае осуществляется путем операций сравнения, правда, уже не только одиночных элементов, но и групп элементов между собой. Во-вторых, как будет показано ниже, задачи на взвешивания вполне можно решать конструктивно.
В качестве примера рассмотрим задачу, предлагавшуюся на теоретическом туре одной из региональных олимпиад по информатике. Пусть у нас имеется 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 кг.

Алгоритмы поиска в неупорядоченных одномерных массива
Поиск в упорядоченных массивах
Поиск подстроки в строке
 
Новости

Современные возможно...

Суббота, 28 Ноябрь 2015
Современные возможности программирования и качественный ламинат в интернет магазине На сегодня в интернете есть немало сайтов, на которых можно приобрести отличные строительные материалы для отделочных работ.

Сетевые экраны: реко...

Пятница, 27 Ноябрь 2015
сетевые экраныНаиболее важным средством защиты сетей являются сетевые экраны, называемые межсетевыми или брандмауэрами. Главная задача сетевого экрана - экранировать сетевой трафик для недопущения несанкционированного доступа между компьютерными сетями.

Язык программировани...

Суббота, 10 Октябрь 2015
Язык программирования В современном мире существует множество профессий, среди которых профессия программиста довольно таки востребована, потому как все в мире компьютеризировано и автоматизировано, и надо создавать дополнительные программы для слаженной работы многофункциональных устройств.

Программирование на...

Среда, 24 Июнь 2015
Программирование на Delphi Благодаря созданию компьютера у многих людей появились новые профессии, связанные с новейшими технологиями. Однако вместе с этим фактом ряд стабильно существующих профессий многие годы просто стали не нужны, и начался процесс...
Читать полностью

Язык програмирования

Суббота, 06 Июнь 2015
Язык программирования В этой статье мы поговорим об изучении языка программирования Delphi , довольно сложно выучить его, прочитав одну статью, а точнее невозможно. Также и одна книга не решит проблемы с языком, вам...
Читать полностью
Опрос
На каком языке Вы программируете?
 
Яндекс.Метрика