Algorytmika

Ciekawe zadanie programistyczne, które umożliwia stworzenie gotowych funkcji do naszego zbioru. Treść brzmi dziwnie: wypisać liczby, które w zapisie ósemkowym mają cyfrę występującą dokładnie dwa razy. Po pierwsze musimy zkonwertować na inny zapis. string dec2other(int x, int base){ int l=x,t; string napis=""; while (l){ t=l%base; if (t<10) napis=char(t+48)+napis; else napis=char(t+55)+napis; l/=base; } return napis; } Kod opiera się na dzieleniu modulo i rzutowaniu na znak - dla cyfr większych od 9 potrzeba nam cyfry z hex’a: A,B,C… Warto zauważyć, że należałoby dołożyć jeszcze założenia podobne do tych:

Operacje bitowe - dla początkujących to brzmi strasznie. Możemy sumować (OR), mnożyć (AND), odejmować (popularniej ksorować - XOR), negować (NOT), lub przesuwać bity. Ale dziś dwa zastosowania: podzielność przez 2 bez dzielenia modulo i sprawdzenie, czy liczba jest potęgą dwójki. Ale na początek trochę podstaw. Operujemy na dwójkowym zapisie liczb, każdy bit, czyli krótko mówiąc jej cyfra. 0 to fałsz, 1 to prawda, często rozpatrywane w kategoriach bitu ustawionego i nie. Chwilow nie będziemy się zajmować liczbamiujemnymi, które można zapisywać na różne sposoby np. w U2.

Artykuł ten zacznę od małego wprowadzenia, żeby uporządkować to, co wiemy. Metoda rozkładu liczb na czynniki pierwsze to sito Eratostenesa (nie Erastotenesa - do tej pory zdaje się, że używałem błędnego imienia za co przepraszam). Skoro mowa o człowieku to warto wspomnieć, że poza oczywistem faktem, że był filozofem (jak każdy kto myślał w starożytnej Grecji) to jest także odpowiedzialny za obwód Ziemii, pewne odległości w astronomii. Obwód naszej planety obliczył dość ciekawie - przez różnicę długości cienii i założenie, że Słońce jako bardzo odległe to między mało odległymi miejscami rzuca nieomal równoległe promienie. Ale wróćmy do sita. Najpierw jakoś tablicujemy wszystkie liczby w naszym zbiorze. Może ku temu posłużyć tablica zmiennych typu boolean domyślnie wyzerowana na True. Dla każdej liczby od 2 do pierwiastka z maksimum tj. granicy zadanego zbioru wykonujemy wykreślanie: wykreślamy wszystkie jej wielokrotności poza nią samą, nie przejmując się, że niektóre wykreślimy dwukrotnie. Wykreślaniem może być na przykład przypisanie False. Teraz wystarczy wypisać wszystkie niewykreślone.

Proste zadanie z zeszłorocznej OI - rozkład Fibonacciego. Naszym zadaniem jest przedstawić minimalną liczbę dodawań lub odejmowań gdzie składnikami są tylko wyrazy ciągu Fibonacciego dla wskazanej liczby. Jest to przykład, że niektóre zadania można, a nawet trzeba rozwiązywać metodą siłową. Ale problem nie tkwi w algorytmie…

Wiek segmentolka. O tym zadaniu mogę powiedzieć chyba parazadanie z parakonkursu parainformatycznego napisane przez humanistę.

Problem, a raczej ćwiczenie programistyczne jest dość szeroko znany - jak ustawić na kwadratowej szachownicy 8x8 dokładnie 8 hetmanów tak, żeby się nie “biły” lub “widziały” tj. żeby w każdej kolumnie, wierszu i skosie był maksymalnie jeden hetman. Moje rozwiązanie problemu postanowiłem poszerzyć o możliwość podania przez użytkownika pozycji pierwszego hetmana - pozwala to ukazać realną pracę algorytmu oraz zgłębić problem rekurencji z powrotami. Jeśli spojrzeć na aspekt definiowalnego przez użytkownika pierwszego hetmana to jest to pionerski algorytm, gdyż w momencie tworzenia na pewno nie był dostępny albo był bardzo trudno dostępny w Internecie.