Как найти количество прямоугольников в прямоугольнике

Сообщения без ответов | Активные темы | Избранное

 

Формула для числа прямоугольников (олимпиада Приморского кр)

Сообщение23.03.2011, 23:00 


23/03/11
∞
7
оттуда, откуда мы все :-)

Выразите через натуральное число n количество прямоугольников на координатной плоскости со сторонами, параллельными осям и целочисленными вершинами (a, b) $0le a, ble n$

Профиль  

ИСН 

Сообщение23.03.2011, 23:04 
Заслуженный участник
Аватара пользователя


18/05/06
13417
с Территории

Большинство людей, когда надо узнать число дней с 26-го, например, по 31-е число месяца, считает путём загибания пальцев. Это из той же оперы?

Профиль  

svv 

Re: Формула для числа прямоугольников (олимпиада Приморского кр)

Сообщение23.03.2011, 23:14 
Заслуженный участник


23/07/08
10076
Crna Gora

ИСН писал(а):

Это из той же оперы?

Нет, это из олимпиады Приморского края.

Профиль  

Sonkina 

Re:

Сообщение23.03.2011, 23:14 


23/03/11
∞
7
оттуда, откуда мы все :-)

Большинство людей, когда надо узнать число дней с 26-го, например, по 31-е число месяца, считает путём загибания пальцев. Это из той же оперы?

Ну а если $n=100$ тоже на пальцах будете? Пальцев не хватит :lol1:

Профиль  

ИСН 

Сообщение23.03.2011, 23:17 
Заслуженный участник
Аватара пользователя


18/05/06
13417
с Территории

Вот поэтому-то математики вывели формулу, сколько целых чисел умещается от сих до сих, и ею пользуются.

Профиль  

Sonkina 

Re:

Сообщение23.03.2011, 23:18 


23/03/11
∞
7
оттуда, откуда мы все :-)

Вот поэтому-то математики вывели формулу, сколько целых чисел умещается от сих до сих, и ею пользуются.

Вы точно эту задачу решаете, а не какую другую?

Профиль  

svv 

Re: Формула для числа прямоугольников (олимпиада Приморского кр)

Сообщение23.03.2011, 23:27 
Заслуженный участник


23/07/08
10076
Crna Gora

Sonkina

, мне тоже совершенно непонятно, в чем фишка. Вы можете ещё как-то по другому объяснить условие?
А то у меня получается совершенно недоброе представление об олимпиаде Приморского края.

Профиль  

Null 

Сообщение23.03.2011, 23:30 
Заслуженный участник


12/08/10
1411

$left(frac{n(n+1)}{2}right)^2$?

Профиль  

Sonkina 

Re: Формула для числа прямоугольников (олимпиада Приморского кр)

Сообщение23.03.2011, 23:32 


23/03/11
∞
7
оттуда, откуда мы все :-)

Sonkina

, мне тоже совершенно непонятно, в чем фишка. Вы можете ещё как-то по другому объяснить условие?

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

Профиль  

svv 

Re: Формула для числа прямоугольников (олимпиада Приморского кр)

Сообщение23.03.2011, 23:35 
Заслуженный участник


23/07/08
10076
Crna Gora

Я всё понял. Надо найти количество всевозможных подпрямоугольников, помещающихся в большой прямоугольник. Их там туча. Отличающиеся только сдвигом считаются всё равно разными. Так?

Подумал примерно то же, что и Null

.

Профиль  

Sonkina 

Re:

Сообщение23.03.2011, 23:41 


23/03/11
∞
7
оттуда, откуда мы все :-)

$left(frac{n(n+1)}{2}right)^2$?

А вопросительный знак — это что? Я знаю что восклицательный это факториал, а вопросительный?

— Ср мар 23, 2011 23:42:34 —

Я всё понял. Надо найти количество всевозможных подпрямоугольников, помещающихся в большой прямоугольник. Их там туча. Отличающиеся только сдвигом считаются всё равно разными. Так?

Подумал примерно то же, что и Null

.

Только не просто большой прямоугольник, а именно большой квадрат.

