Algorytm wydawania reszty ; Palindromy; Anagramy ; Sortowanie tekstu

 Problem wydawania reszty

Problem wydawania reszty – zagadnienie z dziedziny algorytmiki, problem polegający na wybraniu z danego zbioru monet o określonych nominałach takiej konfiguracji, by wydać żądaną kwotę przy użyciu minimalnej liczby monet. Jego rozwiązania są wykorzystywane w automatach z napojami, bankomatach itd.

Przykładowe zadanie

Dane są trzy nominały – 1 zł, 2 zł i 5 zł. Ile minimalnie monet potrzeba, by wydać 13 zł?

Rozwiązanie

Poniżej pokazano dwa popularne rozwiązania tego problemu dla wariantu problemu, w którym zakłada się dostępność dowolnej liczby monet każdego nominału: jedno przy pomocy algorytmu zachłannego, drugie z wykorzystaniem programowania dynamicznego.

Niech:

k – żądana kwota; wg przykładu 13

n – największy element zbioru nominałów

x – liczba potrzebnych monet; początkowo 0

Algorytm zachłanny

Algorytm zachłanny jest poprawny dla tego problemu w większości stosowanych obecnie systemów monetarnych, jednak nie działa np. dla systemu (1, 4, 5) (kontrprzykładem jest kwota 8).

W tym przypadku, algorytm będzie wartość:

k – w każdym kroku pomniejszał o n

n – porównywał z wartością k, by stwierdzić, czy jest ona mniejsza lub równa

x – w każdym kroku zwiększał o 1

Algorytm odejmuje od zadanej kwoty największy spośród nominałów mniejszych i równych kwocie. Następnie, o ile kwota jest większa od zera, powtarza czynność. Liczba powtórzeń jest liczbą potrzebnych monet.

Dla powyższego przykładu algorytm zadziała następująco:

k	13	8	3	1
n	5	5	2	1
x	1	2	3	4

Zaletą powyższego algorytmu jest szybkość i prostota implementacji.

 Palindrom

Palindrom (gr. palindromeo – biec z powrotem) – wyrażenie brzmiące tak samo czytane od lewej do prawej i od prawej do lewej. Przykładem palindromu jest: Kobyła ma mały bok. Współcześnie palindromy pełnią funkcję gry słownej. Prawdopodobnie tak było również i w przeszłości, choć pewne znaleziska sugerują, że palindromy mogły też mieć znaczenie magiczne.

 Anagram

Anagram – nazwa wywodząca się od słów greckich: ana- (nad) oraz grámma (litera), oznacza wyraz, wyrażenie lub całe zdanie powstałe przez przestawienie liter bądź sylab innego wyrazu lub zdania, wykorzystujące wszystkie litery (głoski bądź sylaby) materiału wyjściowego. W czasopismach szaradziarskich pojawiają się zadania polegające na odgadnięciu wykreskowanego anagramu na podstawie wierszowanego komentarza, a także anagramy rysunkowe polegające na ułożeniu hasła z wszystkich liter właściwego określenia rysunku. Formami spokrewnionymi z anagramem są stenoanagram, egzoanagram i endoanagram.

Najprostszy anagram to poukładanie liter w odwrotnej kolejności, np. kebab – babek. Przykładem jednego z prostych przestawień jest zamiana sylab w wyrazie ranty, dająca anagram: tyran. Przestawiając pojedyncze litery możemy otrzymać np. anagram narty.

W 1998 Barbara i Adam Podgórscy w swoim Vademecum szaradzisty (Wydawnictwo Kurpisz) jako rekordowy podało anagram złożony z 16 elementów: krasa, Arska, raska, sarka, askar, kasar, Raksa, sakra, Arkas, Araks, Karsa, rakas, Karas, Sakar, Skara, Askra. Nie należy go jednak traktować jako niezmiennik, ponieważ przybywa zarówno słów, jak i metod wyszukiwania. Już choćby w podanym „rekordzie” dociekliwy czytelnik zauważy brak jednego potocznego wulgaryzmu oraz słowa Ksara.