Здравствуйте все интересующиеся развитием алгоритмического и математического мышления!

Новости

Разбор задачи "ЕГЭ C1"

В этой задаче требуется найти количество точек принадлежащих заданной области. Точки нужно считать только с целочисленными координатами.

Заметим, что смещение заданной фигуры на 100 единиц вниз никак не влияет на количество точек. Это лишнее условие было дано для запутывания.

Способ 1.

Будем перебирать все точки квадрата и проверять, принадлежат ли они заданной области.

Способ простой, но медленный.

Посчитаем. Максимальный квадрат имеет размеры 100000x100000. Значит в нем 10 миллиардов точек. Перебор такого количества точек не укладывается в 1 секунду.

Будем ускорять.

Способ 2.

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

Это просто. Пунктирными линиями на рисунке показано, как можно разбить эту фигуру на части. Получится один маленький квадрат и три одинаковых четверти круга. Количество точек в этих фигурах посчитать несложно.

Наиболее трудным может оказаться подсчёт точек в четверти круга. Существует алгоритм, который вычисляет это количество за линейное время (одним циклом). Этот алгоритм предлагаю найти самим.

Способ 2 работает с такой скоростью,  что 1 секунда для него даже много.

Что добавилось на сайте

Напоминаю, что для заказавших курс "Развитие алгоритмического мышления" действует подарок.

Подарок к 4 декабря — Дню Информатики
Всем заказавшим полный курс до 31 декабря 2010 года: дополнительно 1 час (6 по 10 минут) консультаций в подарок. 

Вячеслав Викторович Пупышев

Курсы

Развитие алгоритмического мышления.    Хочу изучить      Блок в подарок

Базовое программирование.    Хочу изучить

Работа с калькулятором.    Хочу изучить

Подготовка к ЕГЭ по информатике. Хочу получить более 80 баллов