Алгоритмы

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

Решето Эратосфена (Sieve of Eratosthenes) представляет собой способ генерации простых чисел. Простые числа - это такие числа, которые нацело делятся на 1 и на себя самих. Первое простое число - 2, которое к тому же является единственным четным простым.

Эратосфен (276-194 до н.э.) был Александрийским астрономом, математиком и поэтом. Он заведовал легендарной Александрийской библиотекой и знаменит тем, что точно определил длину окружности земного шара, сравнивая длины, которые отбрасывают тени объектов на разных географических широтах во время летнего солнцестояния.

"Решето Эратосфена" начинается с представления последовательного ряда целых чисел, начиная с 2:

2 3 4 5 6 7  8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ...

Исследуем эти числа одно за другим. Двойка - простое число, следовательно, любое кратное 2 - не простое. Таким образом, можно исключить любое число, кратное 2 из списка простых чисел:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...

Тройка - простое, следовательно, любое число, кратное 3, - не простое. Исключаем их:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ...

Следующее просто число - 5.

Описание алгоритма дается в книге Программирование в тональности C# (стр.270)

Конвертер римских чисел

Мы часто используем в своей повседневной жизни римские числа — на циферблатах часов, на страницах книг, на памятниках. Например, в Москве есть станция метро "Римская", построенная при участии итальянских строителей. Над вестибюлем можно увидеть дату открытия станции — MCMXCV. Интересно, вы сможете с ходу определить записанный год? Американский ученый Стивен Шварцман предложил специальный стандарт для римских чисел (ISRN, International Standart Roman Numerals), в котором описаны несколько правил их записи. Например, нельзя записывать одну и ту же цифру более трех раз подряд. Поэтому не удивляйтесь, если увидите на старинных часах числа, не соответствующие стандарту, который был предложен относительно недавно. В частности, нередко встречается запись числа четыре как IIII вместо привычного уже нам IV. В таблице представлено соответствие римских чисел применяемым нами арабским.

Соответствие римских чисел арабским

Единицы		Десятки		Сотни		Тысячи
1	I	10	X	100	C	1000	M
2	II	20	XX	200	CC	2000	MM
3	III	30	XXX	300	CCC	3000	МММ
4	IV	40	XL	400	CD
5	V	50	L	500	D
6	VI	60	LX	600	DC
7	VII	70	LXX	700	DCC
8	VIII	80	LXXX	800	DCCC
9	IX	90	XC	900	СМ

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


private string RomanToArabic(string roman)
{
    int i;
    string ch;
    int result = 0;
    int new_value = 0;
    int old_value = 0;

    for (i = 1; (i <= roman.Length); i++)
    {
        ch = roman.Substring((i - 1), 1);

        switch (ch.ToUpper())
        {
            case "I":
                new_value = 1;
                break;
            case "V":
                new_value = 5;
                break;
            case "X":
                new_value = 10;
                break;
            case "L":
                new_value = 50;
                break;
            case "C":
                new_value = 100;
                break;
            case "D":
                new_value = 500;
                break;
            case "M":
                new_value = 1000;
                break;
        }

        if (new_value > old_value)
        {
            result = result + new_value - 2 * old_value;
        }
        else
        {
            result = result + new_value;
        }

        old_value = new_value;
    }
    return result.ToString();
}

private void button1_Click(object sender, EventArgs e)
{
  MessageBox.Show(RomanToArabic(textBox1.Text));
}

Если у вас возникли затруднения с вычислением даты открытия станции "Римская", то теперь вы можете проверить свои вычисления с помощью написанного конвертера.

Преобразовать int в string без использования

Задача: преобразовать int в string без использования ToString(), а так же boxing и unboxing. Словом без преобразований (из форума www.gotdotnet.ru)

static string[] digits = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };

static void Main(string[] args)        
{
    int N = 892347971; // любое число
    string str = string.Empty;

    while(N > 0)
    {
        str = digits[N - ((N / 10) * 10)] + str;
        N = N / 10;
    }
    Console.WriteLine(str); 
    Console.ReadLine();
}

Комбинаторика

Перестановки, факториал и т.д. (источник: журнал MSDN Magazine)

Перестановка строк – это изменение их порядка в наборе. Например, для исходного набора, состоящего из трех строк: «apple», «banana» и «cherry», существует всего шесть возможных перестановок:

{ "apple", "banana", "cherry" }
{ "apple", "cherry", "banana" }
{ "banana", "apple", "cherry" }
{ "banana", "cherry", "apple" }
{ "cherry", "apple", "banana" }
{ "cherry", "banana", "apple" }

