Сколько прямоугольников на рисунке?
Пипец домашка у ребёнка( Нечто подобное бывает на собеседованиях при приёме на работу. Как то на собеседовании решала какой угол между часовыми стрелками в 3:15. Тоже наверняка школьная задачка!
Екатеринбург
36 параллелограммов, из которых 32 — прямоугольники и 4 квадрата
из 36 параллелограммов все 36 и есть прямоугольники, почему 32 то?
определение прямоугольника: прямоугольник — это параллелограмм, у которого все углы прямые. Свойство прямоугольника — равенство противоположных сторон, т.е. квадрат тоже является прямоугольником
Аноним 540
2 класс :gy:
Екатеринбург
Анонимка автор темы
Ага))) мы тоже в том году с этим заданием зависли. Минут 15 наш папа векторы рисовал, а я сидела закрашивала прямоугольники с ребёнком :gy:
хочу стать мамой
Екатеринбург
Не надо ничего закрашивать. Поставим в узлах этой сетки точки, их будет 16. Прямоугольник однозначно определяется своей диагональю, при этом количество прямоугольников вдвое меньше количества возможных диагоналей. Посчитать возможные диагонали легко: первую точку ставим 16 способами, а вторую 9 способами (16 – 7, где 7 – количество точек на той же вертикали или горизонтали). Поскольку порядок точек не важен, ответ делим пополам. То есть диагоналей всего 16 × 9 : 2 = 72, а прямоугольников вдвое меньше, то есть 36.
хочу стать мамой
Екатеринбург
40 у меня. нее-36..
Екатеринбург
из 36 параллелограммов все 36 и есть прямоугольники, почему 32 то?
параллелограмм — общее название.
прямоугольник, ромб, квадрат — частные случаи
Екатеринбург
40 у меня. нее-36..
кто больше! :gy:
Поставим в узлах этой сетки точки, их будет 16. Прямоугольник однозначно определяется своей диагональю, при этом количество прямоугольников вдвое меньше количества возможных диагоналей. Посчитать возможные диагонали легко: первую точку ставим 16 способами, а вторую 9 способами (16 – 7, где 7 – количество точек на той же вертикали или горизонтали). Поскольку порядок точек не важен, ответ делим пополам. То есть диагоналей всего 16 × 9 : 2 = 72, а прямоугольников вдвое меньше, то есть 36
думаете такая логика доступна 2-класснику.
хочу стать мамой
Екатеринбург
Тут не надо никакой логики, простейшие рассуждения. Второклассники зачастую лучше справляются с подобными задачками, чем иные взрослые. А если бы сетка была не 3 × 3, а 300 × 300, вы бы тоже прямоугольники закрашивали?
Задача о прямоугольниках (чисто алгоритмическая)
Когда ночью не спится, включаю телик. Как-то раз напоролся на игру «деньги на проводе» по ТНТ. Вот и возникла идея решить одну из предложенных там задач в общем случае.
Задача такая. Дан прямоугольник (n строк, m столбцов), «разлинованный» на клетки (как тетрадь в клетку). Но некоторые «границы» между клетками отсутствуют. Нужно подсчитать количество прямоугольников, образуемых этой системой клеток. Думаю, не нужно объяснять, что в данном случае считать прямоугольником: прямоугольником является любая система клеток, ограничиваемая двумя вертикальными и двумя горизонтальными линиями, при этом, естественно, линии не должны проходить по непрочерченным «стенкам».
В приведенном ниже примере пять прямоугольников:
____
|_|_|
|___|
— левая верхняя клетка;
— правая верхняя клетка;
— прямоугольник, образованный двумя верхними клетками;
— нижний прямоугольник;
— вся система тоже является прямоугольником.
Мой вариант решения использует комбинаторику. Обозначения: n — размер генерального прямоугольника в ширину, m — размер генерального прямоугольника в длину, k — количество «непрочерченных» стенок. Абсциссы и ординаты как клеток, так и стенок нумеруются по математическим правилам — от единицы.
Прямоугольник однозначно идентифицируется парой противоположных углов — скажем, левым верхним и правым нижним. Поэтому мы можем подсчитать число прямоугольников, которые мы могли бы образовать, если бы все стенки между клетками существовали, были «прочерчены».
Очевидно, абсциссу левого верхнего угла мы можем выбрать n способами. Причем для каждой выбранной абсциссы левого верхнего угла абсцисса правого нижнего выбирается n+1-i способами, где i — абсцисса текущего левого верхнего угла. Соответственно, число способов образовать абсциссу левого верхнего угла и абсциссу правого нижнего угла равно:
Сумма от i=1 по n (n+1-i) = сумма от i=1 по n (i) = n * (n+1) / 2.
Независимо от выбора абсциссы, ординаты мы можем выбрать
m (m+1) / 2 способами. Благодаря независимости выбора абсциссы и ординаты, получаем общее количество способов (обозначим через S0):
S0 = n * (n+1) / 2 * m * (m+1) / 2.
Теперь для каждой непрочерченной стенки (в нашем примере такая стенка одна) число прямоугольников, которое нельзя провести через данную стенку. Сумму этих чисел обозначим S1.
Используя метод включения и исключения, возьмем полученное число S0 и вычтем из него число прямоугольников, которое нельзя провести через каждую отдельно взятую стенку, т. е. S1. Но при этом мы дважды вычли прямоугольники, которые нельзя провести одновременно через две стенки, поэтому подсчитаем их количество и прибавим их, и т. д.:
S = S0 + S1 — S2 + S3 — . (+-) Sk
«Непрочерченную стенку» можно идентифицировать координатой клетки, для которой эта стенка является левой (если стенка вертикальная) или верхней (если горизонтальная). Если же стенка находится в самом низу генерального прямоугольника, ей не соответствует ни одна клетка; присвоим ей ординату m+1; если она находится на правой «стене» генерального прямоугольника, т. е. опять же вне зоны клеток, присвоим ей абсциссу n+1. Таким образом, абсцисса стенки меняется от 1 до n+1, ордината от 1 до m+1.
Тогда число S1 (число прямоугольников, проходящих через каждую «непрочерченную» стенку, просуммировано по всем таким стенкам) можно посчитать по нижеследующим формулам.
1. Если стенка горизонтальная, через нее нельзя провести i * (n+1-i) * m прямоугольников.
2. Если стенка вертикальная, через нее нельзя провести j * (m+1-j) * n прямоугольников.
Здесь (i, j) — соответственно абсцисса и ордината стенки. Отмечу, что для горизонтальной стенки число не зависит от ее ординаты, а для вертикальной — от абсциссы.
Очевидно, для подсчета S1 требуется время порядка O(k), где k — количество непрочерченных стенок.
Теперь нужно сосчитать число S2 (число прямоугольников, проходящих через пару «непрочерченных» стенок, просуммировано по всевозможным парам стенок).
1. Для пары горизонтальных стенок (i1, j1); (i2, j2):
1а. Если их ординаты не равны (j1 <> j2), т. е. стенки лежат на противоположных стенках прямоугольника, имеем формулу i1 * (n+1-i2)
(предполагается, что i1 1б. Если их ординаты равны (j1 = j2), т. е. стенки лежат на одной стороне прямоугольника, имеем формулу i1 * (n+1-i2) * m (опять же предполагается i1 2. Для пары вертикальных стенок формулы идентичны.
3. Для пары «горизонтальная-вертикальная» (обозначим через (i1, j1) горизонтальную, (i2, j2) вертикальную):
3а. Если i1 < i2 и j2 < j1: i1*j2
3б. Если i1 < i2 и j2 >= j1: i1 * (m+1-j2)
3в. Если i1 >= i2 и j2 < j1: (n+1-i1) * j2
3г. Если i1 >= i2 и j2 >= j1: (n+1-i1) * (m+1-j2)
Число всевозможных пар стенок равно C (2, k) = k! / (2! * (k-2)!) = k * (k-1) / 2, т. е. для подсчета S2 требуется время порядка O (k^2), где k — количество стенок.
Формулы для S3 и т. д. я приводить не буду, поскольку это займет много места. Однако добавлю, что можно вывести формулы и для S4; а дальнейшие случаи сводятся к S1-S4 (поскольку прямоугольник имеет только 4 стороны).
Итак, выводы. Для подсчета числа прямоугольников используется метод включения и исключения, для чего нам нужно провести 1 вычисление для подсчета S0, k вычислений для подсчета S1, k (k-1) / 2 вычислений для подсчета S2 и т. д. Получим общее число вычислений:
Сумма от i=0 по k C(i,k) = 2^k.
Таким образом, алгоритмическая сложность такого решения O (2^k).
Тут есть возможность для оптимизации. Если при вычислении какого-то из чисел Si мы получили ноль, дальнейшие числа вычислять не имеет смысла — они также будут нулевыми (если ни один прямоугольник не проходит, скажем, через произвольную тройку стенок, то ни один прямоугольник не будет также проходить и через четверку стенок). Поэтому в этот момент имеет смысл прервать вычисления и выдать результат. Однако оценку сложности такого оптимизированного алгоритма провести сложно, поскольку нельзя даже сказать определённо, с какой вероятностью алгоритм прервется на каком-то определенном шаге, поэтому будем считать, что сложность алгоритма не хуже O (2^k).
Отмечу, что если решать задачу «напролом», простым перебором вариантов, сложность задачи составит O (2^(n*m)). Однако, если учесть, что для каждого варианта прямоугольника нужно выполнять поиск стенок, через которые он может проходить, и предположить, что время поиска логарифмическое, получим несколько худшее время: O (2^(n*m) * log2 k).
Внимание, вопрос 🙂 Есть ли более быстрый алгоритм?
Сколько прямоугольников на рисунке 7.52?
Прямоугольник это четырехугольник у которого все углы прямые. Частный случай прямоугольника -это прямоугольник у которого равны не только углы, но и стороны , т.е. квадрат.
На рисунке изображен квадрат, разделенный на 4 части . Поскольку квадрат это прямоугольник , то на рисунке изображено 9 прямоугольников .
Новые вопросы в Математика
Розкрий дужки: 1) 2(m + 1); 3) −5(2x + 1); 5) (-2х — у) . 3; 7) (a — b) · (−3); 2) 3(x — 4); 4) (-1,6x + 2) · (−5); 6) -7(x — 2); 8) (-4a + 5b). 2. Зн … айди найбільший спільний дільник чисел: 1) 24 i 40; 4) 231 i 273; 2) 70 i 110; 5) 5, 25 i 45; 3) 49 i 48; 6) 150, 375 i 600.
Домашнее задание на 10.01.24 №1. Одна сторона прямоугольника на 2 см меньше стороны квадрата, а вторая сторона больше, чем сторона квадрата, на 4 см. … Найдите сторону квадрата, если площадь прямоугольника равна 40 CM². №2. Найдите катеты прямоугольного прямоугольного треугольника, если известно, что один из них на 4 см меньше другого, а гипотенуза равна 20 см.
2)5/ 8 ee равны 30 дм;
Скільки з-поміж чисел 5;7; -1/3;0;-4;2;8;58;-8;100 невід’ємних чисел?
Каждое число числового набора Z сначала увеличили в 4 раза, а затем сложили с числом 4,7. Получился числовой набор А. Каким — будет а, если z = 17,06? …
комбинаторика — Количество прямоугольников
Здравствуйте! Попалась интересная задача, но не знаю как к ней подобраться.
В клетчатом прямоугольнике 2 х 3 можно выделить десять прямоугольников, состоящих из четного количества клеток. А какое количество прямоугольников, содержащих четное число клеток, можно выделить в клетчатом прямоугольнике 4 х 9?
задан 16 Дек ’15 0:11
Malahai
107 ● 4 ● 18
81% принятых
1 ответ
Можно решить задачу в общем виде. Рассмотрим прямоугольник $%m\times n$% на координатной плоскости. Он ограничен прямыми $%y=0$%, $%y=m$%, $%x=0$%, $%x=n$%.
Если мы выбираем прямоугольник из клеточек, содержащийся в данном, то мы проводим две вертикальные границы $%x=a$%, $%x=b$%, и две горизонтальные $%y=c$%, $%y=d$%. Тем самым, выбор прямоугольника предполагает задание двух целых чисел $%0\le a < b\le n$%, что делается $%C_^2$% способами, и задание двух целых чисел $%0\le c < d\le m$%, что делается $%C_^2$% способами. Общее количество прямоугольников, содержащихся в данном, равно произведению $%C_^2C_^2$%.
Площадь такого прямоугольника может быть чётной или нечётной. Допустим, что она нечётна. Тогда числа $%a$% и $%b$% имеют разную чётность. В множестве чисел от $%0$% до $%n$% имеется ровно по $%\frac2$% чётных и нечётных, если $%n$% нечётно. Если же $%n$% чётно, то нечётных чисел там $%\frac2$%, а чётных на единицу больше: $%\frac2+1$%. Поэтому можно дать общую формулу $%\lfloor\frac2\rfloor$% для числа нечётных, и $%\lceil\frac2\rceil$% для числа чётных, где скобки вниз и вверх означают округление до целого в сторону уменьшения и увеличения соответственно.
Отсюда следует, что число прямоугольников нечётной площади может быть выражено формулой $%\lfloor\frac2\rfloor\lceil\frac2\rceil\lfloor\frac2\rfloor\lceil\frac2\rceil$%. Соответственно, число прямоугольников чётной площади будет равно $$\frac2\cdot\frac2-\lfloor\frac2\rfloor\lceil\frac2\rceil\lfloor\frac2\rfloor\lceil\frac2\rceil.$$
При $%m=2$%, $%n=3$% получается $%3\cdot6-1\cdot2\cdot2\cdot2=10$%, а при $%m=4$%, $%n=9$% получится ответ $%10\cdot45-2\cdot3\cdot5\cdot5=300$%.
Замечание. Вместо $%\lfloor\frac2\rfloor\lceil\frac2\rceil$% можно писать $%\lfloor\frac4\rfloor$%.
отвечен 16 Дек ’15 1:03
falcao
300k ● 9 ● 38 ● 55