Archive

Posts Tagged ‘C++’

Розв’язання задачі 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++.

Читати далі…

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

Переведення числового запису в його рядковий відповідник

У багатьох програмістів в житті наступає момент, коли виникає потреба в переведенні числа, наприклад прочитаного з бази даних, в рядок як воно читається. Зазвичай для формування фінансових документів. Таке завдання випало й мені. Результат програми виглядає так:
123.12 – сто двадцять три грн. 12 коп.
123832 – сто двадцять три тисячі вiсiмсот тридцять двi грн. 12 коп.
12394355.12 – дванадцять мiльйонiв триста дев’яносто чотири тисячі триста п’ятдесят п’ять грн. 12 коп.

Далі подаю код:
Читати далі…

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

Як розробити простий UDP сервер і клієнт із використанням WinSock.

Цей проект містить прості програми-приклади UDP сервера та клієнта. Якщо ви ніколи не писали програми, що використовують UDP, це прекрасний проект для початку. Сервер виконується на локальному комп’ютері та очікує датаграму із запитом поточного серверного часу з віддаленого комп’ютера. По отриманню такої датаграми сервер повертає свій поточний час клієнту, який відображає його.
Читати далі…

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