Witam ponownie po długiej hibernacji serii. Dopiero teraz udało mi się trafić odpowiedniego kandydata do niej. Już widząc tytuł Zadania domowe C++ – pomoże ktoś? byłem pełen nadziei.

Zadanie przedstawiało się następująco:

Zadanie 1:
Napisz program sprawdzający, czy wszystkie cyfry wczytanej liczby całkowitej dodatniej są jednocyfrowymi liczbami parzystymi. Program powinien wypisać słowo “TAK” lub “NIE”.

Zadanie 2:
Napisz program, który sprawdzi, czy podana liczba całkowita dodatnia jest liczbą palindromiczną (czytana od lewej do prawej i od prawej do lewej ma tę samą wartość).

Jak to bywa w tej serii, nie było ani krzty zainteresowania wykonaniem tych zadań przez autora wątku.

Palindrom metodą macierzową

Zadanie 1

Tutaj przyznam, że poszedłem ciutkę na łatwiznę. Wkleiłem do kodu wersję “single-header” CTRE Hany Dusíkovej i po prostu sprawdziłem czy liczba jest poprawna za pomocą wyrażenia regularnego:

int main()
{
    int val;
    if (std::cin >> val) {
        using namespace ctre::literals;
        std::stringstream conv;
        conv << val;
        std::string str = conv.str();
        if ("^[24680]+$"_ctre.match(str))
            std::cout << "TAK\n";
        else
            std::cout << "NIE\n";
    } else {
        std::cout << "NIE\n";
    }
}

Zadanie 2 – sprawdzenie czy liczba jest palindromem

Uznałem, że nie ma co się bawić w trywialne rozwiązania o złożoności liniowej, a do sprawy należy podejść kompleksowo. Dlatego też jako rozwiązanie obrałem metodę macierzową, którą na poczekaniu wymyśliłem.

Jak wiadomo, jedną z właściwości macierzy kwadratowych jest to, że jeśli dwa rzędy bądź dwie kolumny są identyczne to wyznacznik tej macierzy to zero. Wobec tego, jeśli zapiszemy np. kolejne znaki liczby (albo innego wyrazu) jako elementy pierwszego rzędu macierzy, a w ostatnim zrobimy to w odwrotnej kolejności, to jeśli dany wyraz jest palindromem mamy gwarantowany wyznacznik o wartości zero.

Jednak tutaj od razu napotykamy drobny problem: możemy mieć fałszywie pozytywne wyniki jeśli pozostałe elementy macierzy będą miały nieodpowiednie wartości (to było jednym z problemów mojego pierwszego rozwiązania, które miało niedokładność wyników w okolicach 0.8‰). Kilka testów empirycznych pozwoliło mi ustalić, że wypełnienie macierzy losowymi liczbami pierwszymi pozwala cieszyć się stuprocentową skutecznością w testowanym zakresie wyników (testowałem od 1 do 100 000 000). Jednocześnie moje rozwiązanie ma poważnie wyglądającą złożoność O(n² · n!).

Przykładowe macierze i ich wyniki dla 12345 i 12321:

% make && ./wb
    1     2     3     2     1
 9677  7907  9343  9803  7561
11411 10657  6607  9689 10457
 9277 11369  9907  7297  8681
    1     2     3     2     1
palindromic                                                 true
 
% make && ./wb
    1     2     3     4     5
 9677  7907  9343  9803  7561
11411 10657  6607  9689 10457
 9277 11369  9907  7297  8681
    5     4     3     2     1
palindromic                                                 false

Oraz kod:

#include <algorithm>
#include <iostream>
#include <sstream>
#include <iterator>
#include <vector>
 
