О блоге

Рейтинг
0.00
голосов: 0
Общие вопросы программирования без привязки к конкретному языку.

Администраторы (1)

Модераторы (2)

Читатели (3)

Java Puzzlers #1: Время для сдачи

Всем привет! Решил немного разбавить скучность бытия здесь и порешать несколько интересных задачек. Это задачки из книги Джошуа Блоха "Java Puzzlers" и не только. Да, код будет в основном на Java, но в целом будет понятно всем, кто вообще когда-то что-то писал на любом языке. Первая задача - сразу же под этим сообщением.

Ненормальное программирование (серия 3). Не такое уж и простое это простое число

Простые числа (2, 3, 5, 7, 11, 13...)

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

Для начала, вспомним, что же такое простое число.

Простое число — это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя.


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

1. Перебор делителей

С этим способом знакомы, наверное, все, кто хоть как-то связан с программированием. Алгоритм здесь достаточно прост — перебрать все делители у числа и, если их всего 2 (единица и само число), то число простое:

for x := 1 to n do
  begin
    k := 0;
    for i := 2 to x div 2 do
      if x mod i = 0 then
        inc(k);
    if k = 0 then
      is_prime[x] := true;
  end;


Примечание: Чтобы оценить быстродействие алгоритмов с минимальными погрешностями, мы будем сначала заполнять массив типа Boolean значениями в соответствии с тем, является число простым или нет, и измерять только время заполнения массива, т.к. вывод чисел на экран серьезно замедляет производительность.

Пишем код, запускаем при n = 100 000 и… ждем-с. Работа алгоритма занимает около 10 секунд. Хм, учитывая, что в задачах n бывает даже больше, а время работы программы ограничено 1-2 секундами, нужно поискать более быстрые алгоритмы.

2. Решето Эратосфена

Алгоритм поиска простых чисел, который носит название «Решето Эратосфена», часто изучают в средней школе. Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

  • Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
  • Пусть переменная p изначально равна двум — первому простому числу.
  • Считая от p шагами по p, зачеркнуть в списке все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …)
  • Найти первое не зачеркнутое число, большее, чем p, и присвоить значению переменной p это число.
  • Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n
Теперь все не зачеркнутые числа в списке — простые.

На Pascal’е этот алгоритм можно записать следующим образом:

for i := 2 to trunc(sqrt(n)) do
  if is_prime[i] then
    j := i * i;
    while j <= n do
      begin
        if is_prime[j] then
          is_prime[j] := false;
        inc(j, i);
      end;


При n = 100 000 000 алгоритм отработал за 3 секунды. Первый алгоритм при таких входных данных я просто боюсь запускать. Видно, что повышение производительности просто огромно. К тому же алгоритм «решета Эратосфена» не так уж и сложен для запоминания.

3. Решето Аткина

Напоследок покажу еще один, чуть более сложный алгоритм — решето Аткина — это быстрый современный алгоритм нахождения всех простых чисел до заданного целого числа N. Основная идея алгоритма состоит в использовании неприводимых квадратичных форм (представление чисел в виде a*x^²+b*y^²). Отдельный этап алгоритма вычеркивает числа, кратные квадратам простых чисел. Алгоритм был создан А.О.Л. Аткиным и Д.Ю. Бернштайном, отсюда и его название.

Алгоритм описывать не буду, покажу лишь код:

for x := 1 to trunc(sqrt(n)) do
  for y := 1 to trunc(sqrt(n)) do
    begin
      p := 4 * sqr(x) + sqr(y);
      if (p <= n) and ((p mod 12 = 1) or (p mod 12 = 5)) then
        is_prime[p] := not is_prime[p];
      p := 3 * sqr(x) + sqr(y);
      if (p <= n) and (p mod 12 = 7) then
        is_prime[p] := not is_prime[p];
      p := 3 * sqr(x) - sqr(y);
      if (x > y) and (p <= n) and (p mod 12 = 11) then
        is_prime[p] := not is_prime[p];
    end;

for i := 5 to n do
  if is_prime[i] then
    begin
      k := sqr(i);
      p := k;
      while p <= n do
        begin
          is_prime[p] := false;
          p := p + k;
        end;
    end;


При тех же n = 100 000 000 алгоритм работает около 6 секунд, что несколько медленнее, чем «решето Эратосфена».

Эпилог

Вывод будет простым: не пользуйтесь перебором, а сейте через решето. А вот выбор решета остается за вами… ;)

Олимпиада по программированию (26.05.2012)

Как и обещал, выкладываю текст задач с олимпиады. Если кому-то нужны задачи в печатном виде — обращайтесь, распечатаю.

