4. gyakorlat - megoldások
1. feladat. Írjuk egy függvényt, amely egy int-eket tároló vector-t kap paraméterül, és visszaadja a kapott
számok közül a nemnegatívakat növekvő sorrendben (mindegyik számot annyiszor, ahányszor a kapott
vector-ban szerepelt).
Megoldás:
void f(const vector<int>& input, list<int>& output) {
output.clear();
for (int d : input) {
if (d >= 0) {
output.push_back(d);
}
}
output.sort();
}
Készítsünk egy osztályt, amely egy súlyozott ponthalmaz modellezésére szolgál. Legyenek tagfüggvényei,
amelyekkel pontokat törölhetünk vagy adhatunk hozzá a halmazhoz, ill. amellyel módosíthatjuk
az egyes pontok súlyait. Írjunk tagfüggvényt, amely visszaadja a ponthalmaz súlypontját.
Megoldás:
weighted_points.h
#ifndef WPOINTS_H
#define WPOINTS_H
#include<vector>
#include<utility>
#include "point.h"
using namespace std;
namespace bme{
class WPOINTS {
private:
vector<pair<Point,double>> points;
Point psum;
double wsum;
public:
WPOINTS();
WPOINTS(const vector<Point>& _points);
void addPoint(Point p, double weight);
void deletePoint(int idx);
void setWeight(int idx, double weight);
int nPoints()const;
Point getPoint(int idx)const;
double getWeight(int idx)const;
Point getCenter()const;
};
}
#endif
weighted_points.cpp
#include "weighted_points.h"
#include "point.h"
#include <vector>
#include <utility>
using namespace std;
namespace bme {
WPOINTS::WPOINTS() : wsum(.0) {}
WPOINTS::WPOINTS(const vector<Point>& _points) {
size_t size = _points.size();
points.reserve(size);
for (Point p : _points) {
points.push_back(make_pair(p, 1.0));
psum += p;
}
wsum = static_cast<double>(size);
}
void WPOINTS::addPoint(Point p, double weight) {
if (weight > 0) {
points.push_back(make_pair(p, weight));
psum += p*weight;
wsum += weight;
}
else {
cerr << "ERROR: the weight must be positive! No point added." << endl;
}
}
void WPOINTS::deletePoint(int idx) {
if (idx >= 0 && idx < points.size()) {
pair<Point, double> wp = points[idx];
psum -= wp.first*wp.second;
wsum -= wp.second;
points.erase(points.begin() + idx);
}
else {
cerr << "ERROR: invalid index! No point deleted." << endl;
}
}
void WPOINTS::setWeight(int idx, double weight){
if (idx >= 0 && idx < points.size()) {
double diff = weight - points[idx].second;
wsum += diff;
psum += diff * points[idx].first;
points[idx].second = weight;
}
else {
cerr << "ERROR: invalid index! No weight changed." << endl;
}
}
int WPOINTS::nPoints() const{
return static_cast<int>(points.size());
}
Point WPOINTS::getPoint(int idx) const {
if (idx >= 0 && idx < points.size()) {
return points[idx].first;
}
else {
cerr << "ERROR: invalid index!" << endl;
return Point(.0, .0);
}
}
double WPOINTS::getWeight(int idx) const {
if (idx >= 0 && idx < points.size()) {
return points[idx].second;
}
else {
cerr << "ERROR: invalid index!" << endl;
return .0;
}
}
Point WPOINTS::getCenter() const {
if (points.size() > 0) {
return psum / wsum;
}
else {
return Point(0.,0.);
}
}
}
Egy teszt:
#include <iostream>
#include "weighted_points.h"
#include <vector>
using namespace std;
using namespace bme;
int main() {
vector<Point> v = { Point(0,1.0), Point(2.0,0.) };
WPOINTS wp(v);
wp.addPoint(Point(-1.0, 0.),1.);
wp.setWeight(1, 0.5);
cout << "Points:" << endl << endl;
for (int i = 0; i < wp.nPoints(); ++i) {
cout << wp.getPoint(i) << ", weight: " << wp.getWeight(i) << endl;
}
cout << endl << "Center: " << wp.getCenter() << endl;
return 0;
}
Készítsünk osztályt, amely egy irányítatlan
gráf éllistákkal való tárolására alkalmas.
Í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 <vector>
#include <list>
using namespace std;
namespace bme {
class Graph {
private:
vector<list<int>> adjList;
public:
Graph(int n);
void addEdge(int u, int v);
void removeEdge(int u, int v);
void addVertex();
void removeVertex(int v);
int vertexCount() const;
int edgeCount() const;
const list<int>& neighbors(int idx) const;
bool areConnected(int v1, int v2) const;
int degree(int v) const;
bool isSimple() const;
void simplify();
};
}
#endif
graph.cpp
#include "graph.h"
#include <vector>
#include <list>
namespace bme {
Graph::Graph(int n) {
adjList.resize(n);
}
void Graph::addEdge(int u, int v) {
if (u >= 0 && u < adjList.size() && v >= 0 && v < adjList.size()) {
adjList[u].push_back(v);
adjList[v].push_back(u); //hurokéleket duplán tárolunk (szándékosan)
}
}
void Graph::removeEdge(int u, int v) {
if (u >= 0 && u < adjList.size() && v >= 0 && v < adjList.size()) {
adjList[u].remove(v);
if (u != v) {
adjList[v].remove(u);
}
}
}
void Graph::addVertex() {
adjList.push_back(list<int>());
}
void Graph::removeVertex(int v) {
if (v >= 0 && v < adjList.size()) {
for (list<int>& neighbors : adjList) {
neighbors.remove(v);
}
adjList.erase(adjList.begin() + v);
}
for (list<int>& neighbors : adjList) {
for (int& u : neighbors) {
if (u > v) {
u--;
}
}
}
}
int Graph::vertexCount() const {
return adjList.size();
}
int Graph::edgeCount() const {
int count = 0;
for (const list<int>& neighbors : adjList) {
count += neighbors.size();
}
return count / 2;
}
const list<int>& Graph::neighbors(int idx) const {
return adjList[idx];
}
bool Graph::areConnected(int v1, int v2) const {
if (v1 < 0 || v2 < 0 || v1 >= adjList.size() || v2 >= adjList.size()) {
return false;
}
for (int n : adjList[v1]) {
if (n == v2) {
return true;
}
}
return false;
}
int Graph::degree(int v) const {
if (v >= 0 && v < adjList.size()) {
return adjList[v].size();
}
return -1;
}
bool Graph::isSimple() const {
for (size_t i = 0; i < adjList.size(); ++i) {
vector<bool> seen(adjList.size(), false);
for (int neighbor : adjList[i]) {
if (neighbor == static_cast<int>(i) || seen[neighbor]) {
return false;
}
seen[neighbor] = true;
}
}
return true;
}
void Graph::simplify() {
for (int v = 0; v < adjList.size(); ++v) {
list<int>& neighbors = adjList[v];
neighbors.sort();
neighbors.unique();
neighbors.remove(v);
}
}
}
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);
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;
}