[Pascal] Rekurencja wyszukująca sumy

s0ull
Użytkownik
Użytkownik
Posty: 110
Rejestracja: 13 lis 2010, o 12:50
Płeć: Mężczyzna
Lokalizacja: Jasło
Podziękował: 50 razy

[Pascal] Rekurencja wyszukująca sumy

Post autor: s0ull »

Witam serdecznie,

Mam kilka zadanek z rekurencji do rozwiązania i z jednym z nich mam problem. Prosiłbym o pomoc:
Mamy daną liczbę całkowitą. W tablicy jednowymiarowej należy znaleźć n liczb, których suma jest równa danej liczbie. Proszę napisać funkcję Nka, która otrzymując jako parametry: tablicę array[1..X] of integer, n (ilość liczb stanowiących sumę), oraz sumę sprawdza, ile można w niej znaleźć "enek".
Generalnie coś tam zacząłem tworzyć, ale mam problem jak sprawdzać, czy dana liczba ma w ogóle szansę należeć do tej sumy, oraz jak szukać kolejnych sum, aby były różne niż wcześniejsze. Prosiłbym o jakiekolwiek wskazówki.

Z góry dzięki.
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[Pascal] Rekurencja wyszukująca sumy

Post autor: adambak »

jeszcze się pozastanawiam nad tym, bo znalezienie wszystkich tych "enek" nie wydaje się takie oczywiste.. póki co:
... wiczenia_2
zadania: 4 i 11.. może jakoś Ci pomogą/natchną..-- 2 gru 2011, o 18:23 --jednak to jest proste.. zapomniałem, że rekurencja i chciałem jakoś liniowo.. robisz funkcję rekurencyjną, która przechodzi przez całą tablicę i wywołuje się dwa razy: raz dodając do sumy w swoim wywołaniu daną liczbę w tablicy, a raz nie.. i do następnego wywołania przekazuje jeden indeks dalej w tablicy.. w ten sposób sprawdzamy wszystkie podciągi w tablicy, więc napewno niczego nie pominiemy.. jeśli w danym wywołaniu rekurencyjnym suma wynosi tyle ile szukana to zwiększamy licznik "enek" (niech to będzie dla ułatwienia zmienna globalna) a rekurencję ucinamy(również w przypadku gdy suma przekroczy szukaną).. spróbuj sam, a jak nie będie wychodziło to pomogę.. zacznij od napisania tej rekurencji przechodzącej tablicę i dla danego indeksu wywołującą się dwa razy (no bo każdy element albo dodajemy do rozpatrywanego ciągu, czy się sumuje jak chcemy albo nie) ..
s0ull
Użytkownik
Użytkownik
Posty: 110
Rejestracja: 13 lis 2010, o 12:50
Płeć: Mężczyzna
Lokalizacja: Jasło
Podziękował: 50 razy

[Pascal] Rekurencja wyszukująca sumy

Post autor: s0ull »

Dzięki wielkie za pomoc, ale kurcze hmm.. chyba nie bardzo ogarniam o co biega z dwoma wywołaniami. Mam coś takiego:

Kod: Zaznacz cały

function szukacz(var t:array[1..x] of integer, n,s,p:integer):integer;

var suma,l,i:integer;

begin

 if (n=1) or (suma>=s) then begin
  if suma=s then inc(l);
 
 end else begin

  for i:=p to x do begin
   suma:=suma+tab[i];
   szukacz(t,n-1,s,i+1);
  end;

 end;

szukacz:=l;

end;
I nie bardzo wiem, gdzie to drugie wywołanie wrzucić
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[Pascal] Rekurencja wyszukująca sumy

Post autor: adambak »

ok, no to ja to widzę tak:

Kod: Zaznacz cały

program TEST;

const X=8;
type TAB=array[1..X] of integer;

var ilosc,i,szukana,n:integer;
    A:TAB;

procedure szukacz(var t:TAB; j,s,liczb:integer);
begin
  if (s=szukana) and (liczb=n) then ilosc:=ilosc+1
  else if (s<szukana) and (j<=X) then begin
    szukacz(t,j+1,s+t[j],liczb+1);
    szukacz(t,j+1,s,liczb);
  end;
end;

begin
  ilosc:=0;
  readln(szukana,n);
  for i:=1 to X do readln(A[i]);
  szukacz(A,1,0,0);
  writeln(ilosc);
