Mistrz matematyki - klasa 4 szkoła podstawowa

Question

Hej,

mam zadanie jak w temacie, poniżej treść:

"Liczba jest podzielna przez 11. Wtedy, gdy sumując co drugą cyfrę, otrzymujemy w obydwu przypadkach to samo. Np., dla liczby 5841 mamy 5+4=8+1.
Rozmieść podane niżej cyfry w kwadracie (kwadrat 4x4) w taki sposób, żeby powstałe liczby czterocyfrowe, czytane poziomo i pionowo, w przód i wspak, były podzielne przez 11.
0,1,1,2,2,3,3,4,5,6,7,8,8,8,9,9.".

Chciałbym to rozwiązać za pomocą c++,c#, pl/sql(może by było prościej?) - nieważne. Generalnie, pytanie brzmi: jak napisać algorytm?

Początkowo próbowałem za pomocą tablicy dwuwymiarowej [4,4].
Później pomyślałem, że zrobię to za pomocą tablicy jednowymiarowej i odpowiednio posortuję ciąg podanych cyfr (kolejna cyfra-> kolejny pole w kwadracie).
Jeżeli poniższy warunek będzie spełniony, wówczas mamy posortowany ciąg cyfr(zadanie rozwiązane): podane poniżej liczby to indeksy tablicy jednowymiarowej:
0+2=1+3 & 4+6=5+7 & 8+10=9+11 & 12+14=13+15 & 0+8=4+12 & 1+9=5+13 & 2+10=6+14 & 3+11=7+15

wg mnie jest to wyzwanie. Może ktoś coś podpowie bądź znajdzie rozwiązanie?

Answer 1

Jeśli chcesz wygenerować wszystkie możliwe rozwiązania to w metodzie brutalnej będzie to generowanie permutacji i sprawdzenie warunku. Jeśli jednak chcesz rozwiązać to z mniejszą złożonością obliczeniową, to zastosuj jakikolwiek solver.

Tu masz przykład metody brutalnej. Daje do myślenia szybkość poszukiwania. Nie optymalizowałem programu bo to nie ma sensu dla tego algorytmu. Zerkniesz do kodu jak będziesz chciał. Nie będę psuł zabawy :-) :

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>

inline void showSolution(const std::vector<int>& values) {
    std::cout << "+-+-+-+-+";

    for(size_t i = 0; i < values.size(); ++i) {
        bool newRow = !(i % 4);
        std::cout << (newRow ? "\n|" : "") << values[i] << '|';
    }

    std::cout << "\n+-+-+-+-+\n";
}

inline bool checkRows(const std::vector<int>& v) {
    bool answer = true;

    for(size_t i = 0; i < 16; i += 4) {
        if((v[i] + v[i + 2]) != (v[i + 1] + v[i + 3])) {
            answer = false;
            break;
        }
    }

    return answer;
}

inline bool checkColumns(const std::vector<int>& v) {
    bool answer = true;

    for(size_t i = 0; i < 4; ++i) {
        if((v[i] + v[i + 8]) != (v[i + 4] + v[i + 12])) {
            answer = false;
            break;
        }
    }

    return answer;
}

inline bool checkCondition(const std::vector<int>& values) {
    return checkRows(values) && checkColumns(values);
}

inline void showProgress(unsigned long long solutionCounter) {
    std::cout << std::string(40, '=') << "\nSolution: "
        << solutionCounter << '\n' << std::string(40, '=') << '\n';
}

int main() {
    std::vector<int> values = {0, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 8, 8, 9, 9};
    unsigned long long solutionCounter = 0;

    do {
        if(checkCondition(values)) {
            ++solutionCounter;
            showProgress(solutionCounter);
            showSolution(values);
        }
    } while(std::next_permutation(values.begin(), values.end()));
}

 

Comments

Dziękuje :) good job