Informatika 3 - BME TTK

5. gyakorlat - megoldások

1. feladat. A for_each függvény használatával írjunk programot, amely egy Point típusú objektumokat tartalmazó vector esetén kiírja a képernyőre a megelőző pontból az adott pontba mutató vektort. Az első elem esetén a kiindulópont legyen definíció szerint az origó. (Használjuk az előadáson bemutatott Point osztályt.)

Megoldás:

#include<algorithm>
#include<vector>
#include<iostream>
#include"point.h"
using namespace std;
using namespace bme;

static void step(const Point& p) {
    static Point start = Point(0., 0.);
    cout << p-start << endl; 
    start = p;
}

int main() {
    vector<Point> v = { Point(1.,2.), Point(3.,6.), Point(-1.,2.)};
    for_each(v.begin(), v.end(), step);

    return 0;
}

2. feladat. Írjunk C++ függvényt, amely paraméterül kap egy int-eket tartalmazó list-et és egy további bound nevű int-et, és kitörli a listából azokat a számokat, amelyek a bound értéknél nagyobbak.

Megoldás:

void eraseVals(int bound, list<int>& ls) {
    ls.remove_if([bound](int x) { return x > bound; });
}

3. feladat. A következő kódban van egy hiba, keressük meg és javítsuk ki ezt. (Először próbáljuk meg ezt a számítógép használata nélkül megtenni, keressünk több lehetséges megoldást.) Mit ír ki a képernyőre a kijavított program?

#include <iostream>
using namespace std;
int main() {
    []() {cout << "Hello" << endl; }();
    int x = [](int x, int y) {return x + y; } (10, 5);
    [x](int y) {cout << "Sum: " << (x += y) << endl; }(5);
}

Megoldás:

A hiba az, hogy a capture clause-ban érték szerint rögzítjük az x változót, ezután azt a lambda nem tudja módosítani.

Az egyik lehetséges megoldás, hogy referencia szerint rögzítjük az x-et:

#include <iostream>
using namespace std;
int main() {
    []() {cout << "Hello" << endl; }();
    int x = [](int x, int y) {return x + y; } (10, 5);
    [&x](int y) {cout << "Sum: " << (x += y) << endl; }(5);
}

Egy másik lehetséges megoldás a mutable kulcsszó használata:

#include <iostream>
using namespace std;
int main() {
    []() {cout << "Hello" << endl; }();
    int x = [](int x, int y) {return x + y; } (10, 5);
    [x](int y) mutable {cout << "Sum: " << (x += y) << endl; }(5);
}

Végül pedig megváltoztathatjuk az utolsó lambdát úgy, hogy ugyanazt az értéket írja ki, de az x változót ne változtassa meg:

#include <iostream>
using namespace std;
int main() {
    []() {cout << "Hello" << endl; }();
    int x = [](int x, int y) {return x + y; } (10, 5);
    [x](int y) {cout << "Sum: " << (x + y) << endl; }(5);
}

Mindhárom verzió ugyanat írja ki a képernyőre. A main első sora meghív egy lambda expressiont, ami kiírja, hogy "Hello", majd egy sortörést. Az ezután deklarált x változó értéke egy lambda expression által visszaadott érték lesz, amelyet a 10, 5 paraméterekkel hívunk meg, és amely visszaadja ezen paraméterek összegét. Vagyis az x változó értéke kezdetben 15. Végül meghívunk 5 paraméterrel egy újabb lambda expressiont, amely ezt a paramétert az x változó értékéhez hozzáadja, és a "Sum: " karaktersorozat után kiírja az összeget, vagyis a 20-at a képernyőre (ezt még egy sortörés követi). Az első megoldásban maga az x változó értéke is 20-ra változik, a második megoldásban a lambdán belül a lokális x változó értéke változik meg.

4. feladat. Definiáljuk az \(a_n\) sorozatot a következőképp: legyen \(a_1=3\), továbbá \(n>1\) esetén \[ a_n=\prod_{d\mid n,\, d\lt n} (a_d+(-1)^d). \] Írjunk függvényt, amely visszaadja az \(a_n\) értéket úgy, hogy minden \(n>0\) esetén a korábban kiszámolt értékeket eltároljuk.

Megoldás:

#include<map>
#include<iostream>
using namespace std;

static int recur(int n) {
    static map<int, int> lookup;

    if (n <= 0) {
        lookup.clear();
        return 0;
    }
    if (n == 1) {
        return 3;
    }
    if (lookup.count(n) > 0) {
        return lookup[n];
    }
    int ans = 1;
    for (int k = 1; k <= n / 2; k++) {
        if (n % k == 0) {
            ans *= recur(k) + (k % 2 == 0 ? 1 : -1);
        }
    }
    return lookup[n] = ans;
}

