# Informatyka

## C++
### Drzewa

> Warto na początek zajrzeć [tutaj](https://hackmd.io/XoHx6BGQQIyw394yLKeX7w) i przypomnieć sobie czym są grafy oraz sposoby ich reprezentacji na potrzeby programowania.

*Drzewo* to szczególny przypadek grafu, który spełnia następujące kryteria:
1. ma dokładnie $n - 1$ krawędzi
2. jest spójny
3. nie ma cykli (tą własność można wydedukować z dwóch poprzednich - zastanów się jak?)

Drzewo możemy *ukorzenić*, czyli "powiesić" za wybrany wierzchołek. Ukorzenienie drzewa nie zmienia jego wewnętrznych "relacji", ale zmienia jego kształt. Ta obserwacja jest szczególnie istotna przy dużych drzewach, gdzie Często w treści zadania będzie sprecyzowane, który wierzchołek jest korzeniem.

graph{
1 -- 2
2 -- 3
1 -- 4
2 -- 5
2 -- 8
5 -- 6
4 -- 7
}

*Spójna składowa* to taki podzbiór wierzchołków, że jest możliwe przejście między dowolną parą z nich. Łatwo zauważyć, że *graf spójny* to taki, który ma tylko jedną spójną składową. Poniższy graf nie jest spójny, bo nie ma sposobu na wykonanie przejścia $1 \rightarrow 4$.

graph{
1 -- 2
2 -- 3
1 -- 6
2 -- 6

4 -- 5
}

#### Jak poruszać się po drzewie?

Chcemy sprawnie przechodzić między wierzchołkami w drzewie, niech będzie ono tutaj reprezentowane w postaci list sąsiedztwa. Każde poddrzewo (mniejszy graf "zwisający" z jakiegoś wewnętrznego wierzchołka) również jest drzewem, więc można fajnie wykorzystać zależność rekurencyjną:

void przejdz_po_drzewie(int v) {
    
    // zrób coś dla wierzchołka v
    
    for (int i = 0; i < sasiedzi[v].size(); i++) {
        
        int obecny_syn = sasiedzi[v][i];
        // ewentualnie zrób coś dla syna
        przejdz_po_drzewie(obecny_syn);
    }
}

**Ale uwaga!** Ze względu na nieskierowane krawędzie takie przeszukiwanie może się zapętlić (na przykład ten kod wywołany na drzewie z przykładu daje $1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow \dots$), potrzebny jest jakiś sposób na pamiętanie odwiedzonych wierzchołków. Dobrze sprawdzi się tablica `bool odwiedzony[N]`. Wtedy:

void przejdz_po_drzewie(int v) {
    
    odwiedzony[v] = true
    // zrób coś dla wierzchołka v
    
    for (int i = 0; i < sasiedzi[v].size(); i++) {
        
        int obecny_syn = sasiedzi[v][i];
        if (!odwiedzony[obecny_syn]) {
            // ewentualnie zrób coś dla syna
            przejdz_po_drzewie(obecny_syn);
        }
    }
}

Zwróć uwagę, że w przytoczonych wyżej fragmentach programu jest linijka do uzupełnienia `// zrób coś dla wierzchołka v`. To co będzie w tym miejscu zależy od zadania, ale z reguły wykonamy tutaj jakąś operację arytmetyczną, uzupełnianie odpowiedniego pola w tablicy itp.

Koszt trawersowania drzewa w ten sposób ma złożoność $O(n + m)$, ponieważ do każdego wierzchołka wchodzimy co najwyżej raz (dba o to struktura `odwiedzony[]`).

#### Numeracja *preorder* i *postorder*

Czasem będziemy chcieli "przenumerować" wierzchołki podane na wejściu, żeby przeglądać je w bardziej systematyczny sposób (o dalszych zastosowaniach porozmawiamy później). Dwoma popularnymi metodami są:
* *preorder* - w jakiej kolejności wchodzimy do wierzchołków
* *postorder* - w jakiej kolejności wychodzimy z wierzchołków tj. po przejrzeniu wszystkich synów

Na przykład dla ilustracji z początku notatki nowa numeracja wygląda następująco:

| Numer wierzchołka | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ----------------- | --- | --- | --- | --- | --- | --- | --- | --- |
| **Preorder** | 1 | 2 | 3 | 7 | 4 | 5 | 8 | 6 |
| **Postorder** | 8 | 5 | 1 | 7 | 3 | 2 | 6 | 4 |
### Grafy

**Grafy** to abstrakcyjna struktura danych, która świetnie nadaje się do modelowania zależności z prawdziwego życia. Weźmy na przykład:
* osoby (wierzchołki) i ich znajomości (krawędzie)
* miasta i łączące je drogi
* posty w mediach społecznościowych i tagi

Grafy można reprezentować na różne sposoby, a odpowiednią reprezentację dobieramy do rozwiązywanego zadania. Na przykład dla poniższego przykładu

digraph{
rankdir = LR
1 -> 2
1 -> 3
2 -> 3
3 -> 2
4 -> 2
1 -> 5
4 -> 5
3 -> 4
5 -> 3
}

*reprezentacja macierzowa* wygląda tak:

| | 1 | 2 | 3 | 4 | 5 |
| ----- | - | - | - | - | - |
| **1** | 0 | 1 | 1 | 0 | 1 |
| **2** | 0 | 0 | 1 | 0 | 0 |
| **3** | 0 | 1 | 0 | 1 | 0 |
| **4** | 0 | 1 | 0 | 0 | 1 |
| **5** | 0 | 0 | 1 | 0 | 0 |

a z wykorzystaniem *list sąsiedztwa* tak:

| | Sąsiedzi |
| ----- | ---------- |
| **1** | 2, 3, 5 |
| **2** | 3 |
| **3** | 2, 4 |
| **4** | 2, 5 |
| **5** | 3 |

==Uwaga!== Graf może być *skierowany* lub *nieskierowany*, czyli krawędzie mogą być jednokierunkowe lub obukierunkowe (powyżej mamy przykład grafu skierowanego). W przypadku grafów nieskierowanych dla uproszczenia nie rysujemy strzałek mimo, że teoretycznie tam są (w obie strony).

To jaką reprezentację chcemy wykorzystać w danym zadaniu zależy od wymagań (jakich operacji będziemy wykonywać najwięcej, czy mamy mało czy dużo pamięci itp.). Przeanalizujmy złożoność niektórych operacji grafowych dla obu znanych nam reprezentacji:

| Zadanie | Rep. macierzowa | Rep. listowa |
| -------------------------------- | --------------- | -------------------- |
| Obliczanie stopnia wierzchołka | $O(n)$ | $O(deg(v))$ |
| Przejrzenie wszystkich krawędzi | $O(n^2)$ | $O(n + m)$ |
| Sprawdzenie czy krawędź istnieje | $O(1)$ | $O(deg(v))$ |
| Dodanie nowej krawędzi | $O(1)$ | $O(deg(v))$ |
| Usunięcie krawędzi | $O(1)$ | $O(deg(u) + deg(v))$ |

*Stopniem wejściowym (wyjściowym)* wierzchołka $v$ nazywamy liczbę wchodzących do niego (lub wychodzących z niego). Dla grafów nieskierowanych jest to ta sama wartość i dla uproszczenia używamy po prostu pojęcia stopnia.

### STL
Kod z zajęć

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
vector<int> myVec;
pair<int, int> para;
priority_queue<int, vector<int>, greater<int>> kolejka;

map<int,char> mapa;
//set<int> zbior;
//stack<int> stosik;
//queue<int> kolejka_zwykla;
//deque<int> kolejka_podwojna;

bool cmp(int a, int b){
    if(a%2==0){
        if(b%2==0){
            return a < b;
        }else{
            return true;
        }
    }else if (b%2==0){
        return false;
    }else{
        return a < b;
    }
}

//sort
vector<pair<int, int>> pary;
int tab[10];
int main(){
    /*para = {1, 2};
    pary.push_back(para);
    pary.push_back({3, 1});
    pary.push_back({2,7});
    pary.push_back({1,1});
    pary.push_back({0,0});
    for(int i = 0; i< pary.size(); i++){
        cout << pary[i].first << " " << pary[i].second << endl;
    }
    //sort(tab+0, tab+10);
    sort(pary.begin(), pary.end());
    cout << endl;
    for(int i = 0; i< pary.size(); i++){
        cout << pary[i].first << " " << pary[i].second << endl;
    }
    kolejka.emplace(7); //7
    cout << kolejka.top() << endl;
    kolejka.emplace(3); //3 7
    cout << kolejka.top() << endl;
    kolejka.emplace(5); //3 5 7
    cout << kolejka.top() << endl;
    kolejka.pop(); //5 7
    cout << kolejka.top() << endl;*/

    vector<int> vecc = {1,2,5,8,0, 4,13, 23, 10};
    sort(vecc.begin(), vecc.end(), cmp);
    for(int i = 0; i<vecc.size();i++){
        cout << vecc[i] << " ";
    }

    return 0;
}

### Binary search

Rozważmy następujący problem:
Zostało wybrane n=10 liczb, które zostały zapisane w porządku niemalejącym. Te liczby są zakryte. Naszym celem jest dowiedzieć się czy liczba x znajduje się wśród wybranych liczb. Do dyspozycji mamy tylko pytania o konkretną pozycję i jednocześnie chcemy użyć jak najmniej pytać.

Niech liczby będą takie
2 14 36 44 48 60 79 80 84 95
Szukamy 79
`_ _ _ _ _ _ _ _ _ _`
Optymalną strategią jest pytanie zawsze w połowie
Pytanie o 5 pozycję
`_ _ _ _ 48 _ _ _ _ _`

79 jest większe od 48, więc musimy szukać na prawo

Pytamy o 8 pozycję
`_ _ _ _ 48 _ _ 80 _ _`

Pytamy o 6
`_ _ _ _ 48 60 _ 80 _ _`

Pytamy o 7
`_ _ _ _ 48 60 79 80 _ _`
Znaleźliśmy szukaną liczbę w 4 ruchach.
Przeszukując naiwnie od lewej strony potrzebowalibyśmy ich aż 7

Dzięki dzieleniu przeszukiwanego przedziału na pół co zapytanie osiągnęliśmy złożoność logarytmiczną

Postarajmy się sformalizować to intuicyjne podejście, by ostatecznie wprodukować działający kod

Niech l i r oznaczają końce tablicy (l=0, r=n)
Pytanie o środek realizujemy przez zapytanie o mid=(l+r)/2

Poniższy kod znajduje liczbę q w tablicy tab

int r = n;
int l = 0;
while(l < r) {
    int mid = (l + r) / 2;
    cout << mid << " " << tab[mid] << endl;
    if(tab[mid] >= q) {
    	r = mid;
    }
    else {
	l = mid +1;
    }
}

### Vectory

Korzystając z tablic tablic spotkaliśmy się z problemem zużycia pamięci:
Mamy 10 kategorii w każdej maksymalnie dziesięć produktów, a sumarycznie produktów może być 20
Wówczas musimy przygotować się na najgorsze opcje i musimy zrobić tablicę 10x10 łącznie 100 komórek, czyli 5 razy więcej niż potrzeba

Poznamy rozszerzalne tablice, które pozwolą nam zaoszczędzić pamięć.
Są to vectory

#include <vector>
vector<typ> nazwa;
vector<int> myVec;

Do vectora można dodawać elementy na koniec

myVec.push_back(7);
myVec.push_back(10);

Elementy można odczytywać jak z tablicy

myVec[0];//zwraca 7

Można robić vector vectorów

vector<vector<int>> myVec2d;

Można zmieniać rozmiar vectora, szczególnie przydatne, gdy chcemy rozpocząć pracę z kilkoma wektorami pustymi

myVec2d.resize(n);
//teraz myVec2d składa się z n pustych wektorów

Po użyciu funckji resize można korzystać z myVec2d prawie jak z tablicy 2d
(pamiętać o push_back!)

Porównanie
tablica 2x3

int tab[2][3]

Zawiera od razu 6 komórek pamięci
[[0,0,0],[0,0,0]]

vector intów

vector<int> myVec;

zawiera pusty pojemnik na inty []
Po wykonaniu `myVec.push_back(7)` wygląda tak [7], a po `myVec.push_back(10)` tak [7, 10]

vector vectorów intów

vector<vector<int>> myVec2d;

zawiera pusty pojemnik na pojemniki na inty []

vector vectorów intów + resize

vector<vector<int>> myVec2d;
myVec2d.resize(2);

zawiera 2 pojemniki na inty [[],[]]
Po wykonaniu `myVEc2d[1].push_back(2)`
wygląda tak [[],[2]], a po wykonaniu `myVec2d[0].push_back(6)` tak [[6],[2]]

Żeby wykonywać pętle po wektorach przydaje się funkcja size, która zwara rozmiar wektora

myVec.size();

Przykład
Wczytywanie i wypisywanie listy sąsiedztwa

#include <bits/stdc++.h>
using namespace std;
vector <vector <int>> V;
int main () {
    int n, d; //n - liczba wierzchołków, d liczba krawędzi
    cin >> n >> d;
    V.resize(n);//wierzchołki numeruję od 0 do n-1
    for (int i = 0; i < d; i++) {
        int P1, P2;
        cin >> P1 >> P2;
        V[P1].push_back(P2); //jak jest krawędź to zapisuję
        V[P2].push_back(P1);
    }
    for (int i = 0; i < n; i++) {//pętla dla każdego wierzchołka
	cout << i << ": ";
        for (int j = 0; j < V[i].size(); j++) {//dla każdego sąsiada
            cout << V[i][j] << " ";
        }
    	cout << "\n";
    }
    return 0;
}

### Sito
Schemat rozwiązania

bool czyWykr[50];

czyWykr[0] = ?;
czyWykr[1] = ?;
for(?){//przejdz po wszystkich liczbach
	
	if(?){//jeśli jest pierwsza
		for(?){//to wykreśl wielokrotności
			czyWykr[?]=?;
		}
	}

}

Pętle z wypisywaniem liczb najlepiej zrobić osobno (dla prędkości programu).
Przypominam o magicznych linijkach

### Sumy prefiksowe

Sumy prefiksowe jest to technika pozwalająca na szybkie odpowiadanie na pytanie "Ile razy wystąpiło zjawisko w przedziale a b?".

Nazwa bierze się od sposobu zebrania danych (agregacji) w formie np. sumy dla przedziałów postacii <1, i> dla każdego i tj. dla kolejnych początków tablicy

Rozważmy taki przykład:
Bajtazar notował kiedy w ciągu roku padał deszcz. Wielu jego znajomych pyta go o to, ile razy w pewnych przedziałów czasowych padał deszcz. Pomóż Bajtazarowi przygotować się na serię pytań.

Pomińmy wczytywanie danych

//dane
int deszcz[366]; // tablica wypełniona 1-padało i 0-nie padało
int t; liczba pytań
int pref[366]; 

//pierwszego dnia padało tyle samo razy co w przedziale dni <1, 1>
pref[1] = deszcz[1];

//dla kolejnych przedziałów padało tyle samo razy co wczoraj + 1 jeśli dziś też padało

for(int i = 2; i < 366; i++){
	pref[i] = pref[i-1] + deszcz[i];
}


//teraz możemy odpowiadać na pytania dla dni od a do b

while(t--){
	cin >> a >> b;
	cout << pref[b] - pref[a-1];
	
}

Czemu takie odejmowanie?
Jeżeli pytamy od dnia 3 do 5 to możemy odpowiedzieć, że tyle samo co w dniach 1-5, ale pominąć dni 1-2

### Szybkie potęgowanie

Idea: wykorzystamy zamianę liczby na system binarny, żeby zredukować złożoność potęgowania z liniowej na logarytmiczną

Chcemy obliczyć $3^{19}$. Klasycznie pomnożylibyśmy dziewiętnaście trójek.
Spójrzmy na 19 w systemie binarnym: 10011
Przyda nam się zależność, że $3^{19}=3^{16}\cdot3^{2}\cdot3^1$
16, 2, 1 pojawiają się, bo sumują się do 19
Potrafimy w czasie logarytmicznym obliczyć $3, 3^2, 3^4, 3^8, 3^{16}$ itd.
(Patrz zadania z poprzednich list)
W czasie ich wyliczania do akumulatora wystarczy domnażać liczby odpowiadające jedynkom w zapisie binarnym wykładnika

### Funkcje rekurencyjne

Funkcje rekurencyjne to takie, które w swojej definicji korzystają same z siebie. Pozwalają one na zwięzłe wyrażanie wielu problemów

Policzmy sumę liczb od 0 do n:

int f(int x){
	if(x==0){
		return 0;
	}
	return x+f(x-1);
}

Ta funkcja zwraca 0 dla 0 - czyli dobry wynik
Dla większych liczb obliczenia będą wyglądały tak
f(3) = 3 + f(2) = 3 + 2 + f(1) = 3 + 2 + 1 + f(0) = 3 + 2 + 1 + 0 = 6

Można liczyć znacznie więcej rzeczy jak liczby Fibonacciego
https://pl.wikipedia.org/wiki/Ci%C4%85g_Fibonacciego

int fib(int x){
	if(x <=1 ){
		return 1; //zerowa i pierwsza liczba ciągu to 1
	}
	return f(x-1)+f(x-2);
}

Schemat z liczenia sumy pozwala nam zastąpić pętlę for od n do 0
Po drobnej modyfikacji otrzymamy pętlę for w formie rekurencyjnej od 0 do n
Zróbmy zadanie o treści "Funkcja g liczy magiczne wartości. Policz sumę liczb g(0) + g(1) + ... + g(n-1)"

int g(int x){
	//jakieś obliczenia
	return magiczna_wartosc
}
int forrec(int i, int n){
	if(i>=n){
		return 0;
	}
	return g(i) + forrec(i+1, n);
}

dla każdego i od 0 do n zawołamy funkcję g(i) i dodamy ją do reszty wyników

### Sztuczka dla programów z wieloma testami

Jeśli w zadaniu mamy treść typu "Podana jest liczba t - liczba testów oraz t linii z danymi dla problemu" to można napisać schludny kod w następujący sposób:

int main(){
	int t;
	cin >> t;
	
	while(t--){
		//tutaj kod rozwiązujący pojedynczy przypadek
	}
	
}

Pętla while przerywa się, gdy warunek obliczy się do false lub liczby zero. W tym podejściu korzystamy z tego, że po każdym rozpatrzonym przypadku t zmiejsza się o 1 aż do 0

### Funkcje

Przpomnijmy sobie pewne wzory z geometrii: wzór na pole kwadratu $P = a\cdot a$ oraz na pole prostokąta $P = a \cdot b$
Oba te wzory możemy zapisać jako funkcje
$P(a)=a\cdot a$ oraz $P(a,b) = a\cdot b$
Ten zapis oznacza, że żeby policzyć wartość P należy podać wartości argumentów (tj. zmiennych w nawiasach) i wstawić je do wzoru

Bardzo podobnie jest w programowaniu

int pole_kwadratu(int a){
	return a*a;
} 
int pole_prostokata(int a, int b){
	return a*b;
}

Ponieważ programujemy to musimy powiedzieć komputerowi jakimi rodzajami wartości są a i b - są całkowitoliczbowe czyli int
Wartość którą otrzymamy z tych funkcji również oznaczyliśmy jako int w pierwszym słowie każdej z tych definicji

Żeby skorzystać z naszej funkcji piszemy

int main(){
	int moje_pole;
	moje_pole = pole_prostokata(3, 4);
	cout << moje_pole;
}	

Na razie skorzystaliśmy tylko z funkcji z intami, a co z long longami i charami? Oczywiście też można zrobić takie funkcje

long long duza_funkcja(long long a, long long b){
	long long tmp = a*b;
	return tmp - a - b;
}

Mamy też specjalny typ void. Mówi on o tym, że funkcja nic nie zwraca/nie produkuje żadnej wartości. Po co nam taka funkcja?

void wypisz_ladnie(int a){
	if(a%2==0){
		cout << "Ooo, to bardzo ładna liczba\n";
	}else{
		cout << "Nie podoba mi się\n";
	}
	//można dać return; ale nie trzeba
}

Dzięki takiej funkcji możemy wielokrotnie wypisywać ładnie liczby, ale nie oczekujemy wartości.

Istotne jest, że środku funckji modyfikujemy kopie argumentów. Spójrzmy na przykład

void start(int a){
	a = 5;
}
int main(){
	int a = 7;
	start(a);
	cout<<a;
	//wypisze się 7, bo do funkcji start trafia kopia zmiennej a
}

Do funkcji można przekazywać też tablice, ale zachowują się one inaczej niż zwykłe zmienne - funckja pracuje na oryginale tablicy, a nie kopii

void start(int t[], int n){
	for(int i = 0; i < n; i++){
		t[i] = i;
	}
}
int tab[100];
int main(){
	start(tab, 100);
	cout << tab[57];
	//wypisze 57
}

### Lista 7 - podpowiedzi
Najpierw przeczytaj notatkę poniżej.

#### System binarny
Patrz niżej

#### Szybkie potęgowanie
Złe rozwiązanie działa w czasie liniowym, szybkie w czasie logarytmicznym (w związku z reprezentacją binarną wykładnika)

Jeśli wychodzą Ci dziwne liczby to pewnie musisz zrobić operację modulo po każdym mnożeniu np.
zamiast a=a*x zrób a=(a*x)%1000009

Robienie takiego modulo pozwala na zachowanie dodatnich liczb oraz na sprawdzenie poprawności kodu (więcej na lekcji)

#### Czy jest pierwsza
Złe rozwiązanie działa w czasie liniowym i sprawdza dzielniki od 2 do n,
dobre w czasie pierwiastkowym tj. czas działania szacujemy funkcją $\sqrt n$

Po więcej wskazówek patrz niżej

#### Suma kolejnych

Złe rozwiązanie działa w czasie liniowym i liczy na piechotę sumę liczb w przedziale
Dobre działa w czasie stałym i korzysta ze wzoru na sumę https://pl.wikipedia.org/wiki/Szereg_1_%2B_2_%2B_3_%2B_4_%2B_%E2%80%A6

### Złożoność obliczeniowa

Złożoność programu mówi nam jak wiele operacji zostanie wykonane w zależności od rozmiaru danych wejściowych
Intuicyjnie myślimy o oszacowaniu "mniej więcej", bo nie interesują nas konkretne parametry

#### Czas stały
Np. wtedy gdy zawsze wykonujemy nie więcej niż 10 operacji

Przykład: dana jest liczba n, sprawdź czy jest parzysta

#### Czas liniowy
Gdy na wejściu mamy n liczb i dla wszystkich/większości musimy wykonać jakąś operację

Przykład: dane jest n liczb, policz ich sumę oraz iloczyn

##### Funkcja liniowa
O funkcji matematycznej myślimy jak o wzorze, do którego podstawiamy liczbę. Np. gdy piszemy
$f(x) = 5\cdot x+7$, czytamy ef od iks równa się $\dots$
Możemy policzyć wartość dla dowolnej liczby. Policzmy dla 3. Piszemy wtedy
$f(3)= 5\cdot 3 + 7=22$
Funkcje mogą mieć dowolne wzory po prawej stronie równości, funkcje liniowe to te, które są postaci $c\cdot n + d$

Jeśli możemy oszacować czas działania programu funkcją liniową to mówimy, że działa ona w czasie liniowym

#### Czas logarytmiczny
##### Logarytm
Logarytm to funkcja powiązana ściśle z potęgowaniem. Zapis $log_2 x = 3$ jest prawdą, tylko wtedy gdy prawdą jest $2^3=x$. Można sprawdzić, że $x = 8$
Niektóre programy, które piszemy mają złożoność logartymiczną. Np. zamiana na system binarny. Dlaczego? Każda liczba w systemie binarnym ma tylko logarytmicznie wiele cyfr

int main(){
	
	int n;
	cin >> n;
	int s = 1;
	while(s<=n){
		s*=2;
	}
	s/=2;
	
	while(s>=1){
		if(s <= n){
			cout << 1;
			n = n - s;
		}else{
			cout << 0;
		}
		s /= 2;
	}
	
}

Zamiana na system unarny będzie złym przykładem, bo zajmuje czas liniowy

Dla przypomnienia w systemie unarnym mamy $4 = (11110)_1$ oraz $5=(111110)_1$

int main(){
	
	int n;
	cin >> n;

	
	while(n>0){
		cout << 1;
	}
	cout << 0;
}

#### Czas kwadratowy

Czas kwadratowy mamy wtedy, gdy czas działania programu szacujemy funkcją kwadratową tj. postaci $an^2+bn+c$

Przykładem jest nieefektywne policzenie sum prefiksowych (nieefektywne, bo można to zrobić w czasie liniowym)

int tab[100];
int main(){
	
	
	int n;
	cin >> n;
	
	//wczytywanie
	for(int i = 0; i < n; i++){
		cin >> tab[i];
	}
	
	//rozwiązanie kwadratowe
	for(int i = 0; i < n; i++){
		int suma = 0;
		for(int j = 0; j <= i){
			suma += tab[j];
		}
		cout << suma << " "; 
	}
	cout << endl;
	//rozwiązanie liniowe
	int suma = 0
	for(int i = 0; i < n; i++){
		suma += tab[i];
		cout << suma << " ";
	}
	
}

Często, ale nie zawsze (!) czas liniowy można rozróżnić od czasu kwadratowego liczbą pętli w pętli.
### Pętle while
Pętle while (dopóki) pozwalają powtarzać operacje dopóki sprawdzany warunek jest prawdziwy

int main(){
	int n;
	
	cin >> n;
	
	//ten program wczytuje liczbę n, a potem wypisuje jej dzielniki
	int i = 1;
	while(i*i<=n){
		if(n%i==0){
			cout << i << " ";
			if(n/i!=i){
				cout << n/i << " "
			}
		}
		i++;
	}
	
	return 0;
}

### Pętle for
Pętle umożliwiają wykonywanie tych samych operacji wielokrotnie

#include <iostream>
using namespace std;

int main(){
	
	int n;
	
	cin >> n;
	
	//ten program wczytuje liczbę n, a potem wczytuje n liczb i wypisuje ich kwadraty
	
	for (int i = 0; i < n; i++){
		int a;
		cin >> a;
		cout << a*a << endl;
	}
	
	return 0;
}

for(int i = 0; i < n; i++)
	
int i = 0; <- zmienna, którą będziemy odliczać. Możemy zaczynać od innej liczby niż 0

i < n; <- jeśli prawda, to wykonaj instrukcje w klamerkach. Może być dowolny warunek typu <=, != itd.

i++ <- po każdym wykonaniu zmień liczbę. i++, i+=1, i=i+1 zwiększają o 1; i--,i-=1,i=i-1 zmiejszają o 1, można podawać inne wartości np. i+=2 lub inne operatory np. i *= 2

### Struktura programu

//dwoma slashami oznaczamy komentarze, które nie zmieniają programu

#include <iostream>
//to jest dołączenie bibliotek, które zawierają użyteczne i złożone instrukcje

using namespace std;
//nie musimy pisać std::cout tylko cout itd.

int main(){
	//w mainie piszemy nasz program, jego zakres wyznaczają nawiasy wąsate/klamerki
	
	
	return 0;
	//koniec programu podobny do halt w Maszynie RAM
}

Konstrukcje języka, które poznaliśmy

int main(){
	int liczba1, liczba2; // zmienna całkowitoliczbowa, podobna do komórek w RAM
	
	cin >> liczba1 >> liczba2; //wczytywanie 
	
	cout << "Tekst do wypisania" << liczba1; //wypisywanie
	
	
	if(liczba1 < liczba2){ //konstrukcja jeżeli
		
	}else if (liczba1 > liczba2){//w przeciwnym przypadku, jeżeli
		
	}else{//w przeciwnym przypadku
		
	}
	
	//znamy porównania
	<, <=, >, >=, ==, !=
	//mniejsze, mniejsze równe, większe, większe równe, równe, nierówne
		
	//instrukcja przypisania
	=
	liczba1 = liczba + 2;
	
	//instrukcje arytmetyczne
	+, -, *, /, %
	//ostatnie to reszta z dzielenia

	//sprawdzanie dwóch warunków
	//oraz, koniunkcja, dwa warunki na raz
	liczba1 < liczba2 && liczba3 < liczba4
	
	//lub, alternatywa, wystarczy jeden z
	liczba1 > 0 || liczba 2 > 0
}

Program kompilujemy (tłumaczymy na język komputera) zębatką, a uruchamiamy przyciskiem play

Typowe błędy:
* kompilator nie wie co to iostream - sprawdź czy plik ma rozszerzenie .cpp a nie .c
* przyciski na górze są wyszarzone - sprawdź czy program dalej działa zminimalizowany
* cout (lub inna instrukcja) does not name a type - sprawdź czy instrukcja jest w mainie lub czy main ma poprawne klamerki
* uwaga na count i cout
* inne błędy - często brak klamerek i średników
* program dziwnie działa, ale się uruchamia? - sprawdź czy nie pomyliłeś = z ==
* kierunek strzałek w cin i cout
### Edytory kodu
Wybieramy jeden z edytorów według własnego upodobania.

Jestem w stanie bardziej pomóc przy opcjach 1 i 3, bo je używałem samemu, ale 2 nie powinna odbiegać za bardzo.

1. Code::Blocks

link do pobrania: http://www.codeblocks.org/downloads/binaries/
Wybieramy wersję mingw setup
Mingw to kompilator, czyli narzędzie, które przekłada kod w C++ do zrozumiałego dla maszyny. W wersji bez mingw dostaniecie po prostu skomplikowany edytor tekstu bez możliwości uruchomienia programu.

Tak wygląda edytor

Należy stworzyć nowy plik, wkleić poniższy kod, a następnie wybrać przycisk zębatki i przycisk play (lub łączony). Jeśli program się uruchomił to wszytko ok. Na zajęciach wyjaśnimy sobie strukturę programu

#include <iostream>

using namespace std;

int main(){
	cout << "Witaj świecie!\n";
	return 0;
}

2. Dev C++

Link: https://www.bloodshed.net/

Wybieramy: original Dev-C++5 (NIE wersję IDE only)


Testujemy podobnie jak Code::Blocks z tą różnicą, że przycisk uruchomienia to jeden z tych kolorowych kwadracików u góry. Interesuje nas Compile & Run lub inna podobna opcja.

3. Dowolny inny edytor tekstu/kodu z kompilacją z poziomu linii poleceń

Jest to rozwiązanie dla osób które miały już kontakt z programowaniem i chcą spróbować bardziej współczesnych narzędzi.

Jeżeli ktoś jest zainteresowany wyborem np. VS Code, a nie wie jak to zrobić, to proszę o kontakt. Wtedy napiszę co należy zrobić.

## Maszyna RAM

Elementy interfejsu:
* taśma wejściowa
* na górze ekranu, tutaj wpisujemy liczby wchodzące **po kolei**
* taśma wyjściowa
* na dole ekranu, tutaj wypisywane są liczby **po kolei**
* kod programu
* główna część, w której podajemy listę instrukcji
* pamięć
* numerowana lista po lewej stronie, każda komórka może przechowywać 1 wartość
* procesor
* w lewym górnym rogu, służy do pokazywania obecnie przetwarzanej instrukcji
* akumulator
* komórka 0, służy do wykonywania operacji matematycznych z dwoma argumentami

Omówione instrukcje:
* read i write
* wczytuje wartość z taśmy wejściowej do komórki o numerze danym w argumencie
* wypisuje wartość na taśmę wyjściową z komórki o numerze danym w argumencie
* load i store
* load z numerem komórki wczytuje komórkę do akumulatora
* load ze stałą (=liczba) wpisuje liczbę do akumulatora
* store zapisuje akumulator do komórki
* add, mult, sub, div
* wykonują operacje dodawania, mnożenia, odejmowania, dzielenia całkowitego
* w dwóch wariantach:
* z liczbą w argumencie $\rightarrow$ operacja jest wykonywana na akumulatorze i drugiej komórce
* ze stałą $\rightarrow$ operacja wykonywana jest na akumulatorze z pomocą zadanej liczby

* jump
* program skacze do etykiety podanej w argumencie
* jzero (jump if zero)
* program skacze do etykiety, jeśli w akumulatorze jest 0, w przeciwnym przypadku wykonuje kolejną instrukcję z listy
* jgtz (jump if greater than zero)
* program skacze do etykiety, jeśli w akumaltorze, jest wartość >0

Lista 1 Zadanie Bardzo proste wyrażenie
Ważnym krokiem, w tym zadaniu, jest wczytanie wartości a i b do komórek, tak by nie stacić ich wartości. Można to wykonać przez instrukcję read 1, read 2, a potem skorzystać z instrukcji load, w celu przyniesienia wartości a lub b do akumulatora.

Lista 2 Zadanie Suma ciągu
Załączam schemat blokowy podobny do zadania długość ciągu


Lista 3 Zadanie Suma cyfr
Bardzo podobne do poprzednich zadań. Najważniejsza obserwacja to, że gdy podzielimy całkowicie liczbę dodatnią przez większą od niej otrzymamy 0. Dla przykładu
6 div 10 = 0 r. 6 => to zero pozwala stwierdzić czy należy zatrzymać program

Zamiana liczby na system binarny
Sposób 1:

Dzielimy liczbę całkowicie przez 2, dopóki nie dostaniemy 0. Reszty z dzielenia dają reprezentację binarną

19 div 2 = 9 r. 1
9 div 2 = 4 r. 1
4 div 2 = 2 r. 0
2 div 2 = 1 r. 0
1 div 2 = 0 r. 1

19 w zapisie binarnym to 10011

Sposób 2

Znajdujemy najmniejszą potęgę dwójki, która nie mieści się w naszej liczbie. Dopóki potęga nie spadnie do 0 to wykonujemy sprawdzenie czy potęga mieści się w analizowanej liczbie. Jeśli tak to odejmujemy ją od analizowanej liczby i otrzymujemy 1 w zapisie, jeśli nie to 0 w zapisie. Potęgę dzielimy na 2

Liczba 19
Potęga 32
Potęga 16
Liczba 19 - 16 = 3, do zapisu trafia 1, mamy 1
Potęga 8
Liczba 3, 3 < 8, więc do zapisu trafia 0, mamy 10
Potęga 4
Liczba 3, zapis 100
Potęga 2
Liczba 3 - 2 = 1, zapis 1001
Potęga 1
Liczba 1 - 1 = 0, zapis 10011
Potęga 0 -> Stop