Zmienne

Oto bardzo stary algorytm, który od czterech tysięcy lat pojawia się (z przerwami) na lekcjach matematyki.

Algorytm B (Babiloński)

Dane są dodatnie liczby Q i e.

1. Niech p = 1.
2. Niech s oznacza średnią arytmetyczną liczb p i Q/p.
3. Jeżeli różnica pomiędzy s i p jest mniejsza od e, zakończ i daj odpowiedź s; w przeciwnym przypadku przyjmij za p wartość s i powtórz począwszy od kroku 2.

Na przykład, gdy weźmiemy Q=2 oraz e=0.001, otrzymamy wynik ~1.414214. Można się domyślać, do czego ten algorytm służy, ale zostawimy to jako przedmiot zadania 2, bo przede wszystkim interesuje nas teraz sam opis algorytmu.

Po pierwsze, w opisie algorytmu pojawia się stwierdzenie "niech p = 1". Co to znaczy? W matematyce, gdy piszemy "p = 1", to albo stwierdzamy, że "p" ma wartość jeden, albo pytamy, czy "p" ma wartość jeden. Wyrażenie "niech p=1" oznacza jednak coś innego. To nie jest stwierdzenie faktu, to nie jest pytanie. To jest powołanie do życia nowego oznaczenia - od tej pory symbol "p" będzie oznaczać liczbę 1.

Po drugie, wartości symbolu "p" nie ustanawiamy na zawsze, może się ona zmieniać w czasie. Na przykład, jeżeli weźmiemy Q=2 i e=0.001, to symbol "p" przyjmie kolejno wartości 1, 1.5, 1.416667, 1.414216.

Symbole takie jak Q, e, p i s w programowaniu nazywamy zmiennymi. Zmienna ma nazwę (np. p) oraz wartość (np. 1.414216). Wartość zmiennej może ulegać zmianie z biegiem wykonania programu. Nadanie zmiennej nowej wartości nazywamy przypisaniem.

Zarówno w programowaniu, jak i w matematyce, musimy czytelnie odróżniać przypisanie wartości (do) zmiennej od stwierdzenia (lub pytania) o wartość zmiennej. W matematyce przypisanie zapisujemy za pomocą wyrażenia "niech..." albo "przypisuję..." itp. W programowaniu jednak panuje pewien bałagan. W pewnych językach przypisanie oznacza się za pomocą pojedynczego znaku równości "x = 1". Żeby jednak przypisanie nie myliło się z porównaniem (tj. stwierdzeniem, że "x" jest równe 1), wprowadzono nowe oznaczenie porównania: "x == 1". To rozwiązanie ma pewne zalety, ale ma też tę wadę, że wprowadza mętlik w notacji. Oto zestawienie notacji dla kilku języków.

Przykładowe przypisania w języku Python wyglądają tak:

p = 1;
s = (p + Q/p) / 2;

Jeżeli przed wykonaniem powyższych przypisań mieliśmy Q==2, to po ich wykonaniu będziemy mieli p==1, s==1.5 oraz w dalszym ciągu Q==2.

Przypisania a porównania

Cegła waży kilo i pół cegły, ile waży cegła? Wystarczy rozwiązać równanie x==1+(1/2)*x, by odpowiedzieć, że 2 kilo. Cóż jednak odpowiedzielibyśmy na pytanie Cegła waży kilo i cegłę, ile waży cegła? To pytanie wprawia w zakłopotanie, ponieważ odnośne równanie x == x+1 nie ma rozwiązań. Pozostaje oznajmić pytającemu, że chyba popełnił gafę, bo taka cegła istnieć nie może. To równanie demonstruje różnicę pomiędzy porównaniem, a przypisaniem. Nie istnieje liczba rzeczywista x, dla której odpowiedź na pytanie, czy

x == x + 1

byłaby prawdziwe. Wynikiem porównania

x == x + 1

jest zawsze fałsz. Z drugiej strony, przypisanie

x = x + 1

jest zupełnie poprawne; jest to instrukcja nakazująca zmianę wartości zmiennej "x", tak by nowa wartość była o jeden większa od starej. Można na nie patrzeć w ten sposób, że "x" po prawej stronie to stary "x", natomiast "x" po lewej stronie, to "nowy "x", czyli

x_nowy = x_stary + 1

Przypisania typu "x + 1 = 2'" w większości języków programowania są zabronione, ponieważ mogą prowadzić do niejednoznaczności.

Nazwy

