Програмиране -
Падали се задачи

02 юли
2010 г.

17:19 ч.

http://www.fmi.uni-sofia.bg/exams/drzhaven-izpit/temi-drzhaven-izpit/kompyutrni-nauki/KN%20zadachi%2007-2008.pdf

Screen
clipping taken: 2.7.2010 г. 17:22 ч.

public abstract class ProductOrder {

private String productName;

private float productPrice;

public ProductOrder(String productName,
float productPrice){

this.productName = productName;

this.productPrice = productPrice;

}

public String getProductName(){

return productName;

}

public float getProductPrice(){

return productPrice;

}

public abstract
float getOrderPrice();

}

public class
UnitProductOrder extends ProductOrder {

private int units;

public UnitProductOrder(String
productName, float productPrice, int units){

super(productName, productPrice);

this.units = units;

}

public int getUnits(){

return units;

}

@Override

public float getOrderPrice() {

return getUnits() *
this.getProductPrice();

}

}

public class
QuantityProductOrder extends ProductOrder {

private float quantity;

public QuantityProductOrder(String
productName, float productPrice,

float quantityOrdered){

super(productName, productPrice);

this.quantity = quantityOrdered;

}

public float getQuantity(){

return quantity;

}

@Override

public float getOrderPrice() {

return this.getQuantity() *
this.getProductPrice();

}

}

public class
Order {

private int orderId;

private ProductOrder[] orderedProducts;

public Order(ProductOrder[]
orderedProducts){

this.orderedProducts =
orderedProducts;

}

public int getOrderId(){

return orderId;

}

public ProductOrder[]
getOrderedProducts(){

return orderedProducts;

}

public float getOrderPrice(){

float totalPrice = 0;

for (ProductOrder productOrder :
orderedProducts) {

totalPrice +=
productOrder.getProductPrice();

}

return totalPrice;

}

}

http://www.fmi.uni-sofia.bg/exams/drzhaven-izpit/temi-drzhaven-izpit/kompyutrni-nauki/KN%20zadachi%2009-2008.pdf

Screen
clipping taken: 2.7.2010 г. 17:23 ч.

#include
<iostream>

using
namespace std;

template
<typename T>

class
AbstractSet

{

public:

virtual bool
contains(T element) = 0;

virtual ~AbstractSet()

{

}

};

class IntSet
: public AbstractSet<int>

{

public:

virtual bool
contains(int element) = 0;

};

class
ModulusSet : public IntSet

{

private:

int modulus;

public:

ModulusSet(int modulus)

: modulus(modulus)

{

}

virtual bool
contains(int element)

{

bool contained = element % modulus == 0;

return contained;

}

};

class
ArraySet : public IntSet

{

private:

int *array;

int size;

public:

ArraySet(int arrayNumbers[], int size)

: array(0), size(size)

{

array = new int[size];

for(int i = 0; i < size; i++)

{

array[i] = arrayNumbers[i];

}

}

ArraySet(const ArraySet &other)

: array(0), size(other.size)

{

array = new int[size];

for(int i = 0; i < size; i++)

{

array[i] = other.array[i];

}

}

virtual bool
contains(int element)

{

bool contained = false;

for(int i = 0; i < size; i++)

{

if(array[i] == element)

{

contained = true;

break;

}

}

return contained;

}

virtual ~ArraySet()

{

delete[] array;

}

};

class
SetOfSets : public IntSet

{

private:

ArraySet **array;

int size;

public:

SetOfSets(ArraySet arraySets[], int size)

: array(0), size(size)

{

array = new ArraySet*[size];

for(int i = 0; i < size; i++)

{

array[i] = new ArraySet(arraySets[i]);

}

}

SetOfSets(const SetOfSets &other)

: array(0), size(other.size)

{

array = new ArraySet*[size];

for(int i = 0; i < size; i++)

{

array[i] = new ArraySet(*other.array[i]);

}

}

virtual bool
contains(int element)

{

bool contained = false;

for(int i = 0; i < size; i++)

{

if(array[i]->contains(element))

{

contained = true;

break;

}

}

return contained;

}

virtual ~SetOfSets()

{

for(int i = 0; i < size; i++)

{

delete array[i];

}

delete[] array;

}

};

