Тема за държавен изпит юли 2008
Условия на задачите
http://fmi.wdfiles.com/local--files/di/KN-zadachi-07-2008.pdf
Задача 1
(1)\begin{equation} I_n = I_{n-1} + 2I_{n-2} - 1 \end{equation}
Задача 2
(2)\begin{align} DFA(A) = <\{q_0, q_{01}, q_2, q_3, q_4, q_5, q_{56}, \varnothing \}, \{a, b, c\}, q_0, \delta', \{q_0, q_01\}> \begin{array}{c|c|c|c} q & a & b & c \\ \hline q_0 & q_{01} & \varnothing & q_3 \\ q_{01} & q_{01} & q_2 & q_3 \\ q_2 & q_0 & \varnothing & q_2 \\ q_3 & \varnothing & q_5 & q_4 \\ q_4 & \varnothing & q_{56} & q_2 \\ q_5 & \varnothing & \varnothing & q_4 \\ q_{56} & \varnothing & q_0 & q_4 \\ \end{array} \end{align}
Задача 5
#include <cstdio>
#include <vector>
using namespace std;
struct node {
int val;
node *l, *r;
node() {}
node(int val, node *l=NULL, node *r=NULL): val(val), l(l), r(r) {}
};
struct bst {
node *root;
bst(): root(NULL) {}
void add(int val) {
_add(root, val);
}
~bst() {
_clean(root);
root = NULL;
}
node *find(int val) {
return _find(root, val);
}
void get_elems(int desired_depth, vector<int> &elems) {
_get_elems(root, 0, desired_depth, elems);
}
private:
void _clean(node *nd) {
if (nd == NULL) {
return;
}
_clean(nd->l);
_clean(nd->r);
delete nd;
}
void _add(node *&nd, int val) {
if (nd == NULL) {
nd = new node(val);
return;
}
if (val < nd->val) {
_add(nd->l, val);
} else {
_add(nd->r, val);
}
}
node *_find(node *nd, int val) {
if (nd == NULL) {
return NULL;
}
if (val == nd->val) {
return nd;
} else if (val < nd->val) {
return _find(nd->l, val);
} else {
return _find(nd->r, val);
}
}
void _get_elems(node *nd, int depth, int desired_depth, vector<int> &elems) {
if (nd == NULL) {
return;
}
if (depth == desired_depth) {
elems.push_back(nd->val);
return;
}
_get_elems(nd->l, depth + 1, desired_depth, elems);
_get_elems(nd->r, depth + 1, desired_depth, elems);
}
};
vector<int> get_elems(bst *tree, int depth) {
vector<int> res;
tree->get_elems(depth, res);
return res;
}
int main() {
bst t;
t.add(4);
t.add(2);
t.add(7);
t.add(6);
t.add(3);
t.add(1);
t.add(9);
vector<int> res = get_elems(&t, 2);
for (int i = 0; i < res.size(); ++ i) {
printf("%d \n", res[i]);
}
}
Задача 6
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
class ShopUnit {
public:
ShopUnit(string name, double price): name(name), price(price) {}
virtual double cost() const = 0;
protected:
string name;
double price;
};
class Countable: public ShopUnit {
public:
Countable(string name, double price, int count)
: ShopUnit(name, price), count(count) {}
virtual double cost() const {
return price * count;
}
private:
int count;
};
class Uncountable: public ShopUnit {
public:
Uncountable(string name, double price, double amount)
: ShopUnit(name, price), amount(amount) {}
virtual double cost() const {
return price * amount;
}
private:
double amount;
};
class Receipt {
public:
Receipt(int number, vector<ShopUnit *> units): number(number), units(units) {}
double total_cost() const {
double total = 0.0;
for (int i = 0; i < units.size(); ++ i) {
total += units[i]->cost();
}
return total;
}
private:
int number;
vector<ShopUnit *> units;
};
int main() {
Countable eggs("eggs", 0.45, 6);
Uncountable sugar("sugar", 1.20, 0.5);
Uncountable flour("flour", 1.40, 1.5);
Uncountable butter("butter", 9.40, 0.2);
vector<ShopUnit *> units;
units.push_back(&eggs);
units.push_back(&sugar);
units.push_back(&flour);
units.push_back(&butter);
Receipt receipt(205, units);
printf("You owe %.2lf for the cake ;)\n", receipt.total_cost());
}
Решението с шаблонно наследяване е по-елегантно и спазва DRY принципа, но в условието се иска "да се реализират два производни класа".
template <typename T>
class Foo: public ShopUnit {
public:
Foo(string name, double price, T amount)
: ShopUnit(name, price), amount(amount) {}
virtual double cost() const {
return price * amount;
}
private:
T amount;
};
typedef Foo<int> Countable;
typedef Foo<double> Uncountable;
Задача 7
(define (ways g u v)
;; TODO
)
Задача 8
1
2
3
7
5
4
7
Задача 9
в)
page revision: 2, last edited: 25 Mar 2011 08:44