int main() {
    for (int i = 1; i <= 32; ++i) {
        cout << "a(" << i << ") = " << recur(i) << endl;
    }

    return 0;
}

5. feladat. Valósítsuk meg a Graph osztályt a map tároló segítségével a következő lépésekben:

(a) Definiáljunk egy Edge osztályt, amely egy élet reprezentál. Legyen két unsigned int tagváltozója, amelyek az élen lévő két csúcs címkéjét jelölik. Valósítsuk meg úgy az osztályt, hogy az élen lévő csúcsokat egy felhasználó lekérdezhesse, de módosítani csak közvetve, a később definiált Graph osztályon keresztül tudja. Legyen egy tagfüggvénye, amivel lekérdezhető, hogy hurokélről van-e szó, ill. valósítsuk meg az == és < operátorokat (utóbbi legyen lexikografikus rendezés a csúcspárokon). Minden tagfüggvény és konstruktor legyen inline.

(b) Definiáljunk egy Vertex osztályt, amely egy csúcsot reprezentál. Legyen egy unsigned int tagváltozója, amely a csúcs címkéjét jelöli, és tároljuk el a csúcsra illeszkedő éleket egy Edge objektumokat tartalmazó listában. Úgy valósítsuk meg az osztályt, hogy egy külső felhasználó a tagváltozók értékéhez hozzáférhessen, de azokat módosítani csak közvetve, a később definiált Graph osztályon keresztül tudja. Legyen az osztálynak egy publikus default konstruktora, és legyen egy olyan konstruktor is, aminek a paramétere a csúcs címkéje. Legyen továbbá egy olyan tagfüggvénye, amely visszaadja a csúcsra illeszkedő élek számát. Minden tagfüggvény és konstruktor legyen inline.

(c) Definiáljuk a Graph osztályt, amely egy irányítatlan gráf éllistákkal való tárolására alkalmas. A csúcsokat egy map tárolóban tároljuk, ahol a kulcs unsigned int, míg az érték Vertex típusú. Írjunk tagfüggvényeket, melyekkel csúcsokat és éleket adhatunk hozzá és törölhetünk, ill. amelyek visszaadják a gráf csúcs- ill. élszámát, valamint egy megadott csúcs fokszámát és a szomszédainak listáját. Írjunk olyan tagfüggvényt, amely visszaadja, hogy két megadott csúcs közt fut-e él. Legyen olyan tagfüggvény is, amely eldönti, hogy egyszerű-e a gráf, valamint legyen lehetőség a gráfból az élek összehúzásával és a hurokélek törlésével egyszerű gráfot csinálni.

Megoldás:

graph.h

#ifndef GRAPH_H
#define GRAPH_H

#include <map>
#include <list>
using namespace std;

namespace bme {

    class Graph;

    class Edge {
    private:
        unsigned int vfrom;
        unsigned int vto;
    public:
        Edge(unsigned int  _vfrom, unsigned int _vto) : vfrom(_vfrom), vto(_vto) {}

        unsigned int    vFrom() const { return vfrom; }
        unsigned int    vTo() const { return vto; }
        bool            isLoop()const { return vfrom == vto; }

        bool operator<(const Edge& other) const;
        bool operator==(const Edge& other) const;

        friend Graph;
    };

    class Vertex {
    private:
        unsigned int    label;
        list<Edge>      edges;
    public:
        Vertex(unsigned int _label) : label(_label) {}
        Vertex() : label(0) {}

        unsigned int        getLabel()const { return label; }
        int                 nNeighbors()const { return edges.size(); }
        const list<Edge>&   edgeList() const{ return edges; }

        friend Graph;
    };


    class Graph {
    private:
        unsigned int              nextlabel;
        map<unsigned int, Vertex> vertices;
    public:
        Graph(unsigned int n);

        void                addEdge(unsigned int u, unsigned int v);
        void                removeEdge(unsigned int u, unsigned int v);
        unsigned int        addVertex();
        void                removeVertex(unsigned int v);
        int                 vertexCount() const;
        int                 edgeCount() const;
        const list<Edge>&   neighbors(unsigned int label) const;
        bool                areConnected(unsigned int v1, unsigned int v2) const;
        int                 degree(unsigned int v) const;
        bool                isSimple() const;
        void                simplify();
        unsigned int        nextLabel()const { return nextlabel; }
    };

    inline bool isLoop(const Edge& e) { return e.isLoop(); }

