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

Код на 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

Advertisements
Категорії:C++ Позначки:,
  1. Коментарів ще немає.
  1. No trackbacks yet.

Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: