Programování pro fyziky 2022/23 – Minialgoritmy

Cíl

Shrnujeme zde několik drobnějších algoritmů, které sice bývají v programovacích jazycích připraveny jako už hotové funkce, ale zde nám poslouží jako náměty pro ilustraci a trénink postupů strukturovaného programování. Nejprve je uveden seznam minialgoritmů, můžete zkusit minialgoritmus pomocí podmínek a/nebo cyklů psát ve svém programovacím jazyku už z tohoto bodu. Jako pomůcka do začátku jsou pak předloženy tyto minialgoritmy v Pythonu. Po nalezení inspirace můžete algoritmus převést do svého programovacího jazyka. V tuto chvíli nejde o nalezení a použití prefabrikované podoby, ale o naprogramování algoritmů imperativně a strukturovaně.

SEZNAM MINIALGORITMŮ

1. Absolutní hodnota

Absolutní hodnota celočíselné nebo reálné proměnné. Pro vyzkoušení chování v (interaktivní relaci) Pythonu:

abs(0); abs(1); abs(-1); abs(2.); abs(-2.)

2. Znaménko

Znaménko celočíselné nebo reálné proměnné. Pro kladné hodnoty proměnné na vstupu chceme mít na výstupu 1, pro záporné hodnoty -1, pro nulu 0. Funkce v některých jazycích existuje, může se jmenovat sgn nebo sign. V Pythonu je až v balíčku NumPy (Numeric Python):

import numpy; numpy.sign(2); numpy.sign(-3.1415)

3. Lichost a sudost

Test lichosti nebo sudosti celočíselné proměnné. Test lichosti vrátí True (nebo ekvivalentně nenulovou aritmetickou hodnotu), je-li hodnota proměnná na vstupu lichá, jinak vrací False (nebo nulovou aritmetickou hodnotu). Test sudosti to má opačně.

4. Extrémy

Nalezení menšího (většího) čísla ze dvou celočíselných nebo reálných hodnot. Povede-li se algoritmus zapsat jako funkci, lze ji s výhodou použít pro nalezení extrému z více než dvou hodnot. Hotové řešení v Pythonu:

min(1,-2,3); max(-1.,2,-3.)

5. Uříznutí a zaokrouhlení

Uříznutí desetinné části reálné hodnoty nebo zaokrouhlení reálné hodnoty na celé číslo. Stránky na wikipedii (truncation a rounding) napovídají, jak oba postupy zapsat pomocí funkcí floor (nejbližší celé číslo směrem k nule) a ceil/ceiling (nejbližší celé číslo směrem od nuly). Python:

int(2.718); import math; math.trunc(-2.718); round(2.718); round(-math.exp(1))

6. Desítkový logaritmus

Spočtení desítkového logaritmu log10 pomocí přirozeného logaritmu log. Python a balíčky Math a NumPy:

import math; math.log(1); math.log10(1.); import numpy; numpy.log(1.); numpy.log10(1)

7. Druhá mocnina

Spočtení druhé mocniny pomocí násobení. Pythonský operátor ** a funkce pow a power:

2**2; 3.**2; pow(2,2); pow(3,2.); import numpy; numpy.power(2,2); numpy.power(3.,2.)

8. \(n\)-tá mocnina

Spočtení n-té mocniny pomocí logaritmu log a exponenciály exp. V Pythonu obdobně jako o příklad výše:

0**0; (-0)**(-0); pow(0,0)

Zde by ovšem nulový základ komplikoval přímočarý přepis vzorce \(x^n=e^{n\log x}\). Alespoň si můžeme zkusit rozličnou reakci logaritmů v balíčcích Numpy a Math:

import numpy; numpy.log(1); numpy.log(0); numpy.log(-1)  # vrací návratové hodnoty a pokračuje
import math; math.log(1); math.log(0)  ## nevrátí návratovou hodnotu a nepokračuje
math.log(-1)

9. Přehození hodnot

Přehození hodnot ve dvou proměnných. Python se schopností přiřazovat jedním příkazem do více cílů to má jednoduché:

a=1; b=2; print(a,b); a,b=b,a; print(a,b)

10. Počítačové epsilon

Spočtení nejmenšího čísla, jehož přičtení ještě změní jedničku (více definic na stránce machine epsilon). Reálné typy jsou 8bytové a 4bytové, tedy i počítačových epsilon je více:

import numpy; numpy.finfo(float).eps; numpy.finfo(numpy.float32).eps

MINIALGORITMY V PYTHONU

1. Absolutní hodnota

Absolutní hodnota celočíselné nebo reálné proměnné:

# --1-- absolutni hodnota, abs(x)
print('abs(x) do z')

x=1                 # podmineny prikaz (rozvetveni do dvou vetvi)
if x>=0:
  z=x
else:
  z=-x
print('x,z = ',x,z)

x=-2                # default hodnota a podmineny prikaz o jedne vetvi
z=x
if x<0: z=-x
print('x,z = ',x,z)

x=0                 # podmineny vyraz
z=x if x>=0 else -x
print('x,z = ',x,z)

2. Znaménko

Znaménko celočíselné nebo reálné proměnné:

# --2-- znamenko, sign(x)
print('sign(x) do z')

