| 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"; } // Solution plus complexe mais plus élégante 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; } } cout << "Vous avez trouvé " << note << " bonne"; if (note > 1) cout << 's'; cout << " réponse"; 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) { /* échange les arguments s'ils n'ont pas été donnés dans * * 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 { "Combien de dents possède un éléphant adulte", { "32", "de 6 à 10", "beaucoup", "24", "2" }, 2 // réponse }, // 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);" }, 3 // réponse }, // 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" } , 6 // réponse } }; }
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.question = "Combien de dents possède un éléphant adulte"; q.reponses.clear(); q.reponses.push_back("32"); q.reponses.push_back("de 6 à 10"); 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; // ====================================================================== // la structure de données 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; } // ====================================================================== // Initialisation d'une fraction, sous sa forme irréductible 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; }
/* Programme pour tester le th. d'échantillonnage */ #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 fe; // fréquence d'échantillonnage 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; } // ====================================================================== // échantillonnage d'un signal 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({ { 1.0 , 2.0, 0.0 }, // première composante { 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)); // « dessin » des trois courbes 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; /* Note : les vector ne sont pas la bonne structure de données pour faire * cela (associer une info à un mot en entrée) car la recherche y * est linéraire. * Il vaudrait mieux utiliser des hash-tables. * Mais celles-ci n'ont pas encore été présentées en cours (arrivent à * la fin du 2e semestre). */ // ====================================================================== void affiche_code(Code const& c) { for (auto el : c) { cout << '"' << el.entree << "\" --> \"" << el.code << "\" (" << el.proba << ')' << endl; } } /* ====================================================================== * ajoute un mot au code ou incrémente son compte si déjà présent. */ void add(string const& mot, Code& code) { // recherche le mot for (auto& el : code) { if (el.entree == mot) { // le mot y est déjà : on incrémente son compte et on quitte ++el.proba; return; } } // On n'a pas trouvé le mot => on l'ajoute (avec un compte de 1) 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)); // remplir d'espaces à la fin si nécessaire while (mot.size() < tranche) mot += ' '; add(mot, code); } // normalise les probabilités 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 respectivement 0 et 1 à leur code ajoute_symbole('0', c, arbre[max_1]); ajoute_symbole('1', c, arbre[max_2]); // les fusionne (en écrasant max_1) arbre[max_1] = fusionne(arbre[max_1], arbre[max_2]); // et réduit l'arbre (= « monte » dans l'arbre) en supprimant 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; for (size_t i(0); i < texte.size(); // c'est recherche() qui va mettre i à jour ) { code += recherche_entree(texte, i, c); } return code; } // ====================================================================== string decode(string const& texte_code, Code const& c) { string texte; for (size_t i(0); i < texte_code.size(); // c'est recherche() qui va mettre i à jour ) { 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 << "texte codé : " << tc << endl; cout << "check : " << decode(tc, c) << endl; } // ====================================================================== int main() { string texte = "Un petit texte à compresser : le but de cet exercice est de réaliser des codes de Huffman de textes. Le principe du code de Huffman (binaire) est assez simple : il consiste à regrouper les deux mots les moins probables à chaque étape."; test(texte, 1); test(texte, 2); test(texte, 3); test(texte, 5); cout << "Entrez une chaîne : "; 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 // ---------------------------------------------------------------------- char lecture(Bande& b, Tete& t); // lit le caractère 'courant' void ecriture(char c, Bande& b, Tete& t); /* remplace le caractère courant par * la valeur transmise en argument */ void avance(Tete& t) {++t;} // déplace la tête de lecture vers la droite void recule(Tete& t) {--t;} // déplace la tête de lecture vers la gauche 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; } /* ====================================================================== * * Simule l'aspect infini négatif en ajoutant un caractère en debut de * * chaîne puis en décalant la valeur de la tête (càd la remettre à 0). * * Entrée : la bande et la tête de lecture/écriture * * ====================================================================== */ void gestion_bornes(Bande& b, Tete& t) { // simulation du ruban pour les positions négatives while (t < 0) { b = EPSILON + b; avance(t); } // insertion des EPSILON nécessaires pour les position positives while (t >= b.size()) { // ici t >= 0 : comparaison OK b += EPSILON; } } /* ====================================================================== * * Lit le caractère courant sur une bande doublement infinie. * * Entrée : la bande à lire et la tête de lecture/écriture * * Sortie : le caractère lu * * ====================================================================== */ char lecture(Bande& b, Tete& t) { // gère les bornes de la bande pour assurer l'existence de la case lue gestion_bornes(b, t); // lecture du caractère return b[t]; } /* ====================================================================== * * Écriture d'un caractère sur une bande doublement infinie : * * remplace le caractère courant par la valeur transmise en argument. * * Entrée : le caractère à écrire, la bande et la tête de lecture/écriture* * ====================================================================== */ void ecriture(char c, Bande& b, Tete& t) { // gère les bornes de la bande pour assurer l'existence de la case écrite gestion_bornes(b, t); // écriture du caractère b[t] = c; } /* ====================================================================== * * Crée une machine de Turing : charge sa table de transition et * * initialise la machine. * * ====================================================================== */ TMachine cree(const string& entree) { TMachine m; m.table = { // table pour le calcul de parité (g++-4.6) {{ { 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 le calcul de parité (normalement) { { 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; } /* ====================================================================== * * Réinitialise une machine et écrit les données d'entrée sur la bande. * * Entrée : la machine à initialiser et les données d'entrée * * ====================================================================== */ 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 * * Entrée : la machine à simuler * * ====================================================================== */ void lance(TMachine& m) { cout << "Lancement de la machine de Turing" << endl; affiche(m); while (m.actuel != UNDEF) { // Cherche la position à lire dans la table de transition // indice de ligne int i(m.actuel-1); // indice de colonne (caractère lu) 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: cout << "ERREUR: j'ai lu un caractère inconnu: " << lecture(m.ruban, m.tete) << endl; affiche(m); return; }; // mise à jour de la machine m.actuel = m.table[i][j].etat; cout << " nouvel état : " << m.actuel << ","; ecriture(m.table[i][j].caractere, m.ruban, m.tete); cout << " écrit : " << m.table[i][j].caractere << ","; 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: cout << "ERREUR: déplacement inconnu: " << m.table[i][j].deplacement << endl; affiche(m); return; } affiche(m); } cout << "Arrêt de la machine de Turing." << endl; } /* ====================================================================== * * Affiche l'état d'une machine de Turing * * Entrée : la machine à afficher * * ====================================================================== */ 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; }