Наибольшая общая подпоследовательность

По идее можно решать за O(nlogn), но здесь за O(n^2) простой динамикой:

#include <vector>
#include <iostream>
#include <algorithm>

using std::vector;
using std::cin;
using std::cout;
using std::max_element;

int countLongestCommonSubsequenceLength(const vector<int> &first_sequence,
                                        const vector<int> &second_sequence) {
  vector< vector<int> > common_prefix_length(first_sequence.size() +
    1, vector<int>(second_sequence.size() + 1, 0));
  for (size_t first_number = 1;
       first_number <= first_sequence.size();
       ++first_number) {
    for (size_t second_number = 1;
         second_number <= second_sequence.size();
         ++second_number) {
      if (first_sequence[first_number - 1] ==
          second_sequence[second_number - 1]) {
        common_prefix_length[first_number][second_number] =
          common_prefix_length[first_number - 1][second_number - 1] + 1;
      } else if (common_prefix_length[first_number - 1][second_number] >=
          common_prefix_length[first_number][second_number - 1]) {
        common_prefix_length[first_number][second_number] =
          common_prefix_length[first_number - 1][second_number];
      } else {
        common_prefix_length[first_number][second_number] =
          common_prefix_length[first_number][second_number - 1];
      }
    }
  }
  return common_prefix_length.back().back();
}

void readSequence(vector<int> *sequence) {
  int length, tmp_int;
  cin >> length;
  for (int element_number = 0; element_number < length; ++element_number) {
    cin >> tmp_int;
    sequence->push_back(tmp_int);
  }
}

int main() {
  vector<int> first_sequence, second_sequence;
  readSequence(&first_sequence);
  readSequence(&second_sequence);
  cout << countLongestCommonSubsequenceLength(first_sequence, second_sequence)
       << std::endl;
  return 0;
}

Циклический сдвиг последовательности на заданное число позиций

Параметры begin и end могут быть либо указателями на ячейки массива, либо итераторами, указывающими на начало и конец последовательности. Параметр k может принимать отрицательные значения, что означает сдвиг в другом направлении. Продемонстрирована работа функции с обычным массивом и вектором.

#include <vector>
#include <iostream>
#include <algorithm>

using std::vector;
using std::cout;
using std::endl;
using std::swap;

template <typename T> void rotate(T begin, T end, int k) {
  if (k > 0) {
    for (int i = 0; i < k; ++i) {
      for (T j = end - 1; j != begin; --j) {
        swap(*j, *(j-1));
      }
    }
  }
  if (k < 0) {
    for (int i = 0; i > k; --i) {
      for (T j = begin; j != end - 1; ++j) {
        swap(*j, *(j+1));
      }
    }
  }
}

