Страница 2 из 3 ПерваяПервая 123 ПоследняяПоследняя
Показано с 21 по 40 из 50

Тема: Задачка для скучающих программистов.

  1. #21
    Новобранец
    Регистрация
    30.11.2012
    Сообщений
    94
    To Спалланцани:

    Тогда так:
    На входе массив из 2 полей - L и H.
    Предварительный прогон - если H>L, меняем их местами ("поворачиваем на 90 градусов")

    1. Сортируем массив по L (по убыванию) и Н(по возрастанию)
    2. Базовая площадь: S = L1*H1 (самый длинный прямоугольник)
    3. Сохраняем значение H1 в переменную H_Current
    4. Далее цикл по массиву со второй строки:
    Если H(i) <= H_Current, игнорируем прямоугольник, переход к следующему (он полностью закрыт предыдущим)
    иначе увеличиваем площадь S на площадь выступающего куска (S = S + (H(i) - H_Current)*L(i)) и присваиваем новое значение H_Current = H(i)
    5. Цикл закончен, результат в переменной S.
    Последний раз редактировалось Darij; 26.03.2014 в 02:37.

  2. #22
    Активный участник
    Регистрация
    26.02.2011
    Сообщений
    9,264
    Ну хорошо раз вы такие уверенные и крутые. То пусть омжно будет поворачивать ан любой угол.

    - - - Добавлено - - -

    Darij, Площадь считается не правильно.

  3. #23
    Новобранец
    Регистрация
    30.11.2012
    Сообщений
    94
    To Спалланцани:

    Повороты на угол, отличный от 90 градусов, лишены смысла - площадь меньше не будет. А вот второй вариант задачи (с пустыми коробками) был бы интереснее - классическая задача на оптимизацию с построением дерева возможных комбинаций.

  4. #24
    Активный участник Аватар для napancux
    Регистрация
    15.06.2010
    Сообщений
    631
    С заданной заранее таблицей и сортировкой - неочень У Darij все верно, вроде как.

  5. #25
    Активный участник Аватар для Enta
    Регистрация
    17.05.2010
    Сообщений
    1,898
    Цитата Сообщение от Спалланцани Посмотреть сообщение
    Ну хорошо раз вы такие уверенные и крутые. То пусть омжно будет поворачивать ан любой угол.
    омжно тебя послать?
    чтоб это решить надо пару теорем доказать. работы на пару часов.
    явно не ночью, и не без бумаги.
    а днём мне есть чем заняться, за что либо платят, либо будут платить...

    завтра может быть посмотрю.
    Если в мире будет больше эгоистов - мир станет лучше.
    Когда к власти приходят сукины дети, собачья жизнь начинается у всех.

  6. #26
    Активный участник
    Регистрация
    11.08.2011
    Сообщений
    1,712
    Цитата Сообщение от napancux Посмотреть сообщение
    А еще не обязательно добавляемая площадь при таком методе будет прямоугольником.

    так ты сортируй по убыванию длины и будут только прямоугольники.

  7. #27
    Активный участник
    Регистрация
    26.02.2011
    Сообщений
    9,264
    Darij,

    Вот так может быть.

  8. #28
    Цитата Сообщение от Darij Посмотреть сообщение
    To Спалланцани:

    Условие задачи неполное. Есть два варианта интерпретации:

    1. Проекции прямоугольников могут пересекаться. Пример - прямоугольники из бумаги складываются в стопку. Тогда при условии L<=H общая площадь стопки не может превышать (MAX(L))^2.

    2. Проекции прямоугольников пересекаться не могут. Пример - складывание пустых коробок одна в другую. Тогда прямоугольник можно поместить в другой только при условии L1<=L2, H1<=H2. В таком случае общая площадь в худшем случае (ни одна коробка не помещается в другую) будет равна сумме площадей всех прямоугольников. В лучшем случае (все коробки матрешкой складываются одна в другую) общая площадь будет равна площади самого большого прямоугольника.
    Все нормально с условиями. Сказано же, чтобы площадь была минимальной, а такое достижимо только в 1 варианте. А по теме, если нельзя поворачивать фигуры на произвольный угол, то задача совсем простая.

  9. #29
    Активный участник Аватар для napancux
    Регистрация
    15.06.2010
    Сообщений
    631
    Спалланцани, а что ты скажешь насчет моей догадки на первой странице?
    Последний раз редактировалось napancux; 25.03.2014 в 23:48.

  10. #30
    Новобранец
    Регистрация
    30.11.2012
    Сообщений
    94
    Цитата Сообщение от Спалланцани Посмотреть сообщение
    Darij,

    Вот так может быть.
    Да, так может быть. Тогда нужно прогнать первый вариант, чтобы отбросить тривиальные случаи (обе координаты прямоугольника меньше другого) - а дальше нужно центрировать все прямоугольники и поворачивать по диагонали предыдущего. А вот посчитать в таком случае площадь пересечения - задача муторная, с разбиением на треугольники по точкам пересечения. Это больше из области прикладной геометрии или компьютерной графики.. Решение будет лишено какого-либо изящества.

    P. S. Почему ты считаешь мой расчет площади неправильным? Там все корректно..

    - - - Добавлено - - -

    Цитата Сообщение от Федор Сумкин Посмотреть сообщение
    Все нормально с условиями. Сказано же, чтобы площадь была минимальной, а такое достижимо только в 1 варианте. А по теме, если нельзя поворачивать фигуры на произвольный угол, то задача совсем простая.
    Минимальная площадь достижима в обоих случаях при одинаковом "матрешечном" наборе прямоугольников, и равна площади самого большого прямоугольника.
    Последний раз редактировалось Darij; 25.03.2014 в 23:54.

  11. #31
    забанен навсегда
    Регистрация
    17.05.2010
    Сообщений
    169
    Цитата Сообщение от Darij Посмотреть сообщение
    To Спалланцани:

    Повороты на угол, отличный от 90 градусов, лишены смысла - площадь меньше не будет. А вот второй вариант задачи (с пустыми коробками) был бы интереснее - классическая задача на оптимизацию с построением дерева возможных комбинаций.
    А разве в обоих случаях это не классическая NP полная задача коммивояжера/рюкзака ?

  12. #32
    Освоившийся Аватар для yaCooler
    Регистрация
    17.05.2010
    Сообщений
    233
    Странная задача. Было бы интереснее попробовать разместить их так, чтобы они не пересекались и чтобы площадь описываемой окружности была наименьшей. А так - сортируем по площади и лепим все в центр самого большого, попутно поворачивая каждый вдоль наибольшей его диагонали в случае, когда площадь выступающих за края самого большого остатков превышает площади 4х фигур, образуемых остатками повёрнутой фигуры...
    Последний раз редактировалось yaCooler; 26.03.2014 в 01:58.

  13. #33
    Активный участник
    Регистрация
    26.02.2011
    Сообщений
    9,264
    yaCooler, Описанная тобой задача не имеет 1 алгоритма решения.

  14. #34
    Освоившийся Аватар для yaCooler
    Регистрация
    17.05.2010
    Сообщений
    233
    Цитата Сообщение от Спалланцани Посмотреть сообщение
    yaCooler, Описанная тобой задача не имеет 1 алгоритма решения.
    Которая из? Которая с окружностью? или которая с площадями фигур?

  15. #35
    Новобранец
    Регистрация
    30.11.2012
    Сообщений
    94
    Цитата Сообщение от Ameno_64 Посмотреть сообщение
    А разве в обоих случаях это не классическая NP полная задача коммивояжера/рюкзака ?
    Первый вариант задачи в принципе лишен комбинаторной составляющей - не нужно думать, как расположить прямоугольники в зависимости от входных данных - они всегда будут отсортированы по длине. Решение находится за один цикл по таблице.

    А вот второй вариант требовал бы построения дерева контейнеров с учетом площади и положения содержимого. В зависимости от входных данных дерево решения будет разным.

    P.S. Второй вариант тоже не является "задачей коммивояжера". Наиболее близкий аналог из комбинаторной оптимизации - "задача раскроя".

    Было бы интересно взглянуть на алгоритм, который в общем случае решал бы задачу с коробками подобным образом:



    В качестве параметров можно задавать длину, ширину, высоту коробки (плюс толщина картона - внутренний объем коробки меньше внешних габаритов).
    Последний раз редактировалось Darij; 26.03.2014 в 03:41.

  16. #36
    Освоившийся
    Регистрация
    31.03.2011
    Сообщений
    277
    Это же задача про заказчика: угадай какие условия задачи на самом деле и сдай заказчику проект

  17. #37
    Активный участник Аватар для napancux
    Регистрация
    15.06.2010
    Сообщений
    631
    Darij, а высота коробки в данном случае зачем?

  18. #38
    Новобранец
    Регистрация
    30.11.2012
    Сообщений
    94
    Цитата Сообщение от napancux Посмотреть сообщение
    Darij, а высота коробки в данном случае зачем?
    Чтобы задача была приближена к реальности, добавляем третье измерение. Ну и усложняем тем самым задачу, давая возможность ставить коробки вдоль, поперек и вертикально, поворачивая их при этом как удобно. А картинка иллюстрирует 2D вариант задачи (в 3D слишком долго пришлось бы рисовать).

  19. #39
    Новобранец
    Регистрация
    28.11.2012
    Сообщений
    46
    Не кормите ленивых студентов. Задачка (исходная) элементарная, даже не олимпиадная. Лаба на знание массивов.

  20. #40
    Активный участник Аватар для KoptecW
    Регистрация
    10.05.2011
    Сообщений
    1,233
    Еще не плохо было бы написать алгоритм для задачи: исходное пространство ограничено, прямоугольники/параллелепипеды не могут пересекаться, найти идеальное расположение их на плоскости (или в 3х мерном пространстве). Что-то вроде того, как разместить вещи в багажнике. Она же задача "оптимального раскроя".
    Последний раз редактировалось KoptecW; 26.03.2014 в 09:27.

Страница 2 из 3 ПерваяПервая 123 ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Задачка скучающего ботана №14(для программистов)
    от Спалланцани в разделе Общий форум
    Ответов: 25
    Последнее сообщение: 21.11.2013, 20:47
  2. Задачка скучающих ботанов № 13
    от Спалланцани в разделе Общий форум
    Ответов: 79
    Последнее сообщение: 14.11.2013, 14:04
  3. Задачка для скучающих ботанов №12
    от Спалланцани в разделе Общий форум
    Ответов: 20
    Последнее сообщение: 14.11.2013, 12:28
  4. Задачка для скучающих ботанов №10
    от Спалланцани в разделе Общий форум
    Ответов: 59
    Последнее сообщение: 12.11.2013, 21:42
  5. Задачка для скучающих ботанов №9
    от Спалланцани в разделе Общий форум
    Ответов: 82
    Последнее сообщение: 06.11.2013, 20:16

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •