Математический форум Math Help Planet
http://mathhelpplanet.com/

Задачка про ведра
http://mathhelpplanet.com/viewtopic.php?f=10&t=40685
Страница 2 из 3

Автор:  david1710 [ 28 апр 2015, 08:20 ]
Заголовок сообщения:  Re: Задачка про ведра

Спасибо, очень заинтересован в этом алгоритме.

Автор:  Andy [ 28 апр 2015, 08:41 ]
Заголовок сообщения:  Re: Задачка про ведра

david1710, дело в том, что решение задачи при [math]m-n=1[/math] и целочисленном количестве воды, которое требуется налить, не превосходящем [math]n,[/math] известно. Смотрите, например, здесь: http://www.postupivuz.ru/vopros/14788.htm. Ели это то, что Вам нужно, то вопрос закрыт. Но в таком случае Вы неточно сформулировали задачу в своём первом сообщении. :)

Если [math]m-n\in\mathbb{N},~m-n>1,[/math] то алгоритм усложняется. Но, по моим представлениям, может быть реализован при помощи только двух имеющихся вёдер...

При нецелочисленном количестве воды, которое требуется налить, конечно, только двумя вёдрами не обойтись...

Автор:  david1710 [ 28 апр 2015, 08:45 ]
Заголовок сообщения:  Re: Задачка про ведра

Andy писал(а):
david1710, дело в том, что решение задачи при [math]m-n=1[/math] и целочисленном количестве воды, которое требуется налить, не превосходящем [math]n,[/math] известно. Смотрите, например, здесь: http://www.postupivuz.ru/vopros/14788.htm. Ели это то, что Вам нужно, то вопрос закрыт. Но в таком случае Вы неточно сформулировали задачу в своём первом сообщении. :)

При нецелочисленном количестве воды, которое требуется налить, конечно, только двумя вёдрами не обойтись...


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

Автор:  Andy [ 28 апр 2015, 08:48 ]
Заголовок сообщения:  Re: Задачка про ведра

david1710, я уточнил своё сообщение для случая [math]m-n>1.[/math] Прочитайте его снова.

Пока я рассматриваю тот случай, с которого Вы предлагали начать, полагая, что [math]m-n=1[/math] и требуется налить целочисленное количество воды, не превосходящее [math]n.[/math]

Автор:  david1710 [ 28 апр 2015, 08:53 ]
Заголовок сообщения:  Re: Задачка про ведра

Я предлагал начать со случая, когда НОД (найменьший общий делитель) = 1. Например, когда ведра по 101 и 103 литра.

Автор:  Andy [ 28 апр 2015, 08:57 ]
Заголовок сообщения:  Re: Задачка про ведра

david1710, по приведенной мной ссылке рассматривается задача с вёдрами емкостями [math]15[/math] и [math]14[/math] литров. Это тоже взаимно простые числа.

Какими же, однако, должны быть люди, чтобы носить вёдра ёмкостью [math]101[/math] и [math]103[/math] литра! :crazy:

Но всё-таки, Вы можете записать условие точно так, как оно записано в первоисточнике? Откуда эта задача?

Автор:  venjar [ 28 апр 2015, 08:58 ]
Заголовок сообщения:  Re: Задачка про ведра

Здесь

http://pmpu.ru/vf4/numtheory

есть теорема (с доказательством) в разделе "Линейное представление НОД".

Из нее все следует.

Автор:  Andy [ 28 апр 2015, 09:04 ]
Заголовок сообщения:  Re: Задачка про ведра

venjar, Вы предполагаете, что такой уровень изложения подходит школьнику? :shock:

Автор:  david1710 [ 28 апр 2015, 09:09 ]
Заголовок сообщения:  Re: Задачка про ведра

Задача "от меня", так что все претензии по ее формулировке туда же...

ОК, еще раз условия:

Даны три натуральных числа m,n и k. Предположим что k<n<m.
Даны два ведра по m и n литров и бесконечное количество воды. При каких условиях для m и n можно измерить либое количество k воды.

Моё предположение, что если НОД(m,n)=1, то для любового натурального k<n.
Если НОД(m,n)>1, то только если k делиться на НОД(m,n).
Вопрос как это доказать...

Я чувствую, что это связано с теоремой об остатках и Эвклидовом алгоритме, но не могу увязать представление k через m и n с переливанием.

Автор:  Shadows [ 28 апр 2015, 09:11 ]
Заголовок сообщения:  Re: Задачка про ведра

Andy писал(а):
david1710, и, наверное, нужно полагать, что у нас, помимо вёдер и источника воды, есть ещё и некоторая ёмкость (неограниченной вместимости?)?..
Нет, дополнительной емкости нет.
Andy писал(а):
Возможно, что к концу дня подсознание выработает конструктивный алгоритм переливания
Алгоритм очень простой. Переливаем из меньшего в большой,пока не заполнится, выливаем,продолжаем с остатком. Получатся все остатки от 1 до n.

Страница 2 из 3 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/