void
AssertEqual(bool expected, bool actual)

{

if(actual == expected)

{

cout << "OK" << endl;

}

else

{

cout << "Failed" << endl;

}

}

int main()

{

int testNumber = 12;

int testModulus = 3;

ModulusSet modSet(testModulus);

bool result = modSet.contains(testNumber);

bool expectedResult = true;

AssertEqual(expectedResult, result);

int array[] = {1, 2, 3, 4};

int size = 4;

ArraySet arrSet(array, size);

testNumber = 1;

expectedResult = true;

result = arrSet.contains(testNumber);

AssertEqual(expectedResult, result);

int array2[] = {5, 6, 7, 8};

size = 4;

ArraySet arrSet2(array2, size);

ArraySet arrSets[] = { arrSet, arrSet2 };

SetOfSets setOfSets(arrSets, 2);

testNumber = 1;

expectedResult = true;

result = setOfSets.contains(testNumber);

AssertEqual(expectedResult, result);

testNumber = 6;

expectedResult = true;

result = setOfSets.contains(testNumber);

AssertEqual(expectedResult, result);

}

http://www.fmi.uni-sofia.bg/exams/drzhaven-izpit/temi-drzhaven-izpit/kompyutrni-nauki/INF-KN.pdf

Screen
clipping taken: 2.7.2010 г. 17:27 ч.

public
interface FileSystemObject {

int getSize();

}

public
class File implements FileSystemObject {

private int size;

private String name;

public File(String name, int size) {

this.size = size;

this.name = name;

}

public String getName(){

return name;

}

public int getSize() {

return size;

}

}

public
class Folder implements FileSystemObject {

private String name;

private FileSystemObject[]
fileSystemObjects;

public Folder(String name,
FileSystemObject[] files) {

this.fileSystemObjects = files;

this.name = name;

}

public String getName(){

return name;

}

public FileSystemObject[] getFiles(){

return fileSystemObjects;

}

public int getSize() {

int totalSize = 0;

for (FileSystemObject fsObject :
fileSystemObjects) {

totalSize += fsObject.getSize();

}

return totalSize;

}

}

public class
Main {

public static void main(String[] args) {

FileSystemObject file1 = new
File("text1.txt", 10);

FileSystemObject file2 = new
File("text2.txt", 11);

FileSystemObject[] innerFiles = new
FileSystemObject[] { file1 };

Folder innerFolder = new
Folder("innerFolder", innerFiles);

FileSystemObject[] rootFiles = new
FileSystemObject[] { innerFolder,

file2 };

Folder rootFolder = new
Folder("rootFolder", rootFiles);

int expectedSize = 21;

int actualSize = rootFolder.getSize();

if (expectedSize == actualSize) {

System.out.println("Passed.");

}

else{

System.out.println("Failed.");

}

}

}

