Rodzaje algorytmów i przykładów

Programowanie nagrywa coś za pomocą nieznajomego języka innej osoby. Wraz z rozwojem tej dziedziny wiedzy twórcy poszli jeszcze dalej i nauczyli się pisać "coś", nie rozumiejąc nawet, jak brzmi w języku rosyjskim. Początkujący uczą się pisania kodu na raz w C ++ lub php przy użyciu wielu bibliotek, a oni nawet nie rozumieją, jak to, co tworzą dźwięki w ich ojczystym języku. Algorytmizacja zajmuje się wyjaśnianiem i przybliżaniem tego "czegoś".

Algorytmy

Większość przykładów algorytmów informatycznych, nawet na uniwersytetach, jest badanych na przeciętnym poziomie. Powszechną praktyką jest nieskończone pisanie coraz bardziej złożonego kodu. Próby niedoświadczonych programistów, aby od razu rozpocząć pisanie programów w języku programowania, można porównać z pracą dziennikarza, który ledwo opanował podstawy języka obcego, pisze artykuł do magazynu. Możesz uniknąć tego problemu, jeśli zaczniesz nagrywać swoją pracę w swoim własnym języku, edytować, sprawdzić błędy i na końcu tłumaczyć na wymagany język.

Zaletą tego podejścia jest głównie to, że deweloper będzie zaangażowany w tłumaczenie tylko w 25% przypadków, pisząc program w nowym języku, poświęci 100% na pracę z nieznanym językiem. W tym samym czasie będzie on w ciasnych warunkach i nie będzie w stanie przeprowadzić dobrego sprawdzenia pod kątem błędów i udoskonalenia projektu.

Algorytmy pomagają w implementacji projektu na komputerze, aby opisać proces rozwiązania w natywnym i zrozumiałym języku w postaci schematu połączonych algorytmów, analizować pomysły i uzyskać najbardziej jakościowy i przemyślany kod, który będzie bardziej odporny na błędy i będzie działać wydajniej.

Pojęcie algorytmu

Komputer nie wie, jak rozwiązywać problemy, może wykonywać proste akcje w określonej kolejności. "Jak działa kalkulator?" - pytasz. Jest to także owoc pracy programistów, którzy stworzyli program, który wykorzystuje pewne algorytmy w celu uzyskania niezbędnych rezultatów. Rozważ abstrakcyjną sytuację. Co należy zrobić, jeśli zostaniesz poproszony o znalezienie korzeni trinomialu kwadratowego osoby, która nie zna metod rozwiązywania równań?

Oczywiście, musi być przeszkolony do rozwiązania. równania kwadratowe. Dzieje się to w następujący sposób:

1. Wybierz rozwiązanie.
2. Sprawdź wszystkie szczegóły wybranej metody.
3. Wyjaśnij dwa pierwsze punkty przyszłemu artyście w języku, który rozumie.

Wtedy będzie można podać wykonawcom zadania do rozwiązania równania kwadratowego. A jeśli pierwsze dwa kroki są proste i jasne - wszystkie rozwiązania są opisane w odpowiedniej literaturze, to trzeci krok jest trudny.

Jak możesz upewnić się, że pomysły użyte do rozwiązania problemu będą postrzegane przez wykonawcę tak, jak go rozumiesz? Tutaj zbliżamy się do koncepcji algorytmu. Praktyka pokazuje, że aby ktoś mógł właściwie wyjaśnić coś, należy postępować zgodnie z następującymi krokami:

• określić dane źródłowe (zmienne i współczynniki równania kwadratowego);
• podzielić proces decyzyjny na jednoznacznie znane komponenty dla wykonawcy (formuły dyskryminacyjne i odnajdywanie rootów);
• określić kolejność kroków (najpierw obliczyć wyróżnik, następnie korzenie);
• ustal warunek, w którym rozwiązanie jest uważane za kompletne (sprawdź znalezione pierwiastki, zastępując je równaniem miejsca zmiennych);
• dokładnie wskazać, jak powinien wyglądać wynik rozwiązania (korzenie należą do zbioru liczb rzeczywistych).

Opisany zestaw kroków w ogólnym znaczeniu jest algorytmem. Tak więc algorytm można rozumieć jako metodę rozwiązania problemu, napisaną za pomocą pewnych reguł, pozwalającą na jednoznaczne zrozumienie wykonanych akcji i ich kolejności. Poniżej zostaną omówione bardziej szczegółowo algorytmy i przykłady problemów.

Główne właściwości algorytmu

Dyskrecja Proces rozwiązywania problemu zawsze składa się z ściśle oddzielonych od siebie działań, zwanych krokami, mających określoną kolejność wykonywania.