Do tej pory posługiwaliśmy się zmiennymi o nazwach jednoliterowych. Większość języków programowania dopuszcza nazwy wieloliterowe, np. delta, najwiekszy_element, x1, x2. Zazwyczaj języki programowania nie dopuszczają nazw rozpoczynających się od cyfry.

Deklaracje

W niektórych językach (np. C++, JavaScript, Pascal) należy deklarować zmienne, zanim się ich użyje. Deklaracja to sposób oznajmienia, że dany symbol będzie używany jako zmienna. Dzięki deklaracjom łatwiej uniknąć błędów wynikających np. z pomyłek (literówek). Bez deklaracji trudno stwierdzić, czy najwiekszy_elment to ma być nowa zmienna, czy może chodziło o najwiekszy_element.

Część języków programowania (np. C++) wymaga, by nie tylko deklarować zmienne, ale także podawać zbiór wartości, jakie dana zmienna może przyjmować podczas wykonania programu. Przykładowo w języku C++ zmienną x o wartościach rzeczywistych deklarujemy pisząc

double x;

natomiast zmienną y o wartościach całkowitych deklarujemy pisząc

int y;

Dzięki dodatkowej informacji o zmiennych, komputer może automatycznie sprawdzić, czy zmienne w programie są używane poprawnie. Obecność tej dodatkowej informacji pozwala też na szybsze wykonanie programu.

Przykład - instrukcje przypisania

W znakomitej książce Mozaika matematyczna pod redakcją Endre Hodi (Wiedza Powszechna, Warszawa 1987) można znaleźć opis następującej zabawy-zgadywanki.

Alina mówi do Bolka: rzuć trzema kostkami, zapamiętaj wyniki i nie pokazuj mi. Pierwszy pomnóż przez 2, dodaj 5, pomnóż przez 5, dodaj wynik z drugiej kostki, pomnóż przez 10, na koniec dodaj wynik z trzeciej kostki i powiedz, ile Ci wyszło.

Obliczenie Bolka możemy zakodować tak:

def obliczWynik(kostka1, kostka2, kostka3):
    w = 2 * kostka1;
    w = w + 5;
    w = 5 * w;
    w = w + kostka2;
    w = 10 * w;
    w = w + kostka3;
    return w;    

Bolek oznajmia Alinie sam wynik, ona jednak zawsze potrafi zgadnąć, jakie liczby wypadły na kostkach. Jak to robi? Roztrząsamy to w zadaniach 4 oraz 5.

ZADANIA

Zadanie 1

Przeanalizuj kolejne kroki wykonania Algorytmu B dla \(Q == 2\) i \(e == 0.001\), zapisz kolejne wartości przyjmowane przez zmienne p i s.

Rozwiązanie

niech \( p = 1 \)

\(s = (p + Q / p) / 2 = (1 + 2 / 1) / 2 = {3 \over 2} = 1.500000\)

różnica \(|s-p| = |{3 \over 2} - 1| = {1 \over 2} = 0.500000 \geq 10^{-3} \)

kontynuujemy

przyjmujemy \(p = s = {3 \over 2} = 1.500000\)

\(s = (p + Q / p) / 2 = ({3 \over 2} + 2 / {3 \over 2}) / 2 = {17 \over 12} \approx 1.416667\)

różnica \(|s-p| = |{17 \over 12} - {3 \over 2}| = {1 \over 12} \approx 0.083333 \geq 10^{-3} \)

kontynuujemy

przyjmujemy \(p = {17 \over 12} \approx 1.416667\)

\(s = (p + Q / p) / 2 = ({17 \over 12} + 2 / {17 \over 12}) / 2 = {577 \over 408} \approx 1.414216\)

różnica \(|s-p| = |{577 \over 408} - {17 \over 12}| = {1 \over 408} \approx 0.002451 \geq 10^{-3} \)

kontynuujemy

przyjmujemy \(p = {577 \over 408} \approx 1.414216\)

\(s = (s + Q / p) / 2 = ({577 \over 408} + 2 / {577 \over 408}) / 2 = {665857 \over 470832} \approx 1.414214\)

różnica \(|s-p| = |{665857 \over 470832} - {577 \over 408}| = {1 \over 470832} \approx 0.000002 < 10^{-3} \)

kończymy z wynikiem \({665857 \over 470832} \approx 1.414214\)

Zadanie 2 *

Udowodnij, że Algorytm B oblicza przybliżenie pierwiastka kwadratowego z liczby Q.

Rozwiązanie

