Izpitno vprašanje RAČ2PRA 17600

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka PetraUdir.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje

Dane so dimenzije celoštevilskih matrik a, b, c, ... in pravilen izraz (((((de)f)a)b)c), ki določa vrstni red množenj teh matrik. Sestavi algoritem, ki izračuna število množenj.

Odgovor

Najprej napišemo razred Matrika, ki vsebuje informacije o dimenzijah in imenu matrik, ter razred SeznamMatrik, ki nam pomaga pri shrambi ustvarjenih matrik s pomočjo strukture Hashtable.
Metoda steviloMnozenj sprejme seznam matrik in izraz, v katerem bi radi prešteli število množenj. Predpostavimo, da je izraz napisan pravilno in da so oklepaji postavljeni tako, da je vrstni red množenja matrik enolično določen. Matrike moramo vnaprej definirati, ime matrike pa so male črke, torej spremenljivke tipa char.
Ustvarimo pomožni sklad matrik in se sprehodimo čez cel niz. Če naletimo na znak mala črka, ga vstavimo v naš pomožni sklad, v primeru, da naletimo na zaklepaj, pa iz sklada vzamemo zadnji dve matriki, preštejemo množenja ter jih prištejemo k skupnemu številu množenj. To število množenj je število, ki ga na koncu vrnemo.

  1. public class Matrika{
  2. int vrstice, stolpci;
  3. char ime;
  4. // konstruktor, ki ustvari novo matriko glede na dane parametre
  5. public Matrika(int vr, int st, char ime){
  6. this.ime = ime;
  7. this.vrstice = vr;
  8. this.stolpci = st;
  9. }
  10. }

  1. // Hashtable je struktura implementirana tako, da se do željenih objektov dostopa s pomočjo ključa.
  2. import java.util.Hashtable;
  3. public class SeznamMatrik{
  4. // objekti bodo matrike, ključi prek katerih bomo iskali pa znaki oz. imena matrik
  5. Hashtable<Character, Matrika> seznamMatrik;
  6. public SeznamMatrik(){
  7. seznamMatrik = new Hashtable<Character, Matrika>();
  8. }
  9. public void vstaviMatrike(Matrika[] m){
  10. for(int i=0; i<m.length; i++){
  11. // preverimo, da matrika s tem imenom še ni v seznamu
  12. if(!seznamMatrik.containsKey(m[i].ime)){
  13. //dodamo v hashtable pare ključ (ime matrike) / objekt (matrika)
  14. seznamMatrik.put(m[i].ime, m[i]);
  15. }
  16. }
  17. }
  18. // vrne iskano matriko iz seznama
  19. public Matrika vrniMatriko(char ime) throws Exception{
  20. // preverimo ali seznamMatrik vsebuje matriko z imenom ime
  21. if(seznamMatrik.containsKey(ime)){
  22. // vrnemo matriko s tem imenom
  23. return seznamMatrik.get(ime);
  24. }
  25. // če matrike s tem imenom ni v seznamu, se vrže izjema
  26. throw new Exception("Matrike z imenom " + ime + " ni v seznamu.");
  27. }
  28. }

Metoda, ki prešteje število množenj v danem izrazu.

  1. public static int steviloMnozenj(SeznamMatrik sez, String niz) throws Exception{
  2. // ustvarimo sklad objektov tipa matrika
  3. Sklad<Matrika> skladMatrik = new Sklad<Matrika>();
  4. int stMnozenj = 0;
  5. // pregledamo cel niz
  6. for(int i = 0; i < niz.length(); i++) {
  7. char znak = niz.charAt(i);
  8. if(znak == ')') {
  9. // iz sklada vzamemo dve matriki
  10. Matrika druga = skladMatrik.vrh();
  11. skladMatrik.odstrani();
  12. Matrika prva = skladMatrik.vrh();
  13. skladMatrik.odstrani();
  14. // izračunamo št. množenj za ti dve matriki
  15. stMnozenj = stMnozenj + (prva.stolpci*druga.stolpci*prva.vrstice);
  16. // naredimo novo matriko ustreznih dimenzij
  17. Matrika nova = new Matrika(prva.vrstice,druga.stolpci,'x');
  18. // vstavimo jo nazaj v sklad
  19. skladMatrik.vstavi(nova);
  20. }
  21. else if((znak >= 'a') && (znak <= 'z')) {
  22. // matriko poiščemo v seznamu matrik
  23. Matrika katera = sez.vrniMatriko(znak);
  24. // damo jo v skladMatrik
  25. skladMatrik.vstavi(katera);
  26. }
  27. }
  28. return stMnozenj;
  29. }

Testni program:

  1. public static void main(String[] argc) throws Exception{
  2. int[] vrstice = {7,5,3};
  3. int[] stolpci = {5,3,3};
  4. char[] ime = {'a', 'b', 'c'};
  5.  
  6. // ustvarimo tabelo matrik
  7. Matrika[] m = new Matrika[vrstice.length];
  8.  
  9. for(int i=0; i<vrstice.length; i++) {
  10. m[i] = new Matrika(vrstice[i], stolpci[i], ime[i]);
  11. }
  12. SeznamMatrik sez = new SeznamMatrik();
  13. sez.vstaviMatrike(m);
  14.  
  15. System.out.println("Stevilo potrebnih množenj za izraz \"((ab)c)\": "+ steviloMnozenj(sez, "((ab)c)"));
  16. System.out.println("Stevilo potrebnih množenj za izraz \"(a(bc))\": "+ steviloMnozenj(sez, "(a(bc))"));
  17. }

Izpiše:

 > java Vpr_17600
Stevilo potrebnih množenj za izraz "((ab)c)": 168
Stevilo potrebnih množenj za izraz "(a(bc))": 150
Osebna orodja