| Математический форум 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] литра! Но всё-таки, Вы можете записать условие точно так, как оно записано в первоисточнике? Откуда эта задача? |
|
| Автор: | venjar [ 28 апр 2015, 08:58 ] |
| Заголовок сообщения: | Re: Задачка про ведра |
Здесь http://pmpu.ru/vf4/numtheory есть теорема (с доказательством) в разделе "Линейное представление НОД". Из нее все следует. |
|
| Автор: | Andy [ 28 апр 2015, 09:04 ] |
| Заголовок сообщения: | Re: Задачка про ведра |
venjar, Вы предполагаете, что такой уровень изложения подходит школьнику?
|
|
| Автор: | 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/ |
|