Ю2.12

Задача

Планировка. Можно ли на прямоугольном участке застройки размером a на b метров разместить два дома размером в плане p на q и r на s метров? Дома можно располагать только параллельно  сторонам участка.

Ниже представлены одни из возможных вариантов расположения домов на участке:

Илья_задание_01 Илья_задание_04

a b p q r s Ответ
100 150 20 70 25 50 Дома могут быть построены на заданном участке.
20 50 10 60 10 15 Дома не могут быть построены.
50 150 25 150 25 150 Дома могут быть построены на заданном участке.
50 150 50 75 50 75 Дома могут быть построены на заданном участке.
200 300 115 50 110 100 Дома могут быть построены на заданном участке.
2 4 1 3 2 2 Дома не могут быть построены.
2 5 1 3 2 3 Дома не могут быть построены.
2 5 2 2 1 4 Дома не могут быть построены.
3 3 2 2 2 2 Дома не могут быть построены.
2 10 10 1 10 1 Дома могут быть построены на заданном участке при повороте на 90 градусов.
10 2 1 10 1 10 Дома могут быть построены на заданном участке при повороте на 90 градусов.
2 10 1 10 10 1 Дома могут быть построены на заданном участке при повороте дома со сторонами r s на 90 градусов.
10 2 10 1 1 10 Дома могут быть построены на заданном участке при повороте дома со сторонами r s на 90 градусов.
10 2 1 10 10 1 Дома могут быть построены на заданном участке при повороте дома со сторонами p q на 90 градусов.
2 10 10 1 1 10 Дома могут быть построены на заданном участке при повороте дома со сторонами p q на 90 градусов.
2 3 1 1 2 3 Дома не могут быть построены.
2 4 1 1 3 3 Дома не могут быть построены.
2 6 1 3 3 3 Дома не могут быть построены.

Построенный алгоритм позволяет дать ответ: могут ли дома быть построены на участке или не могут.  Стены могут стоять прямо на границе участка. В программу вводятся исходные данные сторон участка и двух домов, требующиеся для  последующего ответа: могут  дома быть построены или нет.

Всего у нас есть 8 вариантов расположения домов на участке.

Каждый дом можно расположить на участке двумя способами (вертикально или горизонтально). Значит всего четыре различные комбинации их расположения относительно участка. Среди этих четырёх комбинация должна существовать по крайней мере одна в которой дома помещаются. Т.е. либо суммарная ширина домов меньше ширины участка и длина каждого дома меньше его длины, либо суммарная длина домов меньше длины участка и ширина каждого дома меньше ширины участка. Поскольку выполнится должно хоть одно такое условие, то их нужно соединить логическим “или”.

Так же у нас есть 4 различных комбинации размещения домов, в которых один из домов(а может и сразу два) не помещается на участке, но если его развернуть на [latex]90^{\circ}[/latex], то дома успешно разместятся на участке.

Ниже представлен сам код(C++):

Код на Java:

 

Ознакомится с программой можно тут (C++)/тут (Java).

Бровко Ілля
Бровко Ілля

Latest posts by Бровко Ілля (see all)