Задача
4. (8т.) Попълнете в празните полета текстът (///), който се отпечатва на конзолата в резултат на изпълнението на
съответните програмни конструкции.

#include
<iostream.h>

class Base

{

public:

Base () {cout << "Base::Base()\n"; f(); g();}

Base (Base&) {cout << "Base::Base(Base&)\n";
f();g();}

virtual void f () {cout << "Base::f()\n";g();}

void g () {cout << "Base::g()\n";}

};

class
Derived1 : public Base

{

public:

Derived1 () {cout << "Derived1::Derived1()\n"; f();
g();}

Derived1 (Derived1 &) {cout <<
"Derived1::Derived1(Derived1&)\n";f();g();}

void f () {cout << "Derived1::f()\n";g();}

virtual void g () {cout << "Derived1::g()\n";}

};

class
Derived2 : public Derived1

{

public:

Derived2 () {cout <<
"Derived2::Derived2()\n";f();g();}

Derived2 (Derived2 &) {cout <<
"Derived2::Derived2(Derived2&)\n";f();g();}

void f () {cout << "Derived2::f()\n";g();}

void g () {cout << "Derived2::g()\n";}

};

void fCopy
(Base obj)

{

obj.f ();

obj.g ();

}

void main ()

{

Base *pBase = new Derived2;

///

/// при викане на конструктор се викат
базовите конструктори първо,

/// дори и да не са явно извикани

/// по време на конструиране механизма
на виртуалните функции е временно изключен

///

/// Base::Base()

/// Base::f()

/// Base::g()

/// Base::g()

/// Derived1::Derived1()

/// Derived1::f()

/// Derived1::g()

/// Derived1::g()

/// Derived2::Derived2()

/// Derived2::f()

/// Derived2::g()

/// Derived2::g()

///

Derived1 *pDerived1 = new Derived2;

///

/// типа на указателя не влияе на
изпълнението на конструктора

///

/// <sushtoto kato gornoto>

///

Derived2 *pDerived2 = new Derived2;

///

/// <sushtoto kato gornoto>

///

pBase->f ();

///

///

/// Derived2::f()  // в Base f е виртуална, затова имаме
динамично свързване

/// Derived2::g()  // в Derived2 g е виртуална - динамично
свързване

///

pDerived1->f ();

///

/// Derived2::f() // в Derived1 f е
виртуална - динамично свързване

/// Derived2::g() // в Derived2 g е
виртуална - динамично свързване

///

pDerived2->f ();

///

/// Derived2::f() // в Derived2 f е
виртуална - динамично свързване

/// Derived2::g() // в Derived2 g е
виртуална - динамично свързване

///

fCopy (*pBase);

///

/// параметъра на fCopy е от тип Base

/// обектите се предават чрез копиране при викане
на функция

///

/// Base::Base(Base&) //
затова се вика copy-конструктора на Base

/// Base::f()

///
Base::g()

///
Base::g()

/// Base::f()

/// Base::g()

/// Base::g()

///

delete pBase, pDerived1, pDerived2;

}

http://www.fmi.uni-sofia.bg/exams/drzhaven-izpit/temi-drzhaven-izpit/informatika/DI-Inf-septemvri%2009.pdf

Screen clipping taken: 2.7.2010 г. 17:49 ч.

void
merge(int a1[], int a2[], int n, int result[])

{

int i1 = 0;

int i2 = 0;

int ir = 0;

while(ir < n + n)

{

if(a1[i1] <= a2[i2])

{

result[ir] = a1[i1];

ir++;

i1++;

if(i1 == n)

{

break;

}

}

else

{

result[ir] = a2[i2];

ir++;

i2++;

if(i2 == n)

{

break;

}

}

}

for(int i = i1; i < n; i++)

{

result[ir] = a1[i];

ir++;

}

for(int i = i2; i < n; i++)

{

result[ir] = a2[i];

ir++;

}

}

int
main()

{

int a1[] = { 1, 3, 3, 5 };

int a2[] = { 0, 2, 4, 6 };

int result[8];

merge(a1, a2, 4, result);

return 0;

}

http://www.fmi.uni-sofia.bg/exams/drzhaven-izpit/temi-drzhaven-izpit/informatika/DI-Inf-yuli%2009.pdf

Screen clipping taken: 2.7.2010 г. 17:56 ч.

#include
<iostream>

using
namespace std;

const int
rows = 5;//2;

const int
columns = 10;//2;

bool
areLinear(double row1[columns], double row2[columns])

{

for(int column = 0; column < columns; column++)

{

if(row1[column] * row2[0] != row2[column] * row1[0])

{

return false;

}

}

return true;

}

bool
checkMatrix(double matrix[rows][columns])

{

for(int row1 = 0; row1 < rows; row1++)

{

for(int row2 = row1 + 1; row2 < rows; row2++)

{

if(areLinear(matrix[row1], matrix[row2]))

{

return true;

}

}

}

return false;

}

int main()

{

double matrix[rows][columns];

for(int row = 0; row < rows; row++)

{

for(int column = 0; column < columns; column++)

{

cin >> matrix[row][column];

}

}

bool result = checkMatrix(matrix);

cout << (result ? "yes" : "no") <<
endl;

return 0;

}

http://www.fmi.uni-sofia.bg/exams/drzhaven-izpit/temi-drzhaven-izpit/informatika/DI-I_March2008_v1.pdf

Screen clipping taken: 2.7.2010 г. 18:04 ч.

Май има
пропуснат << след cout.

S = 6

...

int S = 0;

for(int row = 0; row < 3; row++)

{

for(int column = 0; column < 3; column)

{

if(B[row][column] == 0)

{

break;

}

S += B[row][column];

}

}

cout << "S = " << S;

http://www.fmi.uni-sofia.bg/exams/drzhaven-izpit/temi-drzhaven-izpit/informatika/DI-I_March2008_v1.pdf

Screen clipping taken: 2.7.2010 г. 18:06 ч.

struct
ListElem

{

double data;

ListElem *next;

};

void
insertAfter(ListElem *element, double data)

{

ListElem *next = element->next;

ListElem *newElem = new ListElem;

newElem->data = data;

newElem->next = next;

element->next = newElem;

}

void
insert(ListElem *start, double key, double data)

{

ListElem *current = start;

while(current != 0)

{

ListElem *next = current->next;

if(current->data == key)

{

insertAfter(current, data);

}

current = next;

}

}

void
main()

{

ListElem elements[3];

elements[0].data = 0;

elements[0].next = &elements[1];

elements[1].data = 1;

elements[1].next = &elements[2];

elements[2].data = 0;

elements[2].next = 0;

insert(&elements[0], 0, 2);

insert(&elements[0], 2, 1);

return;

}

Задача 12. (4 т.)
Допълнете кода на функцията differ така, че да проверява дали редицата от цели
числа a0, a1, ... an-1 се състои от различни елементи.

bool
differ ( int n, int a[ ] )

{

int i, j ;

.........................

for (int i = 0; i
< n ; i++ )

{ .........................................

for ( int j = i +
1; j < n; j++ )

{  if(a[i] == a[j])

return false;

}

.........................................

}

.........................................

return true;

}

http://www.fmi.uni-sofia.bg/exams/drzhaven-izpit/temi-drzhaven-izpit/kompyutrni-nauki/DI-KN-july-09.pdf

Screen clipping taken: 2.7.2010 г. 17:39 ч.

#include <iostream>

using namespace std;

struct
ListElem

{

int data;

ListElem *next;

bool visited;

ListElem()

: next(0), visited(false), data(0)

{}

};

void
clearVisitedFlags(ListElem *start)

{

ListElem *current = start;

while(current != 0)

{

if(!current->visited)

{

return;

}

current->visited = false;

current = current->next;

}

}

bool
checkForCycles(ListElem *start)

{

ListElem *current = start;

while(current != 0)

{

if(current->visited)

{

clearVisitedFlags(start);

return true;

}

current->visited = true;

current = current->next;

}

clearVisitedFlags(start);

return false;

}

void
main()

{

ListElem elements[3];

elements[0].data = 0;

elements[0].next = &elements[1];

elements[1].data = 1;

elements[1].next = &elements[2];

elements[2].data = 0;

elements[2].next = &elements[0];

bool actual = checkForCycles(&elements[0]);

bool expected = true;

if(expected != actual)

{

cout << "Assert 1 Failed" << endl;

}

elements[2].data = 0;

elements[2].next = 0;

actual = checkForCycles(&elements[0]);

expected = false;

if(expected != actual)

{

cout << "Assert 2 Failed" << endl;

}

return;

}

http://www.fmi.uni-sofia.bg/exams/drzhaven-izpit/temi-drzhaven-izpit/kompyutrni-nauki/DI-KN-july-09.pdf

Screen clipping taken: 2.7.2010 г. 17:39 ч.

Java:

public
interface Function {

int
eval(int arg);

}

public
class LinearFunction implements Function {

private int a;

private int b;

public LinearFunction(int a, int b) {

this.a = a;

this.b = b;

}

public int
eval(int arg) {

return
a * arg + b;

}

}

public
class CharacteristicFunction implements
Function{

private int[] set;

public CharacteristicFunction(int[] set) {

this.set = set;

}

public int
eval(int arg) {

for(int
number : set){

if
(number == arg) {

return 1;

}

}

return
0;

}

}

public
class Superposition implements Function {

private Function inner;

private Function outer;

public Superposition(Function inner,
Function outer) {

this.inner = inner;

this.outer = outer;

}

public int
eval(int arg) {

return
outer.eval(inner.eval(arg));

}

}

public
class Main {

public static void Assert(int expected,
int actual){

if (expected != actual) {

System.out.println("Assert
Failed.");

}

else{

System.out.println("OK");

}

}

public static void main(String[] args) {

Function linear = new
LinearFunction(1, 0);

Function set = new
CharacteristicFunction(new int[] { 1, 2, 3, 4});

Function superset = new
Superposition(linear, set);

int x1 = 5;

int actual = linear.eval(x1);

int expected = x1;

Assert(expected, actual);

actual = set.eval(x1);

expected = 0;

Assert(expected, actual);

actual = superset.eval(x1);

expected = 0;

Assert(expected, actual);

int x2 = 4;

actual = linear.eval(x2);

expected = x2;

Assert(expected, actual);

actual = set.eval(x2);

expected = 1;

Assert(expected, actual);

actual = superset.eval(x2);

expected = 1;

Assert(expected, actual);

}

}

C++:

#include
<iostream>

using
namespace std;

class
Function

{

public:

virtual int eval(int x) = 0;

virtual ~Function(){ };

};

class
LinearFunction : public Function

{

private:

int a;

int b;

public:

LinearFunction(int a, int b)

: a(a), b(b)

{

}

virtual int eval(int x)

{

return a * x + b;

}

};

class
CharacteristicFunction : public Function

{

private:

int *set;

int size;

public:

CharacteristicFunction(int
*set, int size)

: size(size), set(0)

{

this->set = new
int[size];

for(int i = 0;i <
size;i++)

{

this->set[i] = set[i];

}

}

CharacteristicFunction(CharacteristicFunction
&other)

: size(other.size), set(0)

{

this->set = new
int[size];

for(int i = 0;i <
size;i++)

{

this->set[i] =
other.set[i];

}

}

virtual
~CharacteristicFunction()

{

delete[] set;

}

virtual int eval(int x)

{

for(int i = 0;i <
size;i++)

{

if(set[i] == x)

{

return 1;

}

}

return 0;

}

};

class
Superposition : public Function

{

private:

Function *inner;

Function *outer;

public:

Superposition(Function &inner, Function &outer)

: inner(&inner), outer(&outer)

{

}

virtual int eval(int x)

{

return outer->eval(inner->eval(x));

}

};

void
assert(int expected, int actual)

{

if (expected != actual)

{

cout << "Assert Failed." << endl;

}

else

{

cout << "OK" << endl;

}

}

void
main()

{

LinearFunction linear(1, 0);

int nums[] = {1, 2, 3, 4};

CharacteristicFunction set(nums, 4);

Superposition superset(linear, set);

int x1 = 5;

int actual = linear.eval(x1);

int expected = x1;

assert(expected, actual);

actual = set.eval(x1);

expected = 0;

assert(expected, actual);

actual = superset.eval(x1);

expected = 0;

assert(expected, actual);

int x2 = 4;

actual = linear.eval(x2);

expected = x2;

assert(expected, actual);

actual = set.eval(x2);

expected = 1;

assert(expected, actual);

actual = superset.eval(x2);

expected = 1;

assert(expected, actual);

}

http://www.fmi.uni-sofia.bg/exams/drzhaven-izpit/temi-drzhaven-izpit/kompyutrni-nauki/DI-KN-septemvri%2009.pdf

Screen clipping taken: 2.7.2010 г. 17:40 ч.

#include
<iostream>

using
namespace std;

const
int StringLen = 50;

bool
isSubstring(char source[StringLen], char target[StringLen])

{

int targetLen = strlen(target);

int sourceLen = strlen(source);

if(sourceLen < targetLen)

{

return false;

}

for(int i = 0; i < sourceLen - targetLen + 1; i++)

{

//strncmp - сравнява низовете, като ограничава дължината до targetLen

if(strncmp(target, &source[i], targetLen))

{

return true;

}

}

return false;

}

void
main()

{

const int count = 4;

char strings[count][StringLen];

for(int i = 0; i < count; i++)

{

cin >> strings[i];

}

for(int i = 0; i < count; i++)

{

bool substringsAll = true;

for(int j = 0; j < count; j++)

{

if(j == i)

{

continue;

}

if(!isSubstring(strings[i], strings[j]))

{

substringsAll = false;

break;

}

}

if(substringsAll)

{

cout << "yes" << endl;

return;

}

}

cout << "no" << endl;

}

http://www.fmi.uni-sofia.bg/exams/drzhaven-izpit/temi-drzhaven-izpit/kompyutrni-nauki/DI-KN-septemvri%2009.pdf

Screen clipping taken: 2.7.2010 г. 17:42 ч.

#include
<iostream>

using
namespace std;

class
Sequence

{

public:

virtual int getElement(int index) = 0;

virtual ~Sequence(){};

};

class
ArithmeticSequence : public Sequence

{

private:

int first;

int step;

public:

ArithmeticSequence(int first, int step)

: first(first), step(step)

{

}

virtual int getElement(int index)

{

return first + step * (index - 1);//1-based index

}

};

class
PeriodicSequence : public Sequence

{

private:

int *period;

int periodLength;

public:

PeriodicSequence(int *periodSequence, int periodLength)

: period(0), periodLength(periodLength)

{

period = new int[periodLength];

for(int i = 0; i < periodLength; i++)

{

period[i] = periodSequence[i];

}

}

PeriodicSequence(const PeriodicSequence &other)

: period(0), periodLength(other.periodLength)

{

period = new int[periodLength];

for(int i = 0; i < periodLength; i++)

{

period[i] = other.period[i];

}

}

virtual ~PeriodicSequence()

{

delete[] period;

}

virtual int getElement(int index)

{

int periodIndex = (index - 1) % periodLength;//1-based
index

return period[periodIndex];

}

};

class
InterleavedSequence : public Sequence

{

private:

Sequence *a;

Sequence *b;

public:

InterleavedSequence(Sequence &a, Sequence &b)

: a(&a), b(&b)

{

}

virtual int getElement(int index)

{

int innerIndex = (index - 1) / 2;//1-based index

if(index % 2 == 1)

{

return a->getElement(innerIndex + 1);

}

else

{

return b->getElement(innerIndex + 1);

}

}

};

void
assert(int expected, int actual)

{

if (expected != actual)

{

cout << "Assert Failed." << endl;

}

else

{

cout << "OK" << endl;

}

}

void
main()

{

ArithmeticSequence aritmSeq(1, 1);

int actual = aritmSeq.getElement(5);

int expected = 5;

assert(expected, actual);

int periodSeq[] = { 1, 2, 3, 4 };

PeriodicSequence periodic(periodSeq, 4);

actual = periodic.getElement(5);

expected = 1;

assert(expected, actual);

InterleavedSequence interleaved(aritmSeq, periodic);

// 1, 1, 2, 2, 3, 3, 4, 4, 5, 1, 6, 2

actual = interleaved.getElement(10);

expected = 1;

assert(expected, actual);

actual = interleaved.getElement(11);

expected = 6;

assert(expected, actual);

}

Задача 13. (5 т.) Дадена е свързана опашка, елементите на която се описват със структурата:

struct
QElem

{

int data;

QElem * next;

};

Самата опашка е представена посредством указатели към първия и последния си елемент:

struct
Queue

{

QElem * front;

QElem * rear;

};

Дадена е и следната функция за инициализиране

void
initialize (Queue* queue)

{

queue->front = 0;

queue->rear = 0;

}

а) (2 т.) Да се напише функцията

void
enqueue(Queue* queue, int data);

която добавя елемента data в опашката.

void
enqueue(Queue* queue, int data)

{

QElem *newElem = new QElem;

newElem->data = data;

newElem->next = 0;

if(queue->front == 0)

{

queue->front = newElem;

queue->rear = newElem;

}

else

{

queue->rear->next = newElem;

queue->rear = newElem;

}

}

б) (2 т.) Да се
напише функцията

int
dequeue(Queue* queue, int* data);

която премахва
елемент от опашката и записва стойността му в data. Връща 0 ако не е успяла да
премахне елемента и 1 ако е успяла.

int
dequeue(Queue* queue, int* data)

{

QElem *front = queue->front;

if(front == 0)

{

return 0;

}

if(front->next == 0)

{

queue->rear = 0;

}

queue->front = front->next;

int frontData = front->data;

delete front;

*data = frontData;

return 1;

}

Created with Microsoft OneNote 2010

One place for all your notes and information