Тема за държавен изпит септември 2008

Условия на задачите

http://fmi.wdfiles.com/local--files/di/KN-zadachi-09-2008.pdf

Задача 1

(1)
\begin{align} MIN(A) = <\{ q_{12}, q_{478}, q_{59}, q_3, q_6 \}, \{x, y, z\}, q_{12}, \delta', \{q_{12}, q_{478}\}> \begin{array}{c|c|c|c} q & x & y & z \\ \hline q_{12} & q_3 & q_{59} & q_{478} \\ q_{478} & q_{59} & q_{59} & q_{12} \\ q_{59} & q_{478} & q_{59} & q_{59} \\ q_3 & q_{478} & q_6 & q_3 \\ q_6 & q_{12} & q_6 & q_{12} \\ \end{array} \end{align}

Задача 2

Задача 3

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

class graph {
public:
  void set_coords() {
    int m, a, b;
    scanf("%d %d", &n, &m);
    v.clear();
    v.resize(n);
    for (int i = 0; i < m; ++ i) {
      scanf("%d %d ", &a, &b);
      v[a].push_back(b);
    }
  }
  void has_path(int source, int length, vector<int> &res) {
    if (length == 0) {
      res.push_back(source);
      return;
    }
    queue<int> q;
    q.push(0);
    q.push(-1);
    while(!q.empty()) {
      int cur = q.front();
      q.pop();
      if (cur < 0) {
        if (-cur == length) break;
        q.push(cur - 1);
        continue;
      }
      vector<int> &children = v[cur];
      for (int i = 0; i < children.size(); ++ i) {
        q.push(children[i]);
      }
    }
    while (!q.empty()) {
      res.push_back(q.front());
      q.pop();
    }
  }

private:
  int n;
  vector<vector<int> > v;
};

int main() {
  graph g;
  g.set_coords();
  vector<int> res;
  int source = 0;
  g.has_path(source, 4, res);

  for (int i = 0; i < res.size(); ++ i) {
    printf("%d ", res[i]);
  }
}

Задача 6

between(A,A,B) :- A =< B. 
between(X,A,B) :- A1 is A+1, between(X,A1,B).   % checks infinitely if 1 is between 2 and 4
square(N) :- between(K,0,N), N is K*K

Задача 7

(define (leaves t)
;; TODO
)

Задача 8

Задача 9

(2)
\begin{align} 1409 = 5 + 234 * 6 i = 1 \rightarrow 3 \\ i = 2 \rightarrow 5 \\ \vdots \\ i = (234 + 1) * 2 \rightarrow 1409 \\ \end{align}

На стъпка $i = 471$ дължината на низа ще надхвърли 1409.

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