Archive

Posts Tagged ‘C++’

Знаходження кількості простих циклів у неорієнтованому графі

Тут ми розглянемо як порахувати кількість простих циклів у неорієнтованому графі. Один зі способів виконання цієї задачі – це динамічне програмування з бітовими масками. Саме цей спосіб ми тут і розглянемо. Ми припускаємо, що ви вже знайомі із поняттям динамічного програмування.

Огляд ДП з бітовими масками

Якщо говорити про нашу задачу, то динамічне програмування з бітовими масками розглядає всі можливі підмножини вершин графа. Наприклад, якщо граф має три вершини пронумеровані від 1 до 3, то такими підножинами будуть {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}. Ці множини зручно представляти у вигляді бітових масок. Таких підмножин буде 2^n, що мовою С++ виглядає як 1 << n, де n – це кількість вершин у графі.

Читати далі…

Advertisements

Стара задача про шляпи

Група чаклунів зібралась на галявині, щоб вирішити питання, що накопичились у магічній країні. Магічна сила чаклунів залежить від їхньої шляпи. Щоб в палу суперечки не спалити один одного своїми закляттями вони вирішили залишити свої шляпи біля сусіднього з галявиною дуба-велетня. Поки вони обговорювали свої питання, впала ніч, тому коли розходились кожен з них взяв першу ліпшу шляпу. Нас цікавить, скільки ж чаклунів повернулись до своїх веж із своїми власними шляпами.

Читати далі…

Розв’язання задачі MappingABC з TopCoder

Тут я розгляну розв’язок задачі MappingABC з TopCoder. Це задача з першого дивізіону другого рівня складності, тому вона вимагає певний рівень учасника для розв’язання.

Основне спостереження, яке допомагає в розв’язанні – це те, що для того, щоб порахувати всі прийнятні рядки ми можемо розбити рядок на три підрядки: до першого A – [0, FA], між першим A і останнім C – [FA, LC] і після останнього C – [LC,t.size()-1]. Ми рахуємо лише ті рядки в яких у [FA, LC] трапляється B.

Введемо дві множини для позначення символів які трапляються лише зовні [FA, LC] і інші, відповідно \mathcal O і \mathcal I. Тоді кількість прийнятних рядків така:
\prod_{s\in \mathcal O}\mbox{bitcount}(s) + \Big( \prod_{s\in \mathcal I}\mbox{bitcount}(s) - \prod_{s\in \mathcal I}\mbox{bitcount}(s \& 5) \Big).

Дивись коментарі в сирцевому коді для подальших роз’яснень.
Читати далі…

Категорії:C++, Комбінаторика Позначки:, ,

Навіщо потрібен make_unique

make_unique завжди варто і завжди правильно використовувати у коді тим більше, що він не має ніякого негативного впливу на швидкодію.
Читати далі…

Категорії:C++ Позначки:,

Виняткові ситуації в конструкторах і деструкторах

У програмістів на C++ часто виникають запитання про те, чи можна кидати винятки у конструкторах і деструкторах. У цій статті ми розглянемо обидва питання.
Читати далі…

Категорії:C++ Позначки:

Код на c++11 для китайської теореми про залишки

Припускають, що назва “китайська теорема про залишки” з’явилась від такого запитання: Як багато солдатів в армії Хан Сінга, якщо вишикувати їх у три шереги, то два солдати залишаться зайвими, якщо вишикувати у п’ять шерег, то три солдати не в шерегах і якщо вишикувати у сім шерег, то два солдати зайві.

Наводжу код на с++11 для розв’язання задач за китайською теоремою про залишки:

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

using namespace std;

template<class T> void ex_al_eu_in(const T &r1, const T &r2, const T &x1, const T &x2, const T &y1, const T &y2, T &gcd, T &a, T &b) {
    T r3 = r1 - r2 * (r1 / r2);
    T x3 = x1 - x2 * (r1 / r2);
    T y3 = y1 - y2 * (r1 / r2);
    if (0 != r3)
        ex_al_eu_in(r2, r3, x2, x3, y2, y3, gcd, a, b);
    else {
        gcd = r2;
        a = x2;
        b = y2;
    }
}

template<class T> void ex_al_eu(const T &r1, const T &r2, T &gcd, T &a, T &b) {
    if (0 == r1 || 0 == r2)
        gcd = a = b = 0;
    else
        ex_al_eu_in(r1 > r2 ? r1 : r2, r1 < r2 ? r1 : r2, T(1), T(0), T(0), T(1), gcd, r1 > r2 ? a : b, r1 < r2 ? a : b);
}

vector<int> modules = {3,5,7};
vector<int> remainders = {2,3,2};
vector<int> ys(remainders.size());

int main() {
    int m_big = 1;
    for(int r : modules) { m_big *= r; };
    int answer = 0;
    transform(modules.begin(), modules.end(), modules.begin(), ys.begin(), [m_big](int mod, int y){ 
            int gcd, f;
            int m = m_big / mod;
            ex_al_eu(mod, m, gcd, f, y);
            return y*m; 
        });
    cout << inner_product(remainders.begin(), remainders.end(), ys.begin(), 0) << endl;
    return 0;
}

Компілюємо так:
g++ ім’я.cpp -std=c++0x

Категорії:C++ Позначки:,

Прагнеш швидкості? Передавай за значенням.

Тільки чесно: які почуття викликає в вас наступний код?

std::vector<std::string> get_names();
...
std::vector<std::string> const names = get_names();

Відверто, я б занервував. В принципі, по завершені get_names() ми маємо копіювати вектор рядків. Потім ми маємо копіювати його знов, коли ініціалізуємо names, і маємо знищити першу копію. Якщо в векторі N рядків, кожне копіювання може вимагати аж по N+1 виділень пам’яті і безліч недружнього щодо кешу доступу до даних, коли вміст рядка копіюється.

Радше ніж відчувати цю тривогу, я часто повертався до використання передачі за посиланням, щоб уникнути непотрібних копій:

get_names(std::vector<std::string>& out_param );
...
std::vector<std::string> names;
get_names( names );

На жаль, цей підхід далекий від досконалості.

  • Об’єм коду виріс на 150%
  • Нам довелось поступитись сталістю, бо ми змінюємо names.
  • Як функційні програмісти захочуть нам нагадати, зміна параметра ускладнює розуміння через підривання прозорості посилань і міркувань щодо рівнянь (equational reasoning.).
  • Ми більше не дотримуємось суворої семантики передачі за значенням для names.

Але, чи дійсно конче необхідно так плутати наш код для досягнення дієвості? На щастя, виявляється, що відповідь ні (особливо, якщо ви використовуєте C++0x). Ця стаття перша в серії, що досліджує п-значення (rvalues) та їх вплив на дієвість семантики значень (value semantics) в C++.

Читати далі…

Категорії:Перекладені Позначки:,