А. Веселый забор
Первые две недели своих каникул Вася решил провести в деревне. Но первые же полчаса, проведенные там, разочаровали его. Еще бы! В этой глуши нет даже GPRS. Тогда он решил заняться чем-то полезным. Например, покрасить забор, ведь, как известно из творчества, Марка Твена покраска забора — процесс очень увлекательный. Однако надо думать не только о самом процессе покраски, но и о том, что получится в результате, поэтому Вася задумался о том, как же сделать так, чтобы получившийся в итоге раскраски забор был наиболее веселым. Для этого Вася решил покрасить забор в разные цвета. Забор состоит из n досок и представляет собой замкнутую окружность. В распоряжении Васи находится k красок различных цветов. Одну доску разрешается красить только в один цвет.
Каждый цвет имеет свою степень веселости. Кроме того для всех пар цветов также определена степень взаимной веселости. Степень веселости всего забора определяется как сумма степеней веселости всех досок и сумма степеней взаимной веселости всех соседних досок забора. Определите, какой наибольшей степенью веселости может обладать забор.

Формат входных данных
В первой строке заданы 2 целых числа n и k (1 <= n,k <= 100). Во второй строке дано k чисел — степени веселости красок. В последующих k строках заданы по k чисел, описывающие степень взаимной веселости всех пар досок.

Формат выходных данных
На выходе должно быть единственное число — максимальная степень веселости забора.

Пример
Ввод 1
4 3
5 3 4
1 2 7
2 3 4
7 4 2
Вывод 1
46

Ввод 2
5 4
3 7 5 6
1 5 2 8
5 1 10 4
2 10 1 9
8 4 9 1
Вывод 2
73
В. Новые правила
Прошел один день в деревне, забор покрашен, больше дел нет. И даже в шахматы поиграть не с кем. Тогда Вася начал думать, как можно модифицировать правила шахмат, чтоб, вернувшись домой, можно было сыграть с друзьями во что-то новое. И первое, что в такой ситуации приходит в голову — это изменение ходов фигур. Вася решил изменить правила перемещения для слонов и ладьей.
Напомним ходы этих фигур в классическом варианте шахмат. Слон может перемещаться на любое количество полей по диагонали. Ладья может перемещаться на любое количество полей по вертикали и горизонтали.
Классические перемещения Вася решил не трогать, но добавить к ним немного своего. Так, слон теперь может перемещаться на 1 поле по вертикали и горизонтали, а ладья — на 1 поле по диагонали.
После модификации правил интересно расставить фигуры на доску и посмотреть, сколько же сейчас фигур находится под боем. А сможете ли вы решить эту задачу?
Кроме того, Вася решил немного изменить размеры поля.

Формат входных данных
В первой строке дано число n (1 <= n <= 1000) — размер стороны шахматного поля.
Во второй строке дано число m (1 <= m <= 100) — количество слонов на поле.
В последующих m строках записаны по паре чисел — координаты слонов.
В m+3 строке дано число k (1 <= k <= 100) — количество ладьей на поле.
В последующих k строках записаны по паре чисел — координаты ладьей.

Формат выходных данных
На выходе должно быть единственное число — количество фигур, которые находятся под боем.

Пример
Ввод 1
6
2
5 1
3 5
3
1 1
5 2
4 6
Вывод 1
4

Ввод 2
6
2
3 1
6 6
2
1 1
2 5
Вывод 2
2
С. Письмо
Васе не терпится рассказать о придуманных им шахматных фигурах своему другу, так что он решил написать об этом ему в письме (да, это то самое классическое письмо, которое пишут на бумаге, ведь в Интернет Вася никак не может выйти). Но он боится, что на почте могут вскрыть конверт, прочитать письмо и украсть его идею. Поэтому он решил прибегнуть к шифрованию с помощью шифровальной решетки.
Шифровальной решёткой называется бумажный квадрат размера n х n клеток, в котором вырезаны (n^2)/4 клетки-окошка. Наложив решётку на листок бумаги, имеющий такой же размер, Вася пишет в её окошках первые (n^2)/4 символа письма. После этого он поворачивает решётку по часовой стрелке на 90 градусов. При таком расположении все ранее написанные буквы оказываются под решёткой, а в окошках появляется чистая бумага. Он записывает в окошках следующие (n^2)/4 символа письма, после чего вновь поворачивает решётку на 90 градусов. Записав очередные (n^2)/4 символа, Вася делает ещё один поворот решётки и после этого пишет последние (n^2)/4 символа письма.
Однако Вася очень не любит рукописные тексты, поэтому он хочет написать письмо на компьютере и распечатать его (к счастью, все необходимое для этого он привез с собой). Но шифровать текст описанным выше способом на компьютере вручную не очень удобно, так что на ваши плечи возлагается задача написания программы, которая зашифрует текст письма.

Формат входных данных
Первая строка входных данных состоит из n^2 (n <= 100, n — четное) символов и является строкой, которую необходимо зашифровать. Данная строка состоит только из строчных латинских символов. В последующих n строка идет по n символов — описание решетки. Символ «.» означает, что на данной позиции находится бумага, символ «#» говорит о том, что на данной позиции находится окошко.

