Короткие примеры C++ кода-1 Кувшинов Д

for (unsigned i = 0; i < sizeof(fs) / sizeof(double); ++i)

if (fact(ns[i]) != fs[i])

return i + 1;

return 0;

}

///////////////////////////////////////////////////////////////////////////////

// lsr == "linear search right"
const int* rec_lsr(const int *begin, const int *end, int x)

{

if (begin == end)

return end;

return *begin == x ? begin : rec_lsr(begin + 1, end, x);

}
const int* itr_lsr(const int *begin, const int *end, int x)

{

for (; begin != end; ++begin)

if (*begin == x)

break;
return begin;

}

///////////////////////////////////////////////////////////////////////////////

// bsl == "binary search left"
const int* rec_bsl(const int *begin, const int *end, int x)

{

const auto mid = begin + (end - begin) / 2;

if (mid == begin)

return begin == end || *begin < x ? end : begin;
return *mid < x ?

rec_bsl(mid + 1, end, x)

: rec_bsl(begin, mid, x);

}

const int* itr_bsl(const int *begin, const int *end, int x)

{

while (true)

{

const auto mid = begin + (end - begin) / 2;

if (mid == begin)

return begin == end || *begin < x ? end : begin;
if (*mid < x)

begin = mid + 1;

else

end = mid;

}

}

typedef const int* (*bsl_variant)(const int*, const int*, int);

int test_bsl(bsl_variant bsl)

{

const int data[] = { 0, 0, 0, 1, 1, 1, 1, 2, 3, 5, 10, 11, 11, 11, 20 };

const struct {

int b, e, x, r;

} ts[] =

{

{ 0, 15, 0, 0 }, //1

{ 0, 15, 1, 3 }, //2

{ 0, 15, 2, 7 }, //3

{ 0, 15, 3, 8 }, //4

{ 0, 15, 5, 9 }, //5

{ 0, 15, 4, 9 }, //6

{ 0, 15, 7, 10 }, //7

{ 0, 15, 10, 10 }, //8

{ 0, 15, 11, 11 }, //9

{ 0, 15, 20, 14 }, //10

{ 0, 15, 25, 15 }, //11

{ 0, 0, 10, 0 }, //12

{ 0, 1, 0, 0 }, //13

{ 0, 1, 10, 1 }, //14

{ 0, 2, 2, 2 }, //15

{ 0, 2, 0, 0 }, //16

{ 0, 3, 2, 3 }, //17

{ 0, 3, 0, 0 }, //18

{ 0, 4, 2, 4 }, //19

{ 0, 4, 1, 3 }, //20

{ 0, 4, 0, 0 }, //21

{ 1, 5, 2, 5 }, //22

{ 1, 5, 1, 3 }, //23

{ 1, 5, 0, 1 }, //24

{ 2, 6, 2, 6 }, //25

{ 2, 6, 1, 3 }, //26

{ 2, 6, 0, 2 }, //27

{ 13, 15, 15, 14 } //28

};

int test = 0;

for (auto &t : ts)

{

++test;

if (bsl(data + t.b, data + t.e, t.x) - data != t.r)

return test;

}
return 0;

}

///////////////////////////////////////////////////////////////////////////////

#include

#include
void report(int test_result, const char* msg)

{

if (test_result)

std::cout << msg << ": " << test_result << std::endl;

}
int main()

{

using namespace std;
cout << "Testing factorial variants:\n";

{

const struct {

fact_variant fact;

const char *name;

} vs[] =

{

{ rec_fact, "rec" },

{ tcr_fact_caller, "tcr" },

{ itr_fact_0, "itr0" },

{ itr_fact, "itr" }

};

for (auto &v : vs)

report(test_fact(v.fact), v.name);

}



cout << "done.\nTesting fib variants:\n";

{

const struct {

fib_variant fib;

const char *name;

} vs[] =

{

{ rec_fib, "rec" },

{ tcr_fib_caller, "tcr" },

{ itr_fib_0, "itr0" },

{ itr_fib, "itr" }

};

for (auto &v : vs)

report(test_fib(v.fib), v.name);

}
cout << "done.\nTesting binary search variants:\n";

{

const struct {

bsl_variant bsl;

const char *name;

} vs[] =

{

{ rec_bsl, "rec" },

{ itr_bsl, "itr" }

};

for (auto &v : vs)

report(test_bsl(v.bsl), v.name);

}
cout << "done." << endl;

return EXIT_SUCCESS;

}

