Задача о вероятности, Задача полностью решена |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Задача о вероятности, Задача полностью решена |
Zxzc |
6.05.2006 22:33
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
Помогите решить задачу:
Мальчик накапливал в копилке деньги. Однажды он увидел в магазине некий товар стоимостью S. Дело в том что копилка заполнена не до конца, а разбивать ее можно лишь при 100% уверенности, что количества денег будет достаточно. Но он не помнит сколько монет какого достоинства клал в копилку. Также известна масса пустой копилки и, конечно, текущая масса. Известны соотношения Номинал <--> Масса монеты. Нужно определить минимальную вероятность и если она равна 100% вывести:"Вперед!!!!!!!!!!!" Я решил задачу, получилось что количество вложенных циклов равно количеству разновидностей монет. Проблема в том, что заранее не известно число разновидностей монет. Также важно, что монеты, номинал которых больше, не всегда тяжелее. Но это не проблема... Препод предложил идти через двумерный массив(M,N его - большие числа). И каким-то замысловатым способом из 2-х массивов(в первом - номиналы, во втором - массы) получаем массив [m,n]-й элемент к-рого - минимальное кол-во денег... Потом он сам запутался... Мда.. Давно я так не попадался... Сообщение отредактировано: Zxzc - 13.05.2006 21:44 |
volvo |
6.05.2006 23:06
Сообщение
#2
|
Гость |
Цитата(Zxzc @ 6.05.2006 22:33) Я решил задачу, получилось что количество вложенных циклов равно количеству разновидностей монет. Проблема в том, что заранее не известно число разновидностей монет. Про рекурсию не слышал никогда? По-моему это как раз то, что ты описываешь... Неплохо было бы твой код посмотреть, конечно, чтобы быть полностью уверенным... |
Zxzc |
7.05.2006 22:51
Сообщение
#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 |
7.05.2006 23:39
Сообщение
#4
|
Гость |
Цитата(Zxzc @ 7.05.2006 22:51) , рекурсия не причем. Уверен? Я - нет... Смотри сюда (если твое, "не массовое решение", верно): const |
мисс_граффити |
8.05.2006 9:23
Сообщение
#5
|
просто человек Группа: Модераторы Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
2. Если бы меньшей монете соответствовал меньший вес, то задача решалась бы в 2 строчки: If P/Massa_min>S/Dostoinstvo_min then Write('Может не хватить!') Если такое решение допустимо, кто нам мешает аналогично посчитать для каждого вида монет? количество видов известно, запускаем цикл и хранить результат, например, в переменной типа boolean (наверняка хватает/не хватает). только, по-моему, со знаком промахнулся. -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
zZz |
8.05.2006 10:25
Сообщение
#6
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
а не судьба определить удельное достоинство каждой монеты(достоинство/масса), это как раз то, насколько я понимаю, что имел в виду препод, говоря о массивах, и если минимальное удельное достоинство * массу монет внутри >= необходимой сумме то точно хватит, аналогично можно проверить на точно не хватит...
|
Zxzc |
8.05.2006 21:28
Сообщение
#7
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
volvo, MaxAvail в моем решении найден не верно. Говорю же "не массовое"
zZz Решение похоже на правильное... Тогда задача решается с одним массивом array[1..100,1..2] - первое число достоинство, второе - масса. В цикле вычисляем по твоей формуле и, на лету, ищем минимальное... Отлично! |
zZz |
8.05.2006 21:53
Сообщение
#8
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
одно маленькое дополнение: может получиться так что монет с этим миниальным удельным достоинством нельзя набрать целое количество так чтобы они полностью покрыли массу монет в копилке... так что надо придумать как делать проверку еще на этот фактор и учитывать и возможность нахождения в копилке других монет... такая вот неприятность... сам уже заинтересовался как сделать эту проверку, жаль времени нет, к экзаменам готовлюсь... а так бы обязательно...
Сообщение отредактировано: zZz - 8.05.2006 22:00 |
Zxzc |
8.05.2006 22:23
Сообщение
#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 |
8.05.2006 22:50
Сообщение
#10
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
предлагаю найти число монет мин удельного достоинства, которое может поместиться в копилку не переполняя массу, обозначим это кол-во за N, тогда можно найти массу которую необходимо добрать, тут следует ввести перебор(других вариантов у меня пока нет) в котором мы можем прибавлять любое количество монет большего уд достоинства и отнимать от 0 до N минимального до момента когда оставшаяся масса компенсируется... вот так сказать эскизный вариант... ничего кроме как удачи пожелать не могу...
|
Zxzc |
8.05.2006 22:51
Сообщение
#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 |
8.05.2006 23:25
Сообщение
#12
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
по-моему это все то нахождение монеты с наименьшей удельной массой/достоинством только в более сложной форме, и все равно встаёт та загвоздка ... всё больше убеждаюсь что задачу эту без перебора не решить(хотя может я и не прав)
|
Zxzc |
9.05.2006 10:31
Сообщение
#13
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
Цитата монет с этим миниальным удельным достоинством нельзя набрать целое количество так чтобы они полностью покрыли массу монет в копилке А нам это надо? Удельное достоинство изначально подразумевает не целые числа. Мы ищем не минимальное количество медяшек, а их сумму! Или я не прав? А! Я наконец-то понял суть проблемы. Раньше я трактовал ее несколько иначе! Сообщение отредактировано: Zxzc - 9.05.2006 16:16 |
Lapp |
9.05.2006 14:52
Сообщение
#14
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Заинтересовала меня эта задачка тоже.. Мужики, вы зря не слушаете volvo - рекурсия тут решает все проблемы в несколько строчек. План примерно такой:
1. Подбираем удобную шкалу, чтоб удельные стоимости (УС) были целыми. 2. Упорядочиваем все типы монет в порядке возрастания УС. 3. Убираем лишние монеты (все, что можно набрать 2-ками весом в 2г, можно набрать и копейками весом 1г - значит, двушки не нужны) 4. Делим полный вес на вес монеты с наименьшей УС (№1). Если их количество вышло нецелым, вычитаем их массу из начальной массы, убираем монету №1 из расмотрения и повторяем то же самое с новой массой и новым набором монет. Если неудачно - убираем одну монету №1 и повторяем. И так до тех пор, пока не будет достигнуто соответствие либо не будет безрезультатно перебрано все. Ниже даю код. Ошибок, вроде, нет, но проверял не очень тщательно. Если есть вопросы - пишите.. const -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
10.05.2006 4:18
Сообщение
#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 |
12.05.2006 6:28
Сообщение
#16
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
Я понял ход твоих мыслей! Т.е. если не будет найдено соответствия - масса введена не верно...
Цитата P.S.Моя фраза об обязательной минимальности резульата на самом деле нуждается в доказательстве. Я уверен в этом довольно сильно, но руку на отсечение пока не дам... Кто это докажет/опровергнет? Это выглядит довольно правдоподобно, но с доказательством труднее. Я сделал несколько набросков доказательства, но пока ничего не выходит. Вчера предложил эту задачу одногрупнику, и если я - лучший в группе, то он из отстающих. За 20 секунд он решил задачу методом zZz, еще через 10 столкнулся с проблемой... Я, конечно, описывал ему задачу в упрощенном варианте, но все-таки...где после этого логика и справедливость? Наверное я загнался... Выспаться бы... |
Lapp |
12.05.2006 6:42
Сообщение
#17
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
> Я понял ход твоих мыслей!
> Т.е. если не будет найдено соответствия - масса введена не верно... Именно так. Не все массы можно скомбинировать из монет. Например, масса 1 в моем наборе не получится никогда.. > Это выглядит довольно правдоподобно, но с доказательством труднее. > Я сделал несколько набросков доказательства, но пока ничего не выходит. А нужно ли здесь строгое доказательство? Это же не комбинаторика, а программирование.. Нет, я не имею в виду, что допустимы неверные решения, но строгость доказательства... кхм.. Ладно, я попробую сделать доказательство, если нужно.. Глюков в моей проге пока не заметил? Сообщение отредактировано: lapp - 12.05.2006 6:42 -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Zxzc |
12.05.2006 21:52
Сообщение
#18
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
Я сейчас готовлюсь к экзаменам и у меня даже нет времени провести несколько тестов для твоей программы и программы volvo, чтобы сравнить результаты... И решения все просматриваю только поверхностно... Надеюсь, в выходные выкрою время...
P.S. Почему в основной панели смайликов нет ? Это же основа... |
Zxzc |
13.05.2006 12:10
Сообщение
#19
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Максим Репутация: 0 |
Внимание! Я достал-таки исходники!
1: const Len=100; В чем суть этого решения? Это,( var e,f,n,i,j:integer; ) решение являлется усовершенствованной версией предыдущего, более оптимальное, но и более запутанное. |
Lapp |
13.05.2006 14:12
Сообщение
#20
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Внимание! Я достал-таки исходники! Первое решение у меня так и не заработало - там явная ошибка в реализации алгоритма, я не стал возиться исправлять. А второе - работает лучше моего. Мое дает неминимальный набор. Слишком рано лезет в область дорогих монет. В принципе понятно, где у меня ошибка, но не знаю, стоит ли исправлять.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 19.04.2024 18:00 |