13. MEŠALICA - rešenje

Ovaj zadatak zahteva simulaciju mešanja niza više puta. Na ulazu se daje permutacija niza 0, 1, 2, ..., n-1 nakon jednog mešanja i broj m koliko puta treba izvršiti mešanje. Cilj je da se odredi krajnji niz posle m mešanja. Prvi prikaz rešenja koristi algoritam grube sile, gde se mešanje ponavlja m puta.


#include <iostream>
#include <vector>
#include <fstream> // dodatak za čitanje iz datoteke, opciono

#define DATOTEKA "01.in" // opciono za testiranje sa fajlom

using namespace std;

// Funkcija za ispis elemenata vektora
void ispisi(vector<int>& v)
{
    for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    {
        cout << (*it) << " ";
    }
    // cout << endl; // po potrebi novi red na kraju ispisa
}

int main()
{
    // Opciono za čitanje iz datoteke
    /*
    fstream dataFile;
    dataFile.open(DATOTEKA);
    if (dataFile.fail())
    {
        cerr << "Error reading data!" << endl;
        system("PAUSE");
        return 1;
    }
    */

    int n;            // veličina niza
    long long m;      // broj ponavljanja mešanja
    cin >> n >> m;  // za standardni ulaz
    // dataFile >> n >> m; // za čitanje iz datoteke

    vector<int> niz;      // originalni niz
    vector<int> niz2(n);  // privremeni niz za skladištenje novog rasporeda
    vector<int> shema(n); // šema mešanja: pozicija gde ide svaki element

    // Učitavanje permutacije i formiranje šeme
    for(int i = 0; i < n; i++)
    {
        int a;
        cin >> a; // za standardni ulaz
        // dataFile >> a; // za čitanje iz datoteke

        niz.push_back(a);   // dodajemo element u originalni niz
        shema[a] = i;       // beležimo gde element 'a' ide nakon mešanja
    }
    // dataFile.close(); // zatvaranje datoteke ako je korišćena

    // Grubo ponavljanje mešanja m puta
    for(int i = 1; i < m; i++)
    {
        vector<int> niz2(n); // inicijalizacija privremenog niza
        for(int j = 0; j < n; j++)
        {
            int pozN = shema[j]; // nova pozicija elementa j prema šemi
            int s = niz[j];      // element koji treba premeštati

            niz2[pozN] = s;      // stavljamo element na novu poziciju
        }
        niz = niz2; // ažuriramo originalni niz posle jednog mešanja
    }

    // Ispis konačnog niza
    ispisi(niz);

    return 0;
}

Komentar: Ovo rešenje radi tačno, ali je efikasno samo za male vrednosti m, jer u svakoj iteraciji ponavlja mešanje celog niza. Za velike m (npr. 10¹⁸) potrebno je primeniti optimizovani pristup koristeći algoritam brzog stepenovanja permutacije.

13. MEŠALICA - rešenje pomoću algoritma brzog stepenovanja

Za velike vrednosti m (npr. 10¹⁸) grubo ponavljanje nije praktično. Optimizovano rešenje koristi algoritam brzog stepenovanja primenjen na permutacije. Ideja je da transformaciju niza "stepenujemo" koristeći binarni pristup, slično kao kod Xⁿ u matematici.


#include <iostream>
#include <vector>
#include <fstream> // opciono za čitanje iz fajla

#define DATOTEKA "01.in"
using namespace std;

// Funkcija za ispis elemenata vektora
void ispisi(vector<int>& v)
{
    for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    {
        cout << (*it) << " ";
    }
    // cout << endl; // po potrebi novi red
}

int main()
{
    int n;            // veličina niza
    long long m;      // broj ponavljanja mešanja
    cin >> n >> m;

    vector<int> niz;      // originalni niz
    vector<int> shema(n); // šema mešanja

    // Učitavanje permutacije i formiranje šeme
    for(int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        niz.push_back(a);
        shema[a] = i; // pozicija elementa a posle jednog mešanja
    }

    // Ako je m = 1, dovoljno je ispisati originalni niz
    if(m == 1)
    {
        ispisi(niz);
        return 0;
    }

    m = m - 1; // smanjenje jer smo već učitali prvo mešanje

    while(m >= 1)
    {
        vector<int> niz2(n); // privremeni niz
        for(int j = 0; j < n; j++)
        {
            int pozN;
            if(m % 2 == 1) // ako je trenutni eksponent neparan
            {
                pozN = shema[j];   // nova pozicija elementa
                int s = niz[j];     // element koji se premesta
                niz2[pozN] = s;
            }
            else // ako je trenutni eksponent paran
            {
                pozN = shema[j];
                int s = shema[pozN]; // "stepenovanje" šeme
                niz2[j] = s;
            }
        }

        if(m == 1) // ako smo došli do poslednjeg koraka
        {
            ispisi(niz2);
            return 0;
        }
        else if(m % 2 == 1) // neparan eksponent
        {
            niz = niz2; // ažuriramo niz
            m--;        // smanjujemo eksponent
        }
        else // paran eksponent
        {
            shema = niz2; // ažuriramo šemu
            m /= 2;       // delimo eksponent na pola
        }
    }

    ispisi(niz2); // konačan ispis
    return 0;
}

Komentar i analiza:

Ovaj pristup koristi logiku brzog stepenovanja: eksponent se deli binarno, što omogućava efikasno računanje niza posle m mešanja.
Operacije se sprovode ili na samom nizu (ako je eksponent neparan) ili na šemi (ako je paran), čime se izbegava direktno ponavljanje m puta.
Kompleksnost je O(n log m), što je dramatično brže od grube sile za velike m.
Kod je modularan i lako ga je proširiti za različite permutacije ili dodatne operacije nad nizom.

Moguća poboljšanja:

Bolje imenovanje promenljivih radi čitljivosti (npr. privremeniNiz, novaPozicija).
Dodavanje funkcije za brzo stepenovanje permutacije radi modularnosti i ponovne upotrebe.
Uklanjanje opcionalnog čitanja iz fajla ako se ne koristi.
Dodavanje komentara koji objašnjavaju binarni pristup i manipulaciju šemom za početnike.

Povratak
|< Kvalifikacije za okružna takmičenja