Задача про прямоугольники
Катя участвовала в олимпиаде от учи.ру. Там была задачка на поиск прямугольников, с которой она не справилась и даже я сначала была удивлена ее объмностью - с учетом того что на все задания олимпиады (их было 4), отводилось всего 30 минут. Задачку мы разобрали и мне показалось, что она довольно интересная. Выкладываю решение.
Итак, надо подсчитать все прямоугольники на поле из квадратов 20х2.
Сначала мы разберем вариант попроще - будем искать прямоугольники в одной полоске из 20 квадратов (20х1).
Тоже задача не простая :)
Но мы попробуем увидеть закономерность, подсчитывая прямоугольники в одной полоске из 3 квадратов, затем 4, затем 5. Если сразу ее не видно - предложите подсчитывать, зарисовывая при этом типы получаемых прямоугольников. Должно получится примерно так:
И вот! Закономерность очевидна. Можно ее проверить еще пару раз, прибавляя к полоске по одному квадратику.
А что бы подсчитать количество получаемых прямоугольников для полоски из 20 квадратов мы увидим еще одну красивую закономерность, открытую, как гласит история, юным Гауссом:
1+2+3+4+...+17+18+19+20=(20+1)*20/2
А если кончается на нечетное число? Моя Катя сказала - подставим 0 для пары: 1+2+3+4+5= (0+5)*6\2
Далее возвращаемся к задаче - столбцов два, а не один. Тут в принципе благодаря минимальному количеству сложностей не возникает.
А если столбцов 4, 5.. 20? Аналогия с количеством строк (т.е. квадратиков) может быть далеко не сразу очевидна. У Кати в голове по-моему это просто не укладывается - множество множеств )
Но в итоге мы нашли алгоритм для поиска прямоугольников на поле любого размера
Итак, надо подсчитать все прямоугольники на поле из квадратов 20х2.
Сначала мы разберем вариант попроще - будем искать прямоугольники в одной полоске из 20 квадратов (20х1).
Тоже задача не простая :)
Но мы попробуем увидеть закономерность, подсчитывая прямоугольники в одной полоске из 3 квадратов, затем 4, затем 5. Если сразу ее не видно - предложите подсчитывать, зарисовывая при этом типы получаемых прямоугольников. Должно получится примерно так:
И вот! Закономерность очевидна. Можно ее проверить еще пару раз, прибавляя к полоске по одному квадратику.
А что бы подсчитать количество получаемых прямоугольников для полоски из 20 квадратов мы увидим еще одну красивую закономерность, открытую, как гласит история, юным Гауссом:
1+2+3+4+...+17+18+19+20=(20+1)*20/2
А если кончается на нечетное число? Моя Катя сказала - подставим 0 для пары: 1+2+3+4+5= (0+5)*6\2
Далее возвращаемся к задаче - столбцов два, а не один. Тут в принципе благодаря минимальному количеству сложностей не возникает.
А если столбцов 4, 5.. 20? Аналогия с количеством строк (т.е. квадратиков) может быть далеко не сразу очевидна. У Кати в голове по-моему это просто не укладывается - множество множеств )
Но в итоге мы нашли алгоритм для поиска прямоугольников на поле любого размера