// Задача за намиране на число по негов римски запис.
//
// Рекурсивна версия:
// 
#include <iostream>
#include <string>
using namespace std;

int StringValue(string s);
int val(char ch);

int main()
{  string str;
   cout << "Enter a Roman numeral: ";
   cin >> str;
   cout << "Value: " << StringValue(str) << endl;
   char ch=cin.get(); ch=cin.get();
   return 0;
}

int StringValue(string s)
{
 int max = 0, imax, v, n=s.length();
 if (n>0)
 {
  for (int i=0; i<n; i++)
     if ((v = val(s[i])) > max)
  {
   max = v; imax = i;
  }
  max -= StringValue(s.substr(0, imax));
  max += StringValue(s.substr(imax+1, n-imax-1));
 }
 return max;
}

int val(char ch)
{  switch(ch)
   {  case 'M': return 1000;
      case 'D': return 500;
      case 'C': return 100;
      case 'L': return 50;
      case 'X': return 10;
      case 'V': return 5;
      case 'I': return 1;
   }
   cout << "Illegal character.\n"; exit(1);
   return 0;
}

// Итеративна версия:
//
#include <iostream>
#include <string>

using namespace std;

class FromRoman {
public:
   FromRoman(const string &s);
   int number;
private:
   int val(char ch);
};

FromRoman::FromRoman(const string &s)
{
 number = 0;
 int i = 0, si, si1;
 while (s[i])
 {
   si = val(s[i]);
   if (s[i+1] && (si1 = val(s[i+1])) > si)
   { number = number + si1 - si; i += 2; }
   else
   { number += si; i++; }
 }
}

int FromRoman::val(char ch)
{
 switch(ch)
 {  case 'M': return 1000;
    case 'D': return 500;
    case 'C': return 100;
    case 'L': return 50;
    case 'X': return 10;
    case 'V': return 5;
    case 'I': return 1;
 }
 cout << "Illegal character.\n"; exit(1);
 return 0;
}

int main()
{  char str[100];
   cout << "Enter a Roman numeral: ";
   cin >> str;
   cout << "Value: " << FromRoman(str).number << endl;
   return 0;
}

Литература: 
[1] - 7.5.2
[3] - 1.4
------------------------------------------------------------
 Функция на Акерман
 А е дефинирана за всички цели неотрицателни числа:
 A(0,n) = n + 1
 A(m,0) = A(m-1,1), m>0
 A(m,n) = A(m-1,A(m,n-1)), m,n>0
 Да се напишат рекурсивна и нерекурсивна програми за пресмятане на 
 тази функция.  
 
Литература: 
[2] - Упр. 3.7
------------------------------------------------------------
Да се напишат рекурсивна и нерекурсивна програми за пресмятане на 
a на степен b по модул с, където 0 < a, b, c < 32000 са естествени 
числа.
Упътване: Използвайте рекурентната формула: 
          a^b mod c = a.(a^(b-1) mod c) mod c
------------------------------------------------------------
Дефиниция 1.
n!!..!=n*(n-k)*(n-2*k)*...*(n mod k) ако k не дели n
n!!..!=n*(n-k)*(n-2*k)*...*k ако k дели n (и в двата случая има 
k знака !)
Дефиниция 2. 
X mod Y - остатъка на X при деление на Y.
Например: 10 mod 3=1; 3!=3*2*1; 10!!!=10*7*4*1
Задача:
Ако знаем n и k трябва да пресметнем стойността от първата 
дефиниция. 

Литература:
http://fmiopen.hit.bg/fact.htm
------------------------------------------------------------
// Търсене с връщане - разходката на коня
//
// Дадена е шахматна дъска с размери n на n. Конят, на 
// който е разрешено да се движи по правилата на шаха, 
// се поставя на полето с начални координати x0,y0.
// Да се намери покритие на цялата дъска, ако такова съществува,
// т.е. да се определи разходка от n^2-1 хода по такъв начин, 
// че всяко поле на дъската да бъде посетено точно веднъж.
//
#include <iostream>
#include <iomanip>
#define and &&

