| Exercice 1 | Exercice 2 | Exercice 3 | Exercice 4 | Exercice 5 | Exercice 6 | Exercice 7 | Exercice 8 |
Le code fourni ici est en C++11. Pour une version compilant avec l'ancien standard (C++98) voir ci-dessous.
#include <iostream>
using namespace std;
struct Complexe {
double x;
double y;
};
// Solution simple
void affiche(Complexe z)
{
cout << "(" << z.x << "," << z.y << ")";
// autre solution : cout << z.x << "+" << z.y << "i";
}
void affiche2(Complexe z)
{
if ((z.x == 0.0) and (z.y == 0.0)) {
cout << "0";
return;
}
if (z.x != 0.0) {
cout << z.x;
if (z.y > 0.0)
cout << "+";
}
if (z.y != 0.0) {
if ((z.x == 0.0) and (z.y == -1.0))
cout << "-";
else if (z.y != 1.0)
cout << z.y;
cout << "i";
}
}
Complexe addition(Complexe z1, Complexe z2)
{
return { z1.x + z2.x, z1.y + z2.y };
}
Complexe soustraction(Complexe z1, Complexe z2)
{
return { z1.x - z2.x, z1.y - z2.y };
}
Complexe multiplication(Complexe z1, Complexe z2)
{
return { z1.x * z2.x - z1.y * z2.y ,
z1.x * z2.y + z1.y * z2.x };
}
Complexe division(Complexe z1, Complexe z2)
{
const double r(z2.x*z2.x + z2.y*z2.y);
return { (z1.x * z2.x + z1.y * z2.y) / r ,
(z1.y * z2.x - z1.x * z2.y) / r };
}
int main()
{
Complexe un = { 1.0, 0.0 };
Complexe i = { 0.0, 1.0 };
affiche(un); cout << " + "; affiche(i); cout << " = ";
Complexe j(addition(un, i));
affiche(j); cout << endl;
affiche(i); cout << " * "; affiche(i); cout << " = ";
affiche(multiplication(i,i)); cout << endl;
affiche(j); cout << " * "; affiche(j); cout << " = ";
Complexe z(multiplication(j,j));
affiche(z); cout << endl;
affiche(z); cout << " / "; affiche(i); cout << " = ";
affiche(division(z,i)); cout << endl;
z= { 2.0, -3.0 };
affiche(z); cout << " / "; affiche(j); cout << " = ";
affiche(division(z,j)); cout << endl;
return 0;
}
La seule différence en C++98, c'est que la syntaxe d'initialisation n'est pas permise en affectation. En clair, les expression du type :
return { z1.x + z2.x, z1.y + z2.y };
doivent être remplacées par une initialisation de variable :
Complexe z = { z1.x + z2.x, z1.y + z2.y };
return z;
De même dans le main()
z= { 2.0, -3.0 };
doit être remplacé par :
z.x = 2.0; z.y = -3.0;
Encore une illustration des avantages de la nouvelle norme C++11 !
Le code fourni ici est en C++11. Pour une version compilant avec l'ancien standard (C++98) voir ci-dessous.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct QCM {
string question;
vector<string> reponses;
unsigned int solution;
};
typedef vector<QCM> Examen;
void affiche(const QCM& question);
unsigned int demander_nombre(unsigned int min, unsigned int max);
unsigned int poser_question(const QCM& question);
Examen creer_examen();
// ======================================================================
int main()
{
unsigned int note(0);
Examen exam(creer_examen());
for (auto question : exam) {
if (poser_question(question) == question.solution) {
++note;
}
}
if (note > 1) cout << 's';
if (note > 1) cout << 's';
cout << " sur " << exam.size() << "." << endl;
return 0;
}
// ======================================================================
void affiche(const QCM& q)
{
cout << q.question << " ?" << endl;
unsigned int i(0);
for (auto reponse : q.reponses) {
cout << " " << ++i << "- " << reponse << endl;
}
}
// ======================================================================
unsigned int demander_nombre(unsigned int a, unsigned int b)
{
* le bon sens. */
if (a > b) { unsigned int tmp(b); b=a; a=tmp; }
unsigned int res;
do {
cout << "Entrez un nombre entier compris entre "
<< a << " et " << b <<" : ";
cin >> res;
} while ((res < a) or (res > b));
return res;
}
// ======================================================================
unsigned int poser_question(const QCM& q)
{
affiche(q);
return demander_nombre(1, q.reponses.size());
}
// ======================================================================
Examen creer_examen()
{
return {
// Question 1
},
// Question 2
{ "Laquelle des instructions suivantes est un prototype de fonction",
{ "int f(0);" ,
"int f(int 0);" ,
"int f(int i);" ,
"int f(i);" },
},
// Question 3
{ "Qui pose des questions stupides",
{ "le prof. de math",
"mon copain/ma copine",
"le prof. de physique",
"moi",
"le prof. d'info",
"personne, il n'y a pas de question stupide",
"les sondages" } ,
}
};
}
La principale différence en C++98 est que la syntaxe d'initialisation n'est pas permise ni pour les vectors, ni en affectation pour les structs. Cela change pas mal la fonction creer_examen :
Examen creer_examen()
{
QCM q;
Examen retour;
q.reponses.clear();
q.reponses.push_back("32");
q.reponses.push_back("beaucoup");
q.reponses.push_back("24");
q.reponses.push_back("2");
q.solution=2;
retour.push_back(q);
q.question = "Laquelle des instructions suivantes est un prototype de fonction";
q.reponses.clear();
q.reponses.push_back("int f(0);");
q.reponses.push_back("int f(int 0);");
q.reponses.push_back("int f(int i);");
q.reponses.push_back("int f(i);");
q.solution=3;
retour.push_back(q);
q.question = "Qui pose des questions stupides";
q.reponses.clear();
q.reponses.push_back("le prof. de math");
q.reponses.push_back("mon copain/ma copine");
q.reponses.push_back("le prof. de physique");
q.reponses.push_back("moi");
q.reponses.push_back("le prof. d'info");
q.reponses.push_back("personne, il n'y a pas de question stupide");
q.reponses.push_back("les sondages");
q.solution=6;
retour.push_back(q);
return retour;
}
L'autre changement est que les boucle for(:) (range-based for) n'existent pas en C++98. Il faut les remplacer par des boucles «à la C» :
int main()
{
//...
for (unsigned int i(0); i < exam.size(); i++) {
if (poser_question(exam[i]) == exam[i].solution) {
++note;
}
}
//...
}
// ======================================================================
void affiche(const QCM& q)
{
cout << q.question << " ?" << endl;
for (unsigned int i(0); i < q.reponses.size(); ++i) {
cout << " " << i+1 << "- " << q.reponses[i] << endl;
}
}
// ...
Le code fourni ici est en C++11. Pour C++98, voir les remarques de l'exercice 1.
#include <iostream>
#include <cmath>
using namespace std;
// ----------------------------------------------------------------------
struct Complexe {
double x;
double y;
};
struct Solutions {
Complexe z1;
Complexe z2;
};
// ----------------------------------------------------------------------
void affiche(Complexe z);
Complexe addition (Complexe z1, Complexe z2);
Complexe soustraction (Complexe z1, Complexe z2);
Complexe multiplication(Complexe z1, Complexe z2);
Complexe division (Complexe z1, Complexe z2);
Complexe sqrt (Complexe z);
Solutions resoudre_second_degre(Complexe b, Complexe c);
// ======================================================================
int main()
{
Complexe b = { 3.0, -2.0 };
Complexe c = { -5.0, 1.0 };
Solutions s;
s = resoudre_second_degre(b, c);
cout << "Avec b="; affiche(b); cout << " et c="; affiche(c);
cout << " on a :" << endl;
cout << " z1="; affiche(s.z1); cout << endl;
cout << " z2="; affiche(s.z2); cout << endl;
return 0;
}
// ======================================================================
void affiche(Complexe z)
{
if ((z.x == 0.0) and (z.y == 0.0)) {
cout << "0";
return;
}
if (z.x != 0.0) {
cout << z.x;
if (z.y > 0.0)
cout << "+";
}
if (z.y != 0.0) {
if ((z.x == 0.0) and (z.y == -1.0))
cout << "-";
else if (z.y != 1.0)
cout << z.y;
cout << "i";
}
}
// ======================================================================
Complexe addition(Complexe z1, Complexe z2)
{
return { z1.x + z2.x, z1.y + z2.y };
}
// ======================================================================
Complexe soustraction(Complexe z1, Complexe z2)
{
return { z1.x - z2.x, z1.y - z2.y };
}
// ======================================================================
Complexe multiplication(Complexe z1, Complexe z2)
{
return { z1.x * z2.x - z1.y * z2.y ,
z1.x * z2.y + z1.y * z2.x };
}
// ======================================================================
Complexe division(Complexe z1, Complexe z2)
{
const double r(z2.x*z2.x + z2.y*z2.y);
return { (z1.x * z2.x + z1.y * z2.y) / r ,
(z1.y * z2.x - z1.x * z2.y) / r };
}
// ======================================================================
Complexe sqrt(Complexe z)
{
const double r(sqrt(z.x * z.x + z.y * z.y));
Complexe retour;
retour.x = sqrt((r + z.x) / 2.0);
if (z.y >= 0.0)
retour.y = sqrt((r - z.x) / 2.0);
else
retour.y = - sqrt((r - z.x) / 2.0);
return retour;
}
// ======================================================================
Solutions resoudre_second_degre(Complexe b, Complexe c)
{
constexpr Complexe deux = { 2.0, 0.0 };
constexpr Complexe quatre = { 4.0, 0.0 };
const Complexe sdelta(sqrt(soustraction(multiplication(b, b),
multiplication(quatre, c))));
// calcule -b
b.x = -b.x; b.y = -b.y;
Solutions reponse;
reponse.z1 = division( soustraction(b, sdelta) , deux);
reponse.z2 = division( addition (b, sdelta) , deux);
return reponse;
}
#include <iostream>
#include <cmath>
using namespace std;
// ======================================================================
struct Fraction
{
int numerateur;
int denominateur;
};
// ======================================================================
// Calcul du plus grand diviseur commun
unsigned int pgcd(unsigned int a, unsigned int b)
{
unsigned int m(b);
if (a < b) {
m = a;
}
while ((a % m != 0) or (b % m != 0)) {
--m;
}
return m;
}
// ======================================================================
Fraction init_frac(int num, int den)
{
const int div( pgcd( abs(num) , abs(den) ) );
if (num < 0 and den < 0) {
num = -num;
den = -den;
}
return { num / div , den / div };
}
// ======================================================================
// Affichage d'une fraction
void afficher_frac(Fraction f)
{
cout << f.numerateur << "/" << f.denominateur;
}
// ======================================================================
// Addition de 2 fractions
Fraction add_frac(Fraction f1, Fraction f2)
{
// Note : la fonction init_frac rend la fraction irreductible
return init_frac(f1.numerateur * f2.denominateur + f2.numerateur * f1.denominateur,
f1.denominateur * f2.denominateur);
}
// ======================================================================
// Multiplication de 2 fractions
Fraction mult_frac(Fraction f1, Fraction f2)
{
return init_frac(f1.numerateur * f2.numerateur,
f1.denominateur * f2.denominateur);
}
// ======================================================================
// Multiplication d'une fractions par un nombre
Fraction mult_scal_frac(int scalaire, Fraction f)
{
return init_frac(f.numerateur * scalaire, f.denominateur);
}
// ======================================================================
int main()
{
Fraction f1 = init_frac(5, 2); // 5/2
Fraction f2 = init_frac(3, 12); // 3/12 --> 1/4
cout << "f1 = ";
afficher_frac(f1);
cout << " et f2 = ";
afficher_frac(f2);
cout << endl;
cout << "f1 + f2 = ";
afficher_frac(add_frac(f1, f2));
cout << endl;
cout << "f1 * f2 = ";
afficher_frac(mult_frac(f1, f2));
cout << endl;
cout << "2 * f2 = ";
afficher_frac(mult_scal_frac(2, f2));
cout << endl;
return 0;
}
*/
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#ifndef M_PI
# define M_PI 3.14159265358979323846
#endif
// --------------------------------------------------
struct Sinusoide {
double amplitude;
double frequence;
double dephasage;
};
// --------------------------------------------------
typedef vector<Sinusoide> Signal;
// --------------------------------------------------
struct Signal_Echant {
double t0; // temps initial
vector<double> echantillons;
};
// ======================================================================
// fonction outil : composante sinusoidale pure
double sin_pure(double x, Sinusoide const& s = { 1.0, 1.0, 0.0 })
{
return s.amplitude * sin(2 * M_PI * s.frequence * x + s.dephasage);
}
// ======================================================================
// fonction outil : signal = somme de sinus
double signal(double x, Signal const& s)
{
double val(0.0);
for (auto composante : s) {
val += sin_pure(x, composante);
}
return val;
}
// ======================================================================
Signal_Echant echantillonne(Signal const& s, double freq,
double t_min = 0.0, double t_max = 1.0)
{
Signal_Echant se;
se.fe = freq;
se.t0 = t_min;
se.echantillons = vector<double>(1+size_t(freq * (t_max - t_min)));
for (size_t i(0); i < se.echantillons.size(); ++i) {
se.echantillons[i] = signal(t_min + i / freq, s);
}
return se;
}
// ======================================================================
// fonction outil : sinus cardinal
double sinc(double x, double precision = 1e-8)
{
return (abs(x) < precision ? 1.0 : sin(M_PI * x)/(M_PI * x));
}
// ======================================================================
// formule de reconstruction
double reconstruction(double x, Signal_Echant const& s)
{
double valeur(0.0);
cout << endl << "\t+ fe = " << s.fe << endl << "\t+ t0=" << s.t0 << endl
<< "\t+ nb ech = " << s.echantillons.size() << endl;
for (size_t i(0); i < s.echantillons.size(); ++i) {
cout << "\t\t" << s.echantillons[i] << " * sinc(" << s.fe << " * (" << x << " - " << s.t0 <<") - "<<i<<" ) = " << s.echantillons[i] << " * " << sinc(s.fe * (x - s.t0) - i) << " = " << s.echantillons[i] * sinc(s.fe * (x - s.t0) - i) << endl;
valeur += s.echantillons[i] * sinc(s.fe * (x - s.t0) - i);
}
cout << "\t-> " << valeur << endl;
return valeur;
}
// ======================================================================
int main()
{
Signal s({
{ 0.5 , 4.0, 0.1 }, // ...
{ 0.33, 6.0, 0.2 }, // ...
{ 0.25, 8.0, 0.3 }, // ...
});
constexpr double t_min(0.0);
constexpr double t_max(2.0);
Signal_Echant se1(echantillonne(s, 20.0, t_min, t_max));
Signal_Echant se2(echantillonne(s, 11.0, t_min, t_max));
constexpr size_t nb_points(1000);
constexpr double dt((t_max-t_min) / nb_points);
for (double t(t_min); t <= t_max; t += dt) {
cout << t
<< " " << signal(t, s)
<< " " << reconstruction(t, se1)
<< " " << reconstruction(t, se2)
<< endl;
}
return 0;
}
/* ======================================================================
*
* Knapsack problem.
*
* Version: 1.0 (170901)
* Author: J.-C. Chappelier (EPFL, 2017)
*
* ======================================================================
*/
#include <iostream>
#include <vector>
#include <algorithm> // pour sort()
using namespace std;
struct Object {
double weight;
double value;
};
/* ======================================================================
* This is the first algorithm:
* solve it naively, in the given order.
*/
void solve_naive(vector<Object> const& objects, double remaining_weight)
{
double value(0.0);
for (auto const& object : objects) {
cout << "considering : w=" << object.weight << ", v=" << object.value;
if (object.weight <= remaining_weight) {
value += object.value;
remaining_weight -= object.weight;
cout << " --> taking";
}
cout << endl;
}
cout << "value = " << value << ", remaining weight = " << remaining_weight << endl;
}
// ======================================================================
bool higher_value(Object const& o1, Object const& o2)
{ return o1.value > o2.value; }
/* ======================================================================
* This is the second algorithm: greedy.
*/
void solve_greedy(vector<Object> const& objects, double maximum_weight)
{
vector<Object> sorted_objects(objects); // need a copy to sort
sort(sorted_objects.begin(), sorted_objects.end(), higher_value);
solve_naive(sorted_objects, maximum_weight);
}
/* ======================================================================
* This is the third algorithm: try all.
*/
double solve_exact_recursive(vector<Object> const& objects, size_t start, double& remaining_weight)
{
double best_value(0.0);
if ((not objects.empty()) and (start < objects.size())) {
// 1) consider NOT taking first object
double best_remaining_weight(remaining_weight);
best_value = solve_exact_recursive(objects, start+1, best_remaining_weight);
// 2) consider taking the first object, if possible
if (objects[start].weight <= remaining_weight) {
double weight(remaining_weight - objects[start].weight);
const double value(objects[start].value + solve_exact_recursive(objects, start+1, weight));
// 3) keep the best of the two
if (value > best_value) {
best_remaining_weight = weight;
best_value = value;
}
}
remaining_weight = best_remaining_weight;
}
return best_value;
}
void solve_exact(vector<Object> const& objects, double remaining_weight)
{
double value(solve_exact_recursive(objects, 0, remaining_weight));
cout << "value = " << value << ", remaining weight = " << remaining_weight << endl;
}
// ======================================================================
int main()
{
const vector<Object> objects({
{ 4.0, 8.0 },
{ 2.0, 3.0 },
{ 5.0, 7.0 },
{ 6.0, 10.0 },
});
constexpr double MAX(9.0);
solve_naive (objects, MAX);
solve_greedy(objects, MAX);
solve_exact (objects, MAX);
return 0;
}
#include <iostream>
#include <utility>
#include <vector>
#include <string>
using namespace std;
// ======================================================================
struct Mot_de_code {
string entree;
double proba;
string code;
};
// ======================================================================
typedef vector<Mot_de_code> Code;
* Il vaudrait mieux utiliser des hash-tables.
* la fin du 2e semestre).
*/
// ======================================================================
void affiche_code(Code const& c) {
for (auto el : c) {
cout << '"' << el.entree << "\" --> \"" << el.code << "\" (" << el.proba << ')' << endl;
}
}
/* ======================================================================
*/
void add(string const& mot, Code& code) {
// recherche le mot
for (auto& el : code) {
if (el.entree == mot) {
++el.proba;
return;
}
}
code.push_back({ mot, 1.0, "" });
}
// ======================================================================
void normalise(Code& code) {
double somme(0.0);
for (auto el : code) {
somme += el.proba;
}
if (somme > 0.0) {
for (auto& el : code) {
el.proba /= somme;
}
}
}
// ======================================================================
Code calcule_probas(string const& texte, size_t tranche = 1)
{
Code code;
for (size_t i(0); i < texte.size(); i += tranche) {
string mot(texte.substr(i, tranche));
while (mot.size() < tranche) mot += ' ';
add(mot, code);
}
normalise(code);
return code;
}
// ======================================================================
struct Entite {
vector<size_t> indices;
double proba;
};
// ======================================================================
Entite fusionne(Entite const& L1, Entite const& L2) {
Entite L;
L.proba = L1.proba + L2.proba;
size_t i(0);
size_t j(0);
while ((i < L1.indices.size()) and (j < L2.indices.size())) {
if (L1.indices[i] < L2.indices[j]) {
L.indices.push_back(L1.indices[i]);
++i;
} else {
L.indices.push_back(L2.indices[j]);
++j;
}
}
while (i < L1.indices.size()) {
L.indices.push_back(L1.indices[i]);
++i;
}
while (j < L2.indices.size()) {
L.indices.push_back(L2.indices[j]);
++j;
}
return L;
}
// ======================================================================
vector<Entite> listes_initiales(Code const& c) {
vector<Entite> v(c.size());
for (size_t i(0); i < c.size(); ++i) {
v[i].indices.push_back(i);
v[i].proba = c[i].proba;
}
return v;
}
// ======================================================================
void deux_moins_probables(vector<Entite> tab, size_t& prems, size_t& deuz)
{
if (tab.size() < 2) return;
double min1(tab[0].proba); prems = 0;
double min2(tab[1].proba); deuz = 1;
if (min1 > min2) {
swap(min1, min2);
swap(prems, deuz);
}
for (size_t i(2); i < tab.size(); ++i) {
if (tab[i].proba < min1) {
min2 = min1;
deuz = prems;
min1 = tab[i].proba;
prems = i;
} else if (tab[i].proba < min2) {
min2 = tab[i].proba;
deuz = i;
}
}
}
// ======================================================================
void ajoute_symbole(char bit, Code& c, Entite l)
{
for(auto i : l.indices) {
c[i].code = bit + c[i].code;
}
}
// ======================================================================
void Huffman(Code& c)
{
vector<Entite> arbre(listes_initiales(c));
while (arbre.size() > 1) {
size_t max_1(0), max_2(0);
// recherche les deux moins probables
deux_moins_probables(arbre, max_1, max_2);
ajoute_symbole('0', c, arbre[max_1]);
ajoute_symbole('1', c, arbre[max_2]);
arbre[max_1] = fusionne(arbre[max_1], arbre[max_2]);
arbre[max_2] = arbre.back();
arbre.pop_back();
}
}
// ======================================================================
string recherche_entree(string const& texte, size_t& pos, Code const& c)
{
for (auto el : c) {
size_t i(0), j(pos);
while ((i < el.entree.size()) and (j < texte.size()) and (el.entree[i] == texte[j])) {
++i; ++j;
}
if ((i == el.entree.size()) and (j <= texte.size())) { // match with el
pos = j; // update pos to point to the rest of texte
return el.code;
}
// special case for end of texte
if ((j == texte.size()) and (el.entree[i] == ' ')) {
while ((i < el.entree.size()) and (el.entree[i] == ' ')) ++i;
if (i == el.entree.size()) { // match with el (ending with whitespaces
pos = j;
return el.code;
}
}
}
return string();
}
// ======================================================================
string recherche_mot_de_code(string const& texte, size_t& pos, Code const& c)
{
for (auto el : c) {
size_t i(0), j(pos);
while ((i < el.code.size()) and (j < texte.size()) and (el.code[i] == texte[j])) {
++i; ++j;
}
if ((i == el.code.size()) and (j <= texte.size())) { // match with el
pos = j; // update pos to point to the rest of texte
return el.entree;
}
}
return string();
}
// ======================================================================
string encode(string const& texte, Code const& c)
{
string code;
) {
code += recherche_entree(texte, i, c);
}
return code;
}
// ======================================================================
string decode(string const& texte_code, Code const& c)
{
string texte;
) {
texte += recherche_mot_de_code(texte_code, i, c);
}
return texte;
}
// ======================================================================
void test(string const& texte, size_t tranche)
{
cout << "==== Par tranches de taille " << tranche << endl;
Code c(calcule_probas(texte, tranche));
//affiche_code(c);
Huffman(c);
affiche_code(c);
string tc(encode(texte, c));
cout << "taille orig. = " << texte.size() << " lettres/octets" << endl;
cout << "taille codee = " << tc.size() << " bits = " << 1 + (tc.size() - 1) / 8 << " octets" << endl;
cout << "long. moyenne = " << double(tc.size()) / double(texte.size()) << " bits" << endl;
cout << "compression = " << 100.0 - 100.0 * tc.size() / (8.0 * texte.size()) << '%' << endl;
cout << "check : " << decode(tc, c) << endl;
}
// ======================================================================
int main()
{
test(texte, 1);
test(texte, 2);
test(texte, 3);
test(texte, 5);
cin >> texte;
test(texte, 1);
return 0;
}
#include <iostream>
#include <string>
#include <vector>
#include <array>
using namespace std;
// ----------------------------------------------------------------------
// STRUCTURES DE DONNEES
// ----------------------------------------------------------------------
typedef string Bande;
constexpr char EPSILON('e');
typedef int Tete;
constexpr Tete POSITION_INITIALE(0);
typedef unsigned int Etat;
constexpr Etat UNDEF(0);
constexpr Etat ETAT_INITIAL(1);
struct Transition
{
Etat etat ;
char caractere ;
int deplacement ;
};
typedef array<Transition, 3> Ligne; // [ 0 , 1 , epsilon ]
typedef vector<Ligne> TableTransition;
struct TMachine {
Etat actuel;
Bande ruban ;
Tete tete ;
TableTransition table;
};
// ----------------------------------------------------------------------
// PROTOYPES
// ----------------------------------------------------------------------
* la valeur transmise en argument */
void initialise(Bande& b, const string& valeur) {b=valeur;}
TMachine cree(const string& entree = "");
void reinitialise(TMachine& m, const string& entree);
void lance(TMachine& m);
void lance(TMachine&& m) { lance(m); }
void affiche(const TMachine& m);
// ----------------------------------------------------------------------
int main()
{
lance(cree("1101"));
return 0;
}
/* ====================================================================== *
* ====================================================================== */
void gestion_bornes(Bande& b, Tete& t)
{
while (t < 0) {
b = EPSILON + b;
avance(t);
}
while (t >= b.size()) { // ici t >= 0 : comparaison OK
b += EPSILON;
}
}
/* ====================================================================== *
* ====================================================================== */
char lecture(Bande& b, Tete& t)
{
gestion_bornes(b, t);
return b[t];
}
/* ====================================================================== *
* ====================================================================== */
void ecriture(char c, Bande& b, Tete& t)
{
gestion_bornes(b, t);
b[t] = c;
}
/* ====================================================================== *
* initialise la machine. *
* ====================================================================== */
TMachine cree(const string& entree)
{
TMachine m;
m.table = {
{{ { 1, '0', 1}, { 1, '1', 1}, { 2, EPSILON, -1} }},
{{ { 3, EPSILON, -1}, { 4, EPSILON, -1}, {UNDEF, EPSILON, -1} }},
{{ { 3, EPSILON, -1}, { 3, EPSILON, -1}, { 5, '1', 1} }},
{{ { 4, EPSILON, -1}, { 4, EPSILON, -1}, { 5, '0', 1} }},
{{ {UNDEF, EPSILON, -1}, {UNDEF, EPSILON, -1}, {UNDEF, EPSILON, -1} }}
/*
{ { 1, '0', 1}, { 1, '1', 1}, { 2, EPSILON, -1} },
{ { 3, EPSILON, -1}, { 4, EPSILON, -1}, {UNDEF, EPSILON, -1} },
{ { 3, EPSILON, -1}, { 3, EPSILON, -1}, { 5, '1', 1} },
{ { 4, EPSILON, -1}, { 4, EPSILON, -1}, { 5, '0', 1} },
{ {UNDEF, EPSILON, -1}, {UNDEF, EPSILON, -1}, {UNDEF, EPSILON, -1} }
*/
/*
// table pour l'inversion de bits
{ { 2, '0', 1}, { 3, '1', 1}, {UNDEF, EPSILON, 1} },
{ { 2, '0', 1}, { 3, '1', 1}, { 4, EPSILON, 1} },
{ { 2, '0', 1}, { 3, '1', 1}, { 5, EPSILON, 1} },
{ { 4, '0', 1}, { 4, '1', 1}, { 6, '0', -1} },
{ { 5, '0', 1}, { 5, '1', 1}, { 6, '1', -1} },
{ { 6, '0', -1}, { 6, '1', -1}, { 7, EPSILON, -1} },
{ { 8, EPSILON, -1}, { 8, EPSILON, -1}, { 7, EPSILON, -1} },
{ { 10, '0', 1}, { 11, '1', 1}, { 9, EPSILON, 1} },
{ {UNDEF, '0', -1}, {UNDEF, '1', -1}, { 9, EPSILON, 1} },
{ { 4, '0', 1}, { 4, '1', 1}, { 10, EPSILON, 1} },
{ { 5, '0', 1}, { 5, '1', 1}, { 11, EPSILON, 1} }
*/
};
reinitialise(m, entree);
return m;
}
/* ====================================================================== *
* ====================================================================== */
void reinitialise(TMachine& m, const string& entree)
{
m.actuel = ETAT_INITIAL;
initialise(m.ruban, entree);
m.tete = POSITION_INITIALE;
}
/* ====================================================================== *
* Lance l'execution d'une machine de Turing *
* ====================================================================== */
void lance(TMachine& m)
{
cout << "Lancement de la machine de Turing" << endl;
affiche(m);
while (m.actuel != UNDEF) {
// indice de ligne
int i(m.actuel-1);
cout << " lu : " << lecture(m.ruban, m.tete) << ",";
int j;
switch (lecture(m.ruban, m.tete)) {
case '0': j = 0; break;
case '1': j = 1; break;
case EPSILON: j = 2; break;
default:
<< lecture(m.ruban, m.tete) << endl;
affiche(m);
return;
};
m.actuel = m.table[i][j].etat;
ecriture(m.table[i][j].caractere, m.ruban, m.tete);
switch(m.table[i][j].deplacement) {
case 1: avance(m.tete); cout << " avance" << endl; break;
case -1: recule(m.tete); cout << " recule" << endl; break;
default:
<< m.table[i][j].deplacement << endl;
affiche(m);
return;
}
affiche(m);
}
}
/* ====================================================================== *
* ====================================================================== */
void affiche(const TMachine& m)
{
cout << " --------------------------------" << endl;
cout << " Etat actuel : " << m.actuel << endl;
cout << " Bande :" << endl;
cout << " " << m.ruban << endl;
cout << " ";
for (Tete i(-1); i < m.tete; ++i) cout << ' ';
cout << "^ (Tete : " << m.tete << ')' << endl;
cout << " --------------------------------" << endl;
}