Problème : du triangle

Traduit à partir d'une olympiade internationale d'informatique : IOI94

Code:

    7
  3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

La figure ci-dessus affiche un triangle de nombre. Ecrire un programme qui calcule la somme maximale de nombre en passant par un chemin qui commence du sommet et se termine à un emplacement quelconque de la base.

• Chaque étape peut se faire en bas en suivant diagonale gauche ou en diagonale droite.
  
• Le nombre de lignes dans le triangle est > 1 et <= 100.
  
• Les nombres dans le triangle sont compris entre 0 et 99.
  

Données Entrées
Les données à propos du nombre de lignes dans le triangle sont à lire depuis le fichier INPUT.TXT. Dans notre exemple, le fichier INPUT.TXT est comme suit :

Code:

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Données Sorties
La somme maximale est inscrite dans le fichier OUTPUT.TXT. Dans notre exemple : 30

Il est très intéressant ce problème.
Le langage recommandé est ... ?
La durée maximale est .... ?

Le langage est le langage de votre choix. Six problèmes de ce type sont à résoudre sur deux journées.

Est-ce que tu penses que c'est faisable en deux journée - temps libre?
Et quel est le niveau ciblé?

En effet les IOI (International Olympiads in Informatics) sont des compétitions pour les doués en Informatique.

Il y a à mon avis quelques difficultés:

1. la représentation des données dans la mémoire de l'ordinateur, ou ce qu'on appelle Les Structudes des Données.

2. selon cette structure de données, trouver le meilleur algorithme de recherche de la solution.

Il y a plusieurs structures de données possibles:
1. un arbre N-Aire: numéro <=> valuation de l'arc.
2. un graphe: numéro <=> valuation de l'arc.
3. un tableau: numéro <=> contenu d'une case

Il y a plusieurs algorithmes qu'on peut utiliser:
1. chemin le plus cours dans un arbre, graphe.
2. recherche du max dans un tableau (modifié)

c'est ma propre réflexion les amis. J'attends vos comments.

Je propose une solution :

Code:

program ioi94_01;

const MAX_COUNT = 100;
type tab = array [1..MAX_COUNT, 1..MAX_COUNT] of integer;

procedure saisie_entree(var n : integer ; var t : tab);
var i, j : integer;
begin
    repeat
        Write('Nombre d''éléments [2..100] : ');
        Readln(n);
    until (n > 1) and (n <= 100);
   
    for j:=1 to n do begin
        for i:=1 to j do begin
            repeat
                Write('0 <= t[', j, ', ', i, '] <= 99 : ');
                Read(t[j, i]);
            until (t[j, i] >= 0) and (t[j, i] <= 99);
        end;
    end;
end;

procedure afficher_tab(n : integer ; var t : tab);
var i, j : integer;
begin
    Writeln;
    for j:=1 to n do begin
        for i:=1 to j do begin
            Write(t[j, i]:3);
        end;
        Writeln;
    end;
end;

function Max(x, y : integer): integer;
begin
    if (x > y) then Max := x else Max := y;
end;

function MaxRS(n, row, col : integer ; var t : tab):integer;
begin
    if (row = n) then MaxRS := t[row, col]
    else MaxRS := t[row, col] + Max(MaxRS(n, row + 1, col, t), MaxRS(n, row + 1, col + 1, t));
end;

var
    n : integer;
    t : tab;
begin
    saisie_entree(n, t);
    afficher_tab(n, t);
    Writeln('Somme Maximale : ', MaxRS(n, 1, 1, t));
    readln;
end.

manianis:
Bravo pour la solution. Comme d'habitude

Quelques commentaires:

1. En voyant une matrice qui contient 100*100 = 10.000 entiers, c'est un peu désagréable, au niveau l'espace mémoire requis, surtout que la matrice est triangulaire et qu'au moins sa moitié ne va pas être utilisée. Suppose que MAX_COUNT = 1000n, alors ... ???!!!!

2. La fonction récursive MaxRS est agréable.

3. Ca serait plus difficile si la question était: trouver la somme maximale ainsi que le chemin engendrant cette somme.

Admin a écrit:manianis:
Bravo pour la solution. Comme d'habitude

merci, mais, il faut être franc j'ai jeté un coup d'oeil rapide sur les solutions proposées.

Admin a écrit:1. En voyant une matrice qui contient 100*100 = 10.000 entiers, c'est un peu désagréable, au niveau l'espace mémoire requis, surtout que la matrice est triangulaire et qu'au moins sa moitié ne va pas être utilisée. Suppose que MAX_COUNT = 1000n, alors ... ???!!!!

Le plus simple est d'utiliser une matrice. J'ai pensé à construire un graphe. Mais je me suis planté dès le premier stage. Il serait aimable qu'un membre nous donne une solution à l'aide de graphes.

Admin a écrit:2. La fonction récursive MaxRS est agréable.

La solution récursive est toujours, comme on le dit, est la plus intuitive et la plus simple.

Admin a écrit:3. Ca serait plus difficile si la question était: trouver la somme maximale ainsi que le chemin engendrant cette somme.

Là c'est une autre question car plusieurs chemins peuvent donner la somme maximale (cas d'un triangle formé par la même valeur) et n'oubliez pas qu'il s'agit d'une compétition avec trois exercices à résoudre pendant une journée (8 heures maximum).

Merci pour ces commentaires que je qualifie consructifs.

je pense que la solution de manianis est très acceptable pour une durée de 3 sujets dans 8 heures (olympiade internationale).

manianis: j'ai une remarque. stp, regardre l'exécution suivante:



c'est faux si j'ai bien compris l'énoncé !

le résultat = 113 !

Non ce n'est pas faux car :

Code:

    5
    0 0
  0 0 0
  0 0 0 99
99 9 9 0  0


vous aurez remarqué que en dessous du 99 t[4,4] il y'a deux case à zéro.

désolé donc. faute visuelle!

Autre remarque:
Pourquoi le VAR avant t dans la fonction récursive? le tableau ne va pas être modifié...

elle m'a beaucoup plu la fonction récursive !!!

Il ne faut pas oublier que la fonction est récursive càd les appels récursifs de cette fonctions sont stockés dans la pile qui risque vite de déborder si on y copie la tableau à chaque fois.
Le Var permet de faire un passage par variable (par référence si vous voulez) ainsi 8 octets seront transmis au programme au lieu des 100*100*2 octets taille du tableau en cas de passage par valeur.

1.
est-ce que ce que vous avez fait (passage par adresse) peut être considéré comme ASTUCE ou bien c'est courant dans les corrections?

2.
y-a-t-il un moyen pour visualiser le contenu de la pile (débogueur?)

The difference between Theory and Practice is that in theory there's no difference between theory and practice but in practice there's.

Le passage par référence est recommandé il ne s'agit pas d'une astuce mais d'une optimisation.

La vraie ASTUCE c'est ce que les enseignants d'informatiques disent aux élèves/étudiants : lorsque le contenu d'une variable change dans un module (procédure/fonction) et que ce changement est requis pour le bon déroulement du programme principal il faut alors procéder à un passage par variable. Il omettent de mentionner le cas que je viens d'évoquer pour simplifier au maximum.

Oui il existe un débogueur et je ne sais pas comment l'utiliser : il s'appelle gdb pour les programmes utilisant GCC. Un débogueur doit être capable de visualiser le contenu de la pile. Microsoft Visual Studio offre aussi un bon debugger.

Pour vous étonner plus que çà Java ne connais que le passage par valeur !!! Comment procéder dans ce cas.

J'ai bricolé une solution en utilisant les graphes... C'est trés difficile comme solution !!!

Code:


program ioi94_02;

type
    ptri_cell = ^tri_cell;
    tri_cell = record
        val : integer;
        s : ptri_cell;
        g : ptri_cell;
        d : ptri_cell;
    end;

procedure allocate_cell(var p : ptri_cell);
begin
    New(p);
    Read(p^.val);
    p^.s := nil;
    p^.g := nil; p^.d := nil;
end;

procedure triangle_allocate(var triangle : ptri_cell ; n : integer);
var
    ins_p, p, t, nline : ptri_cell;
    i : integer;
begin
    if triangle = nil then begin
        allocate_cell(p);
        triangle := p;
    end;
   
    ins_p := triangle;
    for i:=2 to n do begin
        t := ins_p;
        nline := ins_p;
       
        while (t <> nil) do begin
            allocate_cell(p);
           
            if (t = ins_p) then begin
                nline := p;
                t^.g := p;
                allocate_cell(p);
            end;
           
            t^.g^.s := p;
            t^.d := p;
            if (t^.s <> nil) then t^.s^.g := p;
           
            t := t^.s;
        end;
       
        ins_p := nline;
    end;
end;

procedure triangle_free(var triangle : ptri_cell);
var
    t, p : ptri_cell;
begin
    if (triangle <> nil) then begin
        triangle_free(triangle^.g);
       
        t := triangle;
        while (t <> nil) do begin
            p := t;
            t := t^.s;
            Dispose(p);
        end;
    end;
end;

procedure afficher_triangle(triangle : ptri_cell);
var
    start, t : ptri_cell;
begin
    start := triangle;
    while (start <> nil) do begin
        t := start;
        while (t <> nil) do begin
            Write(t^.val, ' ');
            t := t^.s;
        end;
        start := start^.g;
        Writeln;
    end;
end;

function Max(x, y : integer): integer;
begin
    if (x > y) then Max := x else Max := y;
end;

function MaxRS(triangle : ptri_cell):integer;
begin
    if (triangle = nil) then MaxRS := 0
    else MaxRS := triangle^.val + Max(MaxRS(triangle^.g), MaxRS(triangle^.d));
end;

var
    triangle : ptri_cell;
    n : integer;
begin
    triangle := nil;
    Readln(n);
    triangle_allocate(triangle, n);
    afficher_triangle(triangle);
    Writeln('Somme Maximale : ', MaxRS(triangle));
    triangle_free(triangle);
    Readln;
end

.

maestro manianis jai examiné ta solution longtemps. elle est vraiment parfaite. tu as bien soigné la désallocation de l'espace mémoire: réflexe souvent inexistant chez les programmeurs.

mon défi actuel c'est de faire un programme qui fonctionne meme si la dimension du triangllle est grandeee. je pense que la votre manianis fonctionne, mais, la récursivité gene un peu si la dimension est grande!

Il y'a un autre problème mon ami. Avec un triangle de 100 lignes mon programme c'est exécuté pendant 50mn sans trouver un résultat.

Avec n=0 : le programme teste une seule possiblité
Avec n=1 : le programme teste deux possibilités
Avec n=2 : le programme teste quatre possibilités
Avec n=3 : le programme teste huits possibilités
Avec n quelconque le programme teste 2^n possibilité càd pour n=100 il existe 2^100 possibilités
Sachant qu'avec n=30 mon ordinateur a trouvé le résultat en 5mn. avec n=100 le temps sera presque :
5/2^30*2^100=6*10^21 minutes !!!

5.90296E+21