34 thoughts on “Ю2.12

  1. 1. Вы забыли указать рубрику и ключевые слова. Это обязательно.
    2. Вы написали три условных оператора подряд с одинаковыми действиями. Так не нужно делать. Объедините их условия с помощью скобок и логического «или». Останется один условный оператор.
    3. Дома помещаются на участке в случае если можно так развернут дом (по вертикали или по горизонтали), что сумма длин домов не превысит длину участка, а суммарная ширина домов — его ширину. Т.е. нужно для размеров домов решить что из них ширина, а что длина. Всего 4 варианта.
    Это пример того, как следует объяснить своё решение. Вам нужно примерно так объяснить свой подход. Почему важно чтобы сумма сторон домов не превышала удвоенного размера участка?
    4. Тесты проверяют удачный случай только для квадратного участка. Нужно проверить ВСЕ принципиально различные варианты.

  2. — «площади заданных плоскостей» — так не говорят. Сформулируйте иначе или удалите это предложение.
    — «под условием» — так не говорят. Сформулируйте иначе или удалите это предложение.
    — «На первом рисунке изображено классическое расположения домов на участке.» — Вы же это не всерьёз все пишите? Просто удалите , пожалуйста, это предложение.

    Извините, дальше нет сил подробно комментировать У вас идёт текст, который пересказывает словами формулу. Причём с ошибкой. Вы ничего в формуле не объясняете.

    Ответьте, пожалуйста, в комментарии на два вопроса.
    1. Почему Вам важно, чтобы сумма сторон домов не превышала удвоенного размера участка? (На картинках удвоенный участок нигде не появляется. В объяснениях тоже.)
    2. Вы сами писали программу?

    • Да, программу я писал сам.
      Я, честно говоря, не представляю, как можно еще описать условие. На втором рисунке прекрасно показано, почему сумма длин домов не должна превышать удвоенной длинны участка. У нас два дома. Они прямоугольны. Длинны их сторон равняются стороне участка. Длина больше чем ширина. Дома рассположенны в притык к друг другу. Их длины паралельны друг другу и паралельны стороне участка. Длина одного из домов находится внутри участка. Если сумма длинн домов превысит удвоенную длину участка и (или) при этом сумма других сторон превысит ширину, то дома, просто на просто, не поместятся на участке.

  3. «Если сумма длин домов превысит удвоенную длину участка…, то дома… не поместятся». Правильно пишите. А если один дом будет чуть длиннее участка, а другой значительно короче, то в сумме будет меньше удвоенной длины. И Вы считаете, что они поместятся?

    Понимаю Ваши трудности. В школе сейчас редко учат доказывать свои утверждения. Но на мех-мате это обязательно.
    Действуем по такому плану:

    1. Программу не менять!
    2. Доказываете, что Ваши проверки эквивалентны условию.

    Как доказывать?
    Давайте просто переведём условия задачи на математический язык. Каждый дом можно расположить на участке двумя способами (вертикально или горизонтально). Значит всего четыре различные комбинации их расположения относительно участка. Среди этих четырёх комбинация должна существовать по крайней мере одна в которой дома помещаются. Т.е. либо суммарная ширина домов меньше ширины участка и длина каждого дома меньше его длины (рис.4), либо суммарная длина домов меньше длины участка и ширина каждого дома меньше ширины участка (рис.1). Поскольку выполнится должно хоть одно такое условие, то их нужно соединить логическим «или» — дизъюнкция.
    Так вот, Вам необходимо доказать, что выполнение Ваших простых и изящных условий эквивалентно этой длинной формуле. Т.е. показать, что Ваше решение задачи является логически эквивалентной условию формулой.

    Понимаю, что это не просто. Но чего Вы ожидали от высшего образования в области математики? Если не будет получаться, то на ближайшем лабораторном занятии покажите эти комментарии Александру Сергеевичу и попросите помощи. Или подойдите ко мне после лекции.

    • Вы просили код не менять, но нашли контрпример: «А если один дом будет чуть длиннее участка, а другой значительно короче, то в сумме будет меньше удвоенной длины.» Пришлось немного изменить код.
      Постарался все описать.

      • Я не нашёл контрпример. Т.е. не подобрал исходных данных на которых Ваша программа давала бы неправильный ответ. Я высказывал сомнения в Ваших пояснениях.
        Поскольку Вы моей просьбы не выполнили, я не вижу смысла продолжать беседу.
        Подойдите завтра к Вашему преподавателю практики (Александр Сергеевич Антоненко) и разберите с ним свою задачу. Если всё нормально, он Вам обязательно зачтёт.

  4. Уважаемый Илья!

    Попробуйте следующие тесты (в каждой строке по порядку a, b, p, q, r, s через пробел):

    2 4 1 3 2 2
    2 5 1 3 2 3
    2 5 2 2 1 4
    3 3 2 2 2 2

    И заодно внесте их в таблицу тестов.

      • Поправьте пунктуацию – перед и после тире – пробел, и вообще тире желательно чтобы было именно тире, как «в где S – площадь прямоугольника», а не дефис «-«.
        Выражение “все плохо” уместно в устной, неформальной речи, в отчете лучше написать, что дома не могут быть расположены.
        Ну и все же, Вы не пытаетесь, при необходимости, вращать дома. В моем понимании, фраза из условия «Дома можно располагать только параллельно сторонам участка.» обозначает что сторона p может быть параллельна как стороне a, как у Вас, так и стороне b (если повернуть дом на 90 градусов). Аналогично для второго дома. Могу, конечно, и такой вариант засчитать, но он мне кажется неполным. Например, на участке 100 на 10 вы не сможете построить два дома 5 на 50 и 3 на 70.

        • Пунктуацию поправил.
          Я не много не понимаю ваше замечание: «Вы не пытаетесь, при необходимости, вращать дома.» Во втором столбике таблице указан этот случай. Так же в коде указано условие, при котором дома не могут быть построены: q>b s>b r>a p>a.
          От поворота домов на 90 градусов меняются только буквы, но не значение длины и ширины.
          Как по мне, эта задача вполне закончена.

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

    • Есть всего два варианта, при которых нужно поворачивать два дома на 90 градусов
      Допустим у нас есть прямоугольный участок, где b>a. Есть два дома, с заданными длинами сторон, такими, что они смогут быть построены на заданном участке только, если развернуть 2 дома на 90 градусов (по умолчанию стороны p и r параллельны стороне a, q и s – стороне b). При повороте домов, параллельность сторон изменяется. Т.е q и s параллельны a, p и r – стороне b. Получается, что для того, чтобы дома развернулись на 90 градусов должно выполнятся условие: т.к b>a, то cума сторон, которые становятся параллельны стороне b (при повороте домов – p и r) не должна превышать удвоенной стороны b. Одновременно с этим сумма двух других сторон (q и s) не должна превышать стороны a.
      Так же, есть другой вариант, где a>b. Тогда, если развернуть два дома, то стороны q и s становятся параллельны стороне a, p и r – стороне b. Cума сторон q и s не должна превышать удвоенной стороны a, Одновременно с этим, сума сторон p и r не должна превышать стороны b.
      Теперь рассмотрим случаи, когда нужно повернуть только один дом. Всего их 4.
      1) Когда b>a, у первого дома (p и q) с размерами сторон все нормально – он поместится без разворота, но второй дом( r и s) без поворота не влезет, по-этому его нужно развернуть. При развороте это дома на 90 градусов меняется параллельность сторон: r– параллельно стороне b. При этом сумма q и r не должна превышать удвоенной стороны b, сума s и p не должна превышать размер стороны a.
      2)b<a. Снова у дома со сторонами p и q все хорошо. Но дом со сторонами r и s опять надо поворачивать. Т.к b<a должны выполнятся немного другие условия: сума сторон s и p не должна превышать удвоенной стороны a, q+ra, дом со сторонами q и p нужно повернуть. Тогда, при развороте этого дома сума сторон p и s не должна превышать удвоенной стороны b, r+q<=b.
      4) b<a. При развороте дома со сторонами p и q, стороны q и r параллельны стороне a, стороны p и s – стороне b. Тогда должно соблюдаться два условия: q+r<=2a и p+s<=b.

  5. Что же, как всегда, только тестирование рассудит нас. Я опять запустил свою тестирующую систему.

    Илья, проверьте работу Вашей программе на следующих тестах (добавьте их в таблицу тестов):
    2 3 1 1 2 3
    2 4 1 1 3 3
    2 6 1 3 3 3

  6. Теперь у Вас ошибки в другую сторону.

    1 2 1 1 1 1 выдает «Дома не могут быть построены на заданном участке. »
    2 2 1 1 1 1 выдает «Дома не могут быть построены на заданном участке. »

    Или Вы считаете, что это правильный ответ?

  7. Приветствую Ваше упорство. Однако, Вы уже месяц знаете как писать решение «в лоб» — простым перебором всех 8-и вариантов решения. Можно было написать какой-то генератор контрпримеров. Вот Вам генератор контрпримеров. Вместо функции brovko() можете писать свой код. Если генератор не выдаст контрпример за 5 секунд, то есть смысл посылать код на проверку. Генератор построен с учётом Вашего необычного понимания слова «помещается». Т.е. совпадение размеров отбраковывается.

    На всякий случай приведу код, который от Вас ожидали (решение «в лоб»):

  8. Вставлю и свой запоздалый комментарий. Очень странно, что когда Вы не умели решить задачу в исходной формулировке, вместо того, чтобы исправить решение, вы исправили формулировку («Стены дома не могут стоять прямо на границе участка, т.к дизайнеры проекта требуют наличие забора.» — дополнительное условие, таким образом исходное условие задачи модифицировано). Тем не менее, эта модифицированная задача сейчас у Вас не решена, что показывают например тест: 2 3 1 1 1 2 => Ваш ответ да, а в модифицированном варианте ответ нет.

    Раскрою и я свою проверяющую систему:
    1) Вот это показывает, что Ваша программа не решает исходную задачу, которую Вам нужно было решить.
    2) Вот это показывает, что Ваша программа не решает модифицированную Вами задачу.

    B=это ответ Вашей программы, A=моей (я пока не нашел теста, где именно Ваша программа выдает правильный ответ, а моя неправильный, правда я и искал противоположный вариант).

  9. А теперь мой вариант ответа на «вопрос в лоб» — Полностью согласен с формулировкой Игоря Евгеньевича «Решить задачу и написать отчёт.»
    Но все же осмелюсь дать пару советов:
    1) Вы можете посмотреть решение Игоря Евгеньевича или мое.
    2) Дальше советую Вам правильно модифицировать свое решение, чтобы решить ИСХОДНУЮ задачу (безо всяких требований дизайнеров про заборы).
    3) Если не можете ПРАВИЛЬНО модифицировать свое решение, напишите по новой или скопируйте в свою программу решение мое или Игоря Евгеньевича.
    4) Не забудьте поправить отчет в соответствии с правильным решением задачи.

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