Задачка по информатике |
Задачка по информатике |
Yurka |
9.09.2010 22:51
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 143 Пол: Мужской Репутация: 0 |
На мебельном комбинате изготовляют книжные полки длиной 1 м и в ширину 20 см, а на производство
завезли лишь доски длиной 75 см и в ширину 30 см. Мебельный комбинат не может остановить производственный процесс, потому будет изготовлять книжные полки из имеющихся на производстве досок. Самый простой вариант изготовления полки заключается в отпиливании вдоль доски полоски в ширину 10 см и последующем распиливании ее на три одинаковых части по 25 см. После этого нужно приклеить к доске две получены части, увеличив этой операцией ее длину. Однако этот вариант решения не оптимален за количеством операций (три операции отпиливания, две — склеивание). Кроме этого, изготовленная таким образом книжная полка буде непрочной в том месте, где меньшие части приклеено к большей основной доске. Предложите вариант изготовления книжной полки из имеющихся досок указанных размеров за меньшее количество технологических операций. Обязательным условием выбора оптимального варианта есть учет прочности полученной полки. (рисунок к условию в файле) Хотя бы подтолкните на более оптимальный вариант. ) Вариант мой такой: обрезаем 10 см полоску в одной доски - в результате имеем доску 75 см на 20 см и полоску 75 см на 10 см (1 операция обрезания). В другой доске обрезаем полоску 10 см и полоску 25 см от оставшейся доски 75 на 20. В результате имеем полоску 72 на 10, кусок 25 на 20 и кусок 50 на 20 (2 операции обрезания). Можем создать полку 1 м на 20 см из 75 см на 20 см и 25 см на 20 см ( 1 операция склеивания) + доску 75 на 20 из двух кусков по 75 см на 10 см (1 операция склеивания) и остается ещё доска 50 на 20. Следующую третью доску режем аналогично второй. В результате имеем два куска по 50 на 20 (клеим и получаем ещё оду полку+1 операция склеивания), один кусок 25 на 20 и один кусок 75 на 20 ( из склеенных частей 75 на 10). Клеим полку из кусков 75 на 20 и 25 на 20+1 операция склеивания. В результате имеем три полки (одна из полок менее прочная, та что из двух кусков 75 на 10 и одного 25 на 20), 5 операций обрезания и 4 операции склеивания+безотходный вариант )). Метод описанный в условии дает 9 операций обрезания и 6 операций склеивания на 3 полки. Эскизы прикрепленных изображений |
Lapp |
10.09.2010 0:30
Сообщение
#2
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Гм.
Я не понял - тебе что надо? Просто предложить вариант распилки-склейки или тебе нужен алгоритм, для программы, которая будет искать этот вариант? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
10.09.2010 4:11
Сообщение
#3
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Хорошо, примем, что надо просто предложить вариант раскроя..
имеем три полки (одна из полок менее прочная, та что из двух кусков 75 на 10 и одного 25 на 20), 5 операций обрезания и 4 операции склеивания+безотходный вариант )). Во первых, я не понимаю, почему ты назвал его безотходным. Смотри, я не поленился сделать то, что должен был сделать ты - картинку : Один цвет - одна полка, незакрашенное - остаток . Но это ладно, остаток можно использовать потом (только надо сказать, как - и, мне кажется, это увеличит количество склеек/распилов на одну полку). Но главная твоя проблема - с прочностью. По условию (читай внимательно!) признаком непрочности является прямая склейка по ширине, с одного края до другого. У тебя такие склейки есть во всех трех полках! Что скажешь? Добавлено через 4 мин. Кстати, про безотходность ничего не сказано в условии. Хоть делай одну спичку из бревна, остальное выбрасывай.. И еще: нужно, наверное, характеризовать результат каким-то одним параметром. Это может быть, мне кажется, суммарное число операций на одну полку. Для способа в условии это (9+6)/3=5, для твоего способа (5+4)/3=3. Это число не обязано быть целым. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
10.09.2010 4:47
Сообщение
#4
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Если я прав, и прочность определяется наличием склеек от края до края по ширине, то это исключает наличие широких (шириной 20) кусков вообще. И тогда можно сделать, например, так..
1. берем 8 досок; 2. все их распускаем вдоль на 3 полоски 75х10 : 111111111111111 444444444444444- это 2*8=16 распилов; 3. из полученных 24 полосок берем 7; 4. склеиваем их вместе вот так (сдвиг 25 см, пробелы для наглядности): 111111111111111 333333333333333 555555555555555 777777777777777- это 6 склеек; 5. восьмую полоску распиливаем на две по 25 и 50: 88888 8888888888- еще 1 распил; 6. полученные куски подклеиваем к большой склейке в начале и в конце (теперь без пробелов): 111111111111111333333333333333555555555555555777777777777777- еще 2 склейки (8 склеек); 7. полученную склейку 300х20 распливаем на 3 готовые полки: 11111111111111133333 33333333335555555555 55555777777777777777- еще 2 распила (19 распилов); 8. повторяем пункты с 3 по 7 еще 2 раза, то есть всего 3 раза; 9. получаем 9 готовых полок; 10. на все затрачено 16+1х3=19 распилов и 8х3=24 склеек; 11. на одну полку приходится 19/9=2+1/9 распилов и 24/9=2+2/3 склеек; 12. отходов 0; 13. прочность высокая (нет ни одной сквозной склейки по ширине). Если допустить возможность начальной склейки не из 7 полос, а из 15 (или больше) то первое число можно уменьшить. В пределе бесконечной длины промежуточной клееной доски (пп. 4 и 6) получим 16/9=1+7/9 распила на полку. Мог наврать, проверь (кажется, склейки тоже можно экономить увеличением длины, но что-то не выходит).. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Yurka |
10.09.2010 8:02
Сообщение
#5
|
Пионер Группа: Пользователи Сообщений: 143 Пол: Мужской Репутация: 0 |
Если я прав, и прочность определяется наличием склеек от края до края по ширине, то это исключает наличие широких (шириной 20) кусков вообще. И тогда можно сделать, например, так.. 1. берем 8 досок; 2. все их распускаем вдоль на 3 полоски 75х10 : 111111111111111 444444444444444- это 2*8=16 распилов; 3. из полученных 24 полосок берем 7; 4. склеиваем их вместе вот так (сдвиг 25 см, пробелы для наглядности): 111111111111111 333333333333333 555555555555555 777777777777777- это 6 склеек; 5. восьмую полоску распиливаем на две по 25 и 50: 88888 8888888888- еще 1 распил; 6. полученные куски подклеиваем к большой склейке в начале и в конце (теперь без пробелов): 111111111111111333333333333333555555555555555777777777777777- еще 2 склейки (8 склеек); 7. полученную склейку 300х20 распливаем на 3 готовые полки: 11111111111111133333 33333333335555555555 55555777777777777777- еще 2 распила (19 распилов); 8. повторяем пункты с 3 по 7 еще 2 раза, то есть всего 3 раза; 9. получаем 9 готовых полок; 10. на все затрачено 16+1х3=19 распилов и 8х3=24 склеек; 11. на одну полку приходится 19/9=2+1/9 распилов и 24/9=2+2/3 склеек; 12. отходов 0; 13. прочность высокая (нет ни одной сквозной склейки по ширине). Если допустить возможность начальной склейки не из 7 полос, а из 15 (или больше) то первое число можно уменьшить. В пределе бесконечной длины промежуточной клееной доски (пп. 4 и 6) получим 16/9=1+7/9 распила на полку. Мог наврать, проверь (кажется, склейки тоже можно экономить увеличением длины, но что-то не выходит).. Мдаааааа. Вариант, конечно очень интересный. Спасибо. Но, если учитывать только ваши пункты 1-13, то выгоды не получается, почти, в количестве операций. По моему, прочность в этой задаче, определяется просто количеством склеек и без разници по длине или по ширине. Чем меньше количество тем прочнее. P.S. Задачка из учебника по информатике для 9-х классов (украинского учебника) |
Lapp |
10.09.2010 8:58
Сообщение
#6
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Но, если учитывать только ваши пункты 1-13, то выгоды не получается, почти, в количестве операций. Ты не прав. Читай внимательно, тут нет никакой двузначности:По моему, прочность в этой задаче, определяется просто количеством склеек и без разници по длине или по ширине. Чем меньше количество тем прочнее. Цитата изготовленная таким образом книжная полка буде непрочной в том месте, где меньшие части приклеено к большей основной доске. Главное я выделил болдом. Обрати внимание: не между собой, а именно к большой. И по физике дела, если уж на то пошло, это тоже очень разумно (хотя это тут и ни причем, я понимаю)). И еще соображение: если бы речь шла об общей длине склейки, то это не вносило бы ничего такого существенного в задачу. Это просто дублирование параметра количества склеек, вот и все! А зачем?? на фига его дублировать? То есть, это все равно, что сказать: принеси мне воды, и чтоб была мокрой )).Цитата Задачка из учебника по информатике для 9-х классов (украинского учебника) Мне понравилась. Респект авторам учебника. Хотя, можно было сформулировать получше, плюс упомянуть про отходы..-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
TarasBer |
10.09.2010 9:36
Сообщение
#7
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
А лобзик, что на мебельной фабрике, может такое потянуть?
Эскизы прикрепленных изображений -------------------- |
Lapp |
10.09.2010 10:07
Сообщение
#8
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
А лобзик, что на мебельной фабрике, может такое потянуть? Это у тебя лобзик, а на мебельной фабрике дисковая пила, в просторечии "циркулярка" Предложи еще клей получше взять, тогда склейка будет прочнее дерева.. Давай по делу говорить. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Yurka |
10.09.2010 10:08
Сообщение
#9
|
Пионер Группа: Пользователи Сообщений: 143 Пол: Мужской Репутация: 0 |
Ты не прав. Читай внимательно, тут нет никакой двузначности: Главное я выделил болдом. Обрати внимание: не между собой, а именно к большой. И по физике дела, если уж на то пошло, это тоже очень разумно (хотя это тут и ни причем, я понимаю)). И еще соображение: если бы речь шла об общей длине склейки, то это не вносило бы ничего такого существенного в задачу. Это просто дублирование параметра количества склеек, вот и все! А зачем?? на фига его дублировать? То есть, это все равно, что сказать: принеси мне воды, и чтоб была мокрой )). Я согласен, что мой вариант в прочности проигрывает вашему. Вопрос втом, что важнее: количество операций или прочность (для потребителя, конечно прочность , а вот для мебельного комбината...?). Но это вопрос, действительно к авторам. Мне понравилась. Респект авторам учебника. Хотя, можно было сформулировать получше, плюс упомянуть про отходы.. Похвала такого человека как Вы - многого стоит! Так что авторы учебника мне уже должны, за рекламу . Учебник, действительно очень неплох, эта задачка имеет уровень сложности в одну звёздечку, а есть там ещё и с двумя звёздечками ). Могу дать ссылку на учебник, если интересно. |
Lapp |
10.09.2010 10:16
Сообщение
#10
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Вопрос втом, что важнее: количество операций или прочность (для потребителя, конечно прочность , а вот для мебельного комбината...?). когда посыпятся рекламации и возвраты по гарантии - меб.комбинат точно не зарадуется.. ))Я для себя принял, что просто не должно быть сквозных склеек от края до края, вот и все. Это жесткое ограничивающее условие. Цитата Похвала такого человека как Вы - многого стоит! Так что авторы учебника мне уже должны, за рекламу спасибо )).Стрясешь с них - передашь в фонд Форума, 100%.. )) Цитата Учебник, действительно очень неплох, эта задачка имеет уровень сложности в одну звёздечку, а есть там ещё и с двумя звёздечками ). Могу дать ссылку на учебник, если интересно. Кинь в "Ссылки"-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
TarasBer |
10.09.2010 10:22
Сообщение
#11
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Я пытаюсь практическое применение найти сразу, вот. Просто после окончания универа я немного поменял род деятельности на более практический, понимаете.
Можно доску 30х75 попилить по диагонали и сдвинуть на треть (на вектор (10, 25)), будет ровно 20х100, ну и два обрезка с краёв. Вот, всего 2 части, прочность получше, чем у первого варианта. Эскизы прикрепленных изображений -------------------- |
Yurka |
10.09.2010 10:38
Сообщение
#12
|
Пионер Группа: Пользователи Сообщений: 143 Пол: Мужской Репутация: 0 |
когда посыпятся рекламации и возвраты по гарантии - меб.комбинат точно не зарадуется.. )) Я для себя принял, что просто не должно быть сквозных склеек от края до края, вот и все. Это жесткое ограничивающее условие. спасибо )). Стрясешь с них - передашь в фонд Форума, 100%.. )) Кинь в "Ссылки" Ссылка Учебник Добавлено через 5 мин. Я пытаюсь практическое применение найти сразу, вот. Просто после окончания универа я немного поменял род деятельности на более практический, понимаете. Можно доску 30х75 попилить по диагонали и сдвинуть на треть (на вектор (10, 25)), будет ровно 20х100, ну и два обрезка с краёв. Вот, всего 2 части, прочность получше, чем у первого варианта. По вашему методу получается 3 распила и одна слейка+отходы. Варианты ваши интересные, спасибо. Я вот тоже крутил по всякому эти доски |
TarasBer |
10.09.2010 10:46
Сообщение
#13
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Вопрос в том, какова вообще конструкция книжной полки? Если ещё будут 2 стенки с боков, то на продольные распилы можно вовсе не обращать внимания. Поперечные опасне. Да, вариант Лаппа прочнее моего.
-------------------- |
Yurka |
10.09.2010 10:53
Сообщение
#14
|
Пионер Группа: Пользователи Сообщений: 143 Пол: Мужской Репутация: 0 |
Вопрос в том, какова вообще конструкция книжной полки? Если ещё будут 2 стенки с боков, то на продольные распилы можно вовсе не обращать внимания. Поперечные опасне. Да, вариант Лаппа прочнее моего. Выносим вердикт: вариант предложеный Lapp и есть наиболее оптимальным (если не появится чего-нибудь нового). Я в принципе "за" |
Lapp |
10.09.2010 13:15
Сообщение
#15
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
С косым распилом, конечно, неплохая идея. Поскольку про отходы в условии не сказано, можно считать ее оптимальной.
С практическим подходом тут, мне кажется, не нужно перегибать палку.. Ну, считай, что это полки-вставки, в шкаф. А вообще - это типа паркетов задача (с оговорками). А все же интересно, можно ли сделать прогу для поиска наилучшего варианта? скажем, полки a*b из досок c*d.. ? Есть целый раздел со ссылками, я его имел в виду.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 29.04.2024 3:20 |