// Test.
int main() {
  vector<int> a;
  a.push_back(1);
  a.push_back(2);
  a.push_back(3);
  a.push_back(4);
  rotate(a.begin(), a.end(), 2);
  for (vector<int>::iterator it = a.begin(); it != a.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
  int b[] = {1,2,3,4};
  rotate(b+0, b+4, -1);
  for (int i = 0; i < 4; i++) {
    cout << b[i] << " ";
  }
  cout << endl;
  return 0;
}

Метод деления пополам

Нахождение корня передаваемой в качестве параметра монотонной функции f на отрезке [a, b] методом деления пополам.

//Fuction returns b+1 if solution does not exist.
double solve(double a, double b, double (*f)(double)) {
  if (a > b) {
    return b+1;
  }
  if (f(a) * f(b) >= 0) {
    if (f(a) == 0) {
      return a;
    }
    if (f(b) == 0) {
      return b;
    }
    return b+1;
  }
  double x = (a + b) / 2;
  if (f(a) * f(x) <= 0) {
    return solve(a, x, f);
  }
  if (f(x) * f(b) <= 0) {
    return solve(x, b, f);
  }
  return b+1;
}

Расширенный алгоритм Евклида и вычисление обратного элемента по модулю в кольце

Написана функция, вычисляющая НОД целых чисел a и b и находящая целые коэффициенты x и y, такие, что ax + by = НОД(a, b). На основе этой функции написана новая функция, вычисляющая обратный элемент к a в кольце вычетов по модулю n, или сообщающая, что такого элемента не существует.

int gcdex(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int x1, y1;
  int d1 = gcdex(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return d1;
}

// Function returns 1 if such element doesn't exist and 0 if exists and puts it
// in result.
int ReverseElement(int a, int N, int &result) {
  int x, y, d;
  d = gcdex(a, N, x, y);
  if (d != 1) {
    return 1;
  } else {
    result = x;
    return 0;
  }
}

Определение дня недели по заданной дате

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

#include <iostream>
#include <algorithm>

using std::cout;
using std::cin;
using std::endl;
using std::min;
using std::max;

bool IsLeapYear(const int year) {
  if (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)) {
    return true;
  } else {
    return false;
  }
}

const int days_in_month[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int DefineWeekday(const int number, const int month, const int year) {
  // Reference date is 1 Jan 1990 and it is monday.
  int smaller_year = min(1990, year), bigger_year = max(1990, year);
  int days_difference = 0;
  // Count the day of the the 1 Jan of needed year.
  for (int i = smaller_year; i < bigger_year; ++i) {
    if (year > 1990) {
      days_difference += 365;
      if (IsLeapYear(i)) {
        ++days_difference;
      }
    } else {
      days_difference -= 365;
      if (IsLeapYear(i)) {
        --days_difference;
      }
    }
  }
  // Count difference between 1 Jan and our date.
  for (int i = 0; i < month - 1; ++i) {
    days_difference += days_in_month[i];
    if (i == 1 && IsLeapYear(year)) {
      ++days_difference;
    }
  }
  days_difference += number - 1;
  if (days_difference < 0) {
    return (7 + (days_difference % 7)) % 7 + 1;
  } else {
    return (days_difference % 7) + 1;
  }
}
    
  

void ReadInput(int &number, int &month, int &year) {
  cout << "Enter the number of day in month:";
  cin >> number;
  cout << "Enter the number of month:";
  cin >> month;
  if (month < 1 || month > 12) {
    cout << "Wrong number of month" << endl;
  }
  cout << "Enter the number of year:";
  cin >> year;
  if (number < 1 || number > days_in_month[ month - 1]) {
    if (month == 2 && IsLeapYear(year))
      if (number == 29) {
 return;
      }
    cout << "Wrong number" << endl;
  }
}

void WriteOutput(const int number_of_day) {
  switch(number_of_day) {
    case 1: {
      cout << "It is Monday" << endl;
      break;
    }
    case 2: {
      cout << "It is Tuesday" << endl;
      break;
    }
    case 3: {
      cout << "It is Wednesday" << endl;
      break;
    }
    case 4: {
      cout << "It is Thursday" << endl;
      break;
    }
    case 5: {
      cout << "It is Friday" << endl;
      break;
    }
    case 6: {
      cout << "It is Saturday" << endl;
      break;
    }
    case 7: {
      cout << "It is Sunday" << endl;
      break;
    }
  }
}

int main() {
  int number, month, year, day;
  ReadInput(number, month, year);
  day = DefineWeekday(number, month, year);
  WriteOutput(day);
  return 0;
}

Подсветка синтаксиса в Blogspot.

Так как частенько здесь будет появляться код, то подсветка синтаксиса не помешает. Google предложил эту статью, но заработало не сразу. Адреса, которые там используются устарели и по ним уже нет ни скриптов, ни стилей.
Поэтому делаем так: в часть <head>...</head> пишем:

<script src='http://softwaremaniacs.org/media/soft/highlight/highlight.pack.js'/>
<script type='text/javascript'>
initHighlightingOnLoad();
</script>

А еще надо все содержимое подходящего стиля скопировать в html код блога. Стили лежат по адресу  http://softwaremaniacs.org/media/soft/highlight/styles/. Посмотреть примеры стилей можно по адресу http://softwaremaniacs.org/media/soft/highlight/test.html.
После этого код надо заключать в теги <pre><code>...</code></pre> и он будет подсвечен, как показано выше.

Об этом блоге и обо мне

Здравствуйте, меня зовут Василий, и я алк студент МФТИ. Обучаюсь по специализации системного программирования, пишу на c++, python, bash. Здесь буду публиковать код, который пишу. Использование его по любому назначению не запрещается, однако я никакой ответственности за последствия не несу. Может кому-нибудь будет полезно, да и мне самому на память останется.