Choisissez votre style :
colorisé,
impression
Correction 15
Révisions
Les solutions suivantes ne sont évidemment pas uniques. Si vous en trouvez de meilleures (ou si vous trouvez des erreurs), faites-le savoir ! Merci.
Par ailleurs, les solutions proposées correspondent à l'état de vos connaissances au moment où la série est abordée. D'autres solutions pourront être envisagées une fois de nouveaux concepts acquis.
#include <SFML/Graphics.hpp>
#include <iostream>
#include <cmath>
#include "Config.h"
void drawLine(sf::RenderTarget& target, double x1, double y1, double x2, double y2)
{
sf::VertexArray heading(sf::PrimitiveType::Lines, 2);
heading[0] = { sf::Vector2f(x1, y1), sf::Color::White};
heading[1] = { sf::Vector2f(x2, y2), sf::Color::White };
target.draw(heading);
}
void ligne_brisee(sf::RenderTarget& target, double x1, double y1, double x2, double y2)
{
double e = 2.0 * sqrt(3.0);
double
x1p = (2.0 * x1 + x2) / 3.0,
y1p = (2.0 * y1 + y2) / 3.0,
x2p = (x1 + x2) / 2.0 + (y2 - y1) / e,
y2p = (y1 + y2) / 2.0 + (x1 - x2) / e,
x3p = (x1 + 2.0 * x2) / 3.0,
y3p = (y1 + 2.0 * y2) / 3.0;
drawLine(target, x1, y1, x1p, y1p);
drawLine(target, x1p, y1p, x2p, y2p);
drawLine(target, x2p, y2p, x3p, y3p);
drawLine(target, x3p, y3p, x2, y2);
}
int main()
{
sf::RenderWindow window(sf::VideoMode(WINDOW_WIDTH, WINDOW_HEIGHT), "Ligne brisee");
//Chargement fonte
sf::Font font;
if (!font.loadFromFile("res/arial.ttf")) return EXIT_FAILURE;
while (window.isOpen())
{
//Evénements
sf::Event event;
while (window.pollEvent(event))
{
if (event.type == sf::Event::Closed)
{
window.close();
}
}
//Dessin
window.clear(sf::Color(0,102,102));
ligne_brisee(window, OFFSET, WINDOW_HEIGHT/2, WINDOW_WIDTH/2, OFFSET);
window.display();
}
return EXIT_SUCCESS;
}
#include <SFML/Graphics.hpp>
#include <iostream>
#include <cmath>
#include "Config.h"
void drawLine(sf::RenderTarget& target, double x1, double y1, double x2, double y2)
{
sf::VertexArray heading(sf::PrimitiveType::Lines, 2);
heading[0] = { sf::Vector2f(x1, y1), sf::Color::White};
heading[1] = { sf::Vector2f(x2, y2), sf::Color::White };
target.draw(heading);
}
void ligne_brisee(sf::RenderTarget& target, double x1, double y1, double x2, double y2)
{
double e = 2.0 * sqrt(3.0);
double
x1p = (2.0 * x1 + x2) / 3.0,
y1p = (2.0 * y1 + y2) / 3.0,
x2p = (x1 + x2) / 2.0 + (y2 - y1) / e,
y2p = (y1 + y2) / 2.0 + (x1 - x2) / e,
x3p = (x1 + 2.0 * x2) / 3.0,
y3p = (y1 + 2.0 * y2) / 3.0;
drawLine(target, x1, y1, x1p, y1p);
drawLine(target, x1p, y1p, x2p, y2p);
drawLine(target, x2p, y2p, x3p, y3p);
drawLine(target, x3p, y3p, x2, y2);
}
void von_koch(sf::RenderTarget& target, int depth, double x1, double y1, double x2, double y2)
{
if(depth == 0)
{
ligne_brisee(target, x1, y1, x2, y2);
}
else
{
double e = 2.0 * sqrt(3.0);
double
x1p = (2.0 * x1 + x2) / 3.0,
y1p = (2.0 * y1 + y2) / 3.0,
x2p = (x1 + x2) / 2.0 + (y2 - y1) / e,
y2p = (y1 + y2) / 2.0 + (x1 - x2) / e,
x3p = (x1 + 2.0 * x2) / 3.0,
y3p = (y1 + 2.0 * y2) / 3.0;
von_koch(target, depth - 1, x1, y1, x1p, y1p);
von_koch(target, depth - 1, x1p, y1p, x2p, y2p);
von_koch(target, depth - 1, x2p, y2p, x3p, y3p);
von_koch(target, depth - 1, x3p, y3p, x2, y2);
}
}
int main()
{
sf::RenderWindow window(sf::VideoMode(WINDOW_WIDTH, WINDOW_HEIGHT), "Courbe de von Koch");
//Chargement fonte
sf::Font font;
if (!font.loadFromFile("res/arial.ttf")) return EXIT_FAILURE;
while (window.isOpen())
{
//Evénements
sf::Event event;
while (window.pollEvent(event))
{
if (event.type == sf::Event::Closed)
{
window.close();
}
}
//Dessin
window.clear(sf::Color(0,102,102));
// une courbe de von Koch unique:
//von_koch(window, DEPTH, OFFSET, WINDOW_HEIGHT, WINDOW_WIDTH, OFFSET);
// un ensemble de courbes reliées entre elles:
von_koch(window, DEPTH, OFFSET, WINDOW_HEIGHT/2, WINDOW_WIDTH/2, OFFSET);
von_koch(window, DEPTH, WINDOW_WIDTH/2, OFFSET, WINDOW_WIDTH - OFFSET, WINDOW_HEIGHT/2);
von_koch(window, DEPTH, WINDOW_WIDTH/2, WINDOW_HEIGHT-OFFSET, OFFSET, WINDOW_HEIGHT/2);
von_koch(window, DEPTH, WINDOW_WIDTH-OFFSET, WINDOW_HEIGHT/2, WINDOW_WIDTH/2, WINDOW_HEIGHT-OFFSET);
window.display();
}
return EXIT_SUCCESS;
}
Exercice 2
#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 semestre).
*/
// ======================================================================
void affiche_code(Code const& c) {
for (const 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 (const 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;
};
// Peut être utile pour le debug
void affiche_entite(const Entite& e){
for (auto val : e.indices)
std:: cout << val << " " << flush;
std::cout << e.proba << std::endl;
}
// Peut être utile pour le debug
void affiche_arbre(vector<Entite>& arbre){
for (const auto& entite : arbre){
affiche_entite(entite);
}
}
// ======================================================================
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> const& 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, const Entite& l)
{
for(const auto&i : l.indices) {
c[i].code = bit + c[i].code;
}
}
// ======================================================================
void Huffman(Code& c)
{
vector<Entite> arbre(listes_initiales(c));
int step(0);
while (arbre.size() > 1) {
size_t min_1(0), min_2(0);
// recherche les deux moins probables
deux_moins_probables(arbre, min_1, min_2);
// ajoute respectivement 0 et 1 à leur code
ajoute_symbole('0', c, arbre[min_1]);
ajoute_symbole('1', c, arbre[min_2]);
// les fusionne (en écrasant min_1)
arbre[min_1] = fusionne(arbre[min_1], arbre[min_2]);
// et réduit l'arbre (= « monte » dans l'arbre) en supprimant min_2
arbre[min_2] = arbre.back();
arbre.pop_back();
++step;
// Pour debugger (observer ce qui se passe étape par étape):
/*
std::cerr << "step " << step << std::endl;
affiche_arbre(arbre);
std::cerr << "---------------------" << std::endl;
affiche_code(c);
*/
}
}
// ======================================================================
string recherche_entree(string const& texte, size_t& pos, Code const& c)
{
for (const 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 (const 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); // pour le debug
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;
// lecture d'un seul mot
cout << "Entrez un mot : ";
cin >> texte;
test(texte, 1);
// lecture d'une phrase complète
cout << "Entrez une chaîne : " << flush;
// on purge le flot d'entrée de tous les séparateurs
// qui y sont restés
cin >> ws;
getline(cin, texte);
test(texte, 2);
// accents délibérément supprimé pour simplifier:
texte = "Un petit texte a compresser : le but de cet exercice est de realiser des codes de Huffman de textes. Le principe du code de Huffman (binaire) est assez simple : il consiste a regrouper les deux mots les moins probables a chaque etape.";
test(texte, 1);
test(texte, 2);
test(texte, 3);
test(texte, 5);
return 0;
}