end.
program przegląda wszystkie możliwe podciągi w tablicy A szukając takich o długości n które sumują się do szukana.. czy o to chodziło? bo mogłem coś źle zrozumieć.. liczbę X (rozmiar tablicy A) dobrałem przykładowo, żeby sprawdzić czy działa.. odpal program dla np takiego testu:

Kod: Zaznacz cały

8 3
1
2
3
4
5
6
7
8
odpowiedzią powinno być: \(\displaystyle{ 2}\) (ponieważ liczbę \(\displaystyle{ 8}\) możemy przedstawić jako sumę podciągu o długości \(\displaystyle{ 3}\) w tablicy A tylko na dwa sposoby, tzn \(\displaystyle{ 1+2+5=8 \text{ lub } 1+3+4=8}\))

choć zazwyczaj każą uważać na zienne globalne, tutaj uznałem, że będzie przejrzyście jeśli zmienne: ilość, szukana, n będą globalne (łatwy dostęp w kazdym wywołaniu funkcji).. oczywiście zmienne: s, j, liczb są lokalne dla każdego rekurencyjnego wywołania funkcji (z oczywistych względów.. j to zwykły iterator po tablicy, s to aktualna suma podciągu w danym wywołaniu funkcji, a liczb informuje nas ile jest liczb w danym analizowanym podciągu)..

jeśli masz jakieś pytania, bądź coś zrobiłem nie tak jak chcieli to wal.. jeśli tak miało być to oczywiście trochę będzie trzeba kosmetyki (X dać jako większą stałą itp)..
s0ull
Użytkownik
Użytkownik
Posty: 110
Rejestracja: 13 lis 2010, o 12:50
Płeć: Mężczyzna
Lokalizacja: Jasło
Podziękował: 50 razy

[Pascal] Rekurencja wyszukująca sumy

Post autor: s0ull »

Super, wielkie dzięki!
Xitami

[Pascal] Rekurencja wyszukująca sumy

Post autor: Xitami »

Kod: Zaznacz cały

type iptr = ^integer;
const MAX = 200;
 
function Nka(tab: iptr; x, n, szukana:integer):cardinal;
var     r:array[0..MAX] of integer;
        sum:integer;
        liczba:cardinal;
 
        procedure pajechali(d: integer);
        var i:integer;
        begin
                if n=d then begin
                        if sum = szukana then
                                inc(liczba);
                end else 
                        for i:= r[d]+1 to x do begin
                                sum := sum - tab[r[d+1]] + tab[i];
                                r[d+1]:=i;
                                pajechali(d+1)
                        end
        end;
        
begin
        tab^:=0; sum:=0; liczba:=0; r[0]:=0; 
        pajechali(0);
        Nka:= liczba;
end;
 
var
        tab:array[0..MAX] of integer;
        x, szukana, n: integer;
        i:integer;
begin
        //readln(x, n, szukana);
        x:=49; n:=6; szukana:=152;
        for i:=1 to x do
                tab[i]:=i;
                //read(tab[i]);
        writeln(Nka(addr(tab), x, n, szukana));
end.

0,34 sekundy na znalezienie 165490 zakładów (wśród wszystkich możliwych) lotto (49 po 6) dających sumę 152.
Wersja Adam potrzebowała więcej niż 5 sekund (nie wiem ile - limit ideone)
Przy okazji przekazywanie tablicy w stylu C
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[Pascal] Rekurencja wyszukująca sumy

Post autor: adambak »

Xitami, mógłbyś w skrócie opisać jak działa Twój algo? wystarczy w skrócie, bo mam nadzieję, że reszty się domyślę(trochę go nie rozumiem, a jeszcze wskaźników nie miałem w Pascalu, więc jakoś tak ciężko idzie zrozumienie)..
Xitami

[Pascal] Rekurencja wyszukująca sumy

Post autor: Xitami »

"wskaźnikowość" należy rozumieć dokładnie tak jak w C
addr() zamiast & i tyle

generowanie kombinacji to:

Kod: Zaznacz cały

        procedure pajechali(d: integer);
        var i:integer;
        begin
                if n=d then begin
                        r[1..x] to kolejna kombinacja (x po n) elem. 1..x 
                        tą tablicą indeksujemy tablicę właściwą 
                end else 
                        for i:= r[d]+1 to x do begin
                                r[d+1]:=i;
                                pajechali(d+1)
                        end
        end;
miałem to w notatkach, pewnie kiedyś to rozumiałem
ODPOWIEDZ