using namespace std;

int const N=5, NSD=N*N;
int h[N][N];
bool try0(int i, int x, int y);

int main()
{
 int i,j;
 for (i=0; i<N; i++)
    for (j=0; j<N; j++) h[i][j]=0;
 h[0][0]=1;
 if (try0(2,0,0))
   for (i=0; i<N; i++)
   {
    for (j=0; j<N; j++) cout << setw(4) << h[i][j] << "  ";
    cout << endl;
   }
 else cout << "No solution" << endl;
 cout << endl << "Press any key." << endl;
 char ch=cin.get();
 return 0;
}

bool try0(int i, int x, int y)
{
 int const A[8]={2,1,-1,-2,-2,-1, 1, 2};
 int const B[8]={1,2, 2, 1,-1,-2,-2,-1};
 if (i==NSD+1) return true;
 int k, u, v;
 for(k=0; k<8; k++)
 {
  u=x+A[k]; v=y+B[k];
  if ((u<N) and (u>=0) and
      (v<N) and (v>=0) and (h[u][v]==0))
  {
   h[u][v]=i;
   if (try0(i+1,u,v)) return true;
   h[u][v]=0;
  }
 }
 return false;
}
/***************************************************************
Задачи:
1. Коригирайте програмата така, че началната позиция да се въвежда от потребителя.
2. Може ли конят да обходи шахматната дъска, ако му разрешаваме да "завива
само наляво", т.е. полето, на което стъпва е вляво от хоризонтала или 
вертикала, по който се движил конят? 
2. Може ли конят да обходи шахматната дъска, ако променим правилата за 
движението му - да се премества 3 полета направо (вместо 2) и едно встрани?
Литература:
[1] - 1.22
[2] - 3.4
***************************************************************/
------------------------------------------------------------
// Задача за подмножества.
//
// Даден е масив A с N елемента - естествени числа и цяло число S.
// Да се намерят всички суми на елементи на масива, които са равни
// на S.

#include <iostream>
#include <stdlib.h>
#include <cmath>

unsigned int const N=4;
int const A[N]={1,2,3,4};
int const SUM = 6;

int two_p(int n)
{ return static_cast<int>(pow(2,n)); }

int const NN = two_p(N);

void count()
{
 unsigned int i, j;
 for(i=1; i<NN; i++)
 {
  int sum=0;
  for(j=0; j<N; j++) if (two_p(j) & i)
  {
   sum+=A[j]; cout << A[j] << "+";
  }
  if (sum==SUM) cout << "   OK";
  cout << endl;
 }
}

int main()
{
 count();
 system("PAUSE");
 return 0;
}
/***************************************************************
Задачи:
1. Да се промени програмата така, че да се повиши бързодействието й;
2. Програмата да може да работи при N=20;
3. Да се напише нова програма като един елемент на масива да може 
да участва в сумата няколко пъти. 
4. Даден е масив A с N елемента - естествени числа и цяло число S.
Да се намерят всички суми на елементи на масива, които по модул
(остатък от деление) са равни на S.

Литература: 
[1] - 1.13, 1.23, 1.24
[3] - 10.4
***************************************************************/
------------------------------------------------------------
Даден е двумерен масив от положителни и отрицателни цели
числа. Сума в правоъгълник се нарича сумата от всички елементи
в този правоъгълник. В тази задача подправоъгълник с най-голяма
cума се нарича максимален подправоъгълник. Подправоъгълник се
нарича всеки съседен под-масив с размери 1 х 1 или  повече
намиращ се в масива.

Литература:
http://fmiopen.hit.bg/maxsum.htm
------------------------------------------------------------
Дадени са камъни с тегла V1,V2,V3,...,VN. Напишете програма,
която ще ги подреди в две купчини, така че разликата в
тежестите на купчините да е минимална.

Литература:
http://fmiopen.hit.bg/stones.htm
-----------------------------------------------------------