added sem 14

7 files changed, 274 insertions, 0 deletions

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