Отправляет email-рассылки с помощью сервиса Sendsay
  Все выпуски  

Информат - алгоритмическое и математическое мышление


Лого 

 ИНФОРМАТ 

развитие алгоритмического и математического мышления


--

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

-- --

Новости


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

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

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

Разбиенние эту фигуры на части

Способ 1.

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

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

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

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

Способ 2.

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

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

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

 

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

 

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

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

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


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



Курсы

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

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

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

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

  -- 17.12.2010    Добавлена задача районной олимпиады по программированию "ЕГЭ C2". Перейти
16.12.2010    Добавлены тесты для задачи районной олимпиады по программированию "ЕГЭ C1". Перейти
13.12.2010    Разбор задач районных олимпиад Удмуртии по информатике будет рассылаться через Subscribe.ru. Перейти
04.12.2010    Пупышев Вячеслав Викторович поздравляет с Днём информатики через Subscribe.ru. Перейти
13.11.2010    В разделе юмор добавлена картинка "Реальное копирование". Перейти
09.11.2010    Подготовка к ЕГЭ по информатике. Перейти
19.10.2010    Добавлена задача по математике "Софизм: 2x2=5 (No2)". Перейти
17.10.2010    На страницу игр добавлена игра "Коровий марафон". Перейти
03.10.2010    Добавлена статья "Отдых для глаз". Перейти
13.09.2010    Курс: Развитие алгоритмического мышления. Перейти
08.09.2010    Курсы: Реальное программирование. Перейти
07.09.2010    Интересный факт: Y-хромосома и палиндромы. Перейти
01.09.2010    Курс: Базовое программирование. Перейти
Copyright (C) 2010 Информат

В избранное