    inline bool Edge::operator<(const Edge& other) const {
        if (vfrom < other.vFrom()) {
            return true;
        }
        else if (vfrom == other.vFrom() && vto < other.vTo()) {
            return true;
        }
        else {
            return false;
        }
    }

    inline bool Edge::operator==(const Edge& other) const {
        return vfrom == other.vFrom() && vto == other.vTo();
    }
}

#endif

graph.cpp

#include "graph.h"
#include <vector>
#include <map>
#include <list>
using namespace std;

namespace bme {
   
    Graph::Graph(unsigned int n) {
        for (unsigned int i = 0; i < n; ++i) {
            vertices[i] = Vertex(i);
        }
        nextlabel = n;
    }
    
    void Graph::addEdge(unsigned int u, unsigned int v) {
        if (vertices.count(u) > 0 && vertices.count(v) > 0) {
            vertices[u].edges.push_back(Edge(u, v));
            vertices[v].edges.push_back(Edge(v, u)); //hurokéleket duplán tárolunk (szándékosan)
        }
    }

    void Graph::removeEdge(unsigned int u, unsigned int v) {
        if (vertices.count(u) == 0 || vertices.count(v) == 0) {
            return;
        }
        vertices[u].edges.remove_if([v](const Edge& e) {return e.vto == v; });
        if (u!=v) {
            vertices[v].edges.remove_if([u](const Edge& e) {return e.vto == u; });
        }
    }

    unsigned int Graph::addVertex() {
        vertices[nextlabel] = Vertex(nextlabel);
        return nextlabel++;
    }
    
    void Graph::removeVertex(unsigned int v) {
        if (vertices.count(v) == 0) {
            return;
        }
        for (Edge& e : vertices[v].edges) {
            if (!e.isLoop()) {
                list<Edge>& li_other = vertices[e.vTo()].edges;
                li_other.remove_if([v](const Edge& _e) { return _e.vTo() == v; });
            }
        }
        vertices.erase(v);
    }
    
    int Graph::vertexCount() const {
        return vertices.size();
    }

    int Graph::edgeCount() const {
        int count = 0;
        for (unsigned int i = 0; i < nextlabel; ++i) {
            if (vertices.count(i) != 0) {
                count += vertices.at(i).nNeighbors();
            }
        }
        return count / 2;
    }

    const list<Edge>& Graph::neighbors(unsigned int label) const {
        return vertices.at(label).edgeList();
    }

    bool Graph::areConnected(unsigned int v1, unsigned int v2) const {
        if (vertices.count(v1) == 0 || vertices.count(v2) == 0) {
            return false;
        }     
        for (const Edge& e : vertices.at(v1).edgeList()) {
            if (e.vTo() == v2) {
                return true;
            }
        }
        return false;
    }

    int Graph::degree(unsigned int v) const {
        if (vertices.count(v) == 0) {
            return -1;
        }
        return vertices.at(v).nNeighbors();
    }

    bool Graph::isSimple() const {
        for (unsigned int v = 0; v < nextlabel; ++v) {
            if (vertices.count(v) == 0) {
                continue;
            }
            vector<bool> seen(nextlabel, false);
            for (const Edge& neighbor : vertices.at(v).edges) {
                if (neighbor.isLoop() || seen[neighbor.vTo()]) {
                    return false;
                }
                seen[neighbor.vTo()] = true;
            }
        }
        return true;
    }

    void Graph::simplify() {
        for (unsigned int v = 0; v < nextlabel; ++v) {
            if (vertices.count(v) == 0) {
                continue;
            }
            list<Edge>& neighbors = vertices[v].edges;
            neighbors.sort();
            neighbors.unique();
            neighbors.remove_if(isLoop);
        }
    }
    
}

Egy teszt:

#include<iostream>
#include "graph.h"
using namespace std;


int main() {
    bme::Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 1);
    g.addEdge(3, 4);
    g.addEdge(4, 0);
    g.addEdge(1, 1);
    g.removeEdge(1, 2);
    
    cout << "Csucsok szama: " << g.vertexCount() << "\n";
    cout << "Elek szama: " << g.edgeCount() << "\n";
    cout << "Egyszeru graf-e: " << (g.isSimple() ? "Igen" : "Nem") << "\n";

    g.simplify();
    cout << "Egyszerusites utan egyszeru graf-e: " << (g.isSimple() ? "Igen" : "Nem") << "\n";
    cout << "Csucsok szama: " << g.vertexCount() << "\n";
    cout << "Elek szama: " << g.edgeCount() << "\n";

    return 0;
}