C++ snippets for Algorithms/C++ course

fib.cpp

// Числа Фибоначчи
#include <ctime>
#include <iostream>
#include <vector>

int fib(int n);
int fibM(int n);
int fibM(int n, std::vector<int>&);
int fibSM(int n);
int fibF(int n);

int main() {
  for (int i = 0; i <= 35; ++i) {
    auto start = clock();
    auto f = fibM(i);
    auto stop = clock();
    std::cout << i << "\t" << f 
      << "\t// " << (stop-start) // / 1e6 / CLOCKS_PER_SEC << " mks" 
      << std::endl;
  }
}

int fib(int n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

int fibM(int n) {
  std::vector<int> mem;
  return fibM(n, mem);
}

int fibM(int n, std::vector<int>& mem) {
  if (n <= 1) {
    return n;
  }
  if (mem.size() < n + 1) {
    mem.resize(n+1);
  }
  if (mem[n]) {
    return mem[n];
  }
  return mem[n] = fibM(n - 1, mem) + fibM(n - 2, mem);
}

static std::vector<int> memS;

int fibSM(int n) {
  if (n <= 1) {
    return n;
  }
  if (memS.size() < n + 1) {
    memS.resize(n+1);
  }
  if (memS[n]) {
    return memS[n];
  }
  return memS[n] = fibSM(n - 1) + fibSM(n - 2);
}

int fibF(int n) {
  int result = 0;
  int next = 1;
  for(int i = 0; i < n; ++i) {
    auto tmp = next;
    next += result;
    result = tmp;
  }
  return result;
}

paths.cpp

// Подсчёт количества путей из левого верхнего угла матрицы в правый нижний
#include <iostream>
#include <vector>

int paths(int n, int m);	  // time = O(m * n), mem = O(m * n)
int pathsHV(int n, int m);  // time = O(m * n), mem = O(m)
int pathsDiag(int n, int m) {
int pathsHVD(int n, int m);

void cumsum(std::vector<int>&);

int main() {
  for (int y = 1; y <= 7; ++y) {
    for (int x = 1; x <= 7; ++x) {
      if (1 != x) {
        std::cout << "\t";
      }
      std::cout << pathsHVD(y, x);
    }
    std::cout << std::endl;
  }
  return 0;
}

// Вправо и вниз
int paths(int n, int m) {
	matrix M(n);
	for (auto& it : M) {
		it.resize(m);
	}
	M[0][0] = 1;
	for (unsigned i = 0; i < M.size(); ++i) {
		for (unsigned j = 0; j < M[0].size(); ++j) {
			if (i > 0) {
				M[i][j] = M[i - 1][j];
			}
			if (j > 0) {
				M[i][j] += M[i][j - 1];
			}
		}
	}
	return M.back().back();
}

void cumsum(std::vector<int>& v) {
  int sum = 0;
  for (auto& it : v) {
    it = sum += it;
  }
}

// Вправо и вниз. Экономим память
int pathsHV(int n, int m) {
  std::vector<int> row(m);
  row.front() = 1;
  for (int i = 0; i < n; ++i) {
    cumsum(row);
  }
  return row.back();
}

// Вправо, вниз, по диагонали
int pathsDiag(int strok, int stolbcov) {
  stroka pred(stolbcov);
  stroka tek(stolbcov, 1);

  for (int i = 1; i < strok; ++i) {
    // pred = tek;
    pred.swap(tek);
    tek[0] = pred[0];
    for (int j = 1; j < tek.size(); ++j) {
      tek[j] = tek[j-1] + pred[j] + pred[j-1];
    }
  }
  return tek.back();
}

// Альтернативная реализация
int pathsHVD(int n, int m) {
  std::vector<int> row(m), prev(m);
  row.front() = 1;
  for (int i = 0; i < n; ++i) {
    if (i) {
      prev.swap(row);
      int j = 0;
      for (auto& it : row) {
        it = j ? prev[j - 1] + prev[j] : prev[j];
        j++;
      }
    }
    cumsum(row);
  }
  return row.back();
}

perm.cpp

#include <iostream>
#include <vector>

using Prm = std::vector<int>;

bool ok2add(const Prm&, int);
void try2add(Prm&, int size);
std::ostream& operator <<(std::ostream&, const Prm&);

int main() {
  int size;
  std::cin >> size;
  Prm pos;
  try2add(pos, size);
}

bool ok2add(const Prm& start, int item) {
  for (auto it : start)
    if (it == item)
      return false;
  return  true;
}

void try2add(Prm& start, int size) {
  if (start.size() >= size) {
    std::cout << start << std::endl;
    return;
  }
  for (int next = 0; next < size; ++next) {
    if (!ok2add(start, next)) 
      continue;
    start.push_back(next);
    try2add(start, size);
    start.pop_back();
  }
}

std::ostream& operator <<(std::ostream& os, const Prm& v) {
  auto first = true;
  for (auto& it : v) {
    if (!first) {
      os << " ";
    }
    first = false;
    os << it + 1;
  }
  return os;
}

vector.cpp

// Вспомогательные операции с векторами
#include <iostream>
#include <vector>

template <typename T>
std::istream& operator >>(std::istream& is, std::vector<T>& v);

template <typename T>
std::ostream& operator <<(std::ostream& os, const std::vector<T>& v);

template <typename T>
std::vector<T> operator +(const std::vector<T>&, const std::vector<T>&);

template <typename T>
std::vector<T> reverse(const std::vector<T>&);

int main() {
  std::vector<int> x;
  std::cin >> x;
  std::cout << reverse(x) + x << std::endl;
  return 0;
}

template <typename T>
std::istream& operator >>(std::istream& is, std::vector<T>& v) {
  unsigned len;
  is >> len;
  v.resize(len);
  for (auto& it : v) {
    is >> it;
  }
  return is;
}

template <typename T>
std::ostream& operator <<(std::ostream& os, const std::vector<T>& v) {
  auto first = true;
  for (auto& it : v) {
    if (!first) {
      os << " ";
    }
    first = false;
    os << it;
  }
  return os;
}

template <typename T>
std::vector<T> operator +(const std::vector<T>& a, const std::vector<T>& b) {
  auto result = a;
  result.reserve(a.size() + b.size());
  for (auto& it : b) {
    result.push_back(it);
  }
  return result;
}

template <typename T>
std::vector<T> reverse(const std::vector<T>& v) {
  std::vector<T> result(v.size());
  auto pos = v.size();
  for (auto& it : v) {
    result[--pos] = it;
  }
  return result;
}