Формат выходных данных
На выходе должно быть n строк по n символов — результат работы алгоритма шифрования.

Пример
Ввод
thisissimpletext
#...
.#.#
....
.#..
Вывод
ttmi
shsi
pelx
tsie
D. OCR
Вася получил ответ на свое письмо (да, в стране, где происходят действия, почта работает очень оперативно). Но, о, УЖАС! Это письмо оказалось рукописным. Теперь он хочет распознать текст этого письма, чтобы спокойно прочитать текст на компьютере.
К счастью, у Васи есть образцы всех букв, а друг Васи, приславший ему письмо, обладает очень хорошим почерком.

Формат входных данных
Первая строка содержит 2 числа h и w (1 <= h,w <= 10) — высота и ширина каждой буквы. Вторая строка содержит число n (1 <= n <= 26) — количество букв в алфавите. Далее идет описание букв в следующем формате. Сначала задан единственный символ — строчная буква латинского алфавита. Потом идут h строк по w символов, описывающих данную букву (символ «.» означает пустое место, символ «#» означает, что в данном месте есть чернила). В последующих h строках идет текст письма, состоящий из символов «.» и «#». Между соседними буквами может быть любое количество символов «.». Гарантируется, что текст может быть распознан однозначно.

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

Пример
Ввод 1
5 5
3
o
.###.
#...#
#...#
#...#
.###.
c
.###.
#....
#....
#....
.###.
r
####.
#...#
####.
#.#..
#..#.
.###....###....####.
#...#..#.......#...#
#...#..#.......####.
#...#..#.......#.#..
.###....###....#..#.
Вывод 1
ocr

Ввод 2
5 5
5
i
.###.
..#..
..#..
..#..
.###.
p
####.
#...#
####.
#....
#....
e
#####
#....
###..
#....
#####
r
####.
#...#
####.
#.#..
#..#.
m
#...#
##.##
#.#.#
#...#
#...#
..####....#####....####...#...#
..#...#...#........#...#..##.##
..####....###......####...#.#.#
..#.......#........#.#....#...#
..#.......#####....#..#...#...#
Вывод 2
perm
Е. Белочка и орешки
Прошла неделя в деревне. Вася уже начинает втягиваться в эту жизнь. Прогулки по лесу и наблюдение за белочками стали для него обычным делом.
Белочка живет в дупле дерева. Дерево находится в лесу. Лес содержит непроходимые препятствия. Также по лесу разбросаны орешки. Белочка не может нести больше одного орешка за раз.
За какое минимальное количество ходов белочка может собрать все орешки?
В начальный момент белочка находится в дупле.

Формат входных данных
В первой строке даны 2 числа n и m (1 <= n,m <= 100) — высота и ширина поля. Следующие n строк содержат по m символов — описание поля в следующем формате.
«.» — пустая клетка
«#» — непроходимое препятствие
«&» — дерево с дуплом белочки
«@» — орешек
Гарантируется, что символ «&» встречается только один раз.

Формат выходных данных
Выведите единственное число — количество ходов, которое потребуется белочке, чтобы собрать все орешки. Если все орешки собрать невозможно выведите -1.

Пример
Ввод 1
6 8
.@......
.....##@
.##@...#
..#.#.#.
.&#...#.
.......@
Вывод 1
64

Ввод 2
4 4
...@
###.
@.#.
.&#.
Вывод 2
-1
F. Велосипед и старая карта
Однажды вечером, когда Васе в очередной раз стало невыносимо скучно, он изучал весь хлам, который собран на чердаке дома. И внезапно он нашел свой старый велосипед, а вместе с велосипедом была и карта. Вася вспомнил, что когда-то давно он любил кататься до деревни Y, находя при этом каждый раз новые пути до нее. Он решил вспомнить те пути, по которым он ездил, но его очень сильно сбивают пункты, которые не лежат ни на одном пути до деревни Y. Вася хочет, чтобы вы помогли исключить ему эти пункты. Известно, что в стране, в которой Вася живет, по дорогам можно передвигаться только в одном заданном направлении.

Формат входных данных
В первой строке заданы 2 числа n и m (1 <= n <= 1000, 1 <= m <= n*(n-1)) — количество пунктов на карте и количество дорог.
В последующих m строках следует по два числа a и b, что означает, что из пункта a существует дорога в пункт b.
Следует считать, что Вася находится в пункте с номером 1, а деревня Y является пунктом номер n.

Формат выходных данных
В первой строке выведите количество пунктов, которые принадлежат хотя бы одному пути до деревни Y. Во второй строке перечислите эти пункты порядке возрастания их номеров через пробел.

Пример
Ввод 1
7 8
1 2
1 3
1 4
2 5
3 7
4 7
5 2
6 7
Вывод 1
4
1 3 4 7

Ввод 2
8 9
1 2
1 3
2 4
3 8
4 8
5 8
5 7
6 5
7 6
Вывод 2
5
1 2 3 4 8
G. Энергетическая ценность
Вася решил в очередной раз съездить до деревни Y. Но путь до нее не простой, поэтому Васе необходимо запастись едой. При этом Вася знает, что, если его груз станет тяжелее Wmax кг, ему будет ехать очень не комфортно, и он не получит никакого удовольствия от этой поездки.
Открыв холодильник, Вася увидел там много еды, для которой известна ее энергетическая ценность и вес. Помогите Васе выбрать, что брать с собой так, чтобы суммарная энергетическая ценность еды была максимальна.

Формат входных данных
В первой строке даны два числа вещественное Wmax — максимальный вес груза Васи (1 <= Wmax <= 1000 и целое n (1 <= n <= 15) — количество единиц еды, которая есть в холодильнике. В последующих n строках даны по 2 числа целое c и вещественное w (1 <= c <= 1000, 1 <= w <= 1000) — энергетическая ценность и вес текущей единицы еды соответственно.
Все вещественные числа в задаче даны с точностью 10^-2.

Формат выходных данных
Выведите максимальную возможную энергетическую ценность.

Пример
Ввод 1
10.00 4
3 5.00
6 7.00
2 4.00
1 1.00
Вывод 1
7

Ввод 2
23.70 6
10 15.80
5 3.70
23 7.70
13 10.10
8 4.30
20 17.70
Вывод 2
44
H. Хэш-функция
Коротая последние дни в деревне, Вася заинтересовался проблемой хэширования информации и придумал свою хэш-функцию. Нам про эту функцию известно лишь то, что в результате ее работы получается число в интервале [1;n]. Также известно, что необходимо будет обрабатывать k записей. Посчитайте вероятность того, что хотя бы 2 записи будут обладать одинаковым хэшем.

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

Формат входных данных
В единственной строке заданы 2 целых числа (1 <= n,k <= 10000).

Формат выходных данных
Выведите единственное число — ответ на задачу с погрешностью не более 10^-6.

Пример
Ввод 1
100 20
Вывод 1
0.8696005

Ввод 2
100 10
Вывод 2
0.3718435
I. Теория чисел
Пока Вася придумывал хэш-функцию, он изучил немало литературы по теории чисел, и его очень заинтересовала бинарная проблема Гольдбаха. Эта проблема имеет следующее утверждение:
«Любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел»
Теперь Вася хочет убедиться в том, что это действительно так хотя бы для не очень больших чисел.

Формат входных данных
В первой строке входного файла задано число t (1 <= t <= 10) — количество запросов. В последующих t строках перечислены запросы. Каждый запрос содержит единственное четное число x (4 <= x <= 1000000).

Формат выходных данных
На каждый запрос необходимо вывести 2 простых числа a и b таких, что a+b=x. Если возможны несколько ответов, выведите любой.

Пример
Ввод 1
3
4
6
8
Вывод 1
2 2
3 3
3 5

Ввод 2
4
18
26
36
30
Вывод 2
5 13
3 23
5 31
7 23
J. Шарики во сне
Каникулы закончились. Завтра Васе надо идти на занятия. И почему-то накануне первого учебного дня Вася видит странный сон, и снятся ему шарики, которые катятся по столу.
Шарики катятся вдоль одной прямой со скоростью 1 см/сек. Если два шарика сталкиваются, то они меняют направление своего движения на противоположное. Вася смог точно определить положения шариков, а также ширину стола, но он никак не может понять в какую сторону, какой шарик катится. Также Вася осознал, что как только последний шарик упадет со стола, зазвенит будильник, и Васе придется просыпаться.
Определите максимальное возможное время в секундах, в течение которого Вася может еще поспать.
Радиусом шариков следует пренебречь.

Формат входных данных
Первая строка содержит 2 целых числа l и n (2 <= l,n <= 1000000) — длина стола и количество шариков соответственно.
Вторая строка содержит n целых чисел — координаты шариков. Каждая координата принадлежит интервалу (0,l).
Все координаты заданы в сантиметрах.

Формат выходных данных
Выведите единственное число — ответ на задачу.

Пример
Ввод 1
10 3
2 6 7
Вывод 1
8

Ввод 2
214 7
11 12 7 13 176 23 191
Вывод 2
207

Ненормальное программирование (cерия 2). Memento...

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

В Delphi отсутствует как таковая проверка выхода за границы при обращении к элементам массива, поэтому можно обратиться к тем «элементам», которые лежат в памяти перед или после самого массива. Обычно точно не получится сказать, что же именно будет там находиться, однако, если мы объявляем, к примеру, одновременно два массива, то они с достаточно большой долей вероятности будут располагаться в памяти последовательно один за другим.

Что же нам может дать подобное поведение компилятора, кроме проблем?

Разберем простейшую задачу:
Имеются 2 массива по… Ммм… Предположим по 8 элементов (заполним их с помощью генератора псевдослучайных чисел). И элементы этих двух массивов нужно переставить таким образом, чтобы в первом были минимальные элементы из двух исходных массивов, а во втором – максимальные.


Задача элементарная и сводится обычно к двум вариантам: либо это последовательный поиск минимальных/максимальных элементов и постепенная перестановка, либо объединение двух исходных массивов в третий и его сортировка с помощью стандартных средств.

Но… Delphi в силу той особенности, о которой мы сегодня говорим, позволяет провернуть очень изящный фортель, а именно – отсортировать сразу оба массива как один. К тому же для этого даже не нужно делать ничего особенного: просто достаточно сортировать первый массив «сдвинув» его правую границу на длину второго массива.

{$APPTYPE CONSOLE}

uses
  SysUtils;

{ Стандартный алгоритм "быстрой" сортировки (можно использовать любой другой) }
procedure qSort(var a: array of Integer; low, high: Integer);
var
  i, j, x: Integer;
  t: Integer;
begin
      i := low;
      j := high;
      x := a[(low + high) div 2];
      repeat
          while a[i] < x do inc(i);
          while a[j] > x do dec(j);
          if i <= j then
            begin
              t := a[i];
              a[i] := a[j];
              a[j] := t;
              inc(i);
              dec(j);
            end;
      until (i > j);

      if low < j then qSort(a, low, j);
      if i < high then qSort(a, i, high);
end;

{ Это сделано для красивого вывода массивов }
procedure Print(a: array of Integer; name: String);
var
  i: Integer;
begin
  Write(name, ': [ ');
  for i := 0 to length(a) - 1 do
    if i < length(a) - 1 then
      Write(a[i]:3, ', ')
    else
      WriteLn(a[i]:3, ']');
end;

var
  i: integer;
  a, b: array [0..7] of Integer;
begin
  { Заполняем массивы }
  Randomize;
  for i := 0 to length(a) - 1 do
    begin
      a[i] := Random(256);
      b[i] := Random(256);
    end;

  { Выводим, чтобы посмотреть, что было }
  Print(a, 'A');
  Print(b, 'B');
  WriteLn;

  { Сортируем все 16 элементов }
  qSort(a, 0, 15);

  { Выводим, чтобы посмотреть, что стало }
  Print(a, 'A');
  Print(b, 'B');
  WriteLn;

  ReadLn;
end.


Как видите – все просто! Разве что не все позволяют так делать (к примеру, Free Pascal не даст так просто гулять по чужой памяти).

PS.: Напоследок, попробуйте решить задачу тем же способом, если будет 2 массива по 10 элементов типа Byte.

Олимпиада по программированию

Нашел одну олимпиаду по программированию, проводимую факультетом управления и прикладной математики МФТИ. Правда она вроде как для школьников, но и нам можно потренироваться. Олимпиада проводится до 15 23 января (продлена).

В контесте 20 задач. Олимпиада проводится по кировской системе (то есть баллы приносит даже решение, которое проходит только часть тестов) на Ejudge. Языки: C, C++, basic (компилятор yabasic), perl, pascal, Java, C#, ruby, python, fortran. На проверку отправляется исходный текст программы (не исполняемый и не файл проекта). Проверка автоматическая, так что никаких окон и приглашений к вводу делать не надо, а вот строгое соответствие формату данных, указанному в задаче, требуется. Ввод из стандартного потока ввода (с клавиатуры), вывод в стандартный поток вывода (на экран).

Задачи разного уровня от самых простых (из контрольных работ для начинающих и пробных туров олимпиад) до совсем сложных (уровня полуфинала чемпионата мира по програмимрованию ACM ICPC). Составители контеста — тренеры и часть состава команды mipt_waterogers, финалиста ACM ICPC 2010-2011 и 2011-2012 годов.

Вот собственно этот сайт, где проводится олимпиада: judge.mipt.ru. Будем участвовать?

Обработка малых чисел

Эта публикация родилась из обсуждения одной задачки в блоге Команда ФПИ по программированию.
Итак, недавно, столкнулся с двумя похожими ситуациями, когда заведомо известный результат не получается при вычислении его программным образом.
Ситуация 1: Excel не дает ноль для тригонометрической функции cos(Pi/2).
Ситуация 2. FreePascal не дает ноль для функции frac(log2(128)) Команда ФПИ по программированию — функция log2.

Я и раньше встречался с подобными ситуациями. Особенно опасны они ненахождением решения в ситуации проверки равенства двух вещественных чисел. Разберемся, почему всё это происходит? Очевидно, что по причине ограниченности разрядной сетки числа. Например, посмотрим про вещественные типы данных в справке Delphi:
Type		Range	                        Significant digits
Real48		2.9x10^-39 .. 1.7x0^38			11-12
Single		1.5x10^-45 .. 3.4x10^38			7-8
Double		5.0x10^-324 .. 1.7x10^308		15-16
Extended	3.6x10^-4951 .. 1.1x10^4932		19-20

И сделаем два вывода:
1) нельзя задать сколь угодно малое или сколь угодно большое вещественное число, так как есть ограничение на порядок числа;
2) точность представления числа ограничена мантиссой (количеством значащих цифр).

