added sem 14

8 files changed, 276 insertions, 1 deletions

diff --git a/README.md b/README.md
index f56d78a..5f43dc4 100644
--- a/README.md
+++ b/README.md
@@ -13,4 +13,5 @@
  - **Тема 10 (18.12.2020) :** Указатели. Символни низове. 
  - **Тема 11 (22.12.2020) :** Алгоритми върху масиви. Алгоритми за търсене. Алгоритми за сортиране.
  - **Тема 12 (27.12.2020) :** Референции. Пойнтери. Динамична памет. Задачи с низове.
- - **Тема 13 (08.01.2021) :** Стекова рамка. Рекурсия.
\ No newline at end of file
+ - **Тема 13 (08.01.2021) :** Стекова рамка. Рекурсия.
+ - **Тема 13 (09.01.2021) :** Подготовка за контролно 2.
\ No newline at end of file
diff --git a/Sem. 14/README.md b/Sem. 14/README.md
new file mode 100644
index 0000000..40c17fc
--- /dev/null
+++ b/Sem. 14/README.md
@@ -0,0 +1,14 @@
+**������ 1:** �� �� ��������� ���������� �������, ����� �������� ������� ����������.
+
+**������ 2:**  �� �� ������ ���������� �������, ����� �������� ���� ��������� � ���� �� ������ �� ������ �����.
+
+**������ 3:** ������ � ���� ��� ������� ����� �� ���� �����. ��������� �� ����� ������ �������� ����� ����� "����" ����� �� �������� �� ���� ������ � �����
+������ ��� �������. �������� �������, ����� ����� ���� ���� �� ������� �� �������� �� ���� �� ������.
+
+**������ 4:** ������ �� � ����� n � n �������� �� ����� (�� ���������� �����). �������� ���������� �������, ����� �������� ���� � ������ �� �������� ������� n ����� ����� (����� ������).
+
+**������ 5:** �������� �� ��� ��������� (� ���� ������� 1024). �� �� ������ �������, ����� ��������� ���� ����������� �� �� ������� ���� (����� ������ ���� �� ��� ���������� ���� ���������).
+
+**������ 6:** ����� � ������������ � ������� NxM. �� �� ������ �������, ����� ����� ���� �������������� ���� �� ���� ������ � ������ 1x2 � 3x1.
+
+ 
\ No newline at end of file
diff --git a/Sem. 14/task1.cpp b/Sem. 14/task1.cpp
new file mode 100644
index 0000000..01d4eb9
--- /dev/null
+++ b/Sem. 14/task1.cpp
@@ -0,0 +1,16 @@
+#include <iostream>
+using namespace std;
+
+unsigned binom(unsigned n, unsigned k)
+{
+	if (n < k)
+		return 0;
+	if (n == k || k == 0)
+		return 1;
+	return binom(n - 1, k) + binom(n - 1, k - 1);
+}
+
+int main()
+{
+	
+}
\ No newline at end of file
diff --git a/Sem. 14/task2.cpp b/Sem. 14/task2.cpp
new file mode 100644
index 0000000..f22e9ae
--- /dev/null
+++ b/Sem. 14/task2.cpp
@@ -0,0 +1,25 @@
+#include <iostream>
+using namespace std;
+
+void countBinaryElements(unsigned n, unsigned& zeros, unsigned& ones)
+{
+	if (n == 0)
+		return;
+
+	int lastBit = n % 2;
+	if (lastBit == 1)
+		ones++;
+	else if (lastBit == 0)
+		zeros++;
+	countBinaryElements(n >> 1, zeros, ones);
+
+}
+int main()
+{
+	int n;
+	cin >> n;
+
+	unsigned ones = 0, zeros = 0;
+	countBinaryElements(n, ones, zeros);
+	cout << ones << " " << zeros;
+}
\ No newline at end of file
diff --git a/Sem. 14/task3.cpp b/Sem. 14/task3.cpp
new file mode 100644
index 0000000..5df4d01
--- /dev/null
+++ b/Sem. 14/task3.cpp
@@ -0,0 +1,35 @@
+#include <iostream>
+using namespace std;
+
+bool checkIfPathExists(const int* field, bool* visited, int len, int pos)
+{
+	if (pos < 0 || pos >= len || visited[pos]) //out of bounds
+		return false;
+	if (pos == len - 1)
+		return true;
+
+	visited[pos] = true;
+
+	int value = field[pos];
+
+	return checkIfPathExists(field, visited, len, pos - value) || checkIfPathExists(field, visited, len, pos + value);
+
+}
+
+int main()
+{
+	int n;
+	cin >> n; //���������� �� ������.
+	int* field = new int[n];
+	bool* visited = new bool[n];
+
+	for (int i = 0; i < n; i++)
+	{
+		cin >> field[i];
+		visited[i] = false;
+	}
+	
+	cout << checkIfPathExists(field, visited, n, 0);
+
+	delete[] field, visited;
+}
diff --git a/Sem. 14/task4.cpp b/Sem. 14/task4.cpp
new file mode 100644
index 0000000..b48b521
--- /dev/null
+++ b/Sem. 14/task4.cpp
@@ -0,0 +1,32 @@
+#include <iostream>
+using namespace std;
+
+bool checkIfContainsFirstNEvenNumbers(const unsigned* arr, bool* visited, int len, int n)
+{
+	if (len == 0)
+		return true; //all values in visited should be true
+
+	int currentNumber = arr[0];
+	if (currentNumber % 2 != 0 || currentNumber > 2 * n - 2 || visited[currentNumber / 2])
+		return false;
+
+	visited[currentNumber / 2] = true;
+
+	return checkIfContainsFirstNEvenNumbers(arr + 1, visited, len - 1, n);
+
+}
+int main()
+{
+	int n;
+	cin >> n;
+	unsigned* arr = new unsigned[n];
+	bool* visited = new bool[n];
+	for (int i = 0; i < n; i++)
+	{
+		cin >> arr[i];
+		visited[i] = false;
+	}
+
+	cout << checkIfContainsFirstNEvenNumbers(arr, visited, n, n);
+	delete[] arr, visited;
+}
\ No newline at end of file
diff --git a/Sem. 14/task5.cpp b/Sem. 14/task5.cpp
new file mode 100644
index 0000000..9ea3923
--- /dev/null
+++ b/Sem. 14/task5.cpp
@@ -0,0 +1,110 @@
+#include <iostream>
+using namespace std;
+
+
+const int MAX_LEN = 1024;
+
+
+int contains(const char* str, const char* searched) 
+{
+	int len1 = strlen(str);
+	int len2 = strlen(searched);
+	for (int i = 0; i < len1 - len2 + 1; i++)
+	{
+		bool found = true;
+		for (int j = 0; j < len2; j++)
+		{
+			if (searched[j] != str[i + j])
+			{
+				found = false;
+				break;
+			}
+		}
+		if (found)
+			return i;
+	}
+	return -1;
+}
+bool containsOnlyWhiteSpaces(const char* str)
+{
+	while (*str != '\0')
+	{
+		if (*str != ' ')
+			return false;
+		str++;
+	}
+	return true;
+}
+void makeSpaces(char* str, int startIndex, int spacesCount)
+{
+	for (int i = startIndex; i < startIndex + spacesCount; i++)
+		str[i] = ' ';
+}
+bool hasSameWords(const char* sentence1, const char* sentence2)
+{
+	int len1 = strlen(sentence1);
+	int len2 = strlen(sentence2);
+
+	char* s1 = new char[len1 + 1];
+	char* s2 = new char[len2 + 1];
+	
+	char* s1Original = s1;// we change s1. So we could delete the whole array
+
+	strcpy(s1, sentence1);
+	strcpy(s2, sentence2);
+
+
+	for (int i = 0; i <= len1; i++)
+	{
+		if  (s1[i] != ' ' &&s1[i] != '\0' )
+			continue;
+		//we are here if we found a space (or a \0 which means it's the last word).
+
+
+		//if the space is at the begining, there is not a word before it. So we just remove it.
+		if (i == 0)
+		{
+			s1 += 1;
+			len1--;
+			i = -1;
+			continue;
+		}
+
+		char* currentWord = new char[i + 1];
+
+		s1[i] = '\0';
+		strcpy(currentWord, s1);
+
+		if (i != len1) //if it's not the last word (because after the last word there is an '\0').
+			s1[i] = ' ';
+		
+		int res = contains(s2, currentWord);
+		if (res == -1)
+			return false;
+
+		//we make the matched word as whitespaces.
+		makeSpaces(s1, 0, i);
+		makeSpaces(s2, res, i);
+
+		//we move the pointer to continue with the sentense.
+		s1 += i;
+		len1 -= i;
+
+		i = -1;
+		delete[] currentWord;
+	}
+
+	bool res = containsOnlyWhiteSpaces(s1Original) && containsOnlyWhiteSpaces(s2);
+	delete[] s1Original, s2;
+	return res;
+}
+int main()
+{
+	char sentence1[MAX_LEN];
+	char sentence2[MAX_LEN];
+
+	//cin.getline(sentence1, MAX_LEN);
+	//cin.getline(sentence2, MAX_LEN);
+
+	cout << hasSameWords("hello friends bye enemy", "bye friends  hello enemy");
+}
\ No newline at end of file
diff --git a/Sem. 14/task6.cpp b/Sem. 14/task6.cpp
new file mode 100644
index 0000000..f389bcf
--- /dev/null
+++ b/Sem. 14/task6.cpp
@@ -0,0 +1,42 @@
+#include <iostream>
+using namespace std;
+
+
+
+
+bool canBeCovered(int n, int m)
+{
+	if ((n == 0 && m >= 0) || (n>=0 && m==0)) //empty rectangle can be covered
+		return true;
+
+	if (n < 0 || m < 0) //out of range
+		return false;
+
+	if ((n == 1 && m == 2) || (n == 3 && m == 1)) //exactly one 1x2 or 3x1
+		return true;
+
+	if ((n == 1 && m == 1) || (n == 2 && m == 1)) // to swall for our plates
+		return false;
+
+	
+	
+	//if the plate 2x1 stands in the top left corner
+	bool case1 = (m >=2 && canBeCovered(n - 1, 2) && canBeCovered(n, m - 2)) //try cut vertically 
+			 ||  (n>=1 && canBeCovered(n-1, m) && canBeCovered(1, m-2)); //try cut horizontaly
+		
+	if (case1)
+		return true;
+
+	//if the plate 1x3 stands in the top left corner
+	bool case2 = (m >= 1 && canBeCovered(n - 3, 1) && canBeCovered(n, m - 1)) //try cut vertically 
+		|| (n>=3 && canBeCovered(3, m - 1) && canBeCovered(n - 3, m)); //try cut horizontaly
+
+	return case2;
+}
+int main()
+{
+	int n, m;
+
+
+	cout << canBeCovered(4, 3);
+}
\ No newline at end of file