Материалы

Поиск простых чисел за линейное время

Оригинал: Об одном алгоритме поиска простых чисел

Как-то, ради интереса, я решил поискать в Сети материалы о нахождении всех простых чисел в диапазоне от 1 до N за линейное время. Нашлись некоторые статьи на английском, но описанные алгоритмы были несколько сложны для реализации. К сожалению, поиски на русском не увенчались успехом - были какие-то оптимизации, пытающиеся уменьшить объем памяти, константу в оценке времени, но ничего за O(N), так что я решил восполнить данный пробел.

Определение проблемы

Для начала, вспомним, что существует так называемое решето Эратосфена, позволяющее решать нашу задачу за O(N ln ln N):

bool notPrime[MAXN + 1];
int primes[MAXN];
 
int sieve(int n) {
	int primesCount = 0;
	int sqrt_n = (int)sqrt((double)n);
	for (int i = 2; i <= n; ++i) {
		if (!notPrime[i]) {
			primes[primesCount++] = i;
			if (i <= sqrt_n) {
				for (int j = i * i; j <= n; j += i) {
					notPrime[j] = true;
				}
			}
		}
	}
	return primesCount;
}

Почему решето работает не за линейное время? Потому что одно число в нем может вычеркиваться несколько раз (во внутреннем цикле) . Если добиться, чтобы каждое число вычеркивалось не более одного раза, то, очевидно, алгоритм будет линейным

Основы программирования на языке Паскаль - Даулеткулов А.Б

С разрешения автора выложена книга Основы программирования на языке Паскаль (Даулеткулов А.Б., Алматы, 2004).

Данное пособие является базовым курсом по основам программирования на языке Паскаль. Данный курс был опробирован в течении трех лет в Техническом лицее №28 г.Алматы. Пособие соответствует Государственному общеобразовательному стандарту среднего общего образования Республики Казахстан по предмету «Информатика». Особое внимание в нем уделено принципам структурного программирования.

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

Спасибо автору Даулеткулову А.Б. за предоставление pdf-версии книги.

Олимпиады по информатике - Даулеткулов А.Б.

С разрешения автора выложена книга Олимпиады по информатике (Даулеткулов А.Б., Алматы, 2004).

Книга состоит из трех частей.

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

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

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

Спасибо автору Даулеткулову А.Б. за предоставление pdf-версии книги.

ACM ICPC: тяжело в учении - легко в бою

Предупреждение. Данная статья отражает исключительно мнение автора. Автор не претендует на верность всех утверждений. Статья предоставляется “как есть”, и автор не несет ответственности за какие бы то ни было отрицательные последствия ее прочтения и использования :)

Многие студенты, начав участвовать в олимпиадах, задаются вопросом: “Как добиться каких-либо значительных результатов?“. Здесь есть два варианта:

  1. вы - гений, в этом случае, скорее всего, вам не надо читать дальше :)
  2. вы - обычный студент, тогда единственный ответ - тренироваться, об этом и пойдет речь.

В последнее время меня несколько раз спрашивали “как надо готовиться к ACM ICPC“? В свое время и я задавал его некоторым личностям, но так и не получил вразумительного ответа. Поиск в Интернет также практически ничего не дал - видимо, известные корифеи спортивного программирования не очень любят писать. В общем пришлось, как всегда, доходить практически до всего самому, и здесь мне пригодился 7-летний опыт занятий некоторым, довольно специфическим видом спорта. Так или иначе, не без помощи руководителя и товарищей, я получил некоторый опыт, которым и постараюсь поделиться с вами - может кому-нибудь и пригодится.

стек + стек = очередь

Хочу рассказать об одном интересном и полезном, с моей точки зрения, для общего развития применении таких базовых структур данных, как стек и очередь, на которые, к сожалению, неоправданно забивают многие будущие программисты при обучении. Первый раз оно было встречено на зимних сборах 2008 года в Петрозаводске (огромное спасибо Андрею Станкевичу за разбор), а вскоре к нему неожиданно свелась задача для Республиканской олимпиады школьников (правда, там для облегчения проходило и не самое оптимальное решение, но это, увы, не сильно помогло участникам)

Олимпиады по программированию - они такие разные… Часть 4

Последняя статья об известных мне соревнованиях по программированию.

Открытый Кубок по программированиюДолгое время ACM ICPC был единственным крупномасштабным официальным соревнованием. Однако несколько лет назад ситуация изменилась: ежегодно стал проводиться Открытый Кубок по программированию. Участвовать здесь могут все, но подавляющее большинство участников - представители СНГ. Спонсоры: Яндекс и CBOSS.

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

 

TopCoder - все, что вы хотели узнать, но боялись спросить…

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

Пролог

TopCoderПро TopCoder я случайно узнал в далеком 2005 году. Зашел на сайт, зарегистрировался, стал еженедельно получать email’ы с анонсом каких-то SRM’ов с призовым фондом $5000, но так и не решился поучаствовать - думал, нереально какому-то самоучке состязаться с профессионалами и еще претендовать на денежное вознаграждение. На участие сподвигнул меня Андрей Лопатин - двукратный чемпион мира по версии ACM ICPC, приехавший в Алматы в качестве тренера на школьные сборы в мае 2006. С тех пор я участвую почти в каждом Rated Event в секции Algorithm и ничуть не жалею об этом, даже если “сливаю” матч вчистую. Из материального заработал я немного - всего $523, которые при вычете налогов сильно уменьшаются в размере, несколько футболок и почти бесполезных вещиц. Но неоценим нематериальный вклад: возможность вживую пообщаться с легендарными личностями, посмотреть, как пишут программы профессионалы, шанс быть принятым на работу в известную компанию, ну и просто наслаждение и польза от самого процесса.

Итак, начнем-с…

Олимпиады по программированию - они такие разные… Часть 2

В этой части попытаюсь начать разбираться с первой причиной малораспространенности олимпийского движения в Казахстане - неведеньем. Для начала рассмотрим IOI, Республиканскую студенческую олимпиаду и ACM ICPC.

International Olympiad in InformaticsМеждународная олимпиада по информатике (International Olympiad in Informatics, IOI) - самое известное соревнование среди школьников.

Про схему проведения можно почитать в Википедии

Олимпиады по программированию - они такие разные…

Пролог. Написал я как-то вечерком очередной SRM и подумал, а почему же так мало народу с Казахстана там участвует? Одна из причин - неведенье. С ней разберемся попозже. Ну а сейчас вторая…

ACM ICPC 2007 World Finals

Среди многих программистов (и не только) бытует такое мнение, что соревнования по программированию - совершенно никчемная трата времени. Почему же в то же время они с удовольствием занимаются каким-либо видом спорта или хотя бы делают зарядку по утрам (что не является ни чем иным, как бессмысленным передвижением белковой массы по некоторой иногда определенной, иногда хаотичной траектории)?

Синдикация материалов