Zadanie 1. Liczby (12 pkt)

W pliku liczby.txt zapisano 500 liczb całkowitych dodatnich, po jednej w każdym wierszu. Każda liczba należy do zakresu $<1, 100000>$.

Napisz program(y) dający(e) odpowiedzi do poniższych zadań. Zapisz uzyskane odpowiedzi w pliku wyniki.txt, poprzedzając każdą z nich numerem odpowiedniego zadania.

Uwaga: Plik przyklad.txt zawiera przykładowe dane spełniające warunki zadania. Odpowiedzi dla danych z tego pliku są podane pod treściami zadań.

Zadanie 1.1 (3 pkt)

Podaj, ile z podanych liczb jest potęgą liczby $3$ (czyli liczbami postaci $1 = 3^0$, $3 = 3^1$, $9 = 3^2$ itd.).

Dla pliku przyklad.txt odpowiedź wynosi $2$.

Do oceny oddajesz:

• plik wyniki.txt zawierający poprzedzoną numerem zadania odpowiedź (informację, ile liczb jest potęgami liczby $3$);

• plik(i) z komputerową realizacją zadania (kodem programu).

Rozwiązanie

Zanim przystąpimy do rozwiązania, musimy się zastanowić, ile liczb w zadanym zakresie zadania (czyli $<1, 100000>$) jest potęgami liczby $3$. Dla ułatwienia możemy je wypisać:

Jak widzimy, takich liczb mamy $11$ (liczba $3^{11}$ wykracza poza zakres).

Pisanie programu zaczniemy od utworzenia tablicy liczb naturalnych o nazwie liczby oraz wczytania do niej zawartości pliku liczby.txt. Tablica będzie składać się z $500$ elementów.

liczby[500] ← wczytaj dane z pliku "liczby.txt"

W następnym kroku utworzymy zmienną ile, którą zainicjalizujemy wartością $0$. Zmienna ta będzie inkrementowana za każdym razem, gdy znajdziemy liczbę będącą potęgą trójki.

liczby[500] ← wczytaj dane z pliku "liczby.txt"

ile ← 0

Zapiszemy pętlę dla, której zadaniem będzie iterowanie przez wszystkie indeksy w liście liczby.

liczby[500] ← wczytaj dane z pliku "liczby.txt"

ile ← 0

dla i = 0, 1, ..., długość(liczby) - 1

Dla każdego indeksu inicjalizować będziemy zmienną potega wartością 1.

liczby[500] ← wczytaj dane z pliku "liczby.txt"

ile ← 0

dla i = 0, 1, ..., długość(liczby) - 1
	potega ← 1

Następnie wewnątrz pętli dla zapisujemy pętlę dopóki. Pętla będzie wykonywać się, dopóki zmienna potega jest mniejsza od wartości liczby[i] lub jej równa.

liczby[500] ← wczytaj dane z pliku "liczby.txt"

ile ← 0

dla i = 0, 1, ..., długość(liczby) - 1
    potega ← 1
    dopóki potega <= liczby[i] wykonuj
   

W kolejnym kroku wewnątrz pętli dopóki zapisujemy instrukcję warunkową. Będzie ona sprawdzać, czy wartość zmiennej potega jest równa wartości liczby[i]. Jeżeli instrukcja zwróci wartość prawda, zmienna ile będzie inkrementowana o $1$, a pętla dopóki zostanie przerwana.

W przeciwnym razie wartość zmiennej potega będzie mnożona razy $3$, a pętla będzie wykonywać się dalej.

liczby[500] ← wczytaj dane z pliku "liczby.txt"

ile ← 0

dla i = 0, 1, ..., długość(liczby) - 1
    potega ← 1
    dopóki potega <= liczby[i] wykonuj
        jeżeli potega = liczby[i]
            ile ← ile + 1
            przerwij
        w przeciwnym razie
            potega ← potega * 3

Po zakończeniu wszystkich iteracji pętli należy wypisać wartość zmiennej ile.

liczby[500] ← wczytaj dane z pliku "liczby.txt"

ile ← 0

dla i = 0, 1, ..., długość(liczby) - 1
    potega ← 1
    dopóki potega <= liczby[i] wykonuj
        jeżeli potega = liczby[i]
            ile ← ile + 1
            przerwij
        w przeciwnym razie
            potega ← potega * 3

wypisz ile

Poprawna odpowiedź: $18$

Schemat oceniania:

• $3$ pkt – za podanie poprawnej odpowiedzi;

• $2$ pkt – za podanie wyniku różniącego się o $1$ (np. w przypadku pominięcia liczby $1=3^0$ lub liczenia od $0$ zamiast od $1$);

• $1$ pkt – za podanie wyniku mniejszego od prawidłowego o $2$ lub $3$ (w przypadku pominięcia przy zliczaniu maksymalnie trzech liczb);

• $0$ pkt – za błędną odpowiedź lub brak odpowiedzi.

Zadanie 1.2 (4 pkt)