Профиль  

age 

Сообщение23.03.2011, 23:52 
Заблокирован
Аватара пользователя


17/06/09
∞
2213

$left(frac{n(n+1)}{2}right)^2$?

Немножко не так. Для каждой пары $(a_0,b_0)$ — координат первой точки подойдут любые пары $(a_1,b_1)$ координат для второй точки. Кроме $(a_0,b_0)$, т.к. в данном случае прямоугольник будет вырожденный. Также будут вырождаться в отрезок все прямоугольники у которых будет совпадать хоть одна координата. Поэтому их всех надо исключить. Комбинаторная задача. Надо посчитать.

Профиль  

kocuHyc 

Re:

Сообщение24.03.2011, 00:00 


03/03/11
∞
16

$left(frac{n(n+1)}{2}right)^2$?

Немножко не так. Для каждой пары $(a_0,b_0)$ — координат первой точки подойдут любые пары $(a_1,b_1)$ координат для второй точки. Кроме $(a_0,b_0)$, т.к. в данном случае прямоугольник будет вырожденный. Также будут вырождаться в отрезок все прямоугольники у которых будет совпадать хоть одна координата. Поэтому их всех надо исключить. Комбинаторная задача. Надо посчитать.

http://e-science.ru/forum/index.php?showtopic=29108

Профиль  

Xenia1996 

Re:

Сообщение24.03.2011, 01:04 


01/10/10
∞
2116
Израиль (племянница БизиБивера)

$left(frac{n(n+1)}{2}right)^2$?

Выведенная Вами формула является частным случаем более общей закономерности, согласно которой число прямоугольников (с целочисленными вершинами и соронами, параллельными осям координат) внутри (не обязательно строго внутри) большого прямоугольника n на m равна произведению энного и эмного треугольных чисел.
$frac{n(n+1)}2 cdot frac{m(m+1)}2$

Частный случай $n=2; m=3$ подробно рассмотрен в этом детском саду, а задачу, я полагаю, ТС взяла отсюда (год 1990, задача 1).

Профиль  

Модераторы: Модераторы Математики, Супермодераторы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

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

Источник

Ok, you have the number of rectangles with integer coordinates between the points (0, 0), (x, 0), (x, y) and (0, y), x and y being integers too. You now need to remove the perfect squares from this sum.

To compute it, let’s evaluate the number of squares 1*1: there are obviously x*y of them. For squares 2*2, we have x-1 choices for the x-coordinate and y-1 for the y-coordinate of the bottom left-hand corner of such a square, due to the width of this square: this results in (x-1)*(y-1) squares. Idem, we will have (x-2)*(y-2) squares 3*3, etc.

So for a given i, we have (x - i + 1) * (y - i + 1) squares i*i, and i goes from 1 to the minimum of x and y (of course if x is 4 and y is 7, we cannot have a square with a side greater than 4).

So if m = min(x, y), we have:

Sum_Squares = Sum(i = 1, i = m, (x - i + 1) * (y - i + 1))
            = Sum(j = 0, j = m - 1, (x - i) * (y - i))
            = Sum(j = 0, j = m - 1, x*y - (x+y)*j + j^2)
            = m*x*y - (x+y)*Sum(j = 0, j = m - 1, j) + Sum(j = 0, j = m - 1, j^2)
            = m*x*y - (x+y)*Sum(j = 1, j = m - 1, j) + Sum(j = 1, j = m - 1, j^2)
            = m*x*y - (x+y)*m*(m-1)/2 + (m-1)*m*(2*m-1)/6

I get that with an index change (j = i - 1) and via the well-known formulas:

Sum(i = 1, i = n, j) = n*(n + 1)/2
Sum(i = 1, i = n, j^2) = n*(n + 1)*(2*n + 1)/6

You just have to remove this Sum_Squares from (x^2+x)(y^2+y)/4 and you’re done !

Источник

Дана фигура (A) размером M на N.
Дана вторая фигура (B), поменьше, размером K на L.

