kodovi/polinomi/PolinomL.java

   1 /**
   2  * Polinom predstavljen listom monoma od kojih je svaki predstavljen svojim
   3  * koeficijentom (tipa double) i stepenom (tipa int).
   4  *
   5  * U listi su monomi poredjani od najviseg do najnizeg stepena i svi monomi su
   6  * razlicitog stepena. Monomi kojima je koeficijent jednak nula se ne cuvaju u
   7  * listi.
   8  *
   9  * Pomocni materijal za SPA1, DMI, PMF, UNS
  10  * v1.0.1
  11  */
  12 public class PolinomL {
  13
  14         /**
  15          * Predstavlja jedan monom, odnosno njegov koeficijent i stepen, u listi
  16          * monoma u polinomu.
  17          */
  18         class Monom {
  19                 double k;
  20                 int st;
  21                 Monom veza;
  22
  23                 public Monom(double k, int st) {
  24                         this.k = k;
  25                         this.st = st;
  26                         this.veza = null;
  27                 }
  28
  29                 public Monom() {
  30                         this(1.0, 0);
  31                 }
  32
  33                 public String toString() {
  34                         String res = "";
  35                         if (st != 0) {
  36                                 if (Math.abs(k) != 1.0) {
  37                                         res += k;
  38                                 } else if (k == -1.0) {
  39                                         res += '-';
  40                                 }
  41                                 res += 'x';
  42                                 if (st != 1) {
  43                                         res += "^" + st;
  44                                 }
  45                         } else {
  46                                 res += k;
  47                         }
  48                         return res;
  49                 }
  50         }
  51
  52         /** pokazivac na prvi monom u listi monoma */
  53         Monom prvi = null;
  54
  55         public String toString() {
  56                 String res = "";
  57                 if (prvi == null)
  58                         res += 0.0;
  59                 else {
  60                         res += prvi;
  61                         Monom pom = prvi.veza;
  62                         while (pom != null) {
  63                                 if (pom.k > 0)
  64                                         res += "+" + pom;
  65                                 else
  66                                         res += pom;
  67                                 pom = pom.veza;
  68                         }
  69                 }
  70                 return res;
  71         }
  72
  73         /** Vraca nezavisnu kopiju tekuceg polinoma. */
  74         public PolinomL kopija() {
  75                 PolinomL kopija = new PolinomL();
  76                 if (prvi != null) {
  77                         kopija.prvi = new Monom();
  78                         kopija.prvi.st = prvi.st;
  79                         kopija.prvi.k = prvi.k;
  80                         kopija.prvi.veza = null;
  81                         Monom pomocni = prvi.veza;
  82                         Monom tekuci = kopija.prvi;
  83                         while (pomocni != null) {
  84                                 tekuci.veza = new Monom(pomocni.k, pomocni.st);
  85                                 pomocni = pomocni.veza;
  86                                 tekuci = tekuci.veza;
  87                         }
  88                 } else
  89                         kopija.prvi = null;
  90                 return kopija;
  91         }
  92
  93         /** Ubacuje kopiju monoma mon u tekuci polinom. */
  94         public void ubaciMonom(Monom mon) {
  95                 if (mon != null) {
  96                         if (prvi == null) {
  97                                 prvi = new Monom(mon.k, mon.st);
  98                         } else {
  99
 100                                 Monom tekuci = prvi;
 101                                 Monom stari = null;
 102
 103                                 while (tekuci != null && tekuci.st > mon.st) {
 104                                         stari = tekuci;
 105                                         tekuci = tekuci.veza;
 106                                 }
 107
 108                                 if (tekuci != null && mon.st == tekuci.st) {
 109                                         tekuci.k = mon.k + tekuci.k;
 110                                         if (tekuci.k == 0.0) {
 111                                                 if (prvi == tekuci)
 112                                                         prvi = tekuci.veza;
 113                                                 else
 114                                                         stari.veza = tekuci.veza;
 115                                         }
 116                                 } else {
 117                                         Monom kopija = new Monom(mon.k, mon.st);
 118                                         kopija.veza = tekuci;
 119
 120                                         if (tekuci == prvi) {
 121                                                 prvi = kopija;
 122                                         } else {
 123                                                 stari.veza = kopija;
 124                                         }
 125                                 }
 126                         }
 127                 }
 128         }
 129
 130         /** Postavlja clan monoma na dati koeficijent, pri cemu se po potrebi menja postojeci monom,
 131          * kreira novi monom ili brise monom. */
 132         public void postaviClan(double k, int st) {
 133                 Monom cilj, prethodni;
 134                 cilj = prvi;
 135                 prethodni = null;
 136                 while (cilj != null && cilj.st > st) {
 137                         prethodni = cilj;
 138                         cilj = cilj.veza;
 139                 }
 140                 /* da li upisujemo vrednost ili sklanjamo clan */
 141                 if (k != 0.0) {
 142                         /* da li menjamo clan ili pravimo novi */
 143                         if (cilj != null && cilj.st == st) {
 144                                 cilj.k = k;
 145                         } else {
 146                                 cilj = new Monom();
 147                                 cilj.k = k;
 148                                 cilj.st = st;
 149                                 cilj.veza = null;
 150                                 if (prethodni == null) {
 151                                         /* ili je prazan polinom, ili dodajemo na pocetak */
 152                                         cilj.veza = prvi;
 153                                         prvi = cilj;
 154                                 } else {
 155                                         cilj.veza = prethodni.veza;
 156                                         prethodni.veza = cilj;
 157                                 }
 158                         }
 159                 } else {
 160                         /* da li postoji ovakav clan - brisemo ga */
 161                         if (cilj != null && cilj.st == st) {
 162                                 if (prvi == cilj)
 163                                         prvi = prvi.veza;
 164                                 else {
 165                                         prethodni.veza = prethodni.veza.veza;
 166                                 }
 167                         }
 168                 }
 169         }
 170
 171         /** Vraca koeficijent uz monom zadat stepenom. */
 172         public double koeficijentUz(int st) {
 173                 if (prvi != null) {
 174                         Monom tekuci = prvi;
 175                         while (tekuci != null && tekuci.st > st) {
 176                                 tekuci = tekuci.veza;
 177                         }
 178                         if (tekuci != null && tekuci.st == st) {
 179                                 return tekuci.k;
 180                         } else
 181                                 return 0.0;
 182                 } else
 183                         return 0.0;
 184         }
 185
 186         /** Vraca stepen polinoma. */
 187         public int maksimalniStepen() {
 188                 if (prvi != null)
 189                         return prvi.st;
 190                 else
 191                         return 0;
 192         }
 193
 194         /** Trazi od korisnika da unese novi polinom koji ce biti ubacen u tekuci. */
 195         public void unos() {
 196                 int n;
 197                 try {
 198                         do {
 199                                 System.out.print("Unesite broj monoma n (n>=0) ");
 200                                 n = Svetovid.in.readInt();
 201                         } while (n < 0);
 202                         for (int i = 1; i <= n; i++) {
 203                                 Monom novi = new Monom();
 204                                 do {
 205                                         System.out.print("Unesite koeficijent monoma br. " + i + ": ");
 206                                         novi.k = Svetovid.in.readDouble();
 207                                 } while (novi.k == 0);
 208                                 do {
 209                                         System.out.print("Unesite eksponent monoma br. " + i + ": ");
 210                                         novi.st = Svetovid.in.readInt();
 211                                 } while (novi.st < 0);
 212                                 ubaciMonom(novi);
 213                         }
 214                 } catch (Exception e) {
 215                         e.printStackTrace();
 216                 }
 217         }
 218
 219         /** Vraca novi polinom koji je jednak zbiru polinoma p2 i ovog polinoma. */
 220         public PolinomL saberi(PolinomL p2) {
 221                 PolinomL zbir = kopija();
 222                 if (p2 != null) {
 223                         Monom pom = p2.prvi;
 224                         while (pom != null) {
 225                                 zbir.ubaciMonom(pom);
 226                                 pom = pom.veza;
 227                         }
 228                 }
 229                 return zbir;
 230         }
 231
 232         /** Dodaje polinom p na tekuci polinom. */
 233         public void saberiNa(PolinomL p) {
 234                 if (p != null) {
 235                         Monom pom = p.prvi;
 236                         while (pom != null) {
 237                                 ubaciMonom(pom);
 238                                 pom = pom.veza;
 239                         }
 240                 }
 241         }
 242
 243         /** Menja znak tekucem polinomu. */
 244         public void promeniZnak() {
 245                 Monom pom = prvi;
 246                 while (pom != null) {
 247                         pom.k = -pom.k;
 248                         pom = pom.veza;
 249                 }
 250         }
 251
 252         /** Vraca novi polinom koji je jednak razlici izmedju tekuceg polinoma i p2.*/
 253         public PolinomL oduzmi(PolinomL p2) {
 254                 if (p2 == null) {
 255                         return this.kopija();
 256                 }
 257
 258                 PolinomL razlika = p2.kopija();
 259                 razlika.promeniZnak();
 260                 Monom pom = prvi;
 261                 while (pom != null) {
 262                         razlika.ubaciMonom(pom);
 263                         pom = pom.veza;
 264                 }
 265                 return razlika;
 266         }
 267
 268         /** Vraca novi polinom koji je jednak ovom polinomu pomonomenom sa monom mon. */
 269         public PolinomL monomPuta(Monom mon) {
 270                 if (mon != null && prvi != null) {
 271                         PolinomL mp = new PolinomL();
 272                         mp.prvi = new Monom();
 273                         mp.prvi.k = prvi.k * mon.k;
 274                         mp.prvi.st = prvi.st + mon.st;
 275                         Monom pom = prvi.veza;
 276                         Monom tekuci = mp.prvi;
 277                         while (pom != null) {
 278                                 tekuci.veza = new Monom();
 279                                 tekuci.veza.k = pom.k * mon.k;
 280                                 tekuci.veza.st = pom.st + mon.st;
 281                                 pom = pom.veza;
 282                                 tekuci = tekuci.veza;
 283                         }
 284                         return mp;
 285                 }
 286                 return null;
 287         }
 288
 289         /** Vraca novi polinom koji je jednak proizvodu tekuceg polinoma sa p2. */
 290         public PolinomL puta(PolinomL p2) {
 291                 if (p2 != null && prvi != null) {
 292                         PolinomL pr = monomPuta(p2.prvi);
 293                         Monom pom = p2.prvi.veza;
 294                         while (pom != null) {
 295                                 PolinomL pomocni = monomPuta(pom);
 296                                 Monom pomocniMon = pomocni.prvi;
 297                                 do {
 298                                         pr.ubaciMonom(pomocniMon);
 299                                         pomocniMon = pomocniMon.veza;
 300                                 } while (pomocniMon != null);
 301                                 pom = pom.veza;
 302                         }
 303                         return pr;
 304                 } else
 305                         return null;
 306         }
 307
 308         /**
 309          * Vraca niz dva polinoma od koji prvi predstavlja kolicnik, a drugi ostatak pri deljenju
 310          * tekuceg polinom sa prosledjenim polinomom `delilac`.
 311          */
 312         public PolinomL[] kolicnik(PolinomL delilac) {
 313                 if (delilac != null) {
 314                         PolinomL ostatak = this.kopija();
 315                         PolinomL kolicnik = new PolinomL();
 316
 317                         while (ostatak.prvi != null && ostatak.prvi.st >= delilac.prvi.st) {
 318                                 Monom novi = new Monom();
 319                                 novi.k = -ostatak.prvi.k / delilac.prvi.k;
 320                                 novi.st = ostatak.prvi.st - delilac.prvi.st;
 321                                 PolinomL pomocni = delilac.monomPuta(novi);
 322                                 ostatak.saberiNa(pomocni);
 323                                 novi.k = -novi.k;
 324                                 kolicnik.ubaciMonom(novi);
 325                         }
 326
 327                         PolinomL[] rez = { kolicnik, ostatak };
 328                         return rez;
 329                 }
 330                 return null;
 331         }
 332
 333         /** Vraca novi polinom koji je jedank tekucem polinomu podignutom na stepen n. */
 334         public PolinomL polinomNaN(int n) {
 335                 PolinomL rez;
 336                 if (n == 0) {
 337                         rez = new PolinomL();
 338                         rez.prvi = new Monom(1.0, 0);
 339                 } else {
 340                         rez = this.kopija();
 341                         for (int i = 2; i <= n; i++) {
 342                                 PolinomL pret = rez;
 343                                 rez = puta(pret);
 344                         }
 345                 }
 346                 return rez;
 347         }
 348
 349 }