sobota, 19 maja 2012
niedziela, 13 maja 2012
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:
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
- podstawowe pojęcia z teorii grafów
- algorytm Dijkstry
- cykl Eulera
niedziela, 6 maja 2012
Zadanie 1
Zaprojektuj program, który pozwoli skrócić ułamek zwykły zdefiniowany jako wyrażenie:
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:
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.
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:
Subskrybuj:
Posty (Atom)