int primes[] = {
6337,9067,6551,6323,8609,9677,7907,9343,9803,7561,11411,10657,6607,9689,10457,
9277,11369,9907,7297,8681,10477,8443,9973,10589,10957,7039,7307,9749,9349,6907,
10427,10709,11471,11087,8263,6151,6581,8009,10613,7589,9173,8647,8117,10781,
8093,7487,9227,11299,7901,9049,7393,6397,9421,7963,8171,6793,8929,9871,8011,
10091,8893,11159,8237,6857,10177,11399,8887,6599,8039,9319,8863,8963,10847,
6737,8123,9439,11383,11171,7759,9601,10753,9791,9661,10253,11503,10883,6997,
6521,8731,8761,9833,6977,8377,10247,6971,8527,7789,9161,10529,11621,8017,7127,
8719,10259,7549,8821,8699,11149,8167,8707,10141,11083,7187,9187,10729,7867,6317,
6679,6961,6991,9091,11527,9629,7207,9739,9157,7793,10007,9311,10711,8147,8161,
8623,8629,8369,7643,6871,7459,10267,6761,9433,10597,7829,7541,10459,7457,7699,
11467,7517,11329,6359,10631,8287,10301,7877,10099,6361,8521,7937,8663,9901,9109,
9403,8291,10343,8363,10453,6863,8353,7499,6733,7559,6389,6911,8389,6689,10303,
10739,10837,6967,8233,8111,9059,8599,10771,11497,8971,6829,9613,6673,7109,8447,
9203,10333,6473,6311,8501,6299,7069,8311,7639,7213,6959,8779,6637,8089,9199,
11273,9257,10111,7333,10987,6427,11251,7727,6709,7951,9631,10889,10313,6659,
10601,6247,8467,7417,11047,8677,11239,7321,9769,10973,11587,6691,6269,9413,
11003,7369,10501,6197,7577,9859,7433,8689,9397,11597,9001,10867,8839,11161,
10321,7591,8693,11549,10331,10133,7253,8293,11113,10103,11593,7219,7919,8209,
};
 
static_assert(std::size(primes) > 256);
 
template<typename T>
class simple_2d_matrix_view
{
    T* data_;
    size_t width_;
    size_t height_;
 
public:
 
    simple_2d_matrix_view(T* ptr, size_t h, size_t w):
        data_{ptr},
        width_{w},
        height_{h}
    {}
 
    size_t width() const { return width_; }
    size_t height() const { return height_; }
 
    T& operator()(size_t h, size_t w) {
        assert(w < width_);
        assert(h < height_);
        return data_[width_ * h + w];
    }
 
    T const& operator()(size_t h, size_t w) const {
        return const_cast<simple_2d_matrix_view&>(*this)(h, w);
    }
};
 
int sign(std::vector<int> const& vec)
{
    int cnt = 0;
    for(int i = 0; i < vec.size(); i++)
        for(int j = i + 1; j < vec.size(); j++)
            if (vec[i] > vec[j]) cnt++;
    return cnt % 2 == 0 ? 1 : -1;
}
 
long long matrix_det(simple_2d_matrix_view<int> v)
{
    assert(v.height() == v.width());
    long long det = 0;
 
    std::vector<int> indices(v.width());
    std::iota(indices.begin(), indices.end(), 0);
 
    do {
        long long val = 1;
        for(int x = 0; x < v.height(); x++) {
            int y = indices[x];
            val *= v(x, y);
        }
        det += val * sign(indices);
    } while(std::next_permutation(indices.begin(), indices.end()));
 
    return det;
}
 
bool is_palindromic(int val)
{
    std::stringstream conv;
    conv << val;
    std::string tested = conv.str();
    if (tested.size() == 1)
        return true;
    if (tested.size() == 2)
        return tested.front() == tested.back();
 
    std::vector<int> matrix(std::begin(primes), std::end(primes));
    matrix.resize(tested.size() * tested.size());
    simple_2d_matrix_view<int> v(matrix.data(), tested.size(), tested.size());
 
    for (int i = 0; i < tested.size(); i++)
        v(0, i) = tested[i] - '0';
    for (int i = 0; i < tested.size(); i++)
        v(tested.size() - 1, tested.size() - 1 - i) = tested[i] - '0';
 
    return matrix_det(v) == 0;
}
 
int main()
{
    int val;
    if (!(std::cin >> val))
        return 1;
 
    if (is_palindromic(val) == 0)
        std::cout << "TAK\n";
    else
        std::cout << "NIE\n";
}

