PolinomL

diff --git a/kodovi/polinomi/PolinomL.java b/kodovi/polinomi/PolinomL.java
new file mode 100644 (file)
index 0000000..eb1bb5c
--- /dev/null
+++ b/kodovi/polinomi/PolinomL.java
@@ -0,0 +1,349 @@
+/**\r
+ * Polinom predstavljen listom monoma od kojih je svaki predstavljen svojim\r
+ * koeficijentom (tipa double) i stepenom (tipa int).\r
+ * \r
+ * U listi su monomi poredjani od najviseg do najnizeg stepena i svi monomi su\r
+ * razlicitog stepena. Monomi kojima je koeficijent jednak nula se ne cuvaju u\r
+ * listi.\r
+ *\r
+ * Pomocni materijal za SPA1, DMI, PMF, UNS\r
+ * v1.0.1\r
+ */\r
+public class PolinomL {\r
+       \r
+       /**\r
+        * Predstavlja jedan monom, odnosno njegov koeficijent i stepen, u listi\r
+        * monoma u polinomu.\r
+        */\r
+       class Monom {\r
+               double k;\r
+               int st;\r
+               Monom veza;\r
+\r
+               public Monom(double k, int st) {\r
+                       this.k = k;\r
+                       this.st = st;\r
+                       this.veza = null;\r
+               }\r
+\r
+               public Monom() {\r
+                       this(1.0, 0);\r
+               }\r
+\r
+               public String toString() {\r
+                       String res = "";\r
+                       if (st != 0) {\r
+                               if (Math.abs(k) != 1.0) {\r
+                                       res += k;\r
+                               } else if (k == -1.0) {\r
+                                       res += '-';\r
+                               }\r
+                               res += 'x';\r
+                               if (st != 1) {\r
+                                       res += "^" + st;\r
+                               }\r
+                       } else {\r
+                               res += k;\r
+                       }\r
+                       return res;\r
+               }\r
+       }\r
+\r
+       /** pokazivac na prvi monom u listi monoma */\r
+       Monom prvi = null;\r
+\r
+       public String toString() {\r
+               String res = "";\r
+               if (prvi == null)\r
+                       res += 0.0;\r
+               else {\r
+                       res += prvi;\r
+                       Monom pom = prvi.veza;\r
+                       while (pom != null) {\r
+                               if (pom.k > 0)\r
+                                       res += "+" + pom;\r
+                               else\r
+                                       res += pom;\r
+                               pom = pom.veza;\r
+                       }\r
+               }\r
+               return res;\r
+       }\r
+       \r
+       /** Vraca nezavisnu kopiju tekuceg polinoma. */\r
+       public PolinomL kopija() {\r
+               PolinomL kopija = new PolinomL();\r
+               if (prvi != null) {\r
+                       kopija.prvi = new Monom();\r
+                       kopija.prvi.st = prvi.st;\r
+                       kopija.prvi.k = prvi.k;\r
+                       kopija.prvi.veza = null;\r
+                       Monom pomocni = prvi.veza;\r
+                       Monom tekuci = kopija.prvi;\r
+                       while (pomocni != null) {\r
+                               tekuci.veza = new Monom(pomocni.k, pomocni.st);\r
+                               pomocni = pomocni.veza;\r
+                               tekuci = tekuci.veza;\r
+                       }\r
+               } else\r
+                       kopija.prvi = null;\r
+               return kopija;\r
+       }\r
+       \r
+       /** Ubacuje kopiju monoma mon u tekuci polinom. */\r
+       public void ubaciMonom(Monom mon) {\r
+               if (mon != null) {\r
+                       if (prvi == null) {\r
+                               prvi = new Monom(mon.k, mon.st);\r
+                       } else {\r
+\r
+                               Monom tekuci = prvi;\r
+                               Monom stari = null;\r
+\r
+                               while (tekuci != null && tekuci.st > mon.st) {\r
+                                       stari = tekuci;\r
+                                       tekuci = tekuci.veza;\r
+                               }\r
+\r
+                               if (tekuci != null && mon.st == tekuci.st) {\r
+                                       tekuci.k = mon.k + tekuci.k;\r
+                                       if (tekuci.k == 0.0) {\r
+                                               if (prvi == tekuci)\r
+                                                       prvi = tekuci.veza;\r
+                                               else\r
+                                                       stari.veza = tekuci.veza;\r
+                                       }\r
+                               } else {\r
+                                       Monom kopija = new Monom(mon.k, mon.st);\r
+                                       kopija.veza = tekuci;\r
+\r
+                                       if (tekuci == prvi) {\r
+                                               prvi = kopija;\r
+                                       } else {\r
+                                               stari.veza = kopija;\r
+                                       }\r
+                               }\r
+                       }\r
+               }\r
+       }\r
+       \r
+       /** Postavlja clan monoma na dati koeficijent, pri cemu se po potrebi menja postojeci monom, \r
+        * kreira novi monom ili brise monom. */\r
+       public void postaviClan(double k, int st) {\r
+               Monom cilj, prethodni;\r
+               cilj = prvi;\r
+               prethodni = null;\r
+               while (cilj != null && cilj.st > st) {\r
+                       prethodni = cilj;\r
+                       cilj = cilj.veza;\r
+               }\r
+               /* da li upisujemo vrednost ili sklanjamo clan */\r
+               if (k != 0.0) {\r
+                       /* da li menjamo clan ili pravimo novi */\r
+                       if (cilj != null && cilj.st == st) {\r
+                               cilj.k = k;\r
+                       } else {\r
+                               cilj = new Monom();\r
+                               cilj.k = k;\r
+                               cilj.st = st;\r
+                               cilj.veza = null;\r
+                               if (prethodni == null) {\r
+                                       /* ili je prazan polinom, ili dodajemo na pocetak */\r
+                                       cilj.veza = prvi;\r
+                                       prvi = cilj;\r
+                               } else {\r
+                                       cilj.veza = prethodni.veza;\r
+                                       prethodni.veza = cilj;\r
+                               }\r
+                       }\r
+               } else {\r
+                       /* da li postoji ovakav clan - brisemo ga */\r
+                       if (cilj != null && cilj.st == st) {\r
+                               if (prvi == cilj)\r
+                                       prvi = prvi.veza;\r
+                               else {\r
+                                       prethodni.veza = prethodni.veza.veza;\r
+                               }\r
+                       }\r
+               }\r
+       }\r
+       \r
+       /** Vraca koeficijent uz monom zadat stepenom. */\r
+       public double koeficijentUz(int st) {\r
+               if (prvi != null) {\r
+                       Monom tekuci = prvi;\r
+                       while (tekuci != null && tekuci.st > st) {\r
+                               tekuci = tekuci.veza;\r
+                       }\r
+                       if (tekuci != null && tekuci.st == st) {\r
+                               return tekuci.k;\r
+                       } else\r
+                               return 0.0;\r
+               } else\r
+                       return 0.0;\r
+       }\r
+       \r
+       /** Vraca stepen polinoma. */\r
+       public int maksimalniStepen() {\r
+               if (prvi != null)\r
+                       return prvi.st;\r
+               else\r
+                       return 0;\r
+       }\r
+       \r
+       /** Trazi od korisnika da unese novi polinom koji ce biti ubacen u tekuci. */\r
+       public void unos() {\r
+               int n;\r
+               try {\r
+                       do {\r
+                               System.out.print("Unesite broj monoma n (n>=0) ");\r
+                               n = Svetovid.in.readInt();\r
+                       } while (n < 0);\r
+                       for (int i = 1; i <= n; i++) {\r
+                               Monom novi = new Monom();\r
+                               do {\r
+                                       System.out.print("Unesite koeficijent monoma br. " + i + ": ");\r
+                                       novi.k = Svetovid.in.readDouble();\r
+                               } while (novi.k == 0);\r
+                               do {\r
+                                       System.out.print("Unesite eksponent monoma br. " + i + ": ");\r
+                                       novi.st = Svetovid.in.readInt();\r
+                               } while (novi.st < 0);\r
+                               ubaciMonom(novi);\r
+                       }\r
+               } catch (Exception e) {\r
+                       e.printStackTrace();\r
+               }\r
+       }\r
+       \r
+       /** Vraca novi polinom koji je jednak zbiru polinoma p2 i ovog polinoma. */\r
+       public PolinomL saberi(PolinomL p2) {\r
+               PolinomL zbir = kopija();\r
+               if (p2 != null) {\r
+                       Monom pom = p2.prvi;\r
+                       while (pom != null) {\r
+                               zbir.ubaciMonom(pom);\r
+                               pom = pom.veza;\r
+                       }\r
+               }\r
+               return zbir;\r
+       }\r
+       \r
+       /** Dodaje polinom p na tekuci polinom. */\r
+       public void saberiNa(PolinomL p) {\r
+               if (p != null) {\r
+                       Monom pom = p.prvi;\r
+                       while (pom != null) {\r
+                               ubaciMonom(pom);\r
+                               pom = pom.veza;\r
+                       }\r
+               }\r
+       }\r
+       \r
+       /** Menja znak tekucem polinomu. */\r
+       public void promeniZnak() {\r
+               Monom pom = prvi;\r
+               while (pom != null) {\r
+                       pom.k = -pom.k;\r
+                       pom = pom.veza;\r
+               }\r
+       }\r
+       \r
+       /** Vraca novi polinom koji je jednak razlici izmedju tekuceg polinoma i p2.*/\r
+       public PolinomL oduzmi(PolinomL p2) {\r
+               if (p2 == null) {\r
+                       return this.kopija();\r
+               }\r
+\r
+               PolinomL razlika = p2.kopija();\r
+               razlika.promeniZnak();\r
+               Monom pom = prvi;\r
+               while (pom != null) {\r
+                       razlika.ubaciMonom(pom);\r
+                       pom = pom.veza;\r
+               }\r
+               return razlika;\r
+       }\r
+       \r
+       /** Vraca novi polinom koji je jednak ovom polinomu pomonomenom sa monom mon. */\r
+       public PolinomL monomPuta(Monom mon) {\r
+               if (mon != null && prvi != null) {\r
+                       PolinomL mp = new PolinomL();\r
+                       mp.prvi = new Monom();\r
+                       mp.prvi.k = prvi.k * mon.k;\r
+                       mp.prvi.st = prvi.st + mon.st;\r
+                       Monom pom = prvi.veza;\r
+                       Monom tekuci = mp.prvi;\r
+                       while (pom != null) {\r
+                               tekuci.veza = new Monom();\r
+                               tekuci.veza.k = pom.k * mon.k;\r
+                               tekuci.veza.st = pom.st + mon.st;\r
+                               pom = pom.veza;\r
+                               tekuci = tekuci.veza;\r
+                       }\r
+                       return mp;\r
+               }\r
+               return null;\r
+       }\r
+       \r
+       /** Vraca novi polinom koji je jednak proizvodu tekuceg polinoma sa p2. */\r
+       public PolinomL puta(PolinomL p2) {\r
+               if (p2 != null && prvi != null) {\r
+                       PolinomL pr = monomPuta(p2.prvi);\r
+                       Monom pom = p2.prvi.veza;\r
+                       while (pom != null) {\r
+                               PolinomL pomocni = monomPuta(pom);\r
+                               Monom pomocniMon = pomocni.prvi;\r
+                               do {\r
+                                       pr.ubaciMonom(pomocniMon);\r
+                                       pomocniMon = pomocniMon.veza;\r
+                               } while (pomocniMon != null);\r
+                               pom = pom.veza;\r
+                       }\r
+                       return pr;\r
+               } else\r
+                       return null;\r
+       }\r
+       \r
+       /**\r
+        * Vraca niz dva polinoma od koji prvi predstavlja kolicnik, a drugi ostatak pri deljenju\r
+        * tekuceg polinom sa prosledjenim polinomom `delilac`. \r
+        */\r
+       public PolinomL[] kolicnik(PolinomL delilac) {\r
+               if (delilac != null) {\r
+                       PolinomL ostatak = this.kopija();\r
+                       PolinomL kolicnik = new PolinomL();\r
+\r
+                       while (ostatak.prvi != null && ostatak.prvi.st >= delilac.prvi.st) {\r
+                               Monom novi = new Monom();\r
+                               novi.k = -ostatak.prvi.k / delilac.prvi.k;\r
+                               novi.st = ostatak.prvi.st - delilac.prvi.st;\r
+                               PolinomL pomocni = delilac.monomPuta(novi);\r
+                               ostatak.saberiNa(pomocni);\r
+                               novi.k = -novi.k;\r
+                               kolicnik.ubaciMonom(novi);\r
+                       }\r
+\r
+                       PolinomL[] rez = { kolicnik, ostatak };\r
+                       return rez;\r
+               }\r
+               return null;\r
+       }\r
+       \r
+       /** Vraca novi polinom koji je jedank tekucem polinomu podignutom na stepen n. */\r
+       public PolinomL polinomNaN(int n) {\r
+               PolinomL rez;\r
+               if (n == 0) {\r
+                       rez = new PolinomL();\r
+                       rez.prvi = new Monom(1.0, 0);\r
+               } else {\r
+                       rez = this.kopija();\r
+                       for (int i = 2; i <= n; i++) {\r
+                               PolinomL pret = rez;\r
+                               rez = puta(pret);\r
+                       }\r
+               }\r
+               return rez;\r
+       }\r
+\r
+}\r