Treść zadania
1
Napisz program obliczający sumę cyfr podanej liczby, np. 241 : 2+4+1=7.
2
Napisz program:
a) sprawdzający, czy podana liczba jest liczbą automorficzną, tj. znajdującą się na końcu swojego kwadratu, np. 6 jest taką liczbą, ponieważ 62=36.
b) znajdujący wszystkie liczby automorficzne należące do zadanego przedziału liczbowego (użytkownik podaje granice przedziału).
a) sprawdzający, czy podana liczba jest liczbą automorficzną, tj. znajdującą się na końcu swojego kwadratu, np. 6 jest taką liczbą, ponieważ 62=36.
b) znajdujący wszystkie liczby automorficzne należące do zadanego przedziału liczbowego (użytkownik podaje granice przedziału).
3
Napisz program znajdujący wszystkie liczby doskonałe w zadanym przedziale <a, b>, a, b są podawane przez użytkownika na wejściu programu. Liczba doskonała – liczba, która jest równa sumie wszystkich swoich dzielników właściwych (tj. mniejszych od siebie samej), np. 6 = 1+2+3.
4
Napisz program obliczający n - kolejnych wyrazów ciągu arytmetycznego oraz sumę S tych wyrazów. Użytkownik podaje pierwszy wyraz ciągu a1, różnicę r oraz liczbę wyrazów n. Suma S = (a1+an) × n/2.
5
Napisz program, który wczytuje z pliku elementy dwóch macierzy kwadratowych 5×5 i sumuje te macierze.
6
Napisz program, który wczytuje z klawiatury elementy macierzy 3×3 i oblicza sumę elementów głównej przekątnej tej macierzy.
7
Napisz program symulujący spacer mrówki Langtona. Mrówka Langtona jest przykładem deterministycznego chaosu. Wyobraźmy sobie nieskończoną kartkę w kratkę, po której chodzi mrówka. Mrówka wdeptując w białą kratkę maluje ją na czarno i skręca w prawo, natomiast jeśli wdepnie w czarną kratkę, to maluje ją na biało i skręca w lewo. Początkowo wszystkie kratki na kartce są białe. Po kilkudziesięciu krokach mrówki zauważymy, że pokolorowane przez nią kratki tworzą formę chaotyczną. Jednakże po ok. 10 tysiącach kroków mrówka zaczyna replikować pewien wzór tworząc tzw. autostradę.
Jeśli zamkniemy płaszczyznę, po której porusza się mrówka, to zmusimy ją do wchodzenia na swoje stare ślady. Kiedy mrówka budując autostradę napotka swoje ślady, regularny wzór znowu przekształci się w chaos ale następnie, po kilku tysiącach kroków, mrówka powróci do replikowania uporządkowanej struktury.
Należy napisać program symulujący bieganie mrówki i oszacować (obliczyć) w ilu krokach mrówka tworzy strukturę replikowaną podczas budowy autostrady („jedną cegiełkę”).
8
Należy napisać program znajdujący wszystkie liczby Amstronga w zadanym przedziale <a, b>. Liczba Amstronga jest liczbą równą sumie sześcianów swoich cyfr, np. 153: 13+53+33 = 153.
9
Napisz program znajdujący wszystkie dzielniki zadanej liczby.
10
Stwórz program znajdujący wszystkie wspólne podzielniki dwóch podanych liczb
11
Napisz program podający wszystkie liczby zaprzyjaźnione z przedziału <a, b>, gdzie a, b są liczbami naturalnymi oraz 0 <= a <= b. Użytkownik podaje na wejściu wartości a, b. Liczbami zaprzyjaźnionymi nazywamy parę liczb, dla której suma podzielników właściwych jednej z liczb (podzielników mniejszych od samej liczby) jest równa drugiej liczbie, a suma podzielników właściwych drugiej liczby jest równa pierwszej liczbie (np. 220 i 284, bo 1+2+4+5+10+11+20+22+44+55+110=284 oraz 1+2+4+71+142=220).
12
Napisz program obliczający największy wspólny podzielnik zbioru n liczb naturalnych. Użytkownik podaje wartość n, która ma być liczbą całkowitą z przedziału <0, 255>. Program powinien obliczać NWD dla liczb od 1 do n.
13
Napisz program obliczający statystyki dotyczące tekstu przeczytanego z pliku: ile jest cyfr (jaki procent tekstu stanowią), ile samogłosek, ile spółgłosek, jaka litera najczęściej się powtarza, ile jest (i jakich) znaków interpunkcyjnych itp.
14
Napisz program kodujący wprowadzony tekst zgodnie z alfabetem Morse’a. Użytkownik ma możliwość wyboru, czy chce zakodować na piśmie, czy w postaci migającego "światełka", czy dźwiękowo. Kodowany tekst jest wprowadzany z klawiatury lub odczytywany z pliku.
15
Napisz program wyznaczający liczbę i sumę liczb podzielnych przez 3 w zbiorze n liczb naturalnych. Na wejściu użytkownik podaje wartość n będącą liczbą całkowitą z przedziału <0, 255>. Program powinien obliczać w/w wartości dla zbioru liczb 1..n.
16
Napisz program podający wszystkie liczby Goldbacha z przedziału <a, b>, gdzie a, b są liczbami naturalnymi z przedziału <0, 255> podawanymi przez użytkownika. Liczbą Goldbacha nazywamy liczbę, którą można przedstawić jako sumę 2 liczb pierwszych (np. 14 = 11 + 3).
17
Należy zaimplementować algorytm szybkiego sortowania (Quicksort) na n–elementowym zbiorze liczb (10 <= n <= 200). Wczytać zbiór liczb z pliku. Dla danego zbioru obliczyć złożoność algorytmu i porównać ze średnią złożonością O(n log n).
Quicksort: ze zbioru liczb wybieramy jeden (j-ty) element. Pozostałe liczby dzielimy na dwa podzbiory: liczb mniejszych od j-tego elementu (wrzucamy je na lewo) i liczb większych od j-tej (wrzucamy je na prawo). Następnie każdy podzbiór sortujemy zgodnie z procedurą quicksort (rekurencja) itd.
Quicksort: ze zbioru liczb wybieramy jeden (j-ty) element. Pozostałe liczby dzielimy na dwa podzbiory: liczb mniejszych od j-tego elementu (wrzucamy je na lewo) i liczb większych od j-tej (wrzucamy je na prawo). Następnie każdy podzbiór sortujemy zgodnie z procedurą quicksort (rekurencja) itd.
18
Napisz program konwertujący liczby zapisane cyframi arabskimi do liczb w systemie rzymskim i odwrotnie. Bierzemy pod uwagę liczby całkowite
z przedziału (0, 4000) – w systemie rzymskim nie ma jednej ustalonej metody numerowania liczb większych od 3999.
z przedziału (0, 4000) – w systemie rzymskim nie ma jednej ustalonej metody numerowania liczb większych od 3999.
Poniżej podano oznaczenia systemu numeracji.
numeracja arabska: 1 5 10 50 100 500 1000
numeracja rzymska: I V X L C D M
19
Napisz program obliczający n-tą liczbę ciągu Fibonacciego, gdzie ciąg definiuje się następująco: F0=0, F1=1, Fn+2= Fn + Fn+1 (dla n = 1, 2, 3, ...). Użytkownik podaje liczbę n, gdzie n może być dowolną liczbą naturalną.
Kolejne wyrazy ciągu Fibonacciego przyjmują wartości: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...
20
Plik wejściowy zawiera n liczb (1 <= n <= 100). Napisz program, który wśród liczb z pliku wejściowego znajduje wszystkie pary liczb zaprzyjaźnionych (definicja liczb zaprzyjaźnionych w zad 11).
21
Napisz program, który dla temperatury podanej w stopniach Celsjusza oblicza odpowiednie wartości temperatury w skali Kelwina, Reaumura i Fahrenheita oraz odwrotnie (dla Kelwina – podaje stopnie Celsjusza, Reaumura i Fahrenheita itd.).
Fragment skali temperaturowej:
C -2 -1 0 1 2 3 4 5
R -1.6 -0.8 0.0 0.8 1.6 2.4 3.2 4.0
F 28.4 30.2 32.0 33.8 35.6 37.4 39.2 41.0
K 271.15 272.15 273.15 274.15 275.15 276.15 277.15 278.15
Fragment skali temperaturowej:
C -2 -1 0 1 2 3 4 5
R -1.6 -0.8 0.0 0.8 1.6 2.4 3.2 4.0
F 28.4 30.2 32.0 33.8 35.6 37.4 39.2 41.0
K 271.15 272.15 273.15 274.15 275.15 276.15 277.15 278.15
22
Napisz program, który zbiór n liczb całkowitych (6<n<200) dzieli na trzy podzbiory: podzbiór liczb niekompletnych, podzbiór liczb doskonałych i podzbiór liczb zasobnych. Liczby każdego podzbioru wyświetlane są po posortowaniu (rosnąco). Zbiór wejściowy wczytywany jest z pliku lub generowany losowo w programie.
Oznaczmy przez k pewną liczbę, przez s(k) – sumę wszystkich podzielników liczby k (włącznie z ‘1’ i liczbą ‘k’). Wówczas:
- k jest liczbą niekompletną (deficient number) jeżeli s(k) < 2k
- k jest liczbą doskonałą (perfect number) jeżeli s(k) = 2k
- k jest liczbą zasobną (abundant number) jeżeli s(k) > 2k.
Oznaczmy teraz przez t(k) ilość podzielników liczby k. Jeśli s(k) i t(k) są liczbami doskonałymi, to k jest liczbą wspaniałą (sublime number). Znamy na razie tylko dwie liczby wspaniałe (12 oraz 6 086 555 670 238 378 989 670 371 734 243 169 622 657 830 773 351 885 970 528 324 860 512 791 691 264).
Oznaczmy przez k pewną liczbę, przez s(k) – sumę wszystkich podzielników liczby k (włącznie z ‘1’ i liczbą ‘k’). Wówczas:
- k jest liczbą niekompletną (deficient number) jeżeli s(k) < 2k
- k jest liczbą doskonałą (perfect number) jeżeli s(k) = 2k
- k jest liczbą zasobną (abundant number) jeżeli s(k) > 2k.
Oznaczmy teraz przez t(k) ilość podzielników liczby k. Jeśli s(k) i t(k) są liczbami doskonałymi, to k jest liczbą wspaniałą (sublime number). Znamy na razie tylko dwie liczby wspaniałe (12 oraz 6 086 555 670 238 378 989 670 371 734 243 169 622 657 830 773 351 885 970 528 324 860 512 791 691 264).
23
Stwórz program sprawdzający, czy podana liczba jest liczbą pierwszą. Liczbą pierwszą nazywamy liczbę, która dzieli się wyłącznie przez 1 i przez samą siebie.
24
Należy zaimplementować algorytm sortowania bąbelkowego na n–elementowym zbiorze liczb (10 <= n <= 200). Wczytać zbiór liczb z pliku. Dla danego zbioru obliczyć złożoność algorytmu i porównać ze średnią złożonością O((n2-n)/2).
Bubble sort: porównujemy dwie kolejne liczby i jeśli leżą w złej kolejności (np. sortujemy rosnąco, a większy element jest po lewej stronie) zamieniamy je miejscami. Następnie porównujemy kolejne dwie liczby itd. W ten sposób przeglądamy całą listę wiele razy (dopóki nie będzie już można zamienić żadnej pary elementów). Jest to najprostszy i najwolniejszy algorytm sortowania.
Bubble sort: porównujemy dwie kolejne liczby i jeśli leżą w złej kolejności (np. sortujemy rosnąco, a większy element jest po lewej stronie) zamieniamy je miejscami. Następnie porównujemy kolejne dwie liczby itd. W ten sposób przeglądamy całą listę wiele razy (dopóki nie będzie już można zamienić żadnej pary elementów). Jest to najprostszy i najwolniejszy algorytm sortowania.
25
Napisz program sprawdzający czy liczba podana przez użytkownika jest liczbą Keitha, gdzie liczbą Keitha nazywamy n-cyfrową liczbę całkowitą K, która tworzy ciąg liczbowy o następujących elementach: pierwsze n wyrazów ciągu jest równych poszczególnym cyfrom liczby K, każdy kolejny wyraz jest sumą poprzedzających go n wyrazów ciągu. Ponadto na którymś miejscu w ciągu pojawia się liczba K.
Przykład: 197 jest liczbą Keitha, gdyż tworzy następujący ciąg (i sama w nim występuje):
| 1, |
9, |
7, |
17, |
33, |
57, |
107, |
197, ... |
| || |
|| |
|| |
|| |
|| |
|| |
||
| cyfry liczby 197 |
1+9+7 |
9+7+17 |
7+17+33 |
17+33+57 |
33+57+107 |
||
Listę liczb Keitha z przedziału <1,1019> znajdziesz tutaj.
26
Napisz program, który w zadanym (nieposortowanym) ciągu n liczb zidentyfikuje wszystkie inwersje. Inwersje należy policzyć i wylistować.
Niech A[1..n] będzie tablicą zawierającą n różnych liczb. Jeśli i < j oraz A[i] > A[j], to para (i,j) jest nazywana inwersją A. Na przykład w ciągu: 1,2,5,4,7,12,23,125,41,78,130 inwersjami są pary: (5,4), (125,41) oraz (125,78).
Niech A[1..n] będzie tablicą zawierającą n różnych liczb. Jeśli i < j oraz A[i] > A[j], to para (i,j) jest nazywana inwersją A. Na przykład w ciągu: 1,2,5,4,7,12,23,125,41,78,130 inwersjami są pary: (5,4), (125,41) oraz (125,78).
27
Napisz program poszukujący liczb palindromicznych podzielnych przez k, należących do przedziału <a,b>. Użytkownik podaje wartość k oraz granice przedziału (a i b, przy czym: 0 < a < b < 1 000 000).
Palindromem nazywamy wyraz, który wygląda jednakowo gdy czytamy go od lewej do prawej i od prawej do lewej strony, np. 121 jest liczbą palindromiczną, podobnie 99, 3553, 19791 itp. Nie tylko liczby mogą być palindromami: sformułowanie ‘madam, i’m Adam’ jest nim również.
28
Napisz program, który w podanym zbiorze liczb (wczytanym z pliku, z klawiatury lub wygenerowanym losowo) znajdzie liczby pierwsze dające się przedstawić w postaci sumy dwóch kwadratów, np. 2 = 12+12, 5 = 22+12, 13 = 32+22, itp.
29
Napisz program sprawdzający czy podana macierz jest ortogonalna (macierz A jest ortogonalna jeśli A×AT= AT×A =I, gdzie I oznacza macierz jednostkową). Elementami macierzy są liczby całkowite. Rozmiar macierzy może być dowolny, ale mniejszy od 10×10 (zastosować dwuwymiarowe tablice dynamiczne). Ponadto program ma umożliwić zapis do pliku, gdzie zapisywane będą: macierz pierwotna A, macierz transponowana AT, wynik mnożenia A×AT oraz wynik mnożenia AT×A.
30
Plik wejściowy zawiera macierze o rozmiarze 4×4. Należy obliczyć wyznacznik każdej macierzy, a następnie uporządkować macierze rosnąco według wyznacznika i wynik porządkowania zapisać do pliku.
31
Napisz program odgadujący kod przyjęty przez użytkownika. Użytkownik koduje cyfry (0-9) zastępując każdą z nich jedną literą alfabetu (a-z). Następnie wykorzystując przyjęty kod wpisuje w programie sumę liczb (podaje od 2 do 6 składników sumy oraz wynik sumowania). Program ma „odgadnąć” jakie znaki przypisano jakim cyfrom (odgaduje tylko te cyfry, które znalazły się w sumie; podaje wszelkie możliwości zakodowania). Użytkownik podając sumę posługuje się wyłącznie literami a-z oraz znakami ‘+’ i ‘-’. Przykład kodowania: 0-a, 1-b, 2-c, 3-d, itd.
Wpisana suma: cfa+bcb+ji=egj (250+121+98=469).
32
Napisz program zamieniający liczbę zespoloną z postaci z=a+b×i na postać trygonometryczną: z = |z|(cosf + i×sinf). Użytkownik wpisuje liczbę w jednym okienku edycyjnym, liczba ta powinna mieć postać: ±a±bi, przy czym a,b=0,1,2,...
Program ma przedstawić tę samą liczbę w dwóch postaciach trygonometrycznych:
- z wyznaczoną wartością |z| oraz f,
- z wyznaczoną wartością |z|, cosf, sinf.
Przy czym należy wykorzystać wzory: |z|=sqrt(a2+b2), sinf=b/|z|, cosf=a/|z|, f=arctg(b/a).
33
Napisz program sprawdzający poprawność zdań logicznych i wyznaczający ich wartość. Użytkownik wpisuje wyrażenie logiczne, w którym występują tylko dwie zmienne (p, q) oraz podaje wartości tych zmiennych (0 lub 1). W wyrażeniu mogą znaleźć się nawiasy okrągłe oraz operatory: iloczynu, sumy, wynikania, ‘wtedy i tylko wtedy’, zaprzeczenia).
34
Stwórz program znajdujący macierz odwrotną do zadanej. Macierz pierwotna może być wczytana z pliku lub podana przez użytkownika z klawiatury.
35
Magiczny trójkąt. Używając liczb z przedziału <1,50> należy rozłożyć je tak, aby sumy cyfr znajdujących się w 4 polach każdego boku trójkąta były takie same. Przy tym każda liczba może być użyta tylko raz. W programie można zaimplementować opcję, która pozwoli użytkownikowi podać wartość sumy, jaką chciałby uzyskać na każdym boku trójkąta. Należy umożliwić podgląd wszystkich znalezionych rozwiązań.
36
Napisz program, który odczyta tablice znaków z pliku wejściowego, a nastepnie posortuje znaki w tablicy rosnąco według kodu ASCII. Można wybrać dowolną metodę sortowania.
37
Należy napisać program znajdujący liczby pierwsze Mersenne’a w zadanym przedziale <a,b>. Użytkownik podaje granice przedziału (tj. wartości a, b), przy czym 0 <= a < b <= 125 000.
Liczbą pierwszą Mersenne’a nazywamy liczbę pierwszą x, którą można przedstawić w postaci: x=2n-1 (n=1,2,3,...). Początkowe liczby pierwsze Mersenne’a mają następujące wartości: 3, 7, 31, 127, ...
Liczbą pierwszą Mersenne’a nazywamy liczbę pierwszą x, którą można przedstawić w postaci: x=2n-1 (n=1,2,3,...). Początkowe liczby pierwsze Mersenne’a mają następujące wartości: 3, 7, 31, 127, ...
38
Niech plik wejściowy do programu zawiera n liczb (1 < n <100). Należy znaleźć w nim wszystkie podzbiory liczb przystających modulo k, gdzie k należy do zbioru <2,maxi=1..n li>. Podzbiory te należy wylistować.
Mówimy, że liczby są przystające modulo k, jeśli ich różnica jest podzielna przez k. Na przykład liczby 3, 10, 17, 24, 31, ... są przystające modulo 7, ponieważ: 10-3=7, 17-10=7, 17-3=14, 31-3=28 itd. Widzimy, że 7, 14, 28 (...) dzielą się bez reszty przez 7 .
Mówimy, że liczby są przystające modulo k, jeśli ich różnica jest podzielna przez k. Na przykład liczby 3, 10, 17, 24, 31, ... są przystające modulo 7, ponieważ: 10-3=7, 17-10=7, 17-3=14, 31-3=28 itd. Widzimy, że 7, 14, 28 (...) dzielą się bez reszty przez 7 .
39
Należy napisać program znajdujący liczby pierwsze Fermata w zadanym przedziale <a,b>. Użytkownik podaje granice przedziału, przy czym 0 <= a < b <= 125 000.
Liczbą pierwszą Fermata nazywamy liczbę pierwszą x, którą można przedstawić w postaci: x=2n+1 (n=1,2,3,...). Początkowe liczby pierwsze Fermata: 3, 5, 17, 257, ...
Liczbą pierwszą Fermata nazywamy liczbę pierwszą x, którą można przedstawić w postaci: x=2n+1 (n=1,2,3,...). Początkowe liczby pierwsze Fermata: 3, 5, 17, 257, ...
40
Rysowanie trójkąta Sierpińskiego (fraktale). Rysujemy na ekranie trójkąt równoramienny T. Kolorujemy go na czarno. Następnie wykonujemy rekurencyjnie następującą procedurę:1. Znajdujemy środek Si każdego boku trójkąta T; znalezione punkty S1, S2, S3 stają się wierzchołkami nowego trójkąta Tn;
2. Usuwamy trójkąt Tn z trójkąta T (tj. kolorujemy trójkąt Tn na biało);
3. Dla pozostałych 3 części trójkąta T (które są również trójkątami) wykonujemy kroki 1-3 procedury.
Procedurę należy zakończyć po określonej liczbie kroków (liczba ta może być zadana przez użytkownika) lub wtedy, gdy dokonywanie podziałów nie ma już sensu (niczego nie zmienia, gdyż doszliśmy do pojedynczych piksli). Można umożliwić użytkownikowi podgląd wyniku wykonania kolejnej iteracji procedury (np. wstawić do programu przycisk ‘następny krok’, po którego wybraniu dokona się kolejny podział trójkątów).
41
Modyfikacja problemu 40: narysuj trójkąt Sierpińskiego zaczynając od trójkąta, który nie jest równoramienny. Należy umożliwić użytkownikowi wybór wierzchołków początkowego trójkąta T (np. użytkownik wskazuje położenie każdego wierzchołka poprzez kliknięcie przyciskiem myszy w wybranym punkcie planszy). Po narysowaniu trójkąta wejściowego należy powtarzać procedurę rekurencyjną (jak w zadaniu 40).
42
Należy napisać program znajdujący pierwszych k liczb dodatnich, których kwadraty składają się wyłącznie z cyfr 1,4 lub 9. Takimi liczbami są np.: 1, 2, 3, 7, 12, 21, 38, 107, ..., ponieważ 12=1, 22=4, 32=9, 72=49, 122=144, 212=441, 382=1444, 1072=11449, ....
43
Należy napisać program do "gry" w chaos. Na planszy rysujemy trójkąt równoramienny o wierzchołkach ponumerowanych liczbami 1-3 (lub pokolorowanych 3 różnymi kolorami). Użytkownik wybiera na planszy startowy punkt gry x0 (np. poprzez kliknięcie myszą lub wpisanie współrzędnych punktu początkowego) – ten pierwszy punkt nazywać będziemy ziarnem (seed). Następnie wykonujemy kolejne kroki gry:
1. losujemy liczbę z przedziału <1,3> (lub kolor);
2. kolejny punkt gry xi malujemy w punkcie położonym w połowie odcinka pomiędzy poprzednim punktem xi-1 a wierzchołkiem trójkąta o wylosowanym numerze;
3. powtarzamy kroki 1-2 ...
Sekwencja punktów, jakie otrzymujemy w grze nazywa się orbitą (trajektorią) ziarna. Należy sprawdzić, jaki obraz otrzymaliśmy po 100, 500, 1 000, 10 000 iteracjach. Już po 1 000 iteracjach powinniśmy zauważyć, że punkty układają się w trójkąt Sierpińskiego. Figura ta jest zatem atraktorem gry w chaos (tj. chaos prowadzi do deterministycznego kształtu, jakim jest trójkąt Sierpińskiego).
W programie należy umieścić ‘kostkę’ do losowania (np. przycisk) oraz opcję wyboru liczby iteracji gry, która ma się wykonać po wybraniu tej opcji.
1. losujemy liczbę z przedziału <1,3> (lub kolor);
2. kolejny punkt gry xi malujemy w punkcie położonym w połowie odcinka pomiędzy poprzednim punktem xi-1 a wierzchołkiem trójkąta o wylosowanym numerze;
3. powtarzamy kroki 1-2 ...
Sekwencja punktów, jakie otrzymujemy w grze nazywa się orbitą (trajektorią) ziarna. Należy sprawdzić, jaki obraz otrzymaliśmy po 100, 500, 1 000, 10 000 iteracjach. Już po 1 000 iteracjach powinniśmy zauważyć, że punkty układają się w trójkąt Sierpińskiego. Figura ta jest zatem atraktorem gry w chaos (tj. chaos prowadzi do deterministycznego kształtu, jakim jest trójkąt Sierpińskiego).
W programie należy umieścić ‘kostkę’ do losowania (np. przycisk) oraz opcję wyboru liczby iteracji gry, która ma się wykonać po wybraniu tej opcji.
44
Należy napisać program do zmodyfikowanej gry w chaos. Można wybrać jedną z proponowanych modyfikacji (inna figura początkowa, inny współczynnik podziału odcinka):
(a) figura początkowa = trójkąt; jeśli wylosujemy jeden z wierzchołków w podstawy trójkąta, to punkt xi stawiamy jak poprzednio (w połowie odcinka między xi-1 i w), a jeśli wylosujemy wierzchołek górny, to punkt xi stawiamy w odległości 2/3 od xi-1,
(b) figura początkowa = trójkąt; jeśli wylosujemy wierzchołek lewy trójkąta, to punkt xi stawiamy w odległości 1/2 od xi-1, jeśli wylosujemy wierzchołek prawy – punkt stawiamy w odległości 2/3 od xi-1, a jeśli wylosujemy wierzchołek górny, to punkt xi stawiamy w odległości 3/4 od xi-1,
(c) figura początkowa = kwadrat; losujemy spośród 4 liczb; punkt xi stawiamy w odległości 1/2 od punktu poprzedniego xi-1; (niespodzianka – wcale nie otrzymamy dywanu Sierpińskiego; punkty wypełnią cały kwadrat),
(d) figura początkowa = sześciokąt foremny; losujemy spośród 6 liczb; punkt xi stawiamy w odległości 2/3 od punktu xi-1; (otrzymamy sześciokąt Sierpińskiego, którego wewnętrzną granicę stanowi krzywa Kocha przedstawiająca płatek śniegu),
(e) figura początkowa = pięciokąt foremny; losujemy spośród 5 liczb; punkt xi stawiamy w odległości 5/8 od punktu xi-1; (otrzymamy pięciokąt Sierpińskiego);
45
Należy napisać program do gry w chaos uwzglęniający rotacje:
(a) figura początkowa = trójkąt; jeśli wylosujemy jeden z wierzchołków w podstawy trójkąta, to punkt xi stawiamy jak poprzednio (w połowie odcinka między xi-1 i w), a jeśli wylosujemy wierzchołek górny, to poruszamy się na odległość 1/2 w kierunku wierzchołka, a następnie przeciwnie do ruchu wskazówek zegara obracamy się o 90o wokół wierzchołka i stawiamy punkt xi,
(b) figura początkowa = trójkąt; jeśli wylosujemy jeden z wierzchołków w podstawy trójkąta, to punkt xi stawiamy jak poprzednio (w połowie odcinka między xi-1 i w), a jeśli wylosujemy wierzchołek górny, to poruszamy się na odległość 1/2 w kierunku wierzchołka, a następnie przeciwnie do ruchu wskazówek zegara obracamy się o 180o wokół wierzchołka i stawiamy punkt xi.
(a) figura początkowa = trójkąt; jeśli wylosujemy jeden z wierzchołków w podstawy trójkąta, to punkt xi stawiamy jak poprzednio (w połowie odcinka między xi-1 i w), a jeśli wylosujemy wierzchołek górny, to poruszamy się na odległość 1/2 w kierunku wierzchołka, a następnie przeciwnie do ruchu wskazówek zegara obracamy się o 90o wokół wierzchołka i stawiamy punkt xi,
(b) figura początkowa = trójkąt; jeśli wylosujemy jeden z wierzchołków w podstawy trójkąta, to punkt xi stawiamy jak poprzednio (w połowie odcinka między xi-1 i w), a jeśli wylosujemy wierzchołek górny, to poruszamy się na odległość 1/2 w kierunku wierzchołka, a następnie przeciwnie do ruchu wskazówek zegara obracamy się o 180o wokół wierzchołka i stawiamy punkt xi.
46
Rysowanie dywanu Sierpińskiego (fraktale).
Problem jest podobny do problemu z zadania 40. Figurą wyjściową jest kwadrat, który dzielimy na dziewięć równych części (kwadratów). Usuwamy część leżącą w środku, a każdą pozostałą część dzielimy podobnie jak kwadrat początkowy na 9 części, spośród nich usuwamy część środkową itd.
Należy wykonać maksymalnie 10 podziałów i umożliwić podgląd obrazu po każdej iteracji.
47
Napisz program szyfrujący systemem Juliusza Cezara używanym w starożytnym Rzymie (kodowanie i rozkodowanie). System jest następujący: załóżmy, że mamy 26-literowy alfabet A-Z oraz jego liczbowe odpowiedniki 0-25. Niech P należące do zbioru {0,1,2,...,25} oznacza jednostkę tekstu jawnego, natomiast C - jednostkę kryptogramu. Zdefiniujmy funkcję f({0,1,2,...,25})->{0,1,2,...,25} za pomocą wzoru: C = f(P) = P+3 dla x<23 oraz C = f(P) = P-23 dla x>=23. Inaczej mówiąc f dodaje 3 modulo 26. Uzyskane liczby zamieniamy z powrotem na litery. Rozszyfrowanie jest funkcją odwrotną i polega na odejmowaniu 3 modulo 26 (P = f--1(C) = C-3 (mod 26)). Ten system kryptograficzny można uogólnić: dla danego alfabetu N-literowego oraz zbioru liczb {0,1,2,...,N-1}, ustalamy klucz szyfrujący b oraz funkcję f zwaną przesunięciem: f(P) = P-b (mod N). Funkcja odwrotna: f--1(C) = C-b (mod N).
Przykład. Zaszyfrujmy teraz w naszym systemie kryptograficznym słowo „YES”. Najpierw przekształcamy litery słowa na liczby: 24 4 18, potem dodajemy 3 modulo 26: 1 7 21, a na końcu z powrotem przekształcamy na litery: „BHV”.
Przykład. Zaszyfrujmy teraz w naszym systemie kryptograficznym słowo „YES”. Najpierw przekształcamy litery słowa na liczby: 24 4 18, potem dodajemy 3 modulo 26: 1 7 21, a na końcu z powrotem przekształcamy na litery: „BHV”.
48
Napisz program znajdujący wszystkie możliwości zastąpienia znaku ‘.’ (kropka) po lewej stronie równania znakami ‘+’ (plus), ‘-’ (minus) lub ‘’ (brak znaku) tak, aby prawdziwe było równanie: .1.2.3.4.5.6.7.8.9 = x. Wartość x podaje użytkownik.
Przykładowo w równaniu .1.2.3.4.5.6.7.8.9 = 1 istnieje aż 69 sposobów ustawienia ‘+’, ‘-’ lub ‘’ w miejsce kropki, tak że równanie jest spełnione, np. 1+23+4-5+67-89 = 1.
Przykładowo w równaniu .1.2.3.4.5.6.7.8.9 = 1 istnieje aż 69 sposobów ustawienia ‘+’, ‘-’ lub ‘’ w miejsce kropki, tak że równanie jest spełnione, np. 1+23+4-5+67-89 = 1.
49
W pliku wejściowym znajduje się k liczb. Należy napisać program zliczający ile liczb zawiera plik, następnie utworzyć jednowymiarową tablicę dynamiczną T1 o rozmiarze k i do tej tablicy przepisać liczby z otwartego pliku.
Dalej, należy utworzyć dwie nowe jednowymiarowe tablice dynamiczne T2, T3. Do tablicy T2 program ma przepisać wszystkie liczby parzyste znajdujące się w tablicy T1, natomiast do tablicy T3 – wszystkie liczby nieparzyste z tablicy T1.
Dalej, należy utworzyć dwie nowe jednowymiarowe tablice dynamiczne T2, T3. Do tablicy T2 program ma przepisać wszystkie liczby parzyste znajdujące się w tablicy T1, natomiast do tablicy T3 – wszystkie liczby nieparzyste z tablicy T1.
50
Napisz program obliczający ile palindromów wyświetli zegar elektroniczny między godziną g1 i godziną g2. Wszystkie znalezione palindromy z podanego zakresu należy wylistować. Użytkownik podaje w programie godzinę g1 i g2, które tworzą przedział poszukiwań. Godzina może być podana w jednym z następujących formatów: h:mm, hh:mm, h:mm:ss, hh:mm:ss (h – godzina, m – minuta, s – sekunda). Zakładamy, że zegar wyświetla czas w systemie 24-godzinnym, wobec tego: 0 <= h <= 23, 0 <= m <= 59, 0 <= s <= 59 (brak określeń AM, PM). Ponadto g1 <= g2. Użytkownik ma dowolność w określeniu czy znak ":" (dwukropek) należy uwzglęniać przy kwalifikowaniu godziny jako palindromu, czy też można go pominąć.
Przykład. Załóżmy, że pomijamy znak ":", wówczas:
(a) między godziną 0:00 a 23:59 zegar elektroniczny wyświetla 70 palindromów (np. 0:00, 0:50, 3:13, 4:44 itd.)
(b) między godziną 00:00 a 23:59 zegar elektroniczny wyświetla 16 palindromów (np. 00:00, 10:01, 12:21 itd.)
(c) między godziną 0:00:00 a 23:59:59 zegar elektroniczny wyświetla 660 palindromów (np. 0:23:20, 13:22:31 itd.)
(d) między godziną 00:00:00 a 23:59:59 zegar elektroniczny wyświetla 96 palindromów (np. 05:00:50, 14:11:41 itd.)
Definicja palindromów (liczb palindromicznych) znajduje się w zadaniu 27.
51
Stwórz program sprawdzający, czy daną liczbę można przedstawić w postaci sumy dwóch liczb bliźniaczych. Liczbą bliźniaczą nazywać będziemy liczbę, która powstaje przez zdublowanie połowy swoich cyfr, np. 99, 2121, 537537, ...
Przykładem liczby rozkładalnej na sumę bliźniaków jest liczba 341396 = 55 + 341341.
Przykładem liczby rozkładalnej na sumę bliźniaków jest liczba 341396 = 55 + 341341.
52
Napisz program znajdujący najmniejszą liczbę, która po podniesieniu do kwadratu daje liczbę bliźniaczą (np. 363636363642 = 1322314049613223140496).
53
Napisz program sprawdzający, czy podane wyrażenie matematyczne daje w wyniku liczbę Friedmana. W wyrażeniu mogą wystąpić następujące operatory: +, -, ×, /, ^ oraz nawiasy.
Liczbą Friedmana nazywamy liczbę całkowitą dodatnią, którą można zapisać w postaci równania, w którym po lewej stronie równania występuje dana liczba, natomiast po prawej stronie – wyrażenie składające się z cyfr danej liczby (i żadnych innych), z których każda musi wystąpić dokładnie raz oraz z operacji: + (dodawanie), - (odejmowanie), × (mnożenie), / (dzielenie), ^ (potęgowanie), () (nawiasy) oraz konkatenacja.
Przykładowe liczby Friedmana:
123456789 = ((86 + 2 × 7)5 - 91) / 34,
987654321 = (8 × (97 + 6 / 2)5 + 1) / 34.
Liczbą Friedmana nazywamy liczbę całkowitą dodatnią, którą można zapisać w postaci równania, w którym po lewej stronie równania występuje dana liczba, natomiast po prawej stronie – wyrażenie składające się z cyfr danej liczby (i żadnych innych), z których każda musi wystąpić dokładnie raz oraz z operacji: + (dodawanie), - (odejmowanie), × (mnożenie), / (dzielenie), ^ (potęgowanie), () (nawiasy) oraz konkatenacja.
Przykładowe liczby Friedmana:
123456789 = ((86 + 2 × 7)5 - 91) / 34,
987654321 = (8 × (97 + 6 / 2)5 + 1) / 34.
54
Napisz program sprawdzający czy podana liczba jest liczbą pierwszą kołową (circular prime). Liczba pierwsza kołowa jest to liczba pierwsza o następującej własności: po przeniesieniu pierwszej cyfry tej liczby na jej koniec otrzymujemy liczbę pierwszą – taką operację wykonujemy n-1 razy (n – liczba cyfr naszej liczby) i za każdym razem otrzymujemy liczbę pierwszą.
Przykład: 1193 jest kołową liczbą pierwszą, ponieważ:
1193 – jest liczbą pierwszą
1931 – jest liczbą pierwszą
9311 – jest liczbą pierwszą
3119 – jest liczbą pierwszą
Inne liczby pierwsze kołowe: 1, 3, 7, 11, 13, 17, 37, 79, 113, 187, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933, ...
Zauważmy, że liczbą pierwsza kołowa może składać się wyłącznie z cyfr: 1, 3, 7, 9 (wyjątek stanowią liczby jednocyfrowe 2, 5).
Przykład: 1193 jest kołową liczbą pierwszą, ponieważ:
1193 – jest liczbą pierwszą
1931 – jest liczbą pierwszą
9311 – jest liczbą pierwszą
3119 – jest liczbą pierwszą
Inne liczby pierwsze kołowe: 1, 3, 7, 11, 13, 17, 37, 79, 113, 187, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933, ...
Zauważmy, że liczbą pierwsza kołowa może składać się wyłącznie z cyfr: 1, 3, 7, 9 (wyjątek stanowią liczby jednocyfrowe 2, 5).
55
Napisz program, który sumuje elementy leżące w pierwszym wierszu, ostatnim wierszu, w pierwszej kolumnie i ostatniej kolumnie macierzy kwadratowej. Algorytm sumujący wszystkie te elementy ma być ujęty w jednej pętli.
56
Napisz program wczytujący ciąg k liczb i sortujący go metodą sortowania przez wstawianie:
(a) na jednej tablicy,
(b) na dwóch tablicach.
Sortowanie przez wstawianie: Sortowanie odbywa się w taki sposób, w jaki sortujemy karty do gry: pobieramy kartę (element) i wstawiamy go plik kart, które już trzymamy; wstawiamy w taki sposób, aby plik kart był posortowany po wstawieniu karty. Podobnie rzecz ma się z dowolnymi elementami, które sortujemy. Załóżmy, że sortujemy elementy w porządku rosnącym. Bierzemy pierwszy element i wstawiamy go w dowolne miejsce pustej tablicy. Następny pobrany element wstawiamy przed poprzednim (jeśli jest mniejszy) lub za poprzednim (jeśli jest większy). Każdy kolejny element wstawiamy tak, żeby wszystkie leżące po jego lewej stronie były od niego mniejsze, a wszystkie leżące po prawej – większe, itd.
(a) na jednej tablicy,
(b) na dwóch tablicach.
Sortowanie przez wstawianie: Sortowanie odbywa się w taki sposób, w jaki sortujemy karty do gry: pobieramy kartę (element) i wstawiamy go plik kart, które już trzymamy; wstawiamy w taki sposób, aby plik kart był posortowany po wstawieniu karty. Podobnie rzecz ma się z dowolnymi elementami, które sortujemy. Załóżmy, że sortujemy elementy w porządku rosnącym. Bierzemy pierwszy element i wstawiamy go w dowolne miejsce pustej tablicy. Następny pobrany element wstawiamy przed poprzednim (jeśli jest mniejszy) lub za poprzednim (jeśli jest większy). Każdy kolejny element wstawiamy tak, żeby wszystkie leżące po jego lewej stronie były od niego mniejsze, a wszystkie leżące po prawej – większe, itd.
57
Stwórz środowisko graficzne do rozwiązywania problemu wież Hanoi. Program ma działać dla 3 – 10 krążków (liczbę krążków wybiera użytkownik) oraz 3 palików (oznaczmy je literami: A, B, C). Po wyborze liczby krążków program przechodzi do stanu początkowego, w którym wszystkie krążki są ułożone od największego do najmniejszego na paliku A. Użytkownik przekładając krążki (przy pomocy myszy) ma uzyskać stan końcowy, w którym krążki będą ułożone na paliku C w porządku od największego do najmniejszego. Po osiągnięciu stanu końcowego program nie pozwala na dalsze ruchy. Program kontroluje poprawność ruchów, które muszą odbywać się zgodnie z następującymi regułami:
- użytkownik może przenosić krążki tylko pojedynczo,
- można wziąć tylko krążek leżący na wierzchu,
- krążek można położyć tylko na pustym paliku lub na krążku większym od trzymanego.
- użytkownik może przenosić krążki tylko pojedynczo,
- można wziąć tylko krążek leżący na wierzchu,
- krążek można położyć tylko na pustym paliku lub na krążku większym od trzymanego.
58
Napisz program znajdujący wszystkie liczby pierwsze, które można stworzyć z podzbiorów cyfr podanej liczby całkowitej typu Integer (taką liczbę nazywa się w jęz. ang. primeval number).
Przykład: pytamy ile liczb pierwszych można stworzyć z cyfr liczby 1379. Potraktujmy liczbę 1379 jako zbiór cyfr {1,3,7,9} i znajdźmy wszystkie podzbiory, które tworzą liczby pierwsze. Okazuje się, że możemy znaleźć aż 31 liczb pierwszych „zanurzonych” w liczbie 1379. Są to: 3, 7, 13, 17, 19, 31, 37, 71, 73, 79, 97, 137, 139, 173, 179, 193, 197, 317, 379, 397, 719, 739, 937, 971, 1973, 3719, 3917, 7193, 9137, 9173, 9371. Uwaga: budując liczbę pierwszą możemy każdą cyfrę ze zbioru wejściowego wziąć tylko raz.
Przykład: pytamy ile liczb pierwszych można stworzyć z cyfr liczby 1379. Potraktujmy liczbę 1379 jako zbiór cyfr {1,3,7,9} i znajdźmy wszystkie podzbiory, które tworzą liczby pierwsze. Okazuje się, że możemy znaleźć aż 31 liczb pierwszych „zanurzonych” w liczbie 1379. Są to: 3, 7, 13, 17, 19, 31, 37, 71, 73, 79, 97, 137, 139, 173, 179, 193, 197, 317, 379, 397, 719, 739, 937, 971, 1973, 3719, 3917, 7193, 9137, 9173, 9371. Uwaga: budując liczbę pierwszą możemy każdą cyfrę ze zbioru wejściowego wziąć tylko raz.
59
Napisz program znajdujący najmniejszą liczbę całkowitą dodatnią, z której cyfr można zbudować wszystkie dwucyfrowe liczby pierwsze (objaśnienia patrz zadanie 58).