Di Zad2012sep

Държавен изпит септември 2012

Disclaimer: редът на задачите не е този, едва ли е важно. За задачите, които помня, съм сложил условията или материала, в/у който са.

Зад. 1

Зад. 2

Намиране на най-дълга обща подредица - точно както е формулирано в темата за динамично програмиране.

Зад. 3

Обхождане на граф в дълбочина.

class Node
{
    public double data;
    public Node south;
    public Node north;
    public Node west;
    public Node east;
}

Даден ви е начален Node. Напишете функция

void printNodes(Node start);

която да принтира всички достижими възли. Обхождането да става в дълбочина.
Може да е на Java или C++

Зад. 4

Функционално програмиране
Дефинирайте на Scheme функция, която да приема 3 аргумента - функция на един аргумент f,2 списъка l1, l2 с еднакъв брой аргументи. Трябва да се оценява като #t, ако l2 е пермутация на (map f l1). т.е. l2 се получава като приложим f върху всеки един от елементите на l1 и след това вземем някоя пермутация на резултата.
Пример:

(shaken_image (lambda (x) (* x x)) '(1 2 5 2 1) '(25 1 4 1 4)) ---> #t
(shaken_image (lambda (x) (* x x)) '(1 2 5 2 1) '(1 3 4 8 4)) ---> #f

Решение

(define (list-without-helper list element current-sublist)
  (cond
    ((null? list) current-sublist)
    ((= (car list) element) (append current-sublist (cdr list)))
    (else (list-without-helper (cdr list) element (append current-sublist (cons (car list) '()))))))

(define (list-without list element) (list-without-helper list element '()))

(define (permutation? list1 list2)
  (cond
    ((and (null? list1) (null? list2)) #t)
    ((and (null? list1) (not (null? list2))) #f)
    (else (permutation? (cdr list1) (list-without list2 (car list1))))))

(define (shaken-image f list1 list2)
  (permutation? list2 (map f list1)))

Зад. 5

Да се напише клас Object
Всеки Object има volume.
Клас Box extends Object.
Box има capacity.
Volume на Box е capacity * 1.1.
Box може да съдържа Objects.
Box трябва да предоставя функционалност за добавяне на обект като проверява да не се добавя сама себе си, както и общия обем на обектите вътре да не е по-голям от capacity.
Трябва да предоставя методи за общия зает и незает capacity.
Трябва да предоставя static метод който да връща общия брой създадени Box-ове;

Ball extends Object
Ball има радиус.
Обемът на Ball е 4/3πr^3.(толкова беше, нали)

Зад. 6

DB. нищо по-различно от обикновено

Зад. 7

Алгебра, Sn, действие на група в/у множество, спрягане.

Зад. 8

Доказване на предикатна тавтология по метода на резолюцията.

Зад. 9

Сортиране на Singly Linked List

Зад. 10

Интегралче