Ispitni zadaci sa rešenjima

(vanredni novembarski rok 2000. iz Osnova programiranja - 3. tok - 25.11.2000.)

    Zadaci

  1. Sastaviti program koji ispisuje n! (faktorijel) za prvih 50 prirodnih brojeva tačno u svakoj cifri. (Napomena: 50! ima manje od 100 cifara).
  2. Pod anagramima se podrazumevaju reči sastavljene od istih slova. Na primer, reči trava, vatra i vrata su anagrami. Za dve reči x i y koje se sastoje od istih alfabetskih karaktera u ASCII-kodu kazaćemo da su u relaciji anagram.
    1. Pokazati da je relacija anagram jedna relacija ekvivalencije.
    2. Ako se kao kanonski predstavnik za klasu ekvivalencije izabere reč koja se sastoji od karaktera koji su poređani u rastućem poretku u odnosu na ASCII-kolacionu sekvenciju (na primer, za trava, vatra, kanonski predstavnik je aartv), sastaviti proceduru koja za zadatu reč efikasno pronalazi njenog kanonskog predstavnika.
    3. Data je tekstuelna datoteka. Sastaviti proceduru koja iz ove datoteke vadi sve različite reči dužine m koje se sastoje od alfabetskih karaktera. Različitih reči dužine m u datom tekstu nema više od 200.
    4. Sastaviti proceduru koja pronalazi sve anagrame dužine m koristeći se procedurama pod (2.2) i (2.3). Voditi opet računa o efikasnosti.
    5. Sastaviti program koji na osnovu prethodnih procedura ispisuje sve anagrame zadate dužine iz zadate ulazne datoteke tekst.txt.

    Rešenja ili njihove skice

  1. Opis postupka: Ograničenost intervala u kome su predstavljeni brojevi tipa integer ne omogućava da računamo sa velikim celim brojevima. Rešenje se, tada, traži tako što se broj n predstavi kao niz cifara nk, ... , n0 u sistemu sa osnovom b:

    n = nk * bk + ... + n1 * b1 + n0 * b0

    Tada je neophodno napisati programe koji izvršavaju pojedine aritmetičke operacije nad ovakvom reprezentacijom broja. Za osnovu se obično bira b = 10, ali je osnovni kriterijum da se aritmetičke operacije što lakše implementiraju.

    Veliki broj se predstavlja pomoću niza čiji su elementi cifre tog broja. Na taj način se problem izračunavanja velikog broja prevodi na rad sa malim brojevima (koji su u opsegu tipa integer.

    Rešenje: 

    program faktorijel;
const m = 100; mc = 100; max = 50;
var fakt: array[ 1 .. mc ] of integer; 
    n, d, prenos, i, p: integer; 

procedure ispis; 
var i, k:  integer; 
begin
    write(n : 3,"! = ", fakt[ d ] : 1 ); 
    for i := d +  1 to mc do 
    begin
       k := m; 
       while k > 1 do 
       begin 
          k := k div 10; 
          write( fakt[ i ] div k mod 10 : 1 ); 
       end 
    end; 
    writeln
end {ispis}; 

begin
    fakt[ mc ] := 1; d := mc; n := 0; 
    ispis;    
    for n := 1 to max do 
    begin
      prenos := 0; 
      for i := dm downto d do 
      begin
         p := fakt[ i ] * n + prenos;   
         f[ i ] := p mod m; 
         prenos := p div m;
      end
      if prenos > 0 then
        begin
           d := d - 1; 
           fakt[ d ] := prenos
        end;
        ispis; 
    end
end.

  2. Skica rešenja: Sugerirano rešenje potiče od Džona Bentlija (Bentley, John: Programming Pearls, Addison-Wesley, 1986; pp. 19 - 21). Originalno Bentlijevo rešenje, pod UNIX-om, koristi sledeči "pipeline" nad ulaznim tekstom:

    SIGN <tekst.txt | SORT | SQUASH >izlaz

    Funkcija SIGN odgovara koraku 2.2 u zadatku, a implementirana je kao funkcija u C-u koja koristi QUICKSORT:

     
    
    #define WORDMAX 101 
    main()
    {  char thisword[ WORDMAX ], sig[ WORDMAX ]; 
       while( scanf("%s", thisword ) != EOF ) {
           strcpy( sig, thisword ); 
           qsort( sig, strlen( sig ), 1, compchar ); 
           printf("%s %s\n", sig, thisword); 
        }
    }

    Ovaj program čita sa ulaza reč thisword, maksimalne dužine MAXWORD, i prepisuje je u nisku sig. Niska sig se sortira prema poretku definisanom funkcijom compchar (u zadatku 2. to je poredak indukovan ASCII-kolacionom sekvencijom). Rezultat sortiranja se prenosi na izlaz preko funkcije printf u obliku para (kanonski oblik reči, reč) (na primer, (aartv, vatra).

    Izlaz iz prethodnog koraka se u Bentlijevom rešenju prosleđuje u program za eksterno sortiranje SORT. U zadatku je ovaj korak pojednostavljen tako što se iz ulazne datoteke izdavaju samo reči određene dužine m kojih ima najviše 200. Umesto eksternog sortiranja dovoljno je koristiti strukturu niza (array).

    Funkcija SQUASH odgovara koraku 2.4: kako je rezultat prethodnog koraka niz dvodimenzionali niz sortiran po prvoj koloni (koja sadrži kanonske oblike), da bi se izdvojili anagrami dovoljno je porediti uzastopne elementa iz prve kolone. Ova operacija predstavlja jedan red koda u AWK-u:

     
    
     $1 != prev { prev = $1; if ( NR > 1 ) printf "\n" }
                { printf "%s", $2 }
                { printf "\n" }
     END

    Interpretirani na primeru 2. zadaaka, ovi redovi znače da se u matrici parova oblika (kanonski oblik reči, reč), poredi prvi element ($1) u tekućem redu sa prvim elementom prethodnog reda. Ako su ove niske jednake, onda je drugi element para ($2) anagram sa drugim elementom iz prethodnog reda i treba ga ispisati. Ako je pak $1 != prev, onda se vrši zamena vrednosti u promenljivoj prev.

    Na primer, ako je ulazna datoteka sadržavala tekst:

    vatra rada trava dana dara vrata nada...

    rezultati pojedinih koraka su sledeći:

    vatra             aartv vatra           aand nada
rada              aadr rada             aand dana   
trava             aartv trava           aard dara               dana nada
dana   --SIGN-->  aand dana   --SORT--> aard rada  --SQUASH-->  dara rada
dara              aard dara             aartv trava             trava vatra vrata
vrata             aartv vrata           aartv vatra
nada              aand nada             aartv vrata