BitCell

by **sharky92** » 23 Dec 2010, 12:19

De cateva zile am inceput sa fac probleme de pe infoarena.ro , si m-am "impotmolit" un pic la problema combinarilor de N luate cate K. Prima sursa am facut-o eu si am primit 0 puncte pe ea, apoi de curiozitate am copiat problema combinarilor din manualul de clasa 10, modificand cateva date pentru a corespunde cerintelor celor de pe infoarena.ro si am trimis-o spre evaluare. Din cele 10 teste facute, in 9 a dat raspunsuri gresite si intr-un test a depasit timpul limita.
Imi poate spune cineva ce nu e bine la sursa mea :

Line number On/Off | Expand/Contract | Select all

Program combinari;
Type vector=array[1..25] of integer;
var St:vector; n,k:integer;  Fo,FI:text;
 
procedure initializare;           {initializam stiva cu 0}
var i:integer;
begin
For i:=1 to  25 do St[i]:=0;
end;
 
 
 
 
Procedure Tipar (p:integer);                            {tiparim o solutie valida}
var j:integer;
begin
    for j:=1 to p do
        write(FO,St[j]:4,' ');
        writeln(FO);
end;
 
Function Valid(p:integer):boolean;                                 {verificam dac o solutie este valida sau nu }
var i:integer;
begin
    if (P>1) and (St[p]<=St[p-1]) then valid:=false
                                  else valid:=true;
end;
 
Procedure bktr(p:integer);                                               {procedura recursiva pentru combinari}
var pval:integer;
begin
    for pval:=1 to n do
        begin
        St[p]:=pval;
            if valid(p) then
                if p=k then
                Tipar(P)
                else
                bktr(p+1);
        end;
end;
 
Begin
initializare;
Assign(FI,'combinari.in'); reset(FI);
Assign(FO,'combinari.out'); rewrite(FO);
readln(FI,N,K);                                                                {citim N si K din fisierul text}
close(FI);
Bktr(1);
close(FO);
end.

Mentionez ca ambele surse le-am compilat pe calculatorul meu si functioneaza foarte bine. Va multumesc.

by **DarkByte** » 23 Dec 2010, 12:29

Sincer, e prea dimineata (si prea la inceput de concediu) pentru mine ca sa ma apuc de verificat back-tracking ...

Fa niste teste si vezi ce si cum.

Singura chestie care-mi sare in ochi la o prima privire e "afisarea" ta. Tu afisezi fiecare element din solutie pe patru pozitii, incearca sa lasi doar un spatiu intre elemente (stiu, n-ar trebui sa comenteze evaluatorul din cauza asta, but who knows).

by **sharky92** » 23 Dec 2010, 21:22

Multumesc , am reusit sa rezolv problema .

by **smith** » 23 Dec 2010, 21:37

Pot să văd și eu rezolvarea cu enunțul? Poate mai sunt curioși

by **sharky92** » 23 Dec 2010, 23:11

Enunt : Sa se genereze toate combinarile de N luate cate K in ordine lexicografica.
Rezolvare :

Line number On/Off | Expand/Contract | Select all

Program combinari;
var s:array[0..20] of longint;
    n,k:longint;
 
procedure back(l:longint);
var i:longint;
begin
if (l=k) then
       begin
        for i:=1 to k do
                write(s[i],' ');
        writeln;
        end
else
      begin
       for i:=s[l]+1 to n do
               begin
               s[l+1]:=i;
               back(l+1);
               end;
        end;
end;
 
begin
assign(input,'C:\Documents and Settings\Roland\Desktop\sums\in.txt');reset(input);
assign(output,'C:\Documents and Settings\Roland\Desktop\sums\out.txt');rewrite(output);
readln(n,k);
back(0);
close(input);close(output);
end.

by **andreiandreiq** » 23 Dec 2010, 23:57

@sharky92: Nu cumva ai uitat sa pui " input,output:text; " ? :-?

by **sharky92** » 24 Dec 2010, 00:20

Nu...input si output sunt default in Pascal....cand afisezi cu write pe ecran, scrii intr-un fisier, denumit, standard, output , deci daca redirectezi output catre un fisier, scrii in fisier direct.

BitCell

Problema combinari

Problema combinari

Re: Problema combinari

Re: Problema combinari

Re: Problema combinari

Re: Problema combinari

Re: Problema combinari

Re: Problema combinari

Who is online