Тема за държавен изпит юли 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

в)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License