Sztuka z komputera

Tworząc programy staramy się wykonywać je zgodnie z określonymi algorytmami. Algorytmy, które są w pełni określone i w jasny sposób tłumaczą użytkownikowi jak dojść do upragnionego celu. A co, by było w przypadku gdy algorytm zależałby od inwencji twórczej jego autora. Dobrym przykładem może być tutaj zagadnienie fraktali czy też chaosu.
Zastanówmy się jak w prosty sposób wygenerować coś np. obraz dwuwymiarowy, który spełni nasze oczekiwania i przedstawi jakąś formę przekazu matematyczno-plastycznego. Zmuśmy do pracy te szybkie maszynki, by na nasz pożytek coś wygenerowały. Zaczniemy od czegoś prostego. Zbioru punktów pseudolosowych, które posłużą dalej do generacji znanego efektu śnieżenia telewizora.
Od czego zacząć. Wystarczą podstawy algebry oraz trygonometrii no i trochę cierpliwości. Zacznijmy od przykładu, który pozwoli przygotować ekran do tworzenia naszej aplikacji.
Do doświadczeń wybrano język Java. Zakładam podstawową znajomość tego języka w zakresie programowania. Dalsze szczegóły zostawmy sobie na później.

Zadanie 3

Zadanie 2

Wyobraźmy sobie, że żyjemy w kraju bardzo odległym od naszego jakim są Chiny. Odbywamy właśnie staż w urzędzie pocztowym w Pekinie. Bagatela mieszka tam/przebywa około 20 mln ludzi. Naszym zadaniem jako listonosza jest dotarcie do mieszkańców w wybranej dzielnicy. Trudność polega na tym, że liczba mieszkańców jest stosunkowo duża, a listonosz jest jeden. Zatem należy wypracować sobie taki algorytm, który pozwoliłby nam zoptymalizować naszą trasę. W końcu doba ma tylko 24 godziny.

Zatem przejdźmy do czynów. W 1962 roku chiński matematyk Mei-Kowan by rozwiązać ten problem w następujący sposób: 

wędrując od skrzynki do skrzynki (w wybranej dzielnicy), listonosz odwiedza mieszkańców swojego rejonu w taki sposób, by wędrować od domu do domu po czym wrócić na pocztę; duża liczba mieszkańców sprawia, że listonosz pragnie przebyć trasę jak najkrótszą drogą. 

I właśnie wyszukanie takiej trasy nazywamy problemem chińskiego listonosza ang. Chinese Postman Problem  CPP

W oparciu o teorię grafów zaimplementuj ten problem. Można wykorzystać materiały publikowane w:

• http://www.sciencedirect.com/science/article/pii/S0305054898000926
• www.google.pl - Mei-Ko Kwan postman - pierwszy link jaki się pojawi to dokument

Co się może przydać w rozwiązaniu problemu:

• podstawowe pojęcia z teorii grafów
• algorytm Dijkstry
• cykl Eulera

Zadanie 1

Zaprojektuj program, który pozwoli skrócić ułamek zwykły zdefiniowany jako wyrażenie:

gdzie licznik oraz mianownik to liczby całkowite.

Chcemy skrócić ułamek do jak najprostszej postaci. Uwaga na mianownik, który może przyjąć wartość 0. Może również się zdarzyć, że wartość dla licznika będzie większa lub równa  mianownikowi, wówczas mamy do czynienia z tzw. ułamkami niewłaściwymi. Ułamki takie można wówczas przedstawić przy pomocy sumy liczby całkowitej i ułamka właściwego.

Przykład:
Rozważmy skracanie ułamka zwykłego określonego przy pomocy wyrażenia:

W łatwy sposób można zauważyć, że licznik oraz mianownik ułamka są podzielne przez 7. Możemy zatem w końcu zapisać, że: