Категории

Задачи на размен монет

25 12 2014 задача 3

Задача с монетами (Задание 20 базовый ЕГЭ )

Страшно люблю такую задачу. Вот смотрите. От сотворения мира известно, что любую сумму, начиная от 8, скажем, тугриков, можно разменять 3- и 5- тугриковыми монетами. Только умоляю, не поминайте в этом месте индукцию. Во-первых, всуе, а, во-вторых, дедушка Оккам не велел. А теперь давайте, посмотри на малотугриковые  суммы: 7 не меняется, 6 меняется, 5 меняется, 4 не меняется, 3 меняется, 2 не меняется, 1 не меняется, 0 меняется. Как выразился один из фигурантов вчерашнего занятия, "меняются и не меняются как-то зеркально". Это точно: что зеркально, то зеркально. А теперь давайте понавыпускаем a-тугриковые и b-тугриковые монеты. Только чтобы a b взаимно просты были. Тогда то же самое: с какого-то места меняется всё, а до этого зеркально половина. А с какого места? Ну как же, 8=3+5? Значит a+b? Не-е-е, явно маловато будет. А ещё что такое 8? Ну, конечно, же дважды четыре! Значит, начинаем меняться с (a-1)(b-1). В этом месте вышеупомянутый фигурант аж подпрыгнул! А почему до этого всё зеркально? Ну, это как раз и есть самое сложное. Потому что используется некоторая каноническая запись натурального числа, которая строится по a b.
Задачка. конечно, стара как мир. Я посмотрел авторство в задачнике Васильева и Егорова. Оказывается. А.А. Кириллов 
(http://www.mathnet.ru/php/person.phtml?option_lang=rus&personid=20210) Замечательный случай придумывания детской задачки абсолютно выдающимся математиком! И задачка получилась выдающаяся. И дело даже не в призраке нетёровости в духе новой книжки Хованского и Чулкова и тому подобной научности. Просто это повод для замечательно интересного душевного разговора со школьником, в ходе которого идеи и понятия рождаются тут же, а не приходят из книжек! 

Tags: математика, школьники

Источник: https://dreameranalyst.livejournal.com/3645.html

Научный форум dxdy

Продолжаем подготовку к итоговой государственной аттестации. Сегодня решаем задачи,
которые предлагаются на базовом уровне ЕГЭ по математике под номером 20. Задачи взяты из открытых банков заданий.


За­да­ние 20.

В об­мен­ном пунк­те можно со­вер­шить одну из двух опе­ра­ций:

 · за 2 зо­ло­тые мо­не­ты по­лу­чить 3 се­реб­ря­ные и одну мед­ную;

 · за 5 се­реб­ря­ных монет по­лу­чить 3 зо­ло­тые и одну мед­ную.

У Ни­ко­лая были толь­ко се­реб­ря­ные мо­не­ты. После не­сколь­ких по­се­ще­ний об­мен­но­го пунк­та се­реб­ря­ных монет у него стало мень­ше, зо­ло­тых не по­яви­лось, зато по­яви­лось 100 мед­ных. На сколь­ко умень­ши­лось ко­ли­че­ство се­реб­ря­ных монет у Ни­ко­лая?

Решение:


Из условия мы имеем равенства (сокращения: зм -  золотые монеты, см – серебряные монеты, мм – медные монеты)

2 зм = 3 см + 1мм,

5 см = 3 зм + 1мм.

Так как у Николая были только серебряные монеты, а после обмена остались серебряные и появились медные, то все золотые, которые появились в ходе обмена, были опять обменены.

Из второго равенства мы видим, что за десять серебряных монет он получал 6 золотых и 2 медных.

10 см = 6 зм + 2мм. Но из первого равенства находим, что за 6 золотых монет он получает 9 серебряных и 3 медных.

6 зм = 9 см + 3мм. В итоге этих обменов у него вместо десяти серебряных монет осталось 9, но появилось 5 медных. То есть одна серебряная монета равна 5 медным. Так как у него появилось 100 медных монет, то он отдал за них 20 серебряных.

Ответ 20.

Потренируйтесь в решении подобных задач.

1.     В обменном пункте можно совершить одну из двух операций:

·        за 4 золотых монеты получить 5 серебряных и одну медную;

·        за 8 серебряных монет получить 5 золотых и одну медную.

У Николая были только серебряные монеты. После нескольких посещений обменного пункта серебряных монет у него стало меньше, золотых
не появилось, зато появилось 45 медных. На сколько уменьшилось количество серебряных монет у Николая?

2.     В обменном пункте можно совершить одну из двух операций:

·        за 4 золотых монеты получить 5 серебряных и одну медную;

·        за 7 серебряных монет получить 5 золотых и одну медную.

У Николая были только серебряные монеты. После нескольких посещений обменного пункта серебряных монет у него стало меньше, золотых
не появилось, зато появилось 90 медных. На сколько уменьшилось количество серебряных монет у Николая?

3.     В обменном пункте можно совершить одну из двух операций:

·        за 5 золотых монет получить 7 серебряных и одну медную;

·        за 10 серебряных монет получить 7 золотых и одну медную.

У Николая были только серебряные монеты. После нескольких посещений обменного пункта серебряных монет у него стало меньше, золотых
не появилось, зато появилось 60 медных. На сколько уменьшилось количество серебряных монет у Николая?


1.     В об­мен­ном пунк­те можно со­вер­шить одну из двух опе­ра­ций:

• за 2 зо­ло­тых мо­не­ты по­лу­чить 3 се­реб­ря­ных и одну мед­ную;

• за 5 се­реб­ря­ных монет по­лу­чить 3 зо­ло­тых и одну мед­ную.

У Ни­ко­лая были толь­ко се­реб­ря­ные мо­не­ты. После не­сколь­ких по­се­ще­ний об­мен­но­го пунк­та се­реб­ря­ных монет у него стало мень­ше, зо­ло­тых не по­яви­лось, зато по­яви­лось 50 мед­ных. На сколь­ко умень­ши­лось ко­ли­че­ство се­реб­ря­ных монет у Ни­ко­лая?

Ответ 10. Решение можно посмотреть здесь http://mathb.reshuege.ru/test?theme=230

2.     В об­мен­ном пунк­те можно со­вер­шить одну из двух опе­ра­ций:

1) за 3 зо­ло­тых мо­не­ты по­лу­чить 4 се­реб­ря­ных и одну мед­ную;

2) за 6 се­реб­ря­ных монет по­лу­чить 4 зо­ло­тых и одну мед­ную.

У Ни­ко­лы были толь­ко се­реб­ря­ные мо­не­ты. После по­се­ще­ний об­мен­но­го пунк­та се­реб­ря­ных монет у него стало мень­ше, зо­ло­тых не по­яви­лось, зато по­яви­лось 35 мед­ных. На сколь­ко умень­ши­лось ко­ли­че­ство се­реб­ря­ных монет у Ни­ко­лы?

Ответ 10. Решение можно посмотреть здесь http://mathb.reshuege.ru/test?theme=230

Источник: http://krivoleg.blogspot.ru/2015/09/blog-post.html

егэ по математике. Базовый уровень. Задачи о монетах

Динамическое программирование: размен денег

Это запись -  пример выгодного использование рекурсии. Тем, кто еще не ознакомился, советую прочитать - Линейные рекурсия и итерация. Чего не хватает Python. Я считаю, что именно в тематике динамического программирования рекурсия побеждает всех, как говорится "в шлемах и без" :) Тут я хочу рассмотреть всем известную(а может и не всем, раз вы читаете) задачу размена денег. У неё есть несколько интерпретаций, таких как:
  1. Как дать сдачу определенной суммы, определенным набором монет
  2. Сколькими способами конь может дойти до определенного места на шахмотной доске.
  3. И др.....
*-Нравится статья? Кликни по рекламе! :)
Чтобы сочинить итеративный алгоритм для чисел Фибоначчи, нужно совсем немного смекалки. Теперь для контраста рассмотрим следующую задачу:
Сколькими способами можно разменять сумму в 1 доллар, если имеются монеты по 50, 25, 10, 5 и 1 цент?
В более общем случае, можно ли написать процедуру подсчета способов размена для произвольной суммы денег? У этой задачи есть простое решение в виде рекурсивной процедуры. Предположим, мы как-то упорядочили типы монет, которые у нас есть. В таком случае верно будет
следующее уравнение:

Число способов разменять сумму a с помощью n типов монет равняется
  • числу способов разменять сумму a с помощью всех типов монет, кроме первого,плюс
  • число способов разменять сумму a − d с использованием всех n типов монет, где d — достоинство монет первого типа.
Чтобы увидеть, что это именно так, заметим, что способы размена могут быть поделены на две группы: те, которые не используют первый тип монеты, и те, которые его используют. Следовательно, общее число способов размена какой-либо суммы равно числу способов разменять эту сумму без привлечения монет первого типа плюс число способов размена в предположении, что мы этот тип используем. Но последнее число равно числу способов размена для суммы, которая остается после того, как мы один раз употребили первый тип монеты.
Таким образом, мы можем рекурсивно свести задачу размена данной суммы к задаче размена меньших сумм с помощью меньшего количества типов монет. Внимательно рассмотрите это правило редукции и убедите себя, что мы можем использовать его для описания алгоритма, если укажем следующие вырожденные случаи:
  • Если a в точности равно 0, мы считаем, что имеем 1 способ размена.
  • Если a меньше 0, мы считаем, что имеем 0 способов размена.
  • Если n равно 0, мы считаем, что имеем 0 способов размена.
Это описание легко перевести в рекурсивную процедуру:
def countChange(amount): return cc(amount, 5) def cc(amount, kindsOfCoins): if amount==0: return 1 if amount<0 or kindsOfCoins==0: return 0 else: return cc(amount, kindsOfCoins-1)+cc(amount-firstDenomination(kindsOfCoins), kindsOfCoins) def firstDenomination(kindsOfCoins): if kindsOfCoins==1: return 1#1 цент elif kindsOfCoins==2: return 5#5 центов elif kindsOfCoins==3: return 10#10 центов elif kindsOfCoins==4: return 25#25 центов else: return 50#50 центов Процедура firstDenomination принимает в качестве входа число доступных типов монет и возвращает достоинство первого типа. Здесь мы упорядочили монеты от самой крупной к более мелким, но годился бы и любой другой порядок.
Проверим countChange(100) - выдает нам 292 комбинации размена 100 центов.
Используемая литература:
  1. http://mitpress.mit.edu/sicp/
Источник: http://py-algorithm.blogspot.ru/2011/04/blog-post_20.html
Интересное