Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
Postano: 4:05 ned, 20. 1. 2013 Naslov: |
|
|
Pa, uzastopno mnozenje s brojacem koji u svakom koraku raste za 1, daje faktorijele (s obzirom na realnu aritmetiku, priblizno tocne, ali za relativno veliki argument barem daje tocnije nego cjelobrojna aritmetika). Ne znam sto je tu upitno.
Pa, uzastopno mnozenje s brojacem koji u svakom koraku raste za 1, daje faktorijele (s obzirom na realnu aritmetiku, priblizno tocne, ali za relativno veliki argument barem daje tocnije nego cjelobrojna aritmetika). Ne znam sto je tu upitno.
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
|
|
[Vrh] |
|
mdoko Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12) Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
[Vrh] |
|
patakenjac Forumaš(ica)
Pridružen/a: 23. 10. 2011. (17:34:05) Postovi: (2F)16
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
|
[Vrh] |
|
patakenjac Forumaš(ica)
Pridružen/a: 23. 10. 2011. (17:34:05) Postovi: (2F)16
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
Postano: 3:46 uto, 29. 1. 2013 Naslov: |
|
|
Trenutno ne vidim moze li pametnije, a da je kolokvijski jednostavno, no i ovo ce ti dati linearnu slozenost:
[tex](n-k)! = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot (n-k) = \frac{1 \cdot 2 \cdot 3 \cdot \cdots \cdot (n-k) \cdot (n-k+1) \cdot \cdots \cdot n}{(n-k+1) \cdot \cdots \cdot n} = \frac{n!}{(n-k+1) \cdot \cdots \cdot n}[/tex].
Po koracima zapisano:
[tex]\begin{align*}
n! &= n!, \\
(n-1)! &= \frac{n!}{n}, \\
(n-2)! &= \frac{(n-1)!}{n-1}, \\
&\ \vdots \\
1! &= \frac{2!}{2}
\end{align*}[/tex]
Dakle, izracunas [tex]n![/tex] (u realnoj aritmetici!) prije nego krenes s Hornerom, a onda u svakom koraku podijelis s cim vec treba:
[code:1]prod = /* tu izracunas n! u jednoj for-petlji, sto je linearno */;
for (...) { /* petlja od Hornera; ne sadrzi druge petlje pa je i to linearno */
p = /* korak Hornera koji koristi prod */
if (k) prod /= k; /* if-om izbjegavamo dijeljenje s nulom u zadnjem koraku */
}[/code:1]
Petlja [color=red]u[/color] petlji je kvadratno, ali ovdje imamo petlju [color=green]iza[/color] petlje, sto je linearno po duljini petlji, tj. po [tex]n[/tex].
P.S. Ovisno o vrijednostima [tex]x[/tex] i [tex]n[/tex], ponekad je bolje tako "izvrnuti" racunanje potencija od [tex]x-2[/tex], ali to je -- po meni -- solidno iznad razine kolokvija.
Trenutno ne vidim moze li pametnije, a da je kolokvijski jednostavno, no i ovo ce ti dati linearnu slozenost:
[tex](n-k)! = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot (n-k) = \frac{1 \cdot 2 \cdot 3 \cdot \cdots \cdot (n-k) \cdot (n-k+1) \cdot \cdots \cdot n}{(n-k+1) \cdot \cdots \cdot n} = \frac{n!}{(n-k+1) \cdot \cdots \cdot n}[/tex].
Po koracima zapisano:
[tex]\begin{align*}
n! &= n!, \\
(n-1)! &= \frac{n!}{n}, \\
(n-2)! &= \frac{(n-1)!}{n-1}, \\
&\ \vdots \\
1! &= \frac{2!}{2}
\end{align*}[/tex]
Dakle, izracunas [tex]n![/tex] (u realnoj aritmetici!) prije nego krenes s Hornerom, a onda u svakom koraku podijelis s cim vec treba:
Kod: | prod = /* tu izracunas n! u jednoj for-petlji, sto je linearno */;
for (...) { /* petlja od Hornera; ne sadrzi druge petlje pa je i to linearno */
p = /* korak Hornera koji koristi prod */
if (k) prod /= k; /* if-om izbjegavamo dijeljenje s nulom u zadnjem koraku */
} |
Petlja u petlji je kvadratno, ali ovdje imamo petlju iza petlje, sto je linearno po duljini petlji, tj. po [tex]n[/tex].
P.S. Ovisno o vrijednostima [tex]x[/tex] i [tex]n[/tex], ponekad je bolje tako "izvrnuti" racunanje potencija od [tex]x-2[/tex], ali to je – po meni – solidno iznad razine kolokvija.
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
|
|
[Vrh] |
|
|