Tanulási útmutató
Összefoglalás
Kiválogatás, szétválogatás, unió, metszet algoritmusmintákkal tervezett programok implementálása, fájlokkal
Követelmény
Önállóan megoldható feladatok
- Fájl letöltése: Összetett tételek 2. feladatsor. című háttéranyag letöltése
- Információ az állományról: A feladatsorban az anyagrészhez tartozó önálló gyakorlaó feladatok találhatóak.
- Fájlméret: 0.07 MB
Unió és metszet tételt alkalmazó feladatok implementálása szöveges fájlokkal
Az animáció feladatokon keresztül mutatja be az összetett tételek használatát:
Feladat: „Összetett programozási tételek 2.” feladatsor/3. - Lóverseny
Egy lóversenyen ugyanazoknak a lovaknak két fordulóban kell helytállniuk.
Adjuk meg azokat a lovakat, amelyek mindkét fordulóban célba értek!
Megoldás
Alkalmazott tétel
Metszet
Az animáció bemutatja a metszet tételt:
Specifikáció
Bemenet
N,M: Egész
ElsőForduló: Tömb[1..N: Szöveg]
MásodikForduló: Tömb[1..M: Szöveg]
Kimenet
MindkettőDb: Egész
Mindkettőben: Tömb[1..MindkettőDb: Szöveg]
Előfeltétel
N≥0 és M≥0 és HalmazE(ElsőForduló) és HalmazE(MásodikForduló)
Utófeltétel
MindkettőDb=SZUM(i=1..N;ElsőForduló[i] ∈ MásodikForduló) 1
és ∀ i ∈ [1..MindkettőDb] : (Mindkettőben[i] ∈ ElsőForduló és
Mindkettőben[i] ∈ MásodikForduló) és HalmazE(Mindkettőben)
Algoritmus
Kód
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int MAXN=100;
void Beolvas(string fajlNev, int &n, string fordulo[]);
void Metszet(int n, string elsoFordulo[],int m, string masodikFordulo[],
int &mindkettoDb, string mindkettoben[]);
void Kiiras(string fajlNev, int &mindkettoDb, string mindkettoben[]);
int main()
{
int N,M,MindkettoDb;
string ElsoFordulo[MAXN];
string MasodikFordulo[MAXN];
string Mindkettoben[MAXN];
Beolvas("elso.be",N,ElsoFordulo);
Beolvas("masodik.be",M,MasodikFordulo);
Metszet(N, ElsoFordulo,M,MasodikFordulo,MindkettoDb,Mindkettoben);
Kiiras("loverseny.ki",MindkettoDb,Mindkettoben);
return 0;
}
void Beolvas(string fajlNev, int &n, string fordulo[])
{
//Helyes bemenetet feltételezünk
cout<<"-------------------------------------------------------\n";
cout<<"Loverseny "<<fajlNev.substr(0,fajlNev.find("."));
cout<< " forduloja \n\n";
cout<<"-------------------------------------------------------\n";
ifstream ifs(fajlNev.c_str());
if (ifs.is_open())
{
ifs>>n;
cout<<n<<" darab versenyzo van"<<endl;
for (int i=0;i<n;i++)
{
ifs>>fordulo[i];
//Kepernyore is kiirunk
cout<<fordulo[i]<<endl;
}
ifs.close();
}
cout<<"\n";
};
void Metszet(int n, string elsoFordulo[],int m, string masodikFordulo[],
int &mindkettoDb, string mindkettoben[])
{
int j;
mindkettoDb=0;
for (int i=0;i<n;i++)
{
j=0;
while ((j<m)&&(elsoFordulo[i].compare(masodikFordulo[j])))
{
j++;
}
if (j<m)
{
mindkettoben[mindkettoDb]=masodikFordulo[j];
mindkettoDb++;
}
}
};
void Kiiras(string fajlNev, int &mindkettoDb, string mindkettoben[])
{
ofstream ofs(fajlNev.c_str());
cout<<"-------------------------------------------------------\n";
cout<<mindkettoDb<<" db lo szerepelt mindket forduloban \n";
cout<<"-------------------------------------------------------\n";
if (ofs.is_open())
{
ofs<<mindkettoDb<<"db lo szerepelt mindket forduloban\n";
for (int i=0;i<mindkettoDb;i++)
{
ofs<<mindkettoben[i]<<"\n";
//Kepernyore is kiirunk
cout<<mindkettoben[i]<<"\n";
}
}
};
Feladat: „Összetett programozási tételek 2.” feladatsor/8. - Lóverseny
Egy lóversenyen ugyanazoknak a lovaknak két fordulóban kell helytállniuk.
Adjuk meg azokat a lovakat, amelyek legalább az egyik fordulóban célba értek!
Megoldás
Alkalmazott tétel
Unió
Az animáció bemutatja az unió tételt:
Specifikáció
Bemenet
N,M: Egész
ElsőForduló: Tömb[1..N: Szöveg]
MásodikForduló: Tömb[1..M: Szöveg]
Kimenet
EgyikbenDb: Egész
Egyikben: Tömb[1..EgyikbenDb: Szöveg]
Előfeltétel
N≥0 és M≥0 és HalmazE(ElsőForduló) és HalmazE(MásodikForduló)
Utófeltétel
EgyikbenDb=N + SZUM(i=1..M; MásodikForduló [i] ∉ ElsőForduló) 1
és ∀ i ∈ [1..EgyikbenDb] : (Egyikben[i] ∈ ElsőForduló vagy
Egyikben[i] ∈ MásodikForduló ) és HalmazE(Egyikben)
Algoritmus
Kód
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int MAXN=100;
void Beolvas(string fajlNev, int &n, string fordulo[]);
void Unio(int n, string elsoFordulo[],int m, string masodikFordulo[],
int &egyikbenDb, string egyikben[]);
void Kiiras(string fajlNev, int &mindkettoDb, string mindkettoben[]);
int main()
{
int N,M,EgyikbenDb;
string ElsoFordulo[MAXN];
string MasodikFordulo[MAXN];
string Egyikben[MAXN];
Beolvas("elso.be",N,ElsoFordulo);
Beolvas("masodik.be",M,MasodikFordulo);
Unio(N, ElsoFordulo,M,MasodikFordulo,EgyikbenDb,Egyikben);
Kiiras("loverseny.ki",EgyikbenDb,Egyikben);
return 0;
}
void Beolvas(string fajlNev, int &n, string fordulo[])
{
//Helyes bemenetet feltételezünk
cout<<"-------------------------------------------------------\n";
cout<<"Loverseny "<<fajlNev.substr(0,fajlNev.find("."));
cout<<" forduloja \n\n";
cout<<"-------------------------------------------------------\n";
ifstream ifs(fajlNev.c_str());
if (ifs.is_open())
{
ifs>>n;
cout<<n<<" darab versenyzo van"<<endl;
for (int i=0;i<n;i++)
{
ifs>>fordulo[i];
//Kepernyore is kiirunk
cout<<fordulo[i]<<endl;
}
ifs.close();
}
cout<<"\n";
};
void Unio(int n, string elsoFordulo[],int m, string masodikFordulo[],
int &egyikbenDb, string egyikben[])
{
int i;
for (i=0;i<n;i++)
{
egyikben[i]=elsoFordulo[i];
}
egyikbenDb=n;
for (int j=0;j<m;j++)
{
i=0;
while ((i<n)&&
(elsoFordulo[i].compare(masodikFordulo[j])))
{
i++;
}
if (i>=n)
{
egyikben[egyikbenDb]=masodikFordulo[j];
egyikbenDb++;
}
}
};
void Kiiras(string fajlNev, int &egyikbenDb, string egyikben[])
{
ofstream ofs(fajlNev.c_str());
cout<<"-------------------------------------------------------\n";
cout<<egyikbenDb<<" db lo szerepelt valamelyik forduloban \n";
cout<<"-------------------------------------------------------\n";
if (ofs.is_open())
{
ofs<<egyikbenDb<<"db lo szerepelt valamelyik forduloban\n";
for (int i=0;i<egyikbenDb;i++)
{
ofs<<egyikben[i]<<"\n";
//Kepernyore is kiirunk
cout<<egyikben[i]<<"\n";
}
}
};
Feladat: „Összetett programozási tételek 2.” feladatsor/5. - Szerzők
Ismerjük két szerző műveinek listáját. Írjunk algoritmust, amely meghatározza, hogy vannak-e közös könyveik, s ha igen, melyek azok!
Megoldás
Alkalmazott tétel
Metszet
Az animáció bemutatja a metszet tételt:
Specifikáció
Bemenet
N,M: Egész
Szerző1: Tömb[1..N: Szöveg]
Szerző2: Tömb[1..M: Szöveg]
Kimenet
MindkettenDb: Egész
Mindketten: Tömb[1..MindkettenDb: Szöveg]
Előfeltétel
N≥0 és M≥0 és HalmazE(Szerző1) és HalmazE(Szerző2)
Utófeltétel
MindkettenDb=SZUM(i=1..N; Szerző1[i] ∈ Szerző2) 1 és
∀ i(1 ≤ i ≤ MindkettenDb) : (Mindketten[i] ∈ Szerző1 és Mindketten[i] ∈ Szerző2) és
HalmazE(Mindketten)
Algoritmus
Kód
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int MAXN=100;
void Beolvas(string fajlNev, int &n, string fordulo[]);
void Metszet(int n, string elsoFordulo[],int m, string masodikFordulo[],
int &mindkettoDb, string mindkettoben[]);
void Kiiras(string fajlNev, int &mindkettoDb, string mindkettoben[]);
int main()
{
int N,M,MindkettenDb;
string Szerzo1[MAXN];
string Szerzo2[MAXN];
string Mindketten[MAXN];
Beolvas("Ritchie.be",N,Szerzo1);
Beolvas("Maxwell.be",M,Szerzo2);
Metszet(N,Szerzo1,M,Szerzo2,MindkettenDb,Mindketten);
Kiiras("konyvek.ki",MindkettenDb,Mindketten);
return 0;
}
void Beolvas(string fajlNev, int &n, string szerzo[])
{
//Helyes bemenetet feltételezünk
string eldob;
cout<<"-------------------------------------------------------\n";
cout<<fajlNev.substr(0,fajlNev.find("."))<< " konyvei \n\n";
cout<<"-------------------------------------------------------\n";
ifstream ifs(fajlNev.c_str());
if (ifs.is_open())
{
ifs>>n;
getline(ifs,eldob);
cout<<n<<" darab konyve van"<<endl;
for (int i=0;i<n;i++)
{
getline(ifs,szerzo[i]);
//Kepernyore is kiirunk
cout<<i<<"."<<szerzo[i]<<endl;
}
ifs.close();
}
cout<<"\n";
};
void Metszet(int n, string szerzo1[],int m, string szerzo2[],
int &mindkettenDb, string mindketten[])
{
int j;
mindkettenDb=0;
for (int i=0;i<n;i++)
{
j=0;
while ((j<m)&&(szerzo1[i].compare(szerzo2[j])))
{
j++;
}
if (j<m)
{
mindketten[mindkettenDb]=szerzo2[j];
mindkettenDb++;
}
}
};
void Kiiras(string fajlNev, int &mindkettenDb, string mindketten[])
{
ofstream ofs(fajlNev.c_str());
cout<<"-------------------------------------------------------\n";
cout<<mindkettenDb<<" db konyvben szerzotarsak \n";
cout<<"-------------------------------------------------------\n";
if (ofs.is_open())
{
ofs<<mindkettenDb<<"db konyvben szerzotarsak\n";
for (int i=0;i<mindkettenDb;i++)
{
ofs<<mindketten[i]<<"\n";
//Kepernyore is kiirunk
cout<<mindketten[i]<<"\n";
}
}
};
Házi feladat
Feladat: „Összetett programozási tételek 2.” feladatsor/6. - Oktató
Egy oktató nyilvántartja a hallgatóinak a zh-án és a pót zh-án elért eredményeit. Adjuk meg azokat a hallgatókat, akik legalább az egyik alkalommal próbálkoztak!
