Matematyka

Jak nauczył mnie tegoroczny konkurs o dziką kartę NMC trzeba zawsze mieć konwerter wszystkich możliwych systemów liczenia, bowiem liczenie zadania na 5 konwersji kilkucyfrowych liczb i jednego XORa to wystarczający powód by się lekko zdenerowować 😉 Zadanie brzmiało: 7. Wybierz poprawny wynik operacji 3A995(11) XOR 153262(7) a. 799A(17) b. 13BB3(13) c. B024(15) Cóż, nie ma co się załamywać, tylko trzeba pisać program i mieć go potem cały czas przy sobie. Kod, który jakiś czas temu powstał jest dość prosty i ograniczony do cyfr jako 0..Z i maksymalnym zakresie _long_a (czyli 10 cyfr), jednak dla bezpieczeństwa dałem long longa - nigdy nie wiadomo na czym przyjdzie kompilować kod.

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…