Semplice algoritmo

di il
15 risposte

Semplice algoritmo

Salve a tutti, come da titolo devo scrivere un algoritmo per risolvere un semplice problema.
In pratica ho un vector di interi (ordinato e senza duplicati) contenente almeno due numeri compresi nell'intervallo [0;8], quello che devo fare è riempire un vector di vector con le sottosequenze (di almeno due elementi) tratte dal precedente vector e comprese in uno dei seguenti intervalli: [0;2], [3;5], [6;8].

I ho scritto il seguente codice:
#include <iostream>
#include <vector>

using namespace std;

void stampa_vector(const vector<unsigned int> &v)
{
    for(unsigned int i = 0; i < v.size(); ++i)
    {
        cout << v[i] << " ";
    }
    cout << endl;
}

int main()
{
    vector<unsigned int> v = {1, 3, 5, 6, 7, 8};
    vector<vector<unsigned int>> w;
    //-----------------------------------------------------------
    for(unsigned int i = 0; i < v.size() - 1; ++i)
    {
        if(v[i] / 3 == v[i + 1] / 3)
        {
            vector<unsigned int> u = {v[i], v[++i]};
            if(i < v.size() - 1 && v[i] / 3 == v[i + 1] / 3)
            {
                u.push_back(v[++i]);
            }
            w.push_back(u);
        }
    }
    //-----------------------------------------------------------
    for(unsigned int i = 0; i < w.size(); stampa_vector(w[i++]));
 }