Программист должен уметь: вычислять точное количество перестановок для данного набора строк и создавать все перестановки.

Общее число элементов перестановки порядка n равно n! (читается «эн факториал»). Например, для четырех элементов общее число перестановок составляет

4! = 4 * 3 * 2 * 1 = 24

Перестановки тесно связаны с сочетаниями, и эти понятия иногда путают. Сочетания строк – это подмножества исходного набора строк, где порядок не имеет значения. Например, вернемся к нашему исходному множеству строк: «apple», «banana» и «cherry». Существует три элемента сочетания для размера подмножества k = 1.

{ "apple" }
{ "banana" }
{"cherry" }

Три элемента сочетания существуют и для размера подмножества k = 2.

{ "apple", "banana" }
{ "apple", "cherry" }
{ "banana", "cherry" }

И только один элемент сочетания - для размера подмножества k = 3.

{ "apple", "banana", "cherry" }

Число элементов перестановки порядка n

Вычисление общего числа элементов перестановки строк для данного набора строк – это парадоксальная задача, простая и в то же время сложная. Предположим, имеется четыре строки: «ant», «bat», «cow» и «dog», так что порядок равен n = 4. Общее число возможных элементов перестановки равно 24. В каждом из элементов может присутствовать только одна из четырех строк на первой (самой левой) позиции, любой из оставшихся трех атомов на следующей позиции, один из оставшихся двух строк на следующей позиции, и, наконец, единственный оставшаяся строка на последней позиции. Другими словами, для порядка n = 4 существует 4 * 3 * 2 * 1 = 24 элемента перестановки. Вы, вероятно, узнали формулу n факториал (часто она записывается как n!). Следовательно, общее число элементов перестановки строк порядка n равно n факториал. Давайте рассмотрим три различных реализации метода вычисления факториала.

Первый подход заключается в расчете факториала с помощью рекурсии. Например:

public static ulong FactorialRecursive(int n)
{
  if (n < 0) throw new ArgumentOutOfRangeException("n");
  if (n == 0 || n == 1) return 1;
  else return (ulong)n * FactorialRecursive(n - 1);
}

В большинстве случаев это не самый удачный подход. Если не соблюдать осторожность, легко получить неверный ответ. Значение n! очень быстро становится очень большим. Например, значение 64! примерно равно

126,886,932,100,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000

На самом деле, самое большое значение, которое можно хранить в переменной типа ulong, составляет всего 20!, то есть:

20 * 19 * 18 *. .. * 2 * 1 = 2,432,902,008,176,640,000

Как вы думаете, что произойдет при вызове

ulong result = FactorialRecursive(21)

в программе? По умолчанию, когда компьютер достигнет значения ulong.MaxValue (равного 18 446 744 073 709 551 615), то компьютер вернется обратно к 0 и продолжит вычисления, не показывая никаких предупреждающих сообщений. Обратите внимание, что общеязыковая среда исполнения (CLR) может выполнять проверку переполнения и потери точности для числовых операций. Эту функцию можно включить при компиляции. Впрочем, не существует никаких особенных причин для того, чтобы использовать рекурсивный метод для решения данной задачи.

Второй подход к созданию метода расчета факториала заключается в итеративном вычислении ответа, примерно так:

public static ulong FactorialCompute(int n)
{
  if (n < 0 || n > 20)
      throw new Exception("Значение аргумента должно находиться между 0 и 20");
  ulong answer = 1;
  for (int i = 1; i <= n; ++i) answer = checked(answer * (ulong)i);
  return answer;
}

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

Третий способ - поскольку набор возможных значений входного аргумента очень мал – от 0 до 20 – с тем же успехом можно было бы просто хранить 21 возможный результат в таблице поиска. Это решение выглядит примерно так:

public static ulong FactorialLookup(int n)
{
  if (n < 0 || n > 20)
    throw new Exception("Значение аргумента должно находиться между 0 и 20");
  ulong[] answers = new ulong[] { 1, 1, 2, 6, 24, 120, 720, 5040, 40320,
    362880, 3628800, 39916800, 479001600, 6227020800, 87178291200,
    1307674368000, 20922789888000, 355687428096000, 6402373705728000,
    121645100408832000, 2432902008176640000 };
  return answers[n];
}

Для большинства сценариев тестирования программного обеспечения последний способ с поиском является самым эффективным.