From 1f1bba9cbb7c9924da7aa25de46596c11bd6f202 Mon Sep 17 00:00:00 2001 From: Syndamia Date: Fri, 5 Jan 2024 15:29:15 +0200 Subject: [w12] Added solutions --- week12/ex1.cpp | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++ week12/ex2.cpp | 45 ++++++++++++++++++++++++++++++++++++++ week12/ex3.cpp | 58 +++++++++++++++++++++++++++++++++++++++++++++++++ week12/ex4.cpp | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 234 insertions(+) create mode 100644 week12/ex1.cpp create mode 100644 week12/ex2.cpp create mode 100644 week12/ex3.cpp create mode 100644 week12/ex4.cpp (limited to 'week12') diff --git a/week12/ex1.cpp b/week12/ex1.cpp new file mode 100644 index 0000000..ac00f61 --- /dev/null +++ b/week12/ex1.cpp @@ -0,0 +1,63 @@ +#include + +// Това е значително по-просто решение, аз не се сетих, взех от Катрин Попова +int knapsack2(int i, int *values, int *weights, int size, int maxWeight) { + if (i == size) + return 0; + + int currentNotTaken = knapsack2(i+1, values, weights, size, maxWeight); + + if (weights[i] <= maxWeight) { + int currentTaken = values[i] + knapsack2(i+1, values, weights, size, maxWeight - weights[i]); + return currentTaken > currentNotTaken ? currentTaken : currentNotTaken; + } + return currentNotTaken; +} + +// Това е решението, показано на практикума +void knapsack1(int i, int& maxValues, bool *taken, int *values, int *weights, int size, int maxWeight) { + if (i == size) { + int currentValues = 0, currentWeight = 0; + for (int i = 0; i < size; i++) { + if (taken[i]) { + currentValues += values[i]; + currentWeight += weights[i]; + } + } + if (currentWeight > maxWeight) return; + if (currentValues > maxValues) { + maxValues = currentValues; + } + return; + } + + taken[i] = false; + knapsack1(i+1, maxValues, taken, values, weights, size, maxWeight); + + taken[i] = true; + knapsack1(i+1, maxValues, taken, values, weights, size, maxWeight); +} + +int main() { + int N; + std::cin >> N; + + int *values = new int[N]; + int *weights = new int[N]; + for (int i = 0; i < N; i++) { + std::cin >> values[i] >> weights[i]; + } + int maxWeight; + std::cin >> maxWeight; + + int maxValues = 0; + bool *taken = new bool[N]; + knapsack1(0, maxValues, taken, values, weights, N, maxWeight); + std::cout << maxValues << std::endl; + delete[] taken; + + std::cout << knapsack2(0, values, weights, N, maxWeight) << std::endl; + + delete[] values; + delete[] weights; +} diff --git a/week12/ex2.cpp b/week12/ex2.cpp new file mode 100644 index 0000000..e123ed3 --- /dev/null +++ b/week12/ex2.cpp @@ -0,0 +1,45 @@ +#include + +void floodFill(int row, int col, char** board, int rows, int cols) { + if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] == '#') + return; + + board[row][col] = '#'; + floodFill(row+1, col, board, rows, cols); // up + floodFill(row-1, col, board, rows, cols); // down + floodFill(row, col+1, board, rows, cols); // right + floodFill(row, col-1, board, rows, cols); // left +} + +int main() { + int N, M; + std::cin >> N >> M; + + char** board = new char*[N]; + for (int i = 0; i < N; i++) { + board[i] = new char[M]; + } + + for (int i = 0; i < N; i++) { + for (int j = 0; j < M; j++) { + std::cin >> board[i][j]; + } + } + + int X, Y; + std::cin >> X >> Y; + + floodFill(X, Y, board, N, M); + + for (int i = 0; i < N; i++) { + for (int j = 0; j < M; j++) { + std::cout << board[i][j] << " "; + } + std::cout << std::endl; + } + + for (int i = 0; i < N; i++) { + delete[] board[i]; + } + delete[] board; +} diff --git a/week12/ex3.cpp b/week12/ex3.cpp new file mode 100644 index 0000000..e5c64ef --- /dev/null +++ b/week12/ex3.cpp @@ -0,0 +1,58 @@ +#include + +void markQueen(int valueBy, int row, int col, int board[8][8]) { + for (int i = 0; i < 8; i++) { + board[row][i] += valueBy; + } + for (int i = 0; i < 8; i++) { + board[i][col] += valueBy; + } + for (int i = 0; i < 8; i++) { + if (row+i < 8 && col+i < 8) + board[row+i][col+i] += valueBy; + if (row-i > -1 && col-i > -1) + board[row-i][col-i] += valueBy; + } + for (int i = 0; i < 8; i++) { + if (row-i > -1 && col+i < 8) + board[row-i][col+i] += valueBy; + if (row+i < 8 && col-i > -1) + board[row+i][col-i] += valueBy; + } +} + +void placeQueen(int row, int col, int board[8][8]) { + markQueen(1, row, col, board); +} + +void removeQueen(int row, int col, int board[8][8]) { + markQueen(-1, row, col, board); +} + +int possibleSolutions(int row, int board[8][8]) { + // Board is filled with queens + if (row == 8) { + // За бонуса, тук просто принтираме целия board + return 1; + } + + // Find first free column, if any + int col = 0; + int sum = 0; + while (col < 8) { + // Place queen temporarily + if (board[row][col] == 0) { + placeQueen(row, col, board); + sum += possibleSolutions(row + 1, board); + removeQueen(row, col, board); + } + col++; + } + + return sum; +} + +int main() { + int board[8][8] = { { 0 } }; + std::cout << possibleSolutions(0, board) << std::endl; +} diff --git a/week12/ex4.cpp b/week12/ex4.cpp new file mode 100644 index 0000000..98bbe72 --- /dev/null +++ b/week12/ex4.cpp @@ -0,0 +1,68 @@ +#include + +// Главното неприятно нещо в тази задача е, че трябва да обгърнем вградените оператори във фунцкии +int add(int a, int b) { + return a + b; +} +int sub(int a, int b) { + return a - b; +} +int mul(int a, int b) { + return a * b; +} +int divi(int a, int b) { + return a / b; +} +int pow(int a, int b) { + int res = 1; + while (b-- > 0) { + res *= a; + } + return res; +} + +int recRPN(int (*&op)(int, int), int &on) { + int num; + std::cin >> num; + + // Ако имаме операция, "връщаме" указател към конкретната функция + if (std::cin.fail()) { + std::cin.clear(); + char c; + std::cin >> c; + if (c == '\'') std::cin >> c; + + switch (c) { + case '+': op = add; on = 2; break; + case '-': op = sub; on = 2; break; + case '*': op = mul; on = 2; break; + case '/': op = divi; on = 2; break; + case '^': op = pow; on = 2; break; + case '$': on = -1; break; + } + return 0; + } + + // Докато не плучим "операция" $, гледаме следващите изрази какво ще върнат + do { + int rightValue = recRPN(op, on); + // Ако сегашната стойност е дясната страна на оператора + if (on == 2) { + on = 1; + return num; + } + // Ако сегашната стойност е лявата страна на оператора + if (on == 1) { + on = 0; + num = (*op)(num, rightValue); + } + } while(on > -1); + + return num; +} + +int main() { + int (*op)(int, int); + int on; + std::cout << recRPN(op, on) << std::endl; +} -- cgit v1.2.3