Pewność Każdy krok powinien być jasny i jednoznaczny, zarówno pod względem znaczenia, jak i klucza podejmowanych działań.

Wydajność. Algorytm powinien dać wynik. W takim przypadku liczba kroków może wynosić tysiące lub miliony, ale zawsze musi prowadzić do wyniku.

Msza św. Każdy algorytm opracowany w celu rozwiązania problemu powinien mieć zastosowanie do wszystkich problemów tego typu dla wszystkich ważnych danych wejściowych.

Funkcje komputera

Aby poprawnie tworzyć algorytmy dla komputerów, ważne jest zrozumienie ich możliwości. Zastanów się najpierw, jakie ilości działa komputer. Ogólnie można je podzielić na liczbowe i tekstowe, stałe i zmienne.

Liczby stałe to wszystkie liczby: 3,15, 100, 10 ⁵ , ich osobliwość jest niezmienna w całym programie. Zmienne zmieniają swoją wartość w trakcie wykonywania kodu i są oznaczone, z reguły, literami: x, y, max, min, itd.

Zmienne tekstowe, takie jak numeryczne, są stałe lub zmienne. W pierwszym przypadku jest to tylko tekst: "dobry", "aib" itd. W drugim, symbol jest tym samym symbolem, co zmienne numeryczne: nazwa, miasto itp. Różnica między nimi polega głównie na przydzielonej pamięci komputera pod przechowywaniem takiej zmiennej.

Operacje, które komputer może wykonywać:

1. Odczytywanie danych z urządzeń wejściowych (klawiatura, mysz, pliki).
2. Obliczanie wartości za pomocą funkcji matematycznych: dodawanie, odejmowanie, sin, cos, ln itd. - każdy język programowania ma własny zestaw wbudowanych funkcji.
3. Dane wyjściowe (na ekranie, na papierze, w interfejsie sieci).
4. Przejście między etapami programu.
5. Porównanie dwóch wielkości (więcej, mniej, równe).

Są to podstawowe operacje, które mogą być wykonywane przez większość języków programowania.

Sposoby opisywania algorytmów

Werbalne. To najprostszy sposób. Przykładem jest przepis. Dopuszczalne jest stosowanie prostych formuł matematycznych.

Grafika. Opis za pomocą schematów. Jest to specjalny sposób pisania algorytmów za pomocą ogólnie przyjętego języka algorytmicznego - rysunków i bloków, które mają określone znaczenie: prostokąt jest prostą czynnością, ukośny równoległomik to wejście / wyjście, romb jest warunkiem itp.

Wykorzystanie języka algorytmicznego. Podobnie jak w przypadku grafiki, jest to również specjalny sposób napisania algorytmu. Istnieje wiele języków algorytmicznych. Ich zasady nie są ścisłe, w przeciwnym razie byłby to język programowania. Rozważ przykład algorytmu płac, w zależności od długości usługi, zapisany przy użyciu języka algorytmicznego.

 алг заработная плата (int ST, real ZP)арг STрез ZPначалоесли ST < 5 то zp = 150иначеесли ST <= 15 то ZP = 180иначе ZP = 180 + (ST - 15)*10конец 

Język algorytmiczny można nazwać bardziej rygorystyczną formą pisania niż słowną. Stosuje się ograniczony zestaw słów i ich konstrukcje, a także wcięcia. Wadą formy słownej i języka algorytmicznego jest pogarszająca się widoczność algorytmu przy zwiększaniu jego rozmiaru. Dlatego metody te można wykorzystywać wyłącznie do przekazywania znaczenia małych algorytmów.

Rodzaje algorytmów

Istnieje ogromna różnorodność algorytmów zaprojektowanych do rozwiązywania różnych problemów. Na przykład każdy podręcznik wyższej matematyki zawiera setki algorytmów: rozwiązanie systemowe równania liniowe znajdowanie ekstremy funkcji, obliczanie całki itd. Jednak po dokładnym zbadaniu ich struktury okazuje się, że wszystkie algorytmy można podzielić na kilka typów. Rozważ te typy algorytmów za pomocą przykładów.

• liniowy (obliczanie wyniku dodawania lub mnożenia, wymiana wartości wielu zmiennych);
• rozgałęzienie (określenie największej z kilku liczb);
• cykliczne (sortowanie macierzy, obliczenia czynnikowe).

Są to podstawowe typy. Warto również zauważyć, że w wielu publikacjach podkreśla się także czwarty typ - rekursywny. Ale nie ma specjalnego oznaczenia w notacji schematu i jest realizowany przez podstawowe.

Więcej szczegółów na temat każdego algorytmu obliczeniowego z przykładami zostanie opisanych poniżej.

Zasady algorytmizacji

