Основы алгоритмики. Разбор задач на взвешивания.

Факультативы
Алгори́тмика — раздел информатики, наука об алгоритмах. Круг задач алгоритмики включает создание алгоритмов, доказательство их правильности и выполнимости, изучение их свойств и также исследование различных исполнителей. Алгоритмика -- это первое, что мы изучаем с учениками на факультативах по информатики.
Шкурин Дмитрий Николаевич
Содержимое публикации

Взвешивания

ЗАДАЧА

Из набора гирек с массами 1, 2, …, 101 г потерялась гирька массой 19 г. Можно ли оставшиеся 100 гирек разложить на две кучки по 50 гирек в каждой так, чтобы массы обеих кучек были одинаковы?

РЕШЕНИЕ

Положим в первую кучку две гирьки массой 101 г и 1 г, а во вторую — 100 г и 2 г; затем в первую две гирьки — 99 г и 3 г, а во вторую — 98 г и 4 г. Так будем действовать, пока не положим во вторую кучку гирьки в 84 г и 18 г. К этому моменту в каждой кучке будет лежать по 18 гирек. Теперь положим в первую кучку две гирьки массой 83 г и 20 г, а во вторую — 82 г и 21 г. Так будем продолжать до тех пор, пока во вторую кучку не придется положить последнюю пару гирек массой 52 г и 51 г.

Ответ. Да. 

 

ЗАДАЧА

Лиса Алиса и Кот Базилио — фальшивомонетчики. У Базилио получаются монеты тяжелее настоящих, а у Алисы — легче. У Буратино есть 15 внешне одинаковых монет. Известно, что ровно одна фальшивая. Как двумя взвешиваниями на чашечных весах без гирь Буратино может определить, кто сделал фальшивую монету — Кот Базилио или Лиса Алиса?

РЕШЕНИЕ

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

 

ЗАДАЧА

В корзине лежит 13 яблок. Имеются весы, с помощью которых можно узнать суммарный вес любых двух яблок. Как за 8 взвешиваний выяснить суммарный вес всех яблок?

РЕШЕНИЕ

За пять взвешиваний можно узнать суммарный вес 10 яблок. Осталось найти суммарный вес трех оставшихся яблок. Для этого взвесим первое яблоко со вторым, второе с третьим и третье с первым, затем сложим полученные веса и получим удвоенный вес трех яблок.

 

ЗАДАЧА

Одна из девяти монет фальшивая, она весит легче настоящей. Как определить фальшивую монету за 2 взвешивания? 

РЕШЕНИЕ

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

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

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

Сахарный песок

У завхоза есть 32 килограмма сахарного песку и чашечные весы без гирь. За какое наименьшее количество взвешиваний он сможет отмерить 12 кг? Песок можно сыпать прямо на чаши — они чистые.

Подсказка 1 из 2

За одно взвешивание мы можем разделить весь песок пополам, уравновесив чаши.

Решение задачи

За одно или два взвешивания отвесить 12 кг не получится. Трех взвешиваний хватит.

За одно взвешивание мы можем разделить песок пополам — разложив его на чаши так, чтобы весы пришли в равновесие.

Песок с одной из чаш (16 кг) убираем в пакет, вторую чашу точно так же делим пополам, раскладывая песок на чаши весов, чтобы они пришли в равновесие. Итого, на каждой чаше весов по 8 кг сахара.

Песок с одной из чаш убираем в другой пакет (не к 16 кг). Остаток опять же делим пополам, уравновешивая чаши весов. Теперь на каждой чаше по 4 кг. Песок с одной из чаш добавляем в тот пакет, где лежат 8 кг. Теперь в этом пакете 12 кг.

Гири

Есть чашечные весы и гири весом 1 г, 2 г, 4 г, 8 г, 16 г. 

Какие грузы удастся уравновесить на весах с помощью этих гирь?

32 грамма

31 грамм

3 грамма

10 грамм

11 грамм

26 грамм

19 грамм

50 грамм

Решение задачи

Если на одну чашу весов поставить все гири, то, чтобы весы пришли в равновесие, на другую чашу нужно положить груз весом 1+2+4+8+16=31 грамм. Поэтому груз весом больше 31 грамма взвесить не получится.

Любой вес от 1 грамма до 31 грамма взвесить можно. Покажем, как это сделать для грузов из списка:

3 = 1 + 2

10 = 2 + 8

11 = 1 + 2 + 8

26 = 16 + 8 + 2

19 = 16 + 2 + 1

Взвешиваем и другие фрукты

Яблоко и апельсин вместе весят столько же, сколько груша и персик. Яблоко вместе с грушей весят меньше, чем апельсин с персиком, а груша вместе с апельсином весят меньше, чем яблоко с персиком. Какой из фруктов самый тяжелый? 

Выберите самый тяжелый фрукт

Апельсин

Яблоко

Груша

Персик

Решение задачи

Напишем данные нам в  условии взвешивании в виде равенств и неравенств:

яблоко+апельсин=груша+персик

яблоко+груша<апельсин+персик

груша+апельсин<яблоко+персик.

Второе взвешивание получается из первого обменом апельсина и груши. Правая чаша перевесила, значит апельсин тяжелее груши. А тогда из первого взвешивания видно, что яблоко легче персика.

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

8 монет

У ювелира есть 8 серебряных монет, одна из которых фальшивая — немного легче настоящей. За какое наименьшее количество взвешиваний на чашечных весах без гирь он сможет наверняка найти фальшивую монету?

Решение задачи

Разобьем монеты на три кучки: 3 монеты, 3 монеты, 2 монеты и сравним первые две кучки между собой. Если весы будут в равновесии, то эти шесть монет — настоящие. Тогда вторым взвешиванием сравним две оставшиеся монеты и определим фальшивую. В этом случае хватит двух взвешиваний.

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

Двухчашечные весы со стрелкой

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

Среди 21 внешне неотличимая монета: 10 настоящих и 11 фальшивых (фальшивая на 1 грамм легче настоящей). Антон взял одну из монет. 

За какое наименьшее количество взвешиваний на двухчашечных весах со стрелкой он сможет узнать, фальшива ли она?

Решение задачи

За 1. Положим на каждую чашу по 10 из оставшихся монет. Если разность весов будет четна, то монета в руках Антона — фальшивая, если нечетна — то настоящая.

Комментировать
Свидетельство участника экспертной комиссии
Оставляйте комментарии к работам коллег и получите документ бесплатно!
Подробнее
Также Вас может заинтересовать
Информатика
Информатика
Презентации по информатики для 3 класса «своя игра по мнформатике»
Информатика
Информатика
Конспект занятия по информатики для «Урок – игра «Основы программы CorelDRAW»»
Информатика
Комментарии
Добавить
публикацию
После добавления публикации на сайт, в личном кабинете вы сможете скачать бесплатно свидетельство и справку о публикации в СМИ.
Cвидетельство о публикации сразу
Получите свидетельство бесплатно сразу после добавления публикации.
Подробнее
Свидетельство за распространение педагогического опыта
Опубликует не менее 15 материалов и скачайте бесплатно.
Подробнее
Рецензия на методическую разработку
Опубликуйте материал и скачайте рецензию бесплатно.
Подробнее
Свидетельство участника экспертной комиссии
Стать экспертом и скачать свидетельство бесплатно.
Подробнее
Помощь