beatagmys@o2.pl pgmys@o2.pl

Informatyka rozszerzona

  1. Informatyka rozszerzona
  2. Klasa II

Wiesz umiesz zdasz


ZADANIA

ZADANIE 1 (d22)
plik przykładowy
plik do zadania

W pliku p20_1.txt zapisano 100 nieparzystych liczb całkowitych z przedziału [10, 9999].
Liczby w pliku mogą się powtarzać.
Odbiciem dodatniej nieparzystej liczby całkowitej n nazywamy taką liczbę N, w której zapisie dziesiętnym nastąpiło odwrócenie kolejności cyfr.

Przykład:
Odbiciem liczby 2019 jest 9102, natomiast odbiciem liczby 12345 jest 54321.

Napisz program (lub kilka programów), który(-e) znajdzie(-dą) odpowiedzi na poniższe pytania. Każdą odpowiedź zapisz w pliku wyniki.txt i poprzedź ją numerem oznaczającym zadanie.
Do dyspozycji masz również plik przykładowy- p20_p1.txt zawierający tylko 11 nieparzystych liczb całkowitych z przedziału [10, 9999] – odpowiedzi dla tego pliku podane są w treściach zadań, możesz sprawdzać na nim działanie swojego programu.

Uwaga: Pamiętaj, że Twój program (lub kilka programów) musi(-szą) ostatecznie działać dla 100 liczb zapisanych w pliku liczby.txt.

Pytanie 1

Wyznacz odbicia wszystkich liczb z pliku liczby.txt. Wypisz te odbicia, które są podzielne przez 17.
Dla pliku przyklad.txt odpowiedzią jest 51.

Pytanie 2

Dla każdej liczby z pliku p20_1.txt oblicz wartość bezwzględną różnicy tej liczby i jej odbicia.
Wyznacz taką liczbę n, dla której wartość bezwzględna różnicy tej liczby i jej odbicia jest największa. Podaj tę liczbę oraz wartość bezwzględną różnicy tej liczby i jej odbicia.
W pliku p20_1.txt jest tylko jedna taka liczba.
Dla pliku przykładowym.txt odpowiedzią jest 741 594.

Pytanie 3

Wypisz wszystkie liczby pierwsze z pliku p20_1.txt, których odbicia również są liczbami pierwszymi, każdą w oddzielnym wierszu.
Dla pliku przykładowego odpowiedź to:
13
131

(odbiciem liczby 13 jest 31 – obie są liczbami pierwszymi, odbiciem 131 jest 131)