Niech \(p_n\) oznacza wartość liczby \(p\) po dokładnie \(n\) iteracjach. Zauważmy, że w dowolnym momencie \( \sqrt{Q} \in
[\min(p_n, Q/p_n), \max(p_n, Q/p_n)] \). Jeśli \(p_n \le \sqrt{Q}\), to wtedy \( Q/p_n \ge \sqrt{Q} \). Podobnie, gdy \(p_n \ge \sqrt{Q}\).
Widać już, że jeśli wykonywanie algorytmu się zakończy, to w wyniku otrzymamy przybliżenie pierwiastka kwadratowego, gdyż warunek \( |s - p_n| \le e \) jest równoważny temu, że \( |Q/p_n - p_n| \le 2e \), czyli, że przedział, gdzie się chowa \( \sqrt{Q} \) jest bardzo krótki.
Pozostaje jeszcze pokazać, że się skończy. W tym celu zauważmy, ze \( |Q/p_{n+1} - p_{n+1}| \le \frac{1}{2} |Q/p_n - p_n| \), gdyż \( Q/p_{n+1}, p_{n+1} \in [\min(p_n, Q/p_n), \max(p_n, Q/p_n)] \). Liczba \( p_{n+1} \) jest środkiem tego przedziału, zaś liczba \( Q/p_{n+1} \) nie może być większa od \( \max(p_n, Q/p_n) \), gdyż iloczyn \( p_{n+1} \cdot Q/p_{n+1} = Q \), byłby większy od iloczynu \( p_{n} \cdot Q/p_{n} = Q \), co jest niemożliwe. W analogiczny sposób liczba \( Q/p_{n+1} \) nie może być mniejsza niż \(\min(p_n, Q/p_n)\). Oznacza to, że odległość dowolnej liczby z przedziału \( [\min(p_n, Q/p_n), \max(p_n, Q/p_n)] \), do jego środka jest nie większa niż połowa długości tego przedziału, co oznacza, że \( |Q/p_{n+1} - p_{n+1}| \le \frac{1}{2} |Q/p_n - p_n| \), czyli z każdym kolejnym krokiem jesteśmy przynajmniej dwa razy bliżej pierwiastka niż poprzednio. Algorytm zatem się skończy, jeśli tylko \( e > 0 \)

Zadanie 3

Zakoduj Algorytm Babiloński jako funkcję o argumentach Q i e.

Rozwiązanie

def Babilonski(double Q, double e):
  p = 1;
  s = (p + Q/p)/2; 
  while (abs(s-p) >= e): #abs(x) oznacza wartość bezwzględną liczby x
    p = s; 
    s = (p + Q/p)/2;  
  return s;

Zadanie 4

Treść funkcji obliczWynik() wygodnie zapisać za pomocą pomocniczej zmiennej w, jednak jej użycie nie jest konieczne. Zapisz funkcję obliczWynik() bez dodatkowej zmiennej.

Rozwiązanie

Żeby się nie pogubić, można zacząć od ponumerowania różnych wartości zmiennej w:

w₁ = 2 * kostka1;
w₂ = w₁ + 5;
w₃ = 5 * w₂;
w₄ = w₃ + kostka2;
w₅ = 10 * w₄;
w₆ = w₅ + kostka3;

Chcemy ostatnią wartość (w₆) wyrazić wyłącznie za pomocą zmiennych kostka1, kostka2, kostka3. Podstawiając otrzymujemy

w₆ = 10 * (5*(2*kostka1+5)+kostka2) + kostka3;

upraszczając wyrażenie algebraiczne otrzymujemy kod:

def obliczWynik(kostka1, kostka2, kostka3):
   return 100*kostka1 + 10*kostka2 + kostka3 + 250;  

Zadanie 5

Skąd Alina wie, jakie wartości wypadły na kostkach rzucanych w sekrecie przez Bolka?

Rozwiązanie

W rozwiązaniu zadania 4 widać, że jeżeli od wyniku odejmiemy liczbę 250, to otrzymamy liczbę trzycyfrową o cyfrach a, b, c i wartości równej \(100*a + 10*b + c\). Odpowiedź rzuca się w oczy, jeżeli np. "abc==421", to Bolek musiał wyrzucić 4, 2 oraz 1. Nie jest jednak prosto to zaprogramować. Odpowiedź jest dla nas oczywista, ponieważ piszemy i myślimy w systemie dziesiętnym. Liczba 5219 nie wydaje się jakaś szczególna i nawet nieco zaskakujący jest fakt, że w systemie siedemnastkowym zapisuje się ją jako 111₁₇. Współczesnym maszynom system dziesiętny jest tak obcy, jak nam system siedemnastkowy. Program musi zatem zbadać liczbę abc za pomocą porównań i operacji arytmetycznych. W szczególności przyda się operacja dzielenia całkowitego, która dla liczb dodatnich działa w ten sposób, że oblicza ile razy całkowicie dzielnik mieści się w dzielnej, np. 11/3 daje 3 (dokładny wynik to 3 i 2/3).