Нужно определить, сколько максимально фигур B поместятся в фигуре A. Они должны располагаться одна рядом с другой, часть фигур может располагаться вертикально, другая часть горизонтально, что бы занять максимальное возможное пространство в основной фигуре.

Кто то может подсказать что то по этому вопросу?

На данный момент у меня мысли только если:

считать количество прямоугольников, расположенных горизонтально, которые поместятся горизонтально в фигуре, то есть ставим прямоугольник, рядом второй, заполняем линию, дальше снизу ставим еще одну линию, и так до самого низа.

Далее справа, возможно, останется пространство. Проверяем, помещается ли туда прямоугольник вертикально, если да, то заполняем стобец вертикальными прямоугольниками.

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

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

Из двух подсчетом выбираем тот, который дал наибольшый результат.

Вот пример подсчета, который я описал, реализованный на на JavaScript:

function calcFigures(FigureA, FigureB) {
    var total1 = 0,
        total2 = 0;

    (function() {
        var figures_per_row = Math.floor(FigureA.width / FigureB.width),
            figures_per_col = Math.floor(FigureA.height / FigureB.height),
            invers_figures_per_row = 0,
            invers_figures_per_col = 0;

        if (FigureA.width - (figures_per_row * FigureB.width) >= FigureB.height) {
            invers_figures_per_row = Math.floor((FigureA.width - (figures_per_row * FigureB.width)) / FigureB.height);
            invers_figures_per_col = Math.floor(FigureA.height / FigureB.width);
        }

        total1 = (figures_per_row * figures_per_col) + (invers_figures_per_row * invers_figures_per_col);
    }());

    (function() {
        var figures_per_row = Math.floor(FigureA.width / FigureB.height),
            figures_per_col = Math.floor(FigureA.height / FigureB.width),
            invers_figures_per_row = 0,
            invers_figures_per_col = 0;

        if (FigureA.width - (figures_per_row * FigureB.height) >= FigureB.width) {
            invers_figures_per_row = Math.floor((FigureA.width - (figures_per_row * FigureB.height)) / FigureB.width);
            invers_figures_per_col = Math.floor(FigureA.height / FigureB.height);
        }

        total2 = (figures_per_row * figures_per_col) + (invers_figures_per_row * invers_figures_per_col);
    }());

    return Math.max(total1, total2);
}

Источник

Вася Иванов

Мореплаватель — имя существительное, употребляется в мужском роде. К нему может быть несколько синонимов.
1. Моряк. Старый моряк смотрел вдаль, думая о предстоящем опасном путешествии;
2. Аргонавт. На аргонавте были старые потертые штаны, а его рубашка пропиталась запахом моря и соли;
3. Мореход. Опытный мореход знал, что на этом месте погибло уже много кораблей, ведь под водой скрывались острые скалы;
4. Морской волк. Старый морской волк был рад, ведь ему предстояло отчалить в долгое плавание.

Источник

Сколько прямоугольников в прямоугольнике.

Сколько прямоугольников в прямоугольнике?

Вы зашли на страницу вопроса Сколько прямоугольников в прямоугольнике?, который относится к
категории Математика. По уровню сложности вопрос соответствует учебной
программе для учащихся 10 — 11 классов. В этой же категории вы найдете ответ
и на другие, похожие вопросы по теме, найти который можно с помощью
автоматической системы «умный поиск». Интересную информацию можно найти в
комментариях-ответах пользователей, с которыми есть обратная связь для
обсуждения темы. Если предложенные варианты ответов не удовлетворяют,
создайте свой вариант запроса в верхней строке.

Источник

Понравилась статья? Поделить с друзьями:

Не пропустите также:

  • Как найти людей в hay day
  • Ютуб как найти воду на участке
  • Как составить акт на списание материальных ценностей образец простой
  • Как найти дарвинский заповедник
  • Как найти чаши в соборе парижской богоматери

    • 0 0 голоса
    Рейтинг статьи
    Подписаться
    Уведомить о
    guest

    0 комментариев
    Старые
    Новые Популярные
    Межтекстовые Отзывы
    Посмотреть все комментарии