x=2                 # zretezeny podmineny prikaz
if x>0:
  z=1
elif x<0:
  z=-1
else:
  z=0
print('x,z = ',x,z)

x=-3                # zretezeny podmineny vyraz
z=1 if x>0 else (-1 if x<0 else 0)
print('x,z = ',x,z)

                    # jednoprikazova (tzv. lambda) funkce s argumentem x
sign=lambda x: 1 if x>0 else (-1 if x<0 else 0)
print('sign(2),sign(-3),sign(0) = ',sign(2),sign(-3),sign(0))

3. Lichost a sudost

Test lichosti nebo sudosti celočíselné proměnné:

# --3-- lichost a sudost, odd(x) a even(x)
print('odd(x) do y, even(x) do z')

x=3                 # podmineny prikaz
if x%2==1:          # operator % pro zbytek po deleni
  y=1               # neboli True
  z=0               # neboli False
else:
  y=0
  z=1
print('x,y,z = ',x,y,z)

x=3                 # podmineny vyraz s operatorem % pro zbytek po deleni
y=1 if x%2==1 else 0
z=1 if x%2==0 else 0
print('x,y,z = ',x,y,z)

4. Extrémy

Nalezení menšího (většího) čísla ze dvou celočíselných nebo reálných hodnot:

# --4--  extrem ze 2 a 3 hodnot, min(x,y) a max(x,y)
print('minimum z x,y do z')

x=1; y=2            # podmineny prikaz
if x<y:
  z=x
else:
  z=y
print('x,y,z = ',x,y,z)

x=1; y=2            # podmineny vyraz
z=x if x<y else y
print('x,y,z = ',x,y,z)

x=2; y=1            # jednoprikazova funkce s dvema argumenty
minimum=lambda x,y: x if x<y else y
z=minimum(x,y)
print('x,y,z = ',x,y,z)

print('minimum z x,y,z do w')
x=3; y=1; z=2       # vnorovani funkci
w=minimum(minimum(x,y),z)
print('x,y,z,w = ',x,y,z,w)

5. Uříznutí a zaokrouhlení

Uříznutí desetinné části reálné hodnoty nebo zaokrouhlení reálné hodnoty na celé číslo:

# --5-- uriznuti a zaokrouhleni desetinne casti, trunc(x) a round(x), pomoci floor(x) a ceil(x)/ceiling(x)
# https://en.wikipedia.org/wiki/Floor_and_ceiling_functions#Rounding
print('trunc(x) do y, round(x) do z')
import math
x=1.5               # podminene vyrazy
y=math.floor(x) if x>0 else math.ceil(x)
z=math.floor(x+0.5)
print('x,y,z =',x,y,z)

                    # jednoprikazove funkce s argumentem x
trunc=lambda x: sign(x)*math.floor(abs(x))
round=lambda x: sign(x)*math.floor(abs(x)+0.5)
print('trunc(2),trunc(2.4),trunc(2.6),trunc(-2.6) = ',trunc(2),trunc(2.4),trunc(2.6),trunc(-2.6))
print('round(2),round(2.4),round(2.6),round(-2.6) = ',round(2),round(2.4),round(2.6),round(-2.6))

6. Desítkový logaritmus

Spočtení desítkového logaritmu log10 pomocí přirozeného logaritmu log:

# --6-- desitkovy logaritmus, log10(x), pomoci prirozeneho logaritmu log(x)
print('log10(x) do z')
import math
x=1000              # Python: log v modulu math
z=math.log(x)/math.log(10)
print('x,z = ',x,z)

7. Druhá mocnina

Spočtení druhé mocniny pomocí násobení:

# --7-- druha mocnina, sqr(x)
print('sqr(x) do z')
x=2
z=x*x
print('x,z = ',x,z)

8. \(n\)-tá mocnina

Spočtení n-té mocniny pomocí logaritmu log a exponenciály exp:

# --8-- n-ta mocnina, power(x,n), pomoci logaritmu log(x) a exponencialy exp(x)
print('power(x,n) do z')
import math
x=2; n=10           # Python: log a exp v modulu math
z=math.exp(n*math.log(x))
print('x,n,z = ',x,n,z)

9. Přehození hodnot

Přehození hodnot ve dvou proměnných:

# --9-- prehozeni hodnot v promennych, swap(x,y)
print('swap(x,y)')
x=1; y=2            # prehozeni s pomocnou promennou
print('x,y = ',x,y)
t=x; x=y; y=t
print('swapped x,y = ',x,y)

x=1; y=2            # prehozeni pomoci aritmetickych operaci
print('x,y = ',x,y)
x=x+y; y=x-y; x=x-y
print('swapped x,y = ',x,y)

10. Počítačové epsilon

Spočtení nejmenšího čísla, jehož přičtení ještě změní jedničku:

# --10-- pocitacove epsilon neboli nejmensi cislo, jehoz pricteni zmeni jednicku
# https://en.wikipedia.org/wiki/Machine_epsilon
print('epsilon')
epsilon=1           # cyklus s podminkou: dokud pricteni hodnoty meni jednicku, zmensuj hodnotu
while 1+epsilon*0.5>1:
  epsilon=epsilon*0.5
print('epsilon = ',epsilon)