Problème : du triangle

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