RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/de/dd9/catalan__numbers_8cpp_source.html below:

TheAlgorithms/C++: dynamic_programming/catalan_numbers.cpp Source File

Go to the documentation of this file. 23 using

value_type = std::uint64_t;

24

std::vector<value_type> known{1, 1};

26

value_type compute_next() {

27 return

std::transform_reduce(known.begin(), known.end(), known.rbegin(),

28 static_cast<

value_type

>

(0), std::plus<>(),

32 void

add() { known.push_back(this->compute_next()); }

39

value_type

get

(std::size_t n) {

40 while

(known.size() <= n) {

47void

test_catalan_numbers_up_to_20() {

50

assert(cn.

get

(0) == 1ULL);

51

assert(cn.

get

(1) == 1ULL);

52

assert(cn.

get

(2) == 2ULL);

53

assert(cn.

get

(3) == 5ULL);

54

assert(cn.

get

(4) == 14ULL);

55

assert(cn.

get

(5) == 42ULL);

56

assert(cn.

get

(6) == 132ULL);

57

assert(cn.

get

(7) == 429ULL);

58

assert(cn.

get

(8) == 1430ULL);

59

assert(cn.

get

(9) == 4862ULL);

60

assert(cn.

get

(10) == 16796ULL);

61

assert(cn.

get

(11) == 58786ULL);

62

assert(cn.

get

(12) == 208012ULL);

63

assert(cn.

get

(13) == 742900ULL);

64

assert(cn.

get

(14) == 2674440ULL);

65

assert(cn.

get

(15) == 9694845ULL);

66

assert(cn.

get

(16) == 35357670ULL);

67

assert(cn.

get

(17) == 129644790ULL);

68

assert(cn.

get

(18) == 477638700ULL);

69

assert(cn.

get

(19) == 1767263190ULL);

70

assert(cn.

get

(20) == 6564120420ULL);

73void

test_catalan_numbers_25() {

76

assert(cn.

get

(25) == 4861946401452ULL);

80

test_catalan_numbers_up_to_20();

81

test_catalan_numbers_25();

computes and caches Catalan numbers

value_type get(std::size_t n)

computes the n-th Catalan number and updates the cache.

int main()

Main function.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4