5. DOMAČA NALOGA (23.03. - 30.03.) --- 20 točk

Naslov:  Poglej-in-povej, ena-stop in polinomi
Vrednost naloge: 20 točk

Ta domača naloga je sestavljena iz 3 manjših, neodvisnih nalog. Možnih je 20 točk; pogoj za 10 in več točk je, da se oddana izvorna datoteka prevede in zažene, kot je napisano v navodilih. Če se niti ne prevede, je možnih največ 5 točk.

Vse metode implementirajte v razredu DN05 z metodo public static void main(String[] args), ki bo omogočala testiranje vseh ostalih metod.

Prvi argument programa je številka naloge, ostali argumenti so vhodni podatki.

1. Zaporedje poglej-in-povej

Zaporedje poglej-in-povej, npr. 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ... , je zaporedje, kjer naslednjika generiramo tako, da preberemo njegovega predhodnika, pri čemer štejemo pojavitve istih števk v posamezni skupini istih števk.

Primer:

  • 1 preberemo kot "ena 1" in zapišemo kot 11.
  • 11 preberemo kot "dve 1" in zapišemo kot 21.
  • 21 preberemo kot "ena 2, ena 1" in zapišemo kot 1211.
  • 1211 preberemo kot "ena 1, ena 2, dve 1" in zapišemo kot 111221.
  • 111221 preberemo kot "tri 1, dve 2, ena 1" in zapišemo kot 312211.
a) Napišite metodo public static String pip_next(String s), ki vrne naslednji člen od trenutnega člena $s$ tega zaporedja.
    Npr., pip_next("312211") vrne:

13112221
b) Napišite metodo public static String pip(String s, int n), ki izpiše $n$ členov zaporedja poglej-in-povej z začetnim členom $s$.

Testni primeri (v modrem je podan primer klica programa, v sivem okvirju pa ustrezen izhod):

1.1) java DN05 1a 1234

11121314

1.2) java DN05 1a 1113213211

31131211131221

1.3) java DN05 1b 1 10

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
1.4) java DN05 1b 7 15

7
17
1117
3117
132117
1113122117
311311222117
13211321322117
1113122113121113222117
31131122211311123113322117
132113213221133112132123222117
11131221131211132221232112111312111213322117
31131122211311123113321112131221123113111231121123222117
1321132132211331121321231231121113112221121321133112132112211213322117
11131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222117

2. Zaporedje ena-stop
Zaporedje ena-stop se vedno konča z 1. Tvorimo ga s funkcijo \[f(n)=\left\{ \begin{array}{ll} n/2; & n \text{ je sodo} \\ 3n+1; & n \text{ je liho} \end{array} \right.\]
Naslednji člen zaporedja dobimo tako, da za argument funkcije $f$ vzamemo prejšnji rezultat.

Primer:

Vzemimo, da je začetni člen zaporedja $n=12$. Ker je $n$ sodo, ga delimo z 2 in dobimo 6. Ker je 6 sodo, ga spet delimo z 2 in dobimo 3; 3 je liho, zato ga množimo s 3 in prištejemo 1, kar nam da 10. 10 je sodo, zato ga delimo z 2 in dobimo 5... Postopek ponavljamo, dokler ne pridemo do 1. V tem primeru bi dobili zaporedje 12, 6, 3, 10, 5, 16, 8, 4, 2, 1. Dolžina tega zaporedja je 10.

a) Napišite metodo public static int stop1(int n), ki izračuna dolžino zaporedja $f(n)$.

b) Napišite metodo public static int stop1_2n(double n), ki izračuna dolžino zaporedja $f(n)$, pri čemer je $n$ potenca števila 2. Vhodno število je lahko zelo veliko, zato je predstavljeno s tipomdouble, čeprav gre vedno za celo število. Časovno učinkovitejše rešitve bodo boljše ocenjene.

Testni primeri (v modrem je podan primer klica programa, v sivem okvirju pa ustrezen izhod):

2.1) java DN05 2a 12

10

2.2) java DN05 2a 2000000

154

2.3) java DN05 2b 256

9
2.4) java DN05 2b 1180591620717411303424.0

71

3. Polinomske matrike

Polinomska matrika je $n \times m$ razsežna matrika, katere vrstice vsebujejo koeficiente polinomov.

Primer:

Matrika

2.1   3    1
5.3  -7   2
3   1  -5.2

predstavlja polinome:

$2.1x^2+3x+1$
$5.3x^2-7x+2$
$3x^2+x-5.2$

Napiši metodo public static void vsota(int n, int m, int max, int seed), ki
- napolni matriko z naključnimi realnimi števili tipa float z intervala $[-max, max)$. Pri tem naj bo seme generatorja enako seed.
  Prirejanje vrednosti naj se izvaja po vrsticah, od prve do zadnje, od leve proti desni.

- izpiše matriko na standardni izhod v istem vrstnem redu, kot so bili elementi generirani. Za izpis elementa uporabite format "%6.2f".
  Zadnjo vrstico matrike zaključite tako, da se pomaknete v novo vrstico.

- izračuna vsoto vseh polinomov v matriki in jo izpiše. Format izpisa za koeficient naj bo "%2.1f", ostali del formata dodajte tako, da bo izpis enak izpisu v spodnjih testnih primerih.

Testni primeri (v modrem je podan primer klica programa, v sivem okvirju pa ustrezen izhod):

3.1) java DN05 3 4 5 10 1

  4.62 -7.99 -1.80 -1.85 -5.85
-9.28 -3.35  3.18  9.36  4.21
-9.88 -6.95  9.27 -6.81  8.80
  1.08  8.94  8.22  8.74 -0.26
S(x) = -13.5x^4-9.3x^3+18.9x^2+9.4x+6.9

3.2) java DN05 3 4 2 1 10

  0.46 -0.11
-0.48 -0.17
-0.88 0.34
-0.51 -0.26
S(x) = -1.4x-0.2

3.3) java DN05 3 1 8 10 3

  4.62  1.25 -8.58  6.11 -8.66  1.64  5.36  1.50
S(x) = 4.6x^7+1.2x^6-8.6x^5+6.1x^4-8.7x^3+1.6x^2+5.4x+1.5

Pred oddajo programa na eUčilnci preverite pravilnost delovanja.