Podaj:

  • ile różnych liczb zapisano w pliku liczby.txt
  • ile liczb powtarza się dokładnie dwa razy w pliku liczby.txt
  • ile liczb powtarza się dokładnie trzy razy w pliku liczby.txt. Dla pliku przykładowego odpowiedzią jest 10 1 0.


    ZADANIE 2 (d201)
    plik do zadania

    W pliku p20_p2.txt zapisano 5000 wierszy zawierających w każdym wierszu dwie liczby (x, y) oraz znak.
    Liczby w pliku mogą się powtarzać.
    Napisz program/programy, które po wczytaniu pliku z danymi wypiszą odpowiedzi na poniższe pytania.

    Pytanie 1

    Ile razy wystąpił znak najczęściej się powtarzajacy

    Pytanie 2

    Zakładając iż pierwsza liczba jest współrzędną X, a druga liczba współrzędną Y wyznacz największą odległość punktu (x,y) od początku ukłądu współrzędnych (liczba rzeczywista) OXY oraz wyznacz liczbę takich pnktów.

    Pytanie 3

    Zakładając iż pierwsza liczba jest współrzędną X, a druga liczba współrzędną Y wyznacz ile punktów o współrzędnych (x,y) znajduje się w I ćwiartce przy założeniu, że odpowiada im litera A lub B (litera zapisana w tym samym wierszu)

    Pytanie 4

    Podaj ile w pliku jest łącznie liczb ujemnych


    ZADANIE 3 (interpretowane)
    plik do zadania

    W pliku p20_3.txt znajduje się 1000 wierszy. Każdy wiersz zawiera liczbę binarną,składającą się z maksymalnie 14 cyfr: 0 lub 1. Każda liczba zaczyna się jedynką i żadna z nich się nie powtarza.
    Napisz program(y), który(-e) da(-dzą) odpowiedzi do podanych zadań. Odpowiedzi do zadań zapisz w pliku wyniki4.txt, a każdą z nich poprzedź numerem odpowiedniego zadania lub wyświetl na ekranie komputera.

    Pytanie 1

    Liczbę binarną nazywamy zrównoważoną, gdy zawiera tyle samo zer i jedynek, natomiast prawie zrównoważoną, gdy liczba jedynek różni się od liczby zer o 1.
    Przykład:
    Liczba 101010 jest liczbą zrównoważoną.
    Liczba 1011010 jest liczbą prawie zrównoważoną.
    Podaj, ile jest liczb binarnych prawie zrównoważonych 5-cyfrowych i liczb zrównoważonych 8-cyfrowych w pliku.

    Pytanie 2

    Anagramy cyfrowe to liczby utworzone z tego samego zestawu cyfr w różnych kolejnościach. Przy tym pierwsza cyfra liczby nie może być równa zero.
    Przykład:
    Z liczby 209 zapisanej dziesiętnie można utworzyć 4 anagramy: 209, 290, 902, 920.
    Z liczby dwójkowej 11100 można utworzyć 6 różnych anagramów: 10011, 10101, 10110, 11001, 11010, 11100.
    Wyznacz liczbę anagramów występujących w pliku dla liczby dwójkowej 5-cyfrowej oraz 8-cyfrowej

    Pytanie 3

    Podaj największą wartość bezwzględną różnicy między sąsiednimi liczbami zapisanymi w pliku anagram.txt (to jest liczbami zapisanymi w sąsiednich wierszach pliku np. 2 i 3 wierszu, 3 i 4 wierszu itd.). Tę wartość podaj w zapisie binarnym.

    Pytanie 4

    Zamień wszystkie liczby binarne z pliku anagram.txt na ich odpowiedniki w systemie dziesiętnym. Następnie spośród otrzymanych liczb dziesiętnych: a) podaj, ile jest takich, w których nie występuje cyfra 1 b) podaj liczbę, która ma największą sumę cyfr (jeśli liczb, które mają tę samą największą sumę różnych cyfr, jest więcej niż jedna – podaj tę, która występuje jako ostatnia w pliku z danymi). Przykład:
    Dla liczby 20462 suma jej cyfr to 14 (2+0+4+6+2), dla liczby 344 suma cyfr to 11.


    ZADANIE 4 (interpretowane p2015)
    plik do zadania

    Powiemy, że dwie liczby naturalne a i b są anagramami cyfrowymi, jeśli liczbę a (symetrycznie b) można zapisać dziesiętnie za pomocą cyfr występujących w zapisie dziesiętnym liczby b (symetrycznie a), używając każdej cyfry dokładnie tyle razy, ile razy występuje w zapisie b (symetrycznie w zapisie a).
    Uwaga: przyjmujemy, że w zapisie dziesiętnym żadnej liczby nie ma nieznaczących 0, co oznacza, że 0 występuje na najbardziej znaczącej pozycji tylko w zapisie liczby zero.
    W pliku p20_4.txt znajduje się 1000 par liczb całkowitych dodatnich, z których każda jest nie większa niż 2000000. Każda para liczb jest zapisana w osobnym wierszu. Liczby w wierszu są oddzielone pojedynczym znakiem odstępu.

    Napisz program(-y), który poda odpowiedzi na następujące pytania.
    Odpowiedź do każdego pytania podaj w osobnym wierszu, poprzedzając ją identyfikatorem (numerem pytania).
    Przykład
    Załóżmy, że w pliku dane_anagramy.txt mamy następujące dane:
    232 322 112 111 223 121 223 322 Wiersze, pierwszy i ostatni, zawierają anagramy cyfrowe. W pliku dane_anagramy.txt znajdziemy maksymalnie 5 liczb, z których każde dwie to anagramy cyfrowe: 232, 322, 223, 223, 322. Do oceny oddajesz plik (pliki) z kodem (kodami) źródłowym (źródłowymi) swojego programu (swoich programów) oraz plik wyniki_anagramy.txt zawierający odpowiedzi na pytania a) i b).

    Pytanie 1

    a) W ilu wierszach pliku p20_4.txt zapisane w nich liczby to anagramy cyfrowe?

    Pytanie 2

    b) Ile jest liczb przynajmniej dwucyfrowych zapisanych w pliku p20_4.txt, których cyfry - rozpoczynając od wiodącej tworzą ciąg niemalejący?
    Uwaga: ciąg niemalejący oznacza iż każda kolejna cyfra jest większa bądź równa poprzedniej np.: 11234 spełnia kryteria zadania
    Liczba 122134 - nie spełnia

    Pytanie 3

    Znajdź różnicę pomiędzy największą i najniejsza liczbą.

    Pytanie 4

    Wypisz liczbę, która która posiada największa liczbę dzielników.
    Dzilnikiem nazywamy każdą liczbę naturalną większą od 0, która dzieli daną liczbę bez reszty.
    np.: dzielniki liczby 12 to: 1, 2, 3, 4, 6 i 12, zatem jest 6 dzielników




    • Zadania



    1. Napisz program wypisujący najdłuższy spójny podciąg malejący ciągu n liczb całkowitych.
    2. Napisz program, który wypisze najdłuższy spójny podciąg rosnący ciągu n liczb całkowitych, a w przypadku występowania więcej niż jednego najdłuższego podciągu wypisze ostatni znaleziony.
    3. Napisz program, który wypisze najdłuższy spójny podciąg rosnący ciągu n liczb całkowitych, a w przypadku występowania więcej niż jednego najdłuższego podciągu wypisze wszystkie.
    4. Napisz program wypisujący najdłuższy podciąg spójny złożony z liczb całkowitych dodatnich ciągu n liczb całkowitych. Wykorzystaj w nim funkcję losującą tablicę tak, aby występowały w niej zarówno liczby dodatnie, jak i ujemne.
    5. Napisz program znajdujący maksymalną sumę podciągu spójnego ciągu n liczb całkowitych, w którym mogą wystąpić same liczby ujemne. Program napisz tak, żeby przejrzał tablicę co najwyżej dwa razy.
    6. Napisz program wyznaczający w ciągu n liczb całkowitych liczbę podciągów spójnych o podanej (wczytanej) sumie. Program napisz tak, aby wykonywał jak najmniej operacji.
    7. Napisz program wypisujący z ciągu n liczb całkowitych wszystkie podciągi spójne o podanej (wczytanej) sumie. Program napisz tak, aby wykonywał jak najmniej operacji.




    Podsumowanie



  • Podciąg to wybrane wyrazy ciągu zachowujące kolejność występowania.
  • Podciąg spójny to taki podciąg, którego wyrazy w ciągu wyjściowym występują obok siebie.
  • Podciąg niemalejący to taki podciąg, w którym każdy kolejny element jest większy lub równy poprzedniemu.
  • Żeby znaleźć spójny podciąg niemalejący, wystarczy raz przejrzeć elementy ciągu.
  • Algorytmy znajdowania maksymalnej sumy podciągu analizujące wszystkie możliwe sumy podciągów mają złożoność czasową O(n3) lub O(n2).
  • Istnieje algorytm liniowy O(n), który znajduje maksymalną sumę podciągu spójnego.
  • Nie analizuje on wszystkich podciągów. Kiedy suma aktualnie badanego podciągu nie jest dodatnia, rozpoczyna badanie kolejnego podciągu od następnego elementu.
  • Jeśli funkcja ma zwrócić więcej niż jedną wartość typu prostego, warto zastosować przekazanie parametru przez referencję.

    • Najdłuższy spójny podciąg ciągu binarnego

    https://pl.spoj.com/problems/AL_03_02/



    Zadanie 2 - Najdłuższy podciąg różnowartościowy

    https://pl.spoj.com/problems/FR_02_17/



    Zadanie 3 - Długość najdłuższego wspólnego podciągu (podsłowa)

    https://pl.spoj.com/problems/LENLCS/



    Zadanie 4 - Sok jabłkowy

    https://pl.spoj.com/problems/FR_10_09/



    Zadanie 5 - Ciąg arytmetyczny

    https://pl.spoj.com/problems/AL_20_02/





    Zadania
  • W kolejnych wierszach pliku cyfry.txt znajduje się 1000 liczb naturalnych, mniejszych niż 109 (jeden miliard), po jednej liczbie w każdym wierszu.
    Napisz program, który Wypisz wszystkie liczby z pliku p18a.txt, których cyfry tworzą ciąg rosnący.
    Przykład:
    Cyfry liczby 123579 tworzą ciąg rosnący, ponieważ 1<2<3<5<7<9.
    Cyfry liczby 1232 nie tworzą ciągu rosnącego, ponieważ ostatnia cyfra (2) nie jest większa od przedostatniej (3).
    Cyfry liczby 34556 nie tworzą ciągu rosnącego, ponieważ cyfra trzecia (5) i cyfra czwarta (5) są sobie równe.

    • Zadanie - najlepsze sumy


    treść zadania
    dane do zadania
    Odpowiedzi:
    Przykładowe rozwiązania oraz komentarze do wybranych ćwiczeń i zadań
  • Wkrótce