Отсюда важное для программиста заключение: сравнивать вещественные числа так: «x>y» или так: «x<y» можно, но так: «x=y» — опасно.
Когда-то давно решал я подобную проблему, связанную с заполнением до предела (типа задачи «о заполнении рюкзака», ru.wikipedia.org/wiki/Задача_о_ранце) и столкнулся с проблемой сравнения двух решений, представленных вещественными числами.
— — — — — — — — — — Для текущего изложения я придумал несколько примеров, достаточно простых, но демонстрирующих суть проблемы. Несколько итераций позволят нам выйти на приемлемое решение обсуждаемой проблемы.
program Zero_01;
{$APPTYPE CONSOLE}
uses
  SysUtils,Math;
var argE: double;
    argR,arg: single;
    argR48: Real48;
begin
        arg:=Pi;      // Pi - Returns 3.1415926535897932385
                      // всего 20 значащих цифр
                      // у arg - тип single - 7 значащих цифр
        argR48:=Pi;
        writeln('Pi=',#9,Pi);
        writeln('arg=',#9,arg);
        writeln('argR48=',#9,argR48);
        writeln('__________');
        writeln(' sin=');
{1}     writeln(#9,sin(Pi));

{2}     writeln(#9,sin(arg));
        argE:=sin(arg);  // argE: double;

{3}     writeln(#9,argE);

          argR:=argE/1E30;
          argR:=argR*1E30;
{4}     writeln(#9,argR);

          argR:=argE/1E39;
          argR:=argR*1E39;
{5}     writeln(#9,argR);

        readln;
end.

Вот результаты этой программы:
Обработка малых чисел
Первое что мы увидим — число Пи представлено 20-ю значащими цифрами. Но мы то знаем, что оно иррациональное. Отсюда уже будут возникать ошибки в расчете тригонометрических функций.
Далее видим, что присвоение Pi переменной может еще ухудшить ситуацию: в переменной типа single несовпадения с Pi начинаются с 8-й значащей цифра, а для Real48 — с 13-ой;
Соответственно и вычисления синуса от разных Пи будут отличаться. Но и само значение sin(Pi) окажется отличным от нуля во всех случаях. Однако, отличие от нуля для значения Pi, представленного константой проявляется порядком E-20, а для значения Pi, представленного переменной типа single — Е-08. То есть в подсчет через переменную дает результат в 10^12 раз менее точно.

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

program Zero_02;
{$APPTYPE CONSOLE}
uses
  SysUtils,Math;
var arg: single;

function comparing1(arg1: single; arg2: single): boolean;
begin
  result:= abs(arg1-arg2)<1E-6;
end;

function comparing2(arg1: single; arg2: single): boolean;
var temp: single;
begin
  temp:=abs(arg1-arg2)/1E39;
  result:= temp*1E39 = 0;
end;

begin
        arg:=Pi;
        writeln('Pi=',#9,Pi);
        writeln('arg=',#9,arg);
        writeln('__________');
        writeln(' sin=');
{1}     writeln(#9,sin(2*Pi));
{2}     writeln(#9,sin(2*arg));
{3}     if comparing1(sin(2*arg),0)
                then writeln(#9,'=0')
                else writeln(#9,'<>0');
{4}     if comparing2(sin(2*arg),0)
                then writeln(#9,'=0')
                else writeln(#9,'<>0');

        readln;
end.

Вот результаты этой программы:
Обработка малых чисел
Как видите, константа Pi и переменная всё так же отличаются, как и результаты посчитанные для величины 2*Pi. Результаты всё так же отличаются не только друг от друга, но, что более печально, и от нуля. Однако в последних двух строчках программы нули таки выводятся. Тут я применил два подхода, обозначенных ещё в самом начале этого изложения по поводу ограничений на порядок числа и на точность, заданной мантиссой числа.
Функции сравнения comparing1 и comparing2 разными путями приходят к одинаковому результату: если числа отличаются ненамного, значит их можно признать равными. Только первая функция напрямую сравнивает, можно сказать, порядок несовпадения чисел, а вторая — отсекает все значащие цифры из мантиссы делением/умножением. Деление на порядок 39 выбрано, конечно, не случайно — надо ведь дотянуть до границы в Single 1.5x10^-45.
Итак, этот подход можно применять для работы с малыми числами или для сравнения двух малоотличающихся чисел.

Пойдём дальше и попробуем применить подход к какой-нибудь задаче. Я особо времени не тратил на изобретение задач, а взял задачу с заведомо известным результатом (для того чтобы заранее знать ответ).
Пусть нужно найти точки пересечения двух функций: cos(x/2) и sin(2*x), в диапазоне изменения x от 2,5 до 3,5. Нетрудно догадаться, что при x=Pi значения функций равны. Но только не для вычислителя — см. рисунок:
Обработка малых чисел
Обратите внимание, что косинус и синус для обозначенного значения в Excel не равны нулю.
Так же следует учитывать, что мы считаем значения с определенной дискретностью (шаг на рис. равен 0,01), то есть мы можем просто не попасть точно в точку пересечения функций. Как же быть?
Проведем первый эксперимент, имитируя Excel — просто запустим цикл с определенным, фиксированным шагом 1E-06:
program Zero_03;
{$APPTYPE CONSOLE}
uses SysUtils,Math;

function comparing1(arg1: single; arg2: single): boolean;
begin
  result:= abs(arg1-arg2)<1E-5;
end;

var low,hi,i,z1,z2: single;
    k: word;

begin
  low:=2; hi:=4;
  i:=low; k:=0;
  repeat
    z1:=cos(i/2);
    z2:=sin(2*i);
    if z1=z2 then writeln(#9,i);
    if comparing1(z1,z2)
              then
              begin
                writeln(#9,'z1=',z1);
                writeln(#9,'z2=',z2);
                inc(k);
              end;
    i:=i+1E-06;
  until i>hi;
  writeln(#9,k,' solutions');
  readln;
end.

Обратите внимание — я оставил строку «if z1=z2 then writeln(#9,i);» для того, чтобы удостовериться, что прямое сравнение вещественных чисел не даст желаемого результата.
Вот результаты работы программы:
Обработка малых чисел
Итак, прямой перебор всего диапазона даст нам 8 решений с заданной точностью. Видимо такой подход не оптимален, особенно по причине большого перебора, зависящего от величины диапазона и точности вычисления. Классическим способом преодоления указанной проблемы считается использование метода половинного деления с постепенным сужением диапазона.
program Zero_04;
{$APPTYPE CONSOLE}
uses SysUtils,Math;
const error=1E-6;
var low,hi,i,z1,z2: single;
    k: word;

function comparing1(arg1: single; arg2: single): boolean;
begin
  result:= abs(arg1-arg2)<error;
end;

begin
  low:=2; hi:=4; k:=0;
  // в начале на нижней границе  z1>z2
  // в начале на верхней границе z1<z2
  i:=(low+hi)/2;
  z1:=cos(i/2);
  z2:=sin(2*i);
  while not comparing1(z1,z2) do
  begin
    inc(k);
    i:=(low+hi)/2;
    z1:=cos(i/2);
    z2:=sin(2*i);
    if z1>z2
      then low:=i
      else hi:=i;
  end;
                writeln('Pi=',#9,Pi);
                writeln('i=',#9,i);
                writeln('z1=',#9,z1);
                writeln('z2=',#9,z2);
                writeln('k=',#9,k);                
  readln;
end.

Вот результаты работы программы:
Обработка малых чисел
Что видим: решение (точка пересечения двух функций) с заданной точностью (error) найдено за 21 шаг для аргумента близкого к Пи (отличия проявляются лишь в 8-ой значащей позиции мантиссы аргумента).

==========================================
summary
1) вещественные числа сравнивать операцией "=" не правильно;
2) переменные вещественного типа дают результат с ограниченной точностью;
3) если в задаче не указано с какой точностью найти решение, надо самому об этом позаботиться.
==========================================
P.S.1. Я мог что-то не заметить, что-то упустить — желающие могут оставить свои комментарии…
P.S.2. Программы апробировались на Delphi 7 и Delphi 2010.

Ненормальное программирование (cерия 1). Проверка на нечетность

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

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

  1. Собственно, проверка остатка от деления на 2.
  2. Побитовая конъюнкция исходного числа и единицы (в случае, если в результате получим единицу, то исходное число является нечетным).
  3. Побитовый сдвиг исходного числа на 1 бит вправо и на 1 бит влево (в случае, если число при этом изменится, то оно нечетное).

Помимо этого, для компиляторов Delphi и FPC проверялось использование стандартной функции Odd из модуля System.

Тестирование проводилось с использованием 4 компиляторов:

  • C++/CLI (Visual Studio 2010, .NET Framework 4.0)
  • C++ (Qt 4.7)
  • Delphi (Embarcadero Delphi 2010 Architect)
  • FPC (Free Pascal 2.4)

на следующей машине:

  • Intel Core 2 Duo E7500 с частотой 2,93 ГГц
  • 2 Гбайт оперативной памяти
  • под управлением ОС Microsoft Windows XP Service Pack 3

Тестирование производилось в 10 заходов при проверке по 1 млрд. значений в каждом. Все результаты даны в миллисекундах.

Таблица результатов C++/CLI
Таблица результатов C++ (Qt)
Таблица результатов Delphi 2010
Таблица результатов Free Pascal
Ну и те же самые результаты в графическом представлении:

График результатов C++/CLI
График результатов C++ (Qt)
График результатов Delphi 2010
График результатов Free Pascal
Даже при беглом анализе полученных данных становится понятно, что широко используемый алгоритм проверки остатка от деления на 2 является далеко не самым быстрым.

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

Победителем у нас сегодня оказывается Delphi 2010 с ее результатом в 2,5 секунды. Аутсайдером же становится C++/CLI с результатом работы алгоритма с использованием сдвигов более 31,5 секунд.

На сегодня это все. Старайтесь писать быстрый код… ;)

Qg, или К чему может привести безделье

Летом было такое время, когда работы особо не хватало, а грузить чем-то мозг хотелось, что приводило к непредсказуемым последствиям. Одним из таких «последствий» является язык программирования Qg, который был сработан за пару недель.

Qg 0.1 для Linux

Дистрибутивы интерпретатора для разных ОС (о даже как мозг закрутило) можно скачать тут:


А теперь пара слов о самом языке. Хотя это даже языком сложно назвать, но все же. Qg позволяет работать с однобайтовыми ячейками памяти, модифицируя их различным способом (можно прибавлять или вычитать некоторые величины или значения других ячеек или производить сдвиги значений влево-вправо). Помимо этого есть даже обработка циклов и условий. В следующем сообщении рассмотрю поподробнее синтаксис.

В комплекте с интерпретатором имеется пара написанных на Qg программ (конечно, «Hello, World!», а также программа перемножения двух чисел), поэтому можно посмотреть примерно, как там что устроено.

Инструкция if-else

Инструкция if-else производит ветвление программы в зависимости от результата провери некоторого условия на истинность и имеет следующий вид:
if (условие) 
оператор_1; 
else 
оператор_2;
Условие может быть любым выражением, но чаще всего оно содержит операторы сравнения.
Если условие принимает истинное значение (true), выполняется оператор_1. В противном случае (false) выполнение программы переходит к оператору_2.
В конструкции языка С++ операторы могут быть блочными. Это означает, что в зависимости от принятого решения выполняется не один, а целый блок операторов.
Блок начинается с открывающей фигурной скобки ({) и заканчивается закрывающей фигурной скобкой (}). Все содержимое блока расматривается компилятором, как единый оператор:
if (условие)
{ блок_1;} 
else
{ блок_2;}
Рассмотрим пример использования инструкции if для определения, является введенное с клавиатуры число положительным или отрицательным:
#include 
using namespace std; 
int main(){ 
int b; 
cin >> b;
if(b>0){ 
  //Если условие b>0 выполнено 
  cout << "b положительное" 
} 
else {
  //Если условие b>0 не выполнено 
  cout << "b отрицательнои или равно 0" 
} 
return 0; 
}

В приведенном примере объявляется целочисленная переменная b и считывается ее значение с клавиатуры, а потом следует сравнение этого значения с нулем. Если значение b больше нуля. выводится сообщение «b положительное», а если b меньше или равно нуля — «b отрицательнои или равно 0».
Одной из типичных ошибок при испольозвании инструкции if является пропуск фигурных скобок для обозначения блока выполняемых операторов:
int main(){ 
int x = 0, y = 8, z = 0; 
if(x != 0) 
z++; 
y/=x;  //Ошибка! деление на 0
cout << "y = " << y;
return 0;
}
В этом примере присутствует проверка значения переменной x на неравенство нулю. Если значение x отлично от нуля, производится увеличение на единицу значения переменной z. Однако далее вычисляется выражение y = y/x, независимо от того, какое значение имеет переменная x. Поскольку переменная x имеет нулевое значение, то оператор деления выдаст сообщение о попытке деления на ноль.
Если правильно определить блок исполняемых операторов, как показано ниже, вычисления выполнятся корректно:
int main(){
int x = 0, y = 8, z = 0;
if(x != 0){
  z++;
  y/=x;
}
cout << "y = " << y;
return 0;
}
В данном варианте вычисление выражения y = y/x будет производиться только в том случае, если значение переменной x отлично от нуля.
Прведенный пример показывает, что инструкуция выбора if может быть использована без блока else, который является необязательным.
Вместо инструкции if-else иногда удобнее использовать условное выражение ?:, если входящие в него выражения являются достаточно простыми.