Algorytm wyodrębniania cyfry z liczby pojawia się jako składowa wielu programów maturalnych. W tej lekcji parę słów na temat tego algorytmu.
Oczywiście sam algorytm to część podstawy programowej szkoły podstawowej, a nie matury jako takiej i tenże artykuł stanowi część większej serii. Z drugiej strony, starałem się opisać różne warianty algorytmu oraz zastosować różne języki programowania, myślę więc, że i maturzysta z tego tekstu wyniesie coś wartościowego.
Polecenie wyodrębnienia cyfr z liczby może mieć różną postać. Od prostych pytań, jakie są te cyfry, poprzez ich sumowanie, aż po bardziej złożone operacje. Dlatego w tym artykule chciałbym na różne sposoby przeanalizować algorytm podziału liczby na cyfry, na przykładzie jednego z możliwych zastosowań.
Spis treści
Zamiana na tekst
Jedną z pierwszych metod, jakie przychodzą na myśl, to jest zamiana liczby na ciąg znaków (String) a następnie pobranie odpowiedniego znaku i ponowna jego zamiana na cyfrę. Powiedzmy, że zadanie polega na sumowaniu cyfr z liczby. Przykładowo: dla liczby 1234567890 wynikiem powinna być suma 1+2+3+4+5+6+7+8+9+0 czyli 45.
Zapis w postaci pseudokodu tego rozwiązania mógłby wyglądać mniej więcej tak:
liczba ← wczytaj() napis ← zamienNaNapis (liczba) suma ← 0 dla każdego znak w napis wykonaj: cyfra ← zamienNaLiczbe(znak) suma ← suma + cyfra
Myślę jednak, że konkretna implementacja będzie czytelniejsza. Dlatego poniżej przedstawiam 3 wersje, w trzech różnych językach maturalnych. Zakładam, że każdy z Czytelników dobierze sobie odpowiednią wersję, stąd każdą z nich opisuję oddzielnie, aby można było przeczytać tylko wybrany podrozdział.
Implementacja w Jawie
Jest to fragment kodu, który w programie można umieści np. wewnątrz funkcji public static void main(String[] args)
.
int liczba = 1234567890; String napis = String.valueOf(liczba); int suma = 0; int ileCyfr = napis.length(); for (int i = 0; i<ileCyfr; i++) { char znak = napis.charAt(i); int cyfra = Character.getNumericValue( znak ); suma = suma + cyfra; } System.out.println("Suma wszystkich cyfr to: "+suma);
Oczywiście można to było napisać bardziej zwięźle, jednak specjalnie rozpisałem każdą operację na oddzielną linijkę, aby zachować przejrzystość oraz móc to analizować krok po kroku.
- W pierwszej linii tworzę zmienną liczba o wartości
1234567890
. Jest to zmienna typuint
, czyli liczba całkowita (ang. integer). Może być ona oczywiście wczytana z pliku albo z konsoli tekstowej. Dla uproszczenia programu, jest ona zaszyta bezpośrednio w kodzie. - Następnie przerabiam tę liczbę na obiekt typu String. W Jawie String jest typem obiektowym, a nie tablicowym (jak np. w C++), dlatego klasa String posiada metody statyczne, które można tu użyć. Jedną z metod jest
valueOf()
, która pobiera wartość liczbową i zamienia na tekst. - W trzeciej linii zakładam, że suma cyfr będzie na początku wynosiła 0, aby potem do tej sumy dokładać kolejne cyfry.
- W czwartej linii badam długość napisu. Jak wspomniałem,
String
w Jawie jest klasą. Więc zmiennanapis
będzie zmienną obiektową klasyString
. Dzięki temu znajduję w niej metodęlength()
, która podaje długość. W omawianym przypadku długość ta wynosi 10, gdyż mamy 10 cyfry w liczbie zamienionej w napis. - Piata linia rozpoczyna pętlę
for
, która będzie klasycznie badała znak po znaku z mojego tekstu, a następnie przerabiała go na cyfrę i dodawała do sumy. Kluczowe w tej pętli jest to, aby nie dochodziła ona do wartościileCyfr
(10), gdyż cyfr jest właśnie tyle, ale są numerowane od 0. Czyli dla 10 cyfr, pętla powinna iterować po wartościach 0,1,2,3,4,6,7,8,9 i nie osiągać już wartości 10. - Początek bloku pętli. Można go było zapisać na końcu linii 5, w zależności od stylu programowania.
- Jak wspomniałem,
String
w Jawie jest klasą. Więc zmiennanapis
będzie zmienną obiektową klasyString
. Dzięki temu znajduję w niej metodęcharAt(…)
, która wyciąga z całego napisu znak o podanym numerze. Skoro więc pętla for zmienia i od 0 doileCyfr
, to w takim razie otrzymam kolejne znaki ze Stringa i każdy z tych znaków przypisuję do zmiennej typuchar
czyli character. Jest to typ prosty, nieobiektowy, który ma przechowywać po prostu 1 znak. - Korzystam z tego, że w Jawie istnieje klasa
Character
, która ma statyczną metodęgetNumericValue(…)
, która zamienia znak na liczbęint
. - W każdym przebiegu pętli zwiększam sumę (wynoszącą początkowo 0) o wartość kolejnej odczytanej cyfry. Zapis
suma = suma + cyfra
można zapisać krócej:suma += cyfra
. Jest to dokładnie ta sama operacja. - Tu kończy się pętla
- I w jedenastej linii pozostaje kosmetyka, czyli wypisanie na konsoli wartości sumy, żeby sprawdzić czy mój algorytm zadziałał.
Tak jak pisałem, można ten kod w ogóle skrócić i zapisać tak:
String napis = String.valueOf(1234567890); int suma = 0; for (int i = 0; i<napis.length(); i++) { suma += Character.getNumericValue( napis.charAt(i) ); } System.out.println("Suma wszystkich cyfr to: "+suma);
ale dla osób początkujących łatwiej zapewne rozpisać krok po kroku.
Implementacja w C++
#include <iostream> #include <string> using namespace std; int main() { int liczba = 1234567890; string napis = to_string(liczba); int suma = 0; int ileCyfr = napis.length(); for (int i = 0; i < ileCyfr; i++) { char znak = napis[i]; int cyfra = znak - '0'; suma = suma + cyfra; } cout << "Suma wszystkich cyfr to: " << suma<< endl; return 0; }
Program jest dość zbliżony do przedstawionej wcześniej wersji w Jawie.
- W pierwszej linii dołączam bibliotekę
iostream
, która zawiera np.cout
używane pod koniec programu. Ten zapis pojawia się standardowo w szablonie programu generowanym przez Code::Blocks (IDE dopuszczone do matury). - W drugiej linii dołączam bibliotekę string, co w zasadzie w kompilatorze dołączonym do maturalnego Code::Blocks pod Windows nie jest konieczne i bez tego program działa, jednak standard języka tego nie gwarantuje, dlatego dla porządku ta linia się tu znalazła.
- Trzecia linia to krytykowane przez niektórych użycie domyślnej przestrzeni nazw
std
. Niezależnie od krytyki, takie użycie jest domyślnie w maturalnym Code::Blocks i pozwala uniknąć pisaniastd::
przed wieloma elementami z kodu, więc myślę, że w zastosowaniu maturalnym można tego użyć. Zachęcam jednak do zapoznania się z tym forum: https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice, w którym można przeczytać opinie, dlaczego stosowanieusing namespace
jest niezbyt dobrą praktyką. - W linii czwartej rozpoczyna się program, a dokładnie główna funkcja
main()
. - Na początku programu tworzę zmienną liczba o wartości
1234567890
. Jest to zmienna typuint
, czyli liczba całkowita (ang. integer). Może być ona oczywiście wczytana z pliku albo z konsoli tekstowej. Dla uproszczenia programu, jest ona zaszyta bezpośrednio w kodzie. - Teraz przeprowadzam konwersję z liczby całkowitej na napis (string) stosując funkcję
std::to_string(…)
, która pojawiła się w standardzie C++11, więc myślę, że jej użycie jest w pełni dopuszczalne na maturze - W linii siódmej zakładam, że suma cyfr będzie na początku wynosiła 0, aby potem do tej sumy dokładać kolejne cyfry.
- Następnie badam długość napisu, wywołując na nim metodę
length()
, która podaje długość. W omawianym przypadku długość ta wynosi 10, gdyż mamy 10 cyfr w liczbie zamienionej w napis. - Dziewiąta linia rozpoczyna pętlę
for
, która będzie klasycznie badała znak po znaku z mojego tekstu, a następnie przerabiała go na cyfrę i dodawała do sumy. Kluczowe w tej pętli jest to, aby nie dochodziła ona do wartościileCyfr
(10), gdyż cyfr jest właśnie tyle, ale są numerowane od 0. Czyli dla 10 cyfr, pętla powinna iterować po wartościach 0,1,2,3,4,6,7,8,9 i nie osiągać już wartości 10. - String w C++ można traktować jak tablicę, a więc
napis[i]
to odwołanie po prostu do znaku o numerzei
. Skoro więc pętla for zmieniai
od 0 doileCyfr
, to w takim razie otrzymam kolejne znaki ze Stringa i każdy z tych znaków przypisuję do zmiennej typuchar
czyli character. Jest to typ prosty, nieobiektowy, który ma przechowywać po prostu 1 znak. - Teraz muszę ten znak zamienić na odpowiadającą mu cyfrę. I tu dzieje się pewnego rodzaju magia. zmienna typu char to tak naprawdę jest po prostu liczba zawierająca kod ASCII przedstawianego znaku. W tabeli kodów ASCII znak
'0'
kodowany jest jako liczba 48, znak'1'
jako 49 i tak dalej. Znakowi'9'
odpowiada liczba 57. Dlatego gdy od mojego znaku odejmę'0'
, to tak naprawdę od jego kodu odejmę kod początku zbioru cyfr. Dla'0'
ta różnica wyniesie 0, dla'1'
różnicą będzie 1 i tak dalej. Dzięki temu dokona się „magia” konwersji ze znaku na liczbę.
(UWAGA! To wyjaśnienie zawiera pewne uproszczenie. Standard języka C++ nie gwarantuje, że będzie to ASCII (choć na zdecydowanej większości systemów i kompilatorów tak będzie) i może być zastosowane inne kodowanie znaków, choć to kodowanie nadal będzie zachowywało ten warunek, że kody kolejnych cyfr są ułożone po kolei). - W każdym przebiegu pętli zwiększam sumę (wynoszącą początkowo 0) o wartość kolejnej odczytanej cyfry. Zapis
suma = suma + cyfra
można zapisać krócej:suma += cyfra
. Jest to dokładnie ta sama operacja. - Tu kończy się pętla.
- W czternastej linii pozostaje kosmetyka, czyli wypisanie na konsoli wartości sumy, żeby sprawdzić czy mój algorytm zadziałał.
- Końcówka programu to zwrócenie do systemu operacyjnego kodu zakończenia programu jako 0 (wszystko się udało)
- oraz zamkniecie klamrą funkcji
main()
.
Implementacja w Pythonie
Wężowa wersja będzie najkrótsza z wszystkich i może wyglądać na przykład tak:
liczba = 1234567890 napis = str(liczba) suma = 0 for znak in napis: cyfra = int(znak) suma = suma + cyfra print( suma )
- Na początku programu tworzę zmienną liczba o wartości 1234567890. Jest to zmienna typu
int, czyli liczba całkowita (ang. integer) choć w Pythonie typów się nie określa samemu, jak w Jawie i C++. Język sam „zgaduje”. Ta liczba może być oczywiście wczytana z pliku albo z konsoli tekstowej. Dla uproszczenia programu, jest ona zaszyta bezpośrednio w kodzie. - Teraz przeprowadzam konwersję z liczby na string stosując funkcję
str()
. - Zakładam, że suma cyfr będzie na początku wynosiła 0, aby potem do tej sumy dokładać kolejne cyfry.
- Pętla
for
w Pythonie działa nieco inaczej niż w C++ i Jawie. Jest to pętla której zmienna przyjmuje kolejne wartości z podanego zbioru. W naszym przypadku zbiorem jest napis, czyli zestaw kolejnych znaków. Nie potrzebne są więc żadne dodatkowe zmienne i zmiennaznak
będzie w tej pętli przyjmowała kolejno wszystkie znaki z napisu, aż osiągnie koniec. Nie muszę więc badać długości napisu. - Wyciągnięty z napisu znak muszę przerobić na cyfrę. Nie ma tu jawnie podanych typów, ale zmienna cyfra będzie zawierała już ten znak w postaci nie kawałka stringa, ale w postaci liczbowej. Takiej, na której można dokonywać operacji matematycznych.
- W każdym przebiegu pętli zwiększam sumę (wynoszącą początkowo 0) o wartość kolejnej odczytanej cyfry. Zapis
suma = suma + cyfra
można zapisać krócej:suma += cyfra
. Jest to dokładnie ta sama operacja. - Pozostaje kosmetyka, czyli wypisanie na konsoli wartości sumy, żeby sprawdzić czy mój algorytm zadziałał.
Python z gwiazdką
Pythonową implementację można zapisać bardziej w stylu Pythona, jak mi podesłał mój kolega z HardCoder.pl, który zawodowo oswaja węże. Jego wersja wygląda tak:
liczba=1234567890 napis = str(liczba) cyfry_tekstowo = list( napis ) cyfry_liczbowo = [] for znak in cyfry_tekstowo: cyfra = int(znak) cyfry_liczbowo.append( cyfra ) suma = sum(cyfry_liczbowo) print( suma )
To znaczy przysłał to w nieco innej formie, bo jako zawodowiec nazwał zmienne po angielsku i kod miał mniej linijek 🙂 Pozwoliłem sobie jednak na przetłumaczenie zmiennych oraz wprowadzenie kilku nowych, żeby osoby początkujące od razu widziały co jest z języka, a co jest nasze, autonomiczne.
- W pierwszej linii po prostu uzyskuję liczbę. Z pliku, konsoli, jakkolwiek. Tu jest ona zaszyta w kod.
- Zamieniam liczbę w napis, tak jak poprzednio.
- Teraz tworzę listę. Lista w Pythonie to często wykorzystywana struktura danych. To taka jakby tablica, ale dużo bardziej złożona i o większej mocy. W efekcie polecenia
list(napis)
string zostanie automatycznie rozczłonkowany na pojedyncze znaki, które trafią do tej listy. - Teraz powstaje pusta lista, która ma zawierać z założenia cyfry odpowiadające liście
cyfry_tekstowo
, tylko cyfry już traktowane przez Pythona jako liczby, a nie jako znaki. - W linii piątej jest podobnie jak w mojej wersji i pętla
for
iteruje po wszystkich elementach listy. - Wewnątrz pętli zamieniam
znak
w liczbę… - … i dodaję tą liczbę do listy cyfr. Dzięki temu otrzymam listę z cyframi. W tym zadaniu niespecjalnie się ona może przyda :), ale ogólna zasada podziału liczby na znaki może być pomocna.
- Sumę ten program liczy nie poprzez sumowanie każdego elementu w pętli, ale z wykorzystaniem wbudowanej w Pythona funkcji
sum()
działającej na elementach listy. Nie poznajemy przez to algorytmu sumowania, ale wynik będzie poprawny… - i wypisany na ekranie.
Oczywiście kod można skrócić nie tworząc zbędnych zmiennych tak:
liczba=1234567890 cyfry_tekstowo = list( str(liczba) ) cyfry_liczbowo = [] for element in cyfry_tekstowo: cyfry_liczbowo.append( int(element) ) print( sum(cyfry_liczbowo) )
Czysta matematyka
Powyższe rozwiązanie działa i na pewno można je zastosować. Jednak uczeń, a w szczególności maturzysta, powinien także poruszać się po matematycznych sferach algorytmów, a powyższe rozwiązanie jest takie niematematyczne i trochę toporne. Zajrzę więc do Królowej Nauk i zapiszę algorytm tak:
liczba ← wczytaj() suma ← 0 powtarzaj aż liczba wynosi 0: cyfra ← liczba mod 10 suma ← suma + cyfra liczba ← liczba div 10 gdzie: mod – reszta z dzielenia a div to dzielenie całkowite (z pominięciem ułamka)
Tradycyjnie spróbuję to zapisać w trzech maturalnych językach. Możesz czytelniku wybrać sobie jeden z opisów.
Implementacja w Pythonie
Ponieważ Python najbardziej odpowiada pseodokodowi, to na pierwszy ogień wrzucam tym razem węża. Aczkolwiek wąż zwiódł Ewę i później Adama, więc czynię to z pewną nieśmiałością.
liczba=1234567890 suma = 0 while liczba > 0: cyfra = liczba % 10 suma = suma + cyfra liczba = liczba // 10 print(suma)
lub w wersji z wrzucaniem cyfr do pythonowej listy (patrz wyjaśnienia dla przykładu pythonowego rozdziale z gwiazdką):
liczba=1234567890 cyfry_liczbowo = [] while liczba > 0: cyfra = liczba % 10 cyfry_liczbowo.append( cyfra ) liczba = liczba // 10 print(sum(cyfry_liczbowo))
- Niezależnie od wersji, najpierw pozyskuję liczbę.
- Teraz albo zeruję sumę (wersja pierwsza) albo tworzę pustą listę
cyfry_liczbowo
. - W pętli będę tak długo wyodrębniał cyfry, aż liczba zostanie wyzerowana. Tym razem wyodrębnianie będzie miało miejsce od końca! W algorytmie z zamianą na tekst cyfry były brane od lewej do prawej. Teraz odwrotnie.
- w czwartej linii wyznaczam resztę z dzielenia przez 10 (w pseudokodzie lub w arkuszu kalkulacyjnym nazywa się to najczęściej
mod
od angielskiego modulo. Natomiast w językach programowania zazwyczaj resztę z dzielenia uzyskuje się znaczkiem %. W przypadku dowolnej liczby, reszta z dzielenia przez 10, to jest ostatnia cyfra, prawda? Dla 123 dzielonego przez 10 reszta wynosi 3. Dla 170 reszta to 0. Czyli tu pozyskałem ostatnią cyfrę. - Teraz albo dorzucam pozyskaną cyfrę do sumy (wersja 1 programu) albo do listy (wersja 2)
- W szóstej linii nadszedł czas na wyrzucenie tej ostatniej cyfry. Mogę tego dokonać dzieląc w ciele liczb całkowitych tę liczbę przez 10. Przykładowo 123 podzielone na 10 to 12,3, ale po odrzuceniu ułamka, zostaje 12. W Pythonie dzielenie całkowite obsługuje operator
//
. - I teraz, poza konkursem, w ostatniej linii wypisuję sumę cyfr. Albo policzoną samodzielnie (wersja 1) albo korzystając z funkcji
sum()
Implementacja w Jawie
int liczba=1234567890; int suma = 0; while (liczba > 0) { int cyfra = liczba % 10; suma = suma + cyfra; liczba = liczba / 10; } System.out.println(suma);
Jawowy zapis wersji matematycznej jest bardzo podobny do wersji Pythonowej. Można się także pokusić o wersję z listą cyfr. Ta wersja wymaga dodania wcześniej
import java.util.ArrayList;
na górze pliku z kodem. A następnie, wewnątrz funkcji main() można wykorzystać listę tak:
int liczba=1234567890; ją ArrayList<Integer> cyfryLiczbowo = new ArrayList<Integer>(); while (liczba > 0) { int cyfra = liczba % 10; cyfryLiczbowo.add( cyfra ); liczba = liczba / 10; } int suma = 0; for(Integer cyfra : cyfryLiczbowo) { suma += cyfra; } System.out.println(suma);
Dlaczego taka wersja z listą? Dlatego, że w niektórych zadaniach taka lista może się przydać. Mój przykład sumuje elementy, więc lista jest zdecydowanie nadmiarowa. Ale wprowadzam ją dla pokazania tego mechanizmu jej działania.
- Niezależnie od wersji, najpierw pozyskuję liczbę.
- Teraz albo zeruję sumę (wersja pierwsza) albo tworzę pustą listę
cyfryLiczbowo
. Lista w Jawie wygląda trochę przerażająco, gdyż wymaga podawania typów zawartości. - W pętli będę tak długo wyodrębniał cyfry, aż liczba zostanie wyzerowana. Tym razem wyodrębnianie będzie miało miejsce od końca! W algorytmie z zamianą na tekst cyfry były brane od lewej do prawej. Teraz odwrotnie.
- W czwartej linii wyznaczam resztę z dzielenia przez 10 (w pseudokodzie lub w arkuszu kalkulacyjnym nazywa się to najczęściej
mod
od angielskiego modulo. Natomiast w językach programowania zazwyczaj resztę z dzielenia uzyskuje się znaczkiem %. W przypadku dowolnej liczby, reszta z dzielenia przez 10, to jest ostatnia cyfra, prawda? Dla 123 dzielonego przez 10 reszta wynosi 3. Dla 170 reszta to 0. Czyli tu pozyskałem ostatnią cyfrę. - Teraz albo dorzucam pozyskaną cyfrę do sumy (wersja 1 programu) albo do listy (wersja 2)
- W szóstej linii nadszedł czas na wyrzucenie tej ostatniej cyfry. Mogę tego dokonać dzieląc w ciele liczb całkowitych tę liczbę przez 10. Przykładowo 123 podzielone na 10 to 12,3, ale po odrzuceniu ułamka, zostaje 12. W Pythonie dzielenie całkowite obsługuje operator
//
, ale w Jawie nie jest potrzebny oddzielny operator, bo typ zmiennej liczba jest typem int, czyli całkowitym i Java sama obetnie ułamek. - W siódmej linii kończy się blok pętli.
- I teraz, poza konkursem, wypisuję sumę cyfr. Albo policzoną samodzielnie w pętli (wersja 1) albo sumując na końcu zawartości listy oddzielną pętlą. Myślę, że na tym etapie warto wyjaśnić co się dzieje w liniach 9-10-11 w przypadku wersji 2.
- Pętla
for
w Jawie nie ma tylko budowy odziedziczonej z języków C/++, ale także ma postać właśnie taką, która jest np. charakterystyczna dla Pythona, czyli wersję, w której zmienna sterująca pętli (w tym przypadkucyfra
) przyjmuje kolejne wartości ze zbioru (w tym przypadkuArrayList
). Ponieważ jednak Java wymaga podawania typów, a moja pętla ma biegać po elementach listy Integerów, to również cyfra jest typuInteger
. - W linii dziesiątej stosuję skrócony zapis
suma += cyfra
, który można również zapisać jakosuma = suma + cyfra
, czyli jako zwiększenie sumy o wartość zmiennejcyfra
. - Ostatnia linia to już formalność – wypisanie sumy na konsoli.
Java z gwiazdką
Parę słów chciałbym jeszcze dodać o linijce:
ArrayList<Integer> cyfryLiczbowo = new ArrayList<Integer>();
Która po pierwsze wygląda nieco zawile, a po drugie zawiera typ Integer
, podczas gdy do tej pory raczej stosowałem int
.
Zacznę od wyjaśnienia różnicy pomiędzy int
a Integer
. Otóż, w Jawie prawie wszystko jest obiektem. Obiektem, czyli typem, który zawiera w sobie dane oraz metody (funkcje).
Prawie wszystko, dlatego że Java odziedziczyła po językach C/C++ typy proste takie jak int
, double
, char
, boolean
. Typy te zawierają w sobie wyłącznie dane (int – liczby całkowite, double – liczby rzeczywiste, char – znaki, boolean – wartości logiczne prawda/fałsz).
Jednak Java dostarcza również obiektowe odpowiedniki tych typów, czyli Integer
, Double
, Character
, Boolean
. Zajmują one więcej pamięci i są wolniejsze w działaniu, dlatego nie należy ich używać tam, gdzie nie jest to konieczne. Typy te zawierają w sobie nie tylko dane, ale również powiązane z nimi metody.
W przypadku ArrayList
, czyli listy elementów, musi mieć ona podane jakie elementy zawiera. Stąd zapis pełny to ArrayList<Integer>
albo ArrayList<Double>
itp. Przy czym, elementami składowymi ArrayList muszą być już obiekty, a nie typy proste. I dlatego zapis ArrayList<int>
będzie błędny!
Z tego samego powodu pętla sumująca również używa Integera:
for(Integer cyfra : cyfryLiczbowo) {
gdyż zmienna cyfra musi przyjmować wartość kolejnych elementów listy.
Implementacja w C++
Trzeci maturalny język to C++, więc tłumaczę teraz pseudokod na ten język.
Tak będzie wyglądała wersja prosta, z sumowaniem w pętli, zgodna z pseudokodem:
int liczba=1234567890; int suma = 0; while (liczba > 0) { int cyfra = liczba % 10; suma = suma + cyfra; liczba = liczba / 10; } cout << suma << endl;
- Najpierw pozyskuję liczbę.
- Teraz zeruję sumę.
- W pętli będę tak długo wyodrębniał cyfry, aż liczba zostanie wyzerowana. Tym razem wyodrębnianie będzie miało miejsce od końca! W algorytmie z zamianą na tekst cyfry były brane od lewej do prawej. Teraz odwrotnie.
- W czwartej linii wyznaczam resztę z dzielenia przez 10 (w pseudokodzie lub w arkuszu kalkulacyjnym nazywa się to najczęściej
mod
od angielskiego modulo. Natomiast w językach programowania zazwyczaj resztę z dzielenia uzyskuje się znaczkiem %. W przypadku dowolnej liczby, reszta z dzielenia przez 10, to jest ostatnia cyfra, prawda? Dla 123 dzielonego przez 10 reszta wynosi 3. Dla 170 reszta to 0. Czyli tu pozyskałem ostatnią cyfrę. - Teraz albo dorzucam pozyskaną cyfrę do sumy
- W szóstej linii nadszedł czas na wyrzucenie tej ostatniej cyfry. Mogę tego dokonać dzieląc w ciele liczb całkowitych tę liczbę przez 10. Przykładowo 123 podzielone na 10 to 12,3, ale po odrzuceniu ułamka, zostaje 12. W Pythonie dzielenie całkowite obsługuje operator
//
, ale C++ nie jest potrzebny oddzielny operator, bo typ zmiennej liczba jest typem int, czyli całkowitym i C++ samo obetnie ułamek. - W siódmej linii kończy się blok pętli.
- I teraz, poza konkursem, wypisuję sumę cyfr.
C++ z gwiazdką
Ponieważ jednak w poprzednich przykładach (dla Pythona i Jawy) użyłem list, to tutaj również chciałbym pokazać wersję nieco rozbudowaną. Oczywiście w C++ można również zastosować rozwiązanie ze zbieraniem tych cyfr do zmiennej typu vector (którą wcześniej trzeba dołączyć poleceniem: #include <vector>
). Wtedy program może wyglądać np. tak:
int liczba=1234567890; std::vector<int> cyfryLiczbowo; while (liczba > 0) { int cyfra = liczba % 10; cyfryLiczbowo.push_back(cyfra); liczba = liczba / 10; } int suma = 0; for (auto it = cyfryLiczbowo.begin(); it != cyfryLiczbowo.end(); it++) suma = suma + *it ; std::cout << suma << std::endl;
Tym razem, w linii 5, zamiast sumować oddzielnie elementy, wrzucam je wszystkie do wektora. Jak działa taka struktura danych? Otóż w linii 2 jest zapis:
std::vector<int> cyfryLiczbowo;
który tworzy zmienną o nazwie cyfryLiczbowo
zawierającą elementy typu int. Coś w rodzaju takiej bardziej rozbudowanej tablicy. Następnie w linii 5 mam zapis:
cyfryLiczbowo.push_back(cyfra);
który dodaje cyfrę na koniec zestawu danych.
Najbardziej kłopotliwe jest chyba samo sumowanie, gdyż jest to dość rozbudowany zapis stylu języka C++. W szczególności denerwująca może być linijka:
for (auto it = cyfryLiczbowo.cbegin(); it != cyfryLiczbowo.cend(); it++)
którą spróbuję rozbić na czynniki pierwsze.
Znasz zapewne pętlę for o budowie for(prolog; warunek; epilog)
. Tutaj są te same elementy
- prolog:
auto it = cyfryLiczbowo.cbegin()
- warunek:
it != cyfryLiczbowo.cend()
- epilog:
it++
Zacznę od końca. Epilog, czyli it++ nie wygląda źle. W typowej szkolnej pętli for znajdujesz zazwyczaj takie polecenie, które zwiększa zmienną it o 1. Tu co prawda nie jest to takie matematyczne 1, a przesunięcie się na Następny Element, ale koncepcyjnie mniej więcej o to samo chodzi. Więc na razie jest dobrze. Już wiadomo, że pętla ta będzie miała zmienną it, która się będzie się przesuwała na następny element w każdym przebiegu pętli.
Teraz warunek. it != cyfryLiczbowo.cend()
oznacza sprawdzanie czy it jest różny (!=
) od końca wektora (vector nazywa się cyfryLiczbowo
a jego metoda cend()
zwraca po prostu koniec zestawu danych. Jednym słowem, pętla będzie się wykonywała przez cały czas, przez jaki zmienna it będzie różna od końca. Nie wiemy w sumie po ilu przebiegach ten koniec nastąpi, więc pętla bardziej zachowuje się jak while(…)
niż jak for(…)
, ale w C++ to możliwe.
Na razie jest więc prosto. Mamy pętlę, która zwiększa zmienną it o 1 (a w zasadzie przesuwa ją na następny element) i która zakończy działanie, gdy zmienna it dotrze do ostatniego elementu listy. A skoro tak, to jeszcze musimy określić czym jest ta zmienna oraz nadać jej początkową wartość. I tu wkracza do akcji prolog pętli for. Czyli instrukcja, która wykonuje się jeden raz, przed uruchomieniem pętli. W tym przypadku mamy prolog: auto it = cyfryLiczbowo.begin()
. I nadal patrząc od końca, widzimy, że zmienna it ustawiana jest na pierwszy element listy: it = cyfryLiczbowo.cbegin()
. Tylko jakiego typu jest ta zmienna? Zazwyczaj mamy w pętli for coś w rodzaju int i = 0;
, a teraz nie ma tam prostego int, tylko złożona typ auto
, który mówi, że it będzie iteratorem (Iterator – obiekt pozwalający na sekwencyjny dostęp do wszystkich elementów […] zawartych w innym obiekcie, zwykle […] liście) o typie dobranym tak, aby aby mógł być iteratorem kolejnych elementów zawartych w tej liście (która się nazywa w C++ vector).
Czyniąc długą opowieść krótką, pętla ta ma zmienną it, co jest skrótem od słowa iterator. Zmienna ta jest iteratorem po zestawie liczb całkowitych i z każdym przebiegiem pętli przeskakuje na kolejny element, aż dotrze do końca zestawu.
Dalej już jest prosto i linijka sumująca korzysta po prostu ze zmiennej it. Jedynie warto zauważyć, że jest tam operator *, gdyż samo it jako takie zachowuje się jak wskaźnik na element i operator * pozwoli wyłuskać wskazywany element.
Podsumowanie
W ten sposób przedstawiłem algorytm wyłuskiwania cyfr z liczby w dwóch wersjach podstawowych oraz kilku podwersjach i zaimplementowałem go w trzech maturalnych językach. Mam nadzieję, że takie kompleksowe porównanie pozwoli na zapoznanie się z algorytmem oraz porównanie różnic w jego implementacji.
Jeżeli nadal masz jakieś pytania albo wątpliwości, zachęcam do ich wyrażania w komentarzach pod artykułem, albo na specjalnej grupie Facebookowej: edukacja gwarantowana, informatyka bez problemu zdana
Przemysław Adam Śmiejek
Wersja wideo
Wersja filmowa artykułu w przygotowaniu.