0755-memoized_fib.cpp

// memoized_fib.cpp

// Результат применения техники мемоизации к рекурсивной функции,

// вычисляющей числа Фибоначчи "по определению".

// Мемоизация заключается в запоминании вычисленных значений функции

// и извлечении их при повторном вызове функции с теми же параметрами.

// В данном случае мемоизация позволяет "линеаризовать" вычисление --

// вместо экспоненциального по номеру числа времени требуется линейное

// (или постоянное при повторных вызовах).

#include // HUGE_VAL
double fib(unsigned n)

{

// Хранилище вычисленных значений -- достаточно 1500 элементов,

// так как в диапазон IEEE-754 double precision не вписываются числа Фибоначчи за номером 1500 и более.

// В общем случае мемоизации могут понадобиться сложные структуры данных,

// оперирующие динамической памятью.

static const unsigned N = 1500;

static double value[N] = { 0., 1. };

// Признак того, что значение уже вычисленно и надо извлечь его из таблицы value.

static bool stored[N] = { true, true };
if (N <= n)

return HUGE_VAL;



if (stored[n]) // уже посчитано?

return value[n]; // да -- вернуть сохранённое

// ещё не посчитано -- посчитать по определению, сохранить и вернуть:

stored[n] = true;

return value[n] = fib(n - 1) + fib(n - 2);

}

#include

int main()

{

for (unsigned n; std::cin >> n;)

std::cout << fib(n) << std::endl;

return EXIT_SUCCESS;

}

0756-memoized_fib_thread_local.cpp

// memoized_fib_thread_local.cpp

// Пример использования хранилища потока (ключевого слова thread_local) для

// реализации потокобезопасной (thread-safe) версии memoized_fib.

// Т.е. fib из этого примера можно без проблем выполнять одновременно из разных нитей (threads) исполнения.

#include // HUGE_VAL
double fib(unsigned n)

{

static const unsigned N = 1500;

thread_local static double value[N] = { 0., 1. };

thread_local static bool stored[N] = { true, true };
if (N <= n)

return HUGE_VAL;



if (stored[n])

return value[n];
stored[n] = true;

return value[n] = fib(n - 1) + fib(n - 2);

}

///////////////////////////////////////////////////////////////////////////////

// Проверочный код.
// Вариант fib, не использующий глобальную память.

// Используется для тестирования варианта fib, приведённого выше.

double reference_fib(unsigned n)

{

double a = 0., b = 1.;

while (n--)

{

const auto sum = a + b;

a = b;

b = sum;

}

return a;

}
#include

#include

#include

using namespace std;
int main()

{

void thread_body(unsigned);

// Создать три нити исполнения, которые будут вычислять разные значения fib

// и сравнивать с результатом reference_fib.

thread a(thread_body, 1), b(thread_body, 2), c(thread_body, 3);

// Дождаться завершения вычислений.

a.join();

b.join();

c.join();

// Задержка экрана.

cin.ignore();

return EXIT_SUCCESS;

}
// Код, выполняемый параллельно.

void thread_body(unsigned tid)

{

random_device seed_gen; // генератор случайного зерна

mt19937_64 rng(seed_gen() + tid); // генератор псевдослучайных целых чисел

uniform_int_distribution<> ud(0, 1501); // генератор равномерно распределённых в [0, 1501] целых чисел

for (int rounds = 1000; rounds--;)

{

const auto n = ud(rng); // следующий псевдослучайный аргумент fib

if (fib(n) != reference_fib(n)) // проверить корректность вычисления

return (void)cout.put('0'); // ошибка

}
cout.put('1'); // все раунды успешны

}

0760-prefix_calc.cpp

// prefix_calc.cpp

// Рекурсивная реализация калькулятора с поддержкой четырёх арифметических действий,

// принимающего выражения в префиксной записи (она же "польская нотация").

// Грамматика выражения: операция операнд операнд, где операнд может быть числом или опять выражением

// Например, + * 2 3 4 ==> (2 * 3) + 4 == 10

#include

#include // strchr

using namespace std;
// Читает выражение с cin, возвращает вычисленное значение выражения.

double prefix()

{

// Выражение?

char op;