effettivamente sembra funzionare, ma visto che non mi soddisfa appieno (in quanto un po' ridondante), mi chiedevo se qualcuno avesse qualche idea al riguardo, magari anche con un approccio completamente diverso.

15 Risposte

  • Re: Semplice algoritmo

    Io farei qualcosa di simile: [CODE] class Predicate { public: Predicate(uint32_t min, uint32_t max, vector<uint32_t>& mat) : p_min(min),p_max(max), p_mat(mat) {} void operator()(uint32_t val) { if (val >= p_min && val <= p_max) p_mat.emplace_back(val); } private: int32_t p_min; int32_t p_max; std::vector<uint32_t>& p_mat; }; int main() { vector<uint32_t> v = { 1, 3, 5, 6, 7, 8 }; vector<vector<uint32_t>> w; w.resize(3); std::for_each(v.cbegin(), v.cend(), Predicate{ 0,2,w[0] }); std::for_each(v.cbegin(), v.cend(), Predicate{ 3,5,w[1] }); std::for_each(v.cbegin(), v.cend(), Predicate{ 6,8,w[2] }); // una delle possibili versioni della routine di stampa std::for_each(w.cbegin(), w.cend(), [](auto& v) { std::for_each(v.cbegin(), v.cend(), [](auto val) { std::cout << val << " "; }); std::cout << "\n"; }); }
  • Re: Semplice algoritmo

    Da un primo sguardo al codice il funzionamento più o meno l'avevo intuito, ma mi hai costretto a "studiare" alcune funzionalità del linguaggio che non conoscevo per poterlo apprezzare fino in fondo!

    Lo so che il tuo era solo uno spunto, ma ai fini di quello che devo fare è importante che il vector di vector abbia un valore di size coerente col numero di sottosequenze valide trovate, che, come detto nel post iniziale, devono essere costituite da almeno due elementi. In ogni caso, prendendo spunto dall'idea di base, avrei pensato a qualcosa del genere:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    void stampa_vector(const vector<unsigned int> &v)
    {
        for(unsigned int i = 0; i < v.size(); ++i)
        {
            cout << v[i] << " ";
        }
        cout << endl;
    }
    
    int main()
    {
        vector<unsigned int> v = {1, 3, 5, 6, 7, 8};
        vector<vector<unsigned int>> w;
        //-----------------------------------------------------------
        vector<unsigned int> u;
        for(unsigned int sup, i = 0, flag = true; flag; u.resize(0))
        {
            for(sup = (v[i] / 3 + 1) * 3, u.push_back(v[i++]); (flag = i < v.size()) && v[i] < sup; u.push_back(v[i++]));
            if(u.size() > 1)
            {
                w.push_back(u);
            }
        }
        //-----------------------------------------------------------
        for(unsigned int i = 0; i < w.size(); stampa_vector(w[i++]));
     }
    Questo già mi convince di più rispetto al primo codice che ho postato, ma se secondo voi ci sono margini di miglioramento fatemi sapere.


    P.S.
    @shodan, ma il cambio di avatar è dovuto ai recenti avvenimenti?!
  • Re: Semplice algoritmo

    Quindi nel tuo esempio il numero 1 di v viene escluso: corretto?

    p.s.
    Si
  • Re: Semplice algoritmo

    shodan ha scritto:


    Quindi nel tuo esempio il numero 1 di v viene escluso: corretto?
    Sì, valgono solo le sottosequenze di almeno due elementi.
  • Re: Semplice algoritmo

    Con un paio di aggiunte il codice diventa:
    (Ho cambiato da Predicate a Filter perché i predicati per convenzione restituiscono un boolean)
    
    class Filter {
        public:
            Filter(uint32_t min, uint32_t max, std::vector<std::vector<uint32_t>>& mat) noexcept
                : p_min(min), p_max(max), p_mat(mat)  {}
    
           // sposta i dati necessari
            Filter(Filter&& p) noexcept : p_mat(p.p_mat) , temp(std::move(p.temp)) {  }
    
           // finalizza l'inserimento
            ~Filter() {
               // se ci sono almeno due elementi...
                if (temp.size()>=2) {
                    p_mat.emplace_back(std::move(temp));
                }
            }
    
            void operator()(uint32_t val) {
                if (val >= p_min && val <= p_max) {
                    temp.emplace_back(val);
                }
            }
    
        private:
            std::vector<uint32_t> temp;
            std::vector<std::vector<uint32_t>>& p_mat;
            uint32_t p_min=0;
            uint32_t p_max=0;
    };
    
    int main()
    {
        vector<unsigned int> v = { 1, 3, 5, 6, 7, 8 };
        vector<vector<uint32_t>> w;
    
        std::for_each(v.cbegin(), v.cend(), Filter{0,2, w });
        std::for_each(v.cbegin(), v.cend(), Filter{3,5, w });
        std::for_each(v.cbegin(), v.cend(), Filter{6,8, w });
    
        std::for_each(w.cbegin(), w.cend(), [](auto& v) {
            std::for_each(v.cbegin(), v.cend(), [](auto val) {
                std::cout << val << " ";
            });
            std::cout << "\n";
        });
    
        cin.get();
    
    }
    
    Se i limiti delle sotto sequenze fossero sempre noti a compile time si potrebbe trasformare il tutto in un template, ma è una "raffinatezza" non necessaria al momento.
  • Re: Semplice algoritmo

    "Traducendo" in un C/C++ più terra terra, il tuo codice dovrebbe essere più o meno equivalente al seguente:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    void stampa_vector(const vector<unsigned int> &v)
    {
        for(unsigned int i = 0; i < v.size(); ++i)
        {
            cout << v[i] << " ";
        }
        cout << endl;
    }
    
    void fun(vector<vector<unsigned int>> &w, const vector<unsigned int> &v, const unsigned int min, const unsigned int max)
    {
        vector<unsigned int> temp;
        for(unsigned int i = 0; i < v.size(); ++i)
        {
            if(v[i] >= min && v[i] <= max)
            {
                temp.push_back(v[i]);
            }
        }
        if(temp.size() >= 2)
        {
            w.push_back(temp);
        }
    }
    
    int main()
    {
        vector<unsigned int> v = {1, 3, 5, 6, 7, 8};
        vector<vector<unsigned int>> w;
        //-----------------------------------------------------------
        fun(w, v, 0, 2);
        fun(w, v, 3, 5);
        fun(w, v, 6, 8);
        //-----------------------------------------------------------
        for(unsigned int i = 0; i < w.size(); stampa_vector(w[i++]));
     }
    
    Premesso che parlo da hobbista che conosce giusto le basi del C/C++, volevo chiederti se il tuo codice è, per così dire, volutamente "provocatorio", o se nell'ambito del paradigma della programmazione ad oggetti è abbastanza comune passare per soluzioni di questo tipo.

    Grazie comunque per gli spunti e per avermi fatto conoscere delle funzionalità del linguaggio che non conoscevo.
  • Re: Semplice algoritmo

    @nippolo, 'filosoficamente' parlando, nel codice precedente non c;e' nulla di programmazione ad oggetti.
    Al piu' e' normale programmazione procedurale (se usi il ciclo for')
    oppure 'funzionale' se usi una funzione, ( a cui passi un'altra funzione) per scandire un array/vettore (il 'foreach').
    Anche nella programmazione funzionale esistono i 'cicli'

    Poi, essendo C++, e' ovvio che siano coinvolti degli oggetti, visto che sono parte della libreria realizzata per un linguaggio ad oggetti,
    MA
    lo spirito in cui e' scritto il codice NON E' ad oggetti.
  • Re: Semplice algoritmo

    Nippolo ha scritto:


    Salve a tutti, come da titolo devo scrivere un algoritmo per risolvere un semplice problema.
    In pratica ho un vector di interi (ordinato e senza duplicati) contenente almeno due numeri compresi nell'intervallo [0;8], quello che devo fare è riempire un vector di vector con le sottosequenze (di almeno due elementi) tratte dal precedente vector e comprese in uno dei seguenti intervalli: [0;2], [3;5], [6;8].

    I ho scritto il seguente codice:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    void stampa_vector(const vector<unsigned int> &v)
    {
        for(unsigned int i = 0; i < v.size(); ++i)
        {
            cout << v[i] << " ";
        }
        cout << endl;
    }
    
    int main()
    {
        vector<unsigned int> v = {1, 3, 5, 6, 7, 8};
        vector<vector<unsigned int>> w;
        //-----------------------------------------------------------
        for(unsigned int i = 0; i < v.size() - 1; ++i)
        {
            if(v[i] / 3 == v[i + 1] / 3)
            {
                vector<unsigned int> u = {v[i], v[++i]};
                if(i < v.size() - 1 && v[i] / 3 == v[i + 1] / 3)
                {
                    u.push_back(v[++i]);
                }
                w.push_back(u);
            }
        }
        //-----------------------------------------------------------
        for(unsigned int i = 0; i < w.size(); stampa_vector(w[i++]));
     }
    effettivamente sembra funzionare, ma visto che non mi soddisfa appieno (in quanto un po' ridondante), mi chiedevo se qualcuno avesse qualche idea al riguardo, magari anche con un approccio completamente diverso.
    Mi sembra già quasi ottimale. Puoi giusto risparmiare un altro calcolo
    
        for(unsigned int i = 0; i < v.size() - 1; ++i)
        {
            unsigned int tmp = v[i + 1] / 3;
            if(v[i] / 3 == tmp)
            {
                vector<unsigned int> u = {v[i], v[++i]};
                if(i < v.size() - 1 && tmp == v[i + 1] / 3)
                {
                    u.push_back(v[++i]);
                }
                w.push_back(u);
            }
        }
    
  • Re: Semplice algoritmo

    @migliorabile, capisco, chiedevo giusto per curiosità comunque.

    Weierstrass ha scritto:


    Mi sembra già quasi ottimale. Puoi giusto risparmiare un altro calcolo
    Giusto, non ci avevo pensato.
    Non so se l'hai vista, ma nei precedenti messaggi ho postato anche un'altra versione (la riporto leggermente modificata):
    for(unsigned int sup, i = 0, flag = true; flag;)
    {
        vector<unsigned int> u = {v[i]};
        for(sup = (v[i++] / 3 + 1) * 3; (flag = i < v.size()) && v[i] < sup; u.push_back(v[i++]));
        if(u.size() > 1)
        {
            w.push_back(u);
        }
    }
    Ritieni sia più efficiente (per quanto possa avere senso parlare di "efficienza" per una cosa del genere ) rispetto alla prima versione?
  • Re: Semplice algoritmo

    Secondo me è meglio la prima, dove il vettore dinamico è creato solo quando serve.
  • Re: Semplice algoritmo

    @Nippolo:
    Il discorso è anche più "terra terra" nell'ambito dell'espressività di quel che si vuol fare.
    Nel mio codice o in questo:
    
    fun(w, v, 0, 2);
    fun(w, v, 3, 5);
    fun(w, v, 6, 8);
    
    si può intuire quel che si vuol ottenere, ossia una selezione in base a dei limiti.
    Ma in questo [CODE] for(unsigned int sup, i = 0, flag = true; flag;) { vector<unsigned int> u = {v[i]}; for(sup = (v[i++] / 3 + 1) * 3; (flag = i < v.size()) && v[i] < sup; u.push_back(v[i++])); if(u.size() > 1) { w.push_back(u); } } ci si deve impegnare un bel pò prima di capire che succede e molto spesso (anzi sempre) il tempo del programmatore costa zilioni più del tempo di esecuzione.
  • Re: Semplice algoritmo

    Sì, in effetti mi rendo conto che in ambito professionale la chiarezza, per così dire, prevale sull'efficienza, ma fin quando si programma come passatempo, trovo che sia anche divertente cimentarsi in cose un po' più "strane"!
  • Re: Semplice algoritmo

    Solo che dopo 3/4 mesi ci si dimentica di come funzionano le cose "strane" e si deve perdere tempo per capire come funzionano (dopo aver perso tempo a implementarle). Poi si scopre di dover riutilizzare l'algoritmo per intervalli diversi e dimensioni diverse e si perde altro tempo per reinventare di nuovo una ruota "strana".
  • Re: Semplice algoritmo

    Non sai quante volte mi è capitato... più "passatempo" di così non si può!
Devi accedere o registrarti per scrivere nel forum
15 risposte