Silnią liczby naturalnej $k$ większej od $0$ nazywamy wartość iloczynu $1·2·\dots ·k$ i oznaczamy przez $k!$.
Przyjmijmy, że $0!=1$. Zatem mamy:

Dowolną liczbę naturalną możemy rozbić na cyfry, a następnie obliczyć sumę silni jej cyfr. Na przykład dla liczby $343$ mamy $3!+4!+3!=6+24+6=36$.

Podaj, w kolejności ich występowania w pliku liczby.txt, wszystkie liczby, które są równe sumie silni swoich cyfr.

W pliku przyklad.txt znajduje się jedna taka liczba: $145$ $\left(1!+4!+5!=1+24+120=145\right)$.

Do oceny oddajesz:

• plik wyniki.txt zawierający poprzedzoną numerem zadania odpowiedź (wszystkie liczby z pliku, które są równe sumie silni swoich cyfr);

• plik(i) z komputerową realizacją zadania (kodem programu).

Rozwiązanie

Rozwiązanie zacznijmy od stworzenia pętli dla. Jej zadaniem będzie wskazanie kolejnych liczb z tablicy liczby. Wewnątrz pętli pobieramy do zmiennej liczba aktualnie przetwarzaną liczbę oraz tworzymy zmienną pomocniczą sumaSilni, którą inicjalizujemy wartością $0$.

 dla i = 0, 1 ..., długość(liczby) - 1 wykonuj:
    liczba ← liczby[i]
    sumaSilni ← 0

Zależy nam na przetwarzaniu kolejnych cyfr tworzących badaną liczbę. Zastosujemy więc algorytm, którego zadaniem będzie wyodrębnianie kolejnych cyfr. Nie znamy ich liczby, wiemy natomiast, że operację chcemy powtarzać wielokrotnie. Napiszemy pętlę dopóki, która będzie wykonywać się do czasu, aż liczba stanie się równa $0$. Wewnątrz pętli przypisujemy do zmiennej cyfra wartość wyrażenia liczba % 10, pobierając w ten sposób cyfrę jedności. Zmiennej liczba przypisujemy wynik dzielenia całkowitoliczbowego: liczba = liczba div 10.

 dla i = 0, 1 ..., długość(liczby) - 1 wykonuj:
    liczba ← liczby[i]
    sumaSilni ← 0
    dopóki liczba != 0 wykonuj:
        cyfra ← liczba % 10

        ...

        liczba ← liczba div 10

Pozostało obliczyć wartość silni poszczególnych cyfr oraz ich sumę. Wewnątrz pętli dopóki tworzymy zmienną pomocniczą silnia, którą inicjalizujemy wartością $1$. Tworzymy pętlę dla, której iterator j będzie przyjmował wartości z zakresu $<1, \mathrm{cyfra}>$. Wewnątrz pętli dla do zmiennej silnia zapisujemy jej iloczyn z iteratorem j.

 dla i = 0, 1 ..., długość(liczby) - 1 wykonuj:
    liczba ← liczby[i]
    sumaSilni ← 0
    dopóki liczba != 0 wykonuj:
        cyfra ← liczba % 10

        silnia ← 1
        dla j = 1, 2, ..., cyfra wykonuj:
            silnia ← silnia * j
        
        ...

        liczba ← liczba div 10

Wewnątrz pętli dopóki dopisujemy instrukcję dodającą do zmiennej sumaSilni wartość zmiennej silnia.

 dla i = 0, 1 ..., długość(liczby) - 1 wykonuj:
    liczba ← liczby[i]
    sumaSilni ← 0
    dopóki liczba != 0 wykonuj:
        cyfra ← liczba % 10

        silnia ← 1
        dla j = 1, 2, ..., cyfra wykonuj:
            silnia ← silnia * j
        
        sumaSilni ← sumaSilni + silnia

        liczba ← liczba div 10

Ostatnim brakującym elementem kodu jest wypisanie liczby, jeżeli suma silni jej poszczególnych cyfr jest jej równa. Wewnątrz zewnętrznej pętli dla dopisujemy odpowiednią instrukcję warunkową.

 dla i = 0, 1 ..., długość(liczby) - 1 wykonuj:
    liczba ← liczby[i]
    sumaSilni ← 0
    dopóki liczba != 0 wykonuj:
        cyfra ← liczba % 10

        silnia ← 1
        dla j = 1, 2, ..., cyfra wykonuj:
            silnia ← silnia * j
        
        sumaSilni ← sumaSilni + silnia

        liczba ← liczba div 10

    jeżeli sumaSilni = liczby[i] wykonaj:
        wypisz liczby[i]

Poprawna odpowiedź: $2$, $145$, $1$, $40585$

Schemat oceniania:

• $4$ pkt – za podanie prawidłowej odpowiedzi ($1$ pkt za każdą poprawnie podaną liczbę w wyniku);

• $0$ pkt – za błędną odpowiedź lub brak odpowiedzi.

Słownik

10 mod 6

10 % 6

9 % 2 = 1