1. Zidentyfikuj dane źródłowe.
2. Wybierz rozwiązanie.
3. Podziel wybraną metodę na kroki w oparciu o możliwości komputera (język programowania).
4. Uruchom algorytm w formie schematu, definiując wyraźną kolejność kroków.
5. Wyświetla wyniki obliczeń.
6. Oznacz przejście do obwodu wyjściowego.

Algorytm debugowania

Człowiek popełnia błędy, a to jest fakt. Głównym parametrem każdego algorytmu powinna być poprawność jego pracy. Debugowanie to proces identyfikowania i korygowania błędów algorytmu. Aby to zrobić, weź pewien zestaw danych źródłowych, zwany testem. Z reguły są to wszelkiego rodzaju dane źródłowe. Na przykład, jeśli wprowadzono numer, algorytm powinien być sprawdzony pod kątem poprawności działania, biorąc pod uwagę: liczby dodatnie, ujemne, liczby całkowite i rzeczywiste, wartości zerowe itp.

Głównym narzędziem do sprawdzania dokładności algorytmu pozostaje ludzki mózg. Oczywiście, można zautomatyzować weryfikację za pomocą innych narzędzi komputerowych, ale tak czy inaczej, dana osoba jest zaangażowana w przygotowywanie testów i analizowanie wyników. W tym przypadku powstaje pytanie, dlaczego potrzebujemy algorytmu, jeśli człowiek sam wszystko wykonuje? Następnie głównym zadaniem algorytmu jest wielokrotne rozwiązywanie pewnego rodzaju problemów.

Algorytmy liniowe

Algorytm liniowy to taki, w którym kroki następują kolejno po sobie. Każdy algorytm, który nie zawiera rozgałęzień i cykli, jest liniowy. Rozważmy przykład algorytmu, który rozwiązuje następujący problem: wilk i zając siedzą w dwóch klatkach, musisz je zamienić.

Kluczem do rozwiązania tego problemu jest dodatkowa temp. Komórkowa, którą należy wykorzystać do zamiany zwierząt.

Algorytmy rozgałęzienia

Jak sama nazwa wskazuje, algorytm ma kilka gałęzi. Istotą pracy jest wybór jednego z możliwych wariantów procesu obliczeniowego, w zależności od warunków. Schematyczny rozgałęzienie reprezentuje blok w kształcie rombu, wewnątrz którego zaznaczony jest warunek, a po bokach są to gałęzie z wyboru, w zależności od tego, czy warunek jest prawdziwy, czy fałszywy. Algorytm rozgałęzień i przykłady jego zastosowania można znaleźć wszędzie. W programowaniu jest to typowa konstrukcja if-else, która jest w prawie każdym języku.

Podajemy przykład algorytmu do rozwiązania problemu znalezienia największego spośród trzech liczb.

Cykliczny algorytm

Cykliczny to algorytm, w którym występuje wiele powtórzeń tych samych kroków, w których może zmienić się tylko wartość konkretnej zmiennej, nad którą dokonywane są obliczenia. Typy algorytmu cyklicznego i przykład zostaną omówione poniżej, ale na razie wyliczymy główne etapy budowy cyklu.

1. Przypisywanie wartości początkowej zmiennych. Bez spełnienia tego warunku cykl najprawdopodobniej nie będzie w stanie zadziałać lub popełni błędy.
2. Jednostka obliczająca wyniki. To jest główna część cyklu.
3. Sprawdź końcowy stan procesu cyklicznego. Jeśli zapomnisz określić warunek ukończenia cyklu, algorytm będzie działał przez czas nieokreślony.
4. Zmień zmienne Blok ten wchodzi w życie po sprawdzeniu warunku zakończenia, jeśli był fałszywy. Jeśli zapomnimy o tym bloku, cykl zawsze wykona jedno działanie i nigdy się nie skończy. Dlatego ważne jest, aby zmienne ulegały zmianom w każdej iteracji pętli.

Istnieje kilka typów cyklicznych algorytmów: z warunkiem, warunkiem wstępnym i parametrem.

Konstruujemy cykliczny algorytm na przykładzie znalezienia silni N.

Inne typy algorytmów

Istnieje wiele algorytmów, które różnią się klasyfikacją lub pochodzeniem.

• Algorytmy mechaniczne. Na przykład działanie silnika o spalaniu wewnętrznym lub linii montażowej.
• Algorytmy probabilistyczne. Ich praca oparta jest na teorii prawdopodobieństwa i statystykach matematycznych.
• Algorytmy heurystyczne. Używaj praktycznych rozważań w swojej pracy, bez rygorystycznego matematycznego uzasadnienia.
• Algorytmy genetyczne. Zastosuj biologiczne pomysły w swojej pracy.

I inni.