Задача о вероятности, Задача полностью решена |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Задача о вероятности, Задача полностью решена |
Zxzc |
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
Помогите решить задачу:
Мальчик накапливал в копилке деньги. Однажды он увидел в магазине некий товар стоимостью S. Дело в том что копилка заполнена не до конца, а разбивать ее можно лишь при 100% уверенности, что количества денег будет достаточно. Но он не помнит сколько монет какого достоинства клал в копилку. Также известна масса пустой копилки и, конечно, текущая масса. Известны соотношения Номинал <--> Масса монеты. Нужно определить минимальную вероятность и если она равна 100% вывести:"Вперед!!!!!!!!!!!" Я решил задачу, получилось что количество вложенных циклов равно количеству разновидностей монет. Проблема в том, что заранее не известно число разновидностей монет. Также важно, что монеты, номинал которых больше, не всегда тяжелее. Но это не проблема... Препод предложил идти через двумерный массив(M,N его - большие числа). И каким-то замысловатым способом из 2-х массивов(в первом - номиналы, во втором - массы) получаем массив [m,n]-й элемент к-рого - минимальное кол-во денег... Потом он сам запутался... Мда.. Давно я так не попадался... Сообщение отредактировано: Zxzc - |
volvo |
Сообщение
#2
|
Гость |
Цитата(Zxzc @ 6.05.2006 22:33) Я решил задачу, получилось что количество вложенных циклов равно количеству разновидностей монет. Проблема в том, что заранее не известно число разновидностей монет. Про рекурсию не слышал никогда? По-моему это как раз то, что ты описываешь... Неплохо было бы твой код посмотреть, конечно, чтобы быть полностью уверенным... |
Zxzc |
Сообщение
#3
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
, рекурсия не причем.
Вот моё, абсолютно не массовое, решение: Пусть имеются три вида монет массами m1, m2 и m3 и достоинством d1,d2,d3. MaxAvail - "максимальное число переборов" - найдем по формуле (P/Вес самой дешевой). P - вес монет, S - стоимость товара. Тогда все сводится к For i:=1 to MaxAvail do Но это решение не верно т.к. 1. Число разновидностей не известно заранее. 2. Если бы меньшей монете соответствовал меньший вес, то задача решалась бы в 2 строчки: If P/Massa_min>S/Dostoinstvo_min then Write('Может не хватить!') Может мы что-то сможем получить, развивая второе рассуждение... P.S. На дискете у меня есть 2 варианта решения препода. Но вот незадача: "DISK NOT FORMATED. DO YOU WANT FORMAT IT NOW?" Если у меня получится таки достать файлы с исходниками я сразу же их выложу. А иначе до конца выходных... |
volvo |
Сообщение
#4
|
Гость |
Цитата(Zxzc @ 7.05.2006 22:51) , рекурсия не причем. Уверен? Я - нет... Смотри сюда (если твое, "не массовое решение", верно): const |
мисс_граффити |
Сообщение
#5
|
просто человек Группа: Пользователи Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
2. Если бы меньшей монете соответствовал меньший вес, то задача решалась бы в 2 строчки: If P/Massa_min>S/Dostoinstvo_min then Write('Может не хватить!') Если такое решение допустимо, кто нам мешает аналогично посчитать для каждого вида монет? количество видов известно, запускаем цикл и хранить результат, например, в переменной типа boolean (наверняка хватает/не хватает). только, по-моему, со знаком промахнулся. -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
zZz |
Сообщение
#6
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
а не судьба определить удельное достоинство каждой монеты(достоинство/масса), это как раз то, насколько я понимаю, что имел в виду препод, говоря о массивах, и если минимальное удельное достоинство * массу монет внутри >= необходимой сумме то точно хватит, аналогично можно проверить на точно не хватит...
|
Zxzc |
Сообщение
#7
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
volvo, MaxAvail в моем решении найден не верно. Говорю же "не массовое"
zZz Решение похоже на правильное... Тогда задача решается с одним массивом array[1..100,1..2] - первое число достоинство, второе - масса. В цикле вычисляем по твоей формуле и, на лету, ищем минимальное... Отлично! |
zZz |
Сообщение
#8
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
одно маленькое дополнение: может получиться так что монет с этим миниальным удельным достоинством нельзя набрать целое количество так чтобы они полностью покрыли массу монет в копилке... так что надо придумать как делать проверку еще на этот фактор и учитывать и возможность нахождения в копилке других монет... такая вот неприятность... сам уже заинтересовался как сделать эту проверку, жаль времени нет, к экзаменам готовлюсь... а так бы обязательно...
Сообщение отредактировано: zZz - |
Zxzc |
Сообщение
#9
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
Цитата вот такая вот неприятность... Да вся эта задача сплошная неприятность!!! Продолжаем в двух направлениях: 1. Нахождение MaxAvail. 2. Неприятность ZzZ'та. Хотя, на мой взгляд обе неприятности имеют одни корни - несоответствие "меньшая масса <--> меньшее достоинство". Нужно это как-то себе представить. Вот. 5 копеек весят 10 грамм, 10 копеек - 8. Ээээ... У нас в копилке 40 грамм. Наскребем ли мы 50 копеек? Нет, т.к. 40/10*5=20 копеек. Как я получил эту формулу?!! АГА!!! min_money=P/P_mon*D_mon --> Минимальная сумма, набираемая монетами данного типа. Дальше: В цикле, для каждого типа монет. Теорема: Сумма, набираемая монетами типа с минимальным удельным достоинством, всегда меньше суммы, набираемая монетами этого типа и любого другого типа. |
zZz |
Сообщение
#10
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
предлагаю найти число монет мин удельного достоинства, которое может поместиться в копилку не переполняя массу, обозначим это кол-во за N, тогда можно найти массу которую необходимо добрать, тут следует ввести перебор(других вариантов у меня пока нет) в котором мы можем прибавлять любое количество монет большего уд достоинства и отнимать от 0 до N минимального до момента когда оставшаяся масса компенсируется... вот так сказать эскизный вариант... ничего кроме как удачи пожелать не могу...
|
Zxzc |
Сообщение
#11
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
5 копеек, имея БОЛЬШИЙ вес, "поглотят" БОЛЬШЕ от общего веса, а значит их сумма будет меньше!!!! И ЭТО уже ИХ проблема - а нам лучше - мы же ищем минимальную сумму. Но пусть все нормально - 5 копеек имеют МЕНЬШИЙ вес и если и][... ТАК! Попустительством назовем ситуацию, при которой одинаковая по весу масса монет младшего разряда ценнее чем старшего... Т.Е. В 10 граммах 10-копеечных монет, массой 10 грамм каждая находится 10 копеек. В 10 граммах 5-копеечных монет массой по 8 грамм находится ~7 копеек. А что если масса не 8, а 3 грамма. Тогда ~16 копеек, а значит 10 копеек попустительствуют 5-ти. Предложение: Берем меньшую по достоинству монету[1] и смотрим попустительствует ли ей монета[2] если да то смотрим попустительствует ли ей (первой) [3] и до тех пор, пока не найдем монету которая не попустительствует. Последнюю монету, которая попустительствовала, назовем активной. Если ни одна ни п.(я запарился писать это слово) первой то первая - активная. Для активной монеты act: Минимальная сумма=P/P_act*D_act. Хм.. Я что, РЕШИЛ ЗАДАЧУ?!!!! |
zZz |
Сообщение
#12
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
по-моему это все то нахождение монеты с наименьшей удельной массой/достоинством только в более сложной форме, и все равно встаёт та загвоздка ... всё больше убеждаюсь что задачу эту без перебора не решить(хотя может я и не прав)
|
Zxzc |
Сообщение
#13
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
Цитата монет с этим миниальным удельным достоинством нельзя набрать целое количество так чтобы они полностью покрыли массу монет в копилке А нам это надо? Удельное достоинство изначально подразумевает не целые числа. Мы ищем не минимальное количество медяшек, а их сумму! Или я не прав? А! Я наконец-то понял суть проблемы. Раньше я трактовал ее несколько иначе! Сообщение отредактировано: Zxzc - |
Lapp |
Сообщение
#14
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Заинтересовала меня эта задачка тоже.. Мужики, вы зря не слушаете volvo - рекурсия тут решает все проблемы в несколько строчек. План примерно такой:
1. Подбираем удобную шкалу, чтоб удельные стоимости (УС) были целыми. 2. Упорядочиваем все типы монет в порядке возрастания УС. 3. Убираем лишние монеты (все, что можно набрать 2-ками весом в 2г, можно набрать и копейками весом 1г - значит, двушки не нужны) 4. Делим полный вес на вес монеты с наименьшей УС (№1). Если их количество вышло нецелым, вычитаем их массу из начальной массы, убираем монету №1 из расмотрения и повторяем то же самое с новой массой и новым набором монет. Если неудачно - убираем одну монету №1 и повторяем. И так до тех пор, пока не будет достигнуто соответствие либо не будет безрезультатно перебрано все. Ниже даю код. Ошибок, вроде, нет, но проверял не очень тщательно. Если есть вопросы - пишите.. const -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
Сообщение
#15
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
А! Я наконец-то понял суть проблемы. Раньше я трактовал ее несколько иначе! Сейчас я перечитал свой пост - не очень-то ясно написано.. . Переписывать (без специальных запросов), пожалуй, не буду, но немного добавлю. Общий вес монет задается константой S. Набор монет задается в типизированной константе Coins. В каждой записи указываются номинал монеты (v, от слова value) и вес (w, от слова weight). Число записей (число различных типов монет) задается константой M (в моем примере 6 разичных монет достоинством 1, 2, 5, 10, 20 и 50 единиц (копеек ), соответственно весом 4, 8, 20, 3, 6 и 2 единицы (грамм). Монеты могут идти в любом порядке. Если невозможно подобрать комбинацию монет с заданным весом S, то программа выдает фразу "No match found" (совпадение не найдено). Если найдена искомая комбинация монет (согласно логике поиска, она обязательно минимальная [см. P.S.]), то выводится соответствующая сумма в единцах (копейках). Я думаю, было бы полезно выводить и способ, которым набрана данная сумма. Для этого нужно добавить одну строчку, что я сейчас и сделаю... [в течение некоторого времени ожесточенно колотит по клаве, чешет репу и наливает чай] ...сделал! В результате получилась фактически новая версия . Кроме прочего, старая версия странным образом глючила.. Я так и не смог разобраться, в чем дело, поскольку после добавления определенных переменных и операторов для отладки она глючить перестала, вроде. Если кто-то заметит глюки, прошу сказать мне о них. Еще добавлю, что результаты (зависимость минимально возможной суммы от веса) выглядят довольно забавно . Радостные предвкушения от ощущения тяжести руках может смениться разочарованием (например, при весе 100), а легкость (вес 5) может дать неплохой навар! Распределение монет по весам я взял чисто от балды, оно не имеет к обычной реальности никакого отношения (думаю, это и не требовалось). Рекомендую поиграться с ним, чтобы понять суть проблемы.. И последнее: хочу обратить внимание на пользу рекурсии. Фактически, все решение укладывается в функцию MinFill. Все остальное - подготовка ряда значений и весов монет. Если принять, что он уже упорядоченный и без лишних значений - прога уменьшится драматически . Итак, вот новая версия. Кстати, она запрашивает вес монет с клавиатуры..
P.S. Моя фраза об обязательной минимальности резульата на самом деле нуждается в доказательстве. Я уверен в этом довольно сильно, но руку на отсечение пока не дам... Кто это докажет/опровергнет? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Zxzc |
Сообщение
#16
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
Я понял ход твоих мыслей! Т.е. если не будет найдено соответствия - масса введена не верно...
Цитата P.S.Моя фраза об обязательной минимальности резульата на самом деле нуждается в доказательстве. Я уверен в этом довольно сильно, но руку на отсечение пока не дам... Кто это докажет/опровергнет? Это выглядит довольно правдоподобно, но с доказательством труднее. Я сделал несколько набросков доказательства, но пока ничего не выходит. Вчера предложил эту задачу одногрупнику, и если я - лучший в группе, то он из отстающих. За 20 секунд он решил задачу методом zZz, еще через 10 столкнулся с проблемой... Я, конечно, описывал ему задачу в упрощенном варианте, но все-таки...где после этого логика и справедливость? Наверное я загнался... Выспаться бы... |
Lapp |
Сообщение
#17
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
> Я понял ход твоих мыслей!
> Т.е. если не будет найдено соответствия - масса введена не верно... Именно так. Не все массы можно скомбинировать из монет. Например, масса 1 в моем наборе не получится никогда.. > Это выглядит довольно правдоподобно, но с доказательством труднее. > Я сделал несколько набросков доказательства, но пока ничего не выходит. А нужно ли здесь строгое доказательство? Это же не комбинаторика, а программирование.. Нет, я не имею в виду, что допустимы неверные решения, но строгость доказательства... кхм.. Ладно, я попробую сделать доказательство, если нужно.. Глюков в моей проге пока не заметил? Сообщение отредактировано: lapp - -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Zxzc |
Сообщение
#18
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
Я сейчас готовлюсь к экзаменам и у меня даже нет времени провести несколько тестов для твоей программы и программы volvo, чтобы сравнить результаты... И решения все просматриваю только поверхностно... Надеюсь, в выходные выкрою время...
P.S. Почему в основной панели смайликов нет ? Это же основа... |
Zxzc |
Сообщение
#19
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
Внимание! Я достал-таки исходники!
1: const Len=100; В чем суть этого решения? Это,( var e,f,n,i,j:integer; ) решение являлется усовершенствованной версией предыдущего, более оптимальное, но и более запутанное. |
Lapp |
Сообщение
#20
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Внимание! Я достал-таки исходники! Первое решение у меня так и не заработало - там явная ошибка в реализации алгоритма, я не стал возиться исправлять. А второе - работает лучше моего. Мое дает неминимальный набор. Слишком рано лезет в область дорогих монет. В принципе понятно, где у меня ошибка, но не знаю, стоит ли исправлять.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 27.12.2024 0:59 |