def zgadnijWynikiRzutow(w):
    w = w - 250;
    kostka1 = w // 100;
    w = w - 100 * kostka1;
    # tutaj w zawiera już tylko 'bc'
    kostka 2 = w // 10;
    w = w - 10 * kostka2;
    kostka3 = w;
    return (kostka1,kostka2,kostka3);

Uwaga: w Pythonie dzielenie całkowite zapisujemy za pomocą podwójnego znaku dzielenia

Zadanie 6

Oto dwa algorytmy, które dla danej liczby całkowitej \(a\) obliczają wartość potęgi \(a^4\).

Algorytm A

niech w = a*a*a*a

Algorytm B

niech w = a*a
niech w = w*w

W algorytmie A policzenie \(a^4\) wymaga trzech mnożeń, natomiast w algorytmie B tylko dwóch.

Algorytm C oblicza \( a^{11} \) za pomocą 5 mnożeń.

Algorytm C

niech w = a
niech z = a*a
niech w = w*z wartością w jest \( a^3 \)
niech z = z*z wartością z jest \( a^4 \)
niech z = z*z wartością z jest \( a^8 \)
niech w = w*z wartością w jest \( a^{11} \)

Zaproponuj algorytmy obliczania:

• \( a^{32} \) za pomocą 5 mnożeń,
• \( a^{22} \) za pomocą 7 mnożeń,
• \( a^{31} \) za pomocą 8 mnożeń.

W kolejnych zadaniach bawimy się szachownicą. Kolumny szachownicy są ponumerowane liczbami 1,2, ..., 8 od strony lewej do prawej, wiersze pól szachownicy są ponumerowane liczbami 1,2, ..., 8, z dołu do góry. Przy takiej numeracji, każde pole na szachownicy jest wyznaczone jednoznacznie przez parę współrzędnych (i,j) -- (numer kolumny, numer wiersza).

Zadanie 7

Podaj algorytm obliczania liczby pól atakowanych przez hetmana stojącego na polu (i,i), dla zadanego i z przedziału [1,8], czyli na polu przekątnej szachownicy biegnącej z dolnego-lewego rogu do górnego-prawego rogu. Do dyspozycji masz tylko instrukcje: wyboru, przypisania i operacje na liczbach całkowitych: dodawanie, odejmowanie, mnożenie. Uwaga: pole, na którym stoi hetman też jest atakowane.

Rozwiązanie:

    odpowiedz = 22; //atakowane jest każde pole w wierszu i, każde w kolumnie i, oraz każde pole na przekątnej z dolnego lewego rogu, do górnego prawego rogu
    czy (i <= 4)? 
    jeśli tak, to
        odpowiedz = odpowiedz + 2*(i - 1);  
    jeśli nie, to
        odpowiedz = odpowiedz + 2*( 8 - i); 

Zadanie 8

Podaj algorytm obliczania liczby pól atakowanych przez hetmana stojącego na polu (i,9-i), dla zadanego i z przedziału [1,8]. Tym razem rozważamy przekątną biegnącą górnego-lewego rogu do dolnego-prawego-rogu.

Zadanie 9

Podaj algorytm obliczania liczby pól atakowanych przez hetmana stojącego na polu (i,j), dla i, j spełniających 1 <= i <= j <= 4.

Zadanie 10

Podaj algorytm obliczania liczby pól atakowanych przez hetmana stojącego na polu (i,j), dla dowolnych 1 <= i, j <= 8. Zaprogramuj ten algorytm.

Wkazówka

Wykorzystaj rozwiązanie zadania 9 do rozwiązania zadania 10.

Zadanie 11

Zaimplementuj funkcję

def naProstokacie(x, y,  w1x, w1y,  w2x, w2y):

która oblicza wartość logiczną warunku punkt \((x,y)\) znajduje się na prostokącie o bokach równoległych do osi układu rozpiętym na wierzchołkach \((w1x, w1y)\) i \((w2x, w2y)\). Przyjmujemy, że brzeg należy do prostokąta.

Zadanie 12

Dany jest wektor swobodny o współrzędnych \([x,y]\). Napisz funkcję

def obrocWPrawo(x, y):

która zwraca wektor obrócony o 90 stopni zgodnie z ruchem wskazówek zegara.