Mercurial > lbo > hg > ccplay
view recursion.cc @ 24:b89680a8af68 default tip
graph: detect negative cycles
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 09 Apr 2023 17:27:20 +0200 |
parents | 85a51415f042 |
children |
line wrap: on
line source
#include <algorithm> #include <chrono> #include <cmath> #include <iostream> #include <set> #include <string> #include <string_view> #include <random> #include <ranges> #include <string_view> #include <vector> int childsteps(int n) { if (n == 1) { return 1; } else if (n < 1) { return 0; } else { int whole = n <= 3 ? 1 : 0; return whole + childsteps(n-1) + childsteps(n-2) + childsteps(n-3); } } int robot(int x0, int y0, int x, int y) { // Go from 0,0 (upper left) to x,y. How many ways are there? if (std::abs(x0-x) + std::abs(y0-y) == 1) { return 1; } else if (x0 == x && y0 == y) { return 0; } else { int down = y0 < y ? robot(x0, y0+1, x, y) : 0; int right = x0 < x ? robot(x0+1, y0, x, y) : 0; return down+right; } } int magicindex(const std::vector<int>& v, int from=0, int to=-1) { if (to < 0) { to = v.size()-1; } std::cout << from << " " << v[from] << " " << to << " " << v[to] << "\n"; // Termination conditions if (from == to) { if (v[from] == from) { return from; } else { return -1; } } else if (v[from] < from && v[to] < to) { // No crossing. return -1; } else if (v[from] > from && v[to] > to) { return -1; } else if ((v[from] <= from && v[to] >= to) || (v[from] >= from && v[to] <= to)) { // Magic element between from/to. int mid = (from+to)/2; int left_candidate = magicindex(v, from, mid); int right_candidate = magicindex(v, mid+1, to); if (left_candidate + right_candidate < 0) return -1; return std::max(left_candidate, right_candidate); } else { return -1; } } template<typename T> std::set<std::set<T>> subsets(std::set<T> set) { if (set.size() == 1) { return std::set<std::set<T>>{set, std::set<T>{}}; } else { std::set<std::set<T>> newset{set}; for (const T& e : set) { std::set<T> subset = set; subset.erase(e); newset.merge(subsets(subset)); } return newset; } } std::vector<std::string> permutations(const std::string& str) { std::vector<std::string> perms{}; if (str.size() == 1) { perms.push_back(str); } for (int i = 0; i < str.size(); i++) { std::string substr = str.substr(0, i) + str.substr(i+1, str.size()-i-1); std::vector<std::string> inner_perms = permutations(substr); for (const std::string& s : inner_perms) { perms.push_back(str.substr(i, 1) + s); } } return perms; } int main(void) { auto before = std::chrono::steady_clock::now(); for (const std::string& s : permutations("abcdefg")) { std::cout << s << "\n"; } auto after = std::chrono::steady_clock::now(); std::cout << "Took: " << std::chrono::duration_cast<std::chrono::microseconds>( after-before ).count() << "µs\n"; }