#include <algorithm> #include <iostream> #include <sstream> #include <iterator> #include <vector> int primes[] = { 6337,9067,6551,6323,8609,9677,7907,9343,9803,7561,11411,10657,6607,9689,10457, 9277,11369,9907,7297,8681,10477,8443,9973,10589,10957,7039,7307,9749,9349,6907, 10427,10709,11471,11087,8263,6151,6581,8009,10613,7589,9173,8647,8117,10781, 8093,7487,9227,11299,7901,9049,7393,6397,9421,7963,8171,6793,8929,9871,8011, 10091,8893,11159,8237,6857,10177,11399,8887,6599,8039,9319,8863,8963,10847, 6737,8123,9439,11383,11171,7759,9601,10753,9791,9661,10253,11503,10883,6997, 6521,8731,8761,9833,6977,8377,10247,6971,8527,7789,9161,10529,11621,8017,7127, 8719,10259,7549,8821,8699,11149,8167,8707,10141,11083,7187,9187,10729,7867,6317, 6679,6961,6991,9091,11527,9629,7207,9739,9157,7793,10007,9311,10711,8147,8161, 8623,8629,8369,7643,6871,7459,10267,6761,9433,10597,7829,7541,10459,7457,7699, 11467,7517,11329,6359,10631,8287,10301,7877,10099,6361,8521,7937,8663,9901,9109, 9403,8291,10343,8363,10453,6863,8353,7499,6733,7559,6389,6911,8389,6689,10303, 10739,10837,6967,8233,8111,9059,8599,10771,11497,8971,6829,9613,6673,7109,8447, 9203,10333,6473,6311,8501,6299,7069,8311,7639,7213,6959,8779,6637,8089,9199, 11273,9257,10111,7333,10987,6427,11251,7727,6709,7951,9631,10889,10313,6659, 10601,6247,8467,7417,11047,8677,11239,7321,9769,10973,11587,6691,6269,9413, 11003,7369,10501,6197,7577,9859,7433,8689,9397,11597,9001,10867,8839,11161, 10321,7591,8693,11549,10331,10133,7253,8293,11113,10103,11593,7219,7919,8209, }; static_assert(std::size(primes) > 256); template<typename T> class simple_2d_matrix_view { T* data_; size_t width_; size_t height_; public: simple_2d_matrix_view(T* ptr, size_t h, size_t w): data_{ptr}, width_{w}, height_{h} {} size_t width() const { return width_; } size_t height() const { return height_; } T& operator()(size_t h, size_t w) { assert(w < width_); assert(h < height_); return data_[width_ * h + w]; } T const& operator()(size_t h, size_t w) const { return const_cast<simple_2d_matrix_view&>(*this)(h, w); } }; int sign(std::vector<int> const& vec) { int cnt = 0; for(int i = 0; i < vec.size(); i++) for(int j = i + 1; j < vec.size(); j++) if (vec[i] > vec[j]) cnt++; return cnt % 2 == 0 ? 1 : -1; } long long matrix_det(simple_2d_matrix_view<int> v) { assert(v.height() == v.width()); long long det = 0; std::vector<int> indices(v.width()); std::iota(indices.begin(), indices.end(), 0); do { long long val = 1; for(int x = 0; x < v.height(); x++) { int y = indices[x]; val *= v(x, y); } det += val * sign(indices); } while(std::next_permutation(indices.begin(), indices.end())); return det; } bool is_palindromic(int val) { std::stringstream conv; conv << val; std::string tested = conv.str(); if (tested.size() == 1) return true; if (tested.size() == 2) return tested.front() == tested.back(); std::vector<int> matrix(std::begin(primes), std::end(primes)); matrix.resize(tested.size() * tested.size()); simple_2d_matrix_view<int> v(matrix.data(), tested.size(), tested.size()); for (int i = 0; i < tested.size(); i++) v(0, i) = tested[i] - '0'; for (int i = 0; i < tested.size(); i++) v(tested.size() - 1, tested.size() - 1 - i) = tested[i] - '0'; return matrix_det(v) == 0; } int main() { int val; if (!(std::cin >> val)) return 1; if (is_palindromic(val) == 0) std::cout << "TAK\n"; else std::cout << "NIE\n"; }

Takiego rozwiązania nie powstydziłby się nawet najbardziej pilny student!

Lawful Evil #7 – palindromy metodą macierzową

Zadanie 1

Zadanie 2 – sprawdzenie czy liczba jest palindromem

One thought on “Lawful Evil #7 – palindromy metodą macierzową”

Leave a Reply Cancel reply