5б. Алгоритми 2

Двоично търсене
// bsearch.cpp
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

int binary_search(vector<int> v, int from, int to, int a)
{
if (from > to)  return -1;
int mid = (from + to) / 2;
int diff = v[mid] - a;
if (diff == 0) return mid;          /* v[mid] == a */
else if (diff < 0)                  /* v[mid] < a */
return binary_search(v, mid + 1, to, a);
else
return binary_search(v, from, mid - 1, a);
}

void print(vector<int> a)
{
int i;
for (i = 0; i < a.size(); i++) cout << a[i] << " ";
cout << "\n";
}

void rand_seed()
{
int seed = static_cast<int>(time(0));
srand(seed);
}

int rand_int(int a, int b)
{  return a + rand() % (b - a + 1);  }

int main()
{
rand_seed();
vector<int> v(20);
int i;
v[0] = 1;
for (i = 1; i < v.size(); i++)
v[i] = v[i - 1] + rand_int(1, 10);
print(v);
cout << "Enter number to search for: ";
int n;
cin >> n;
int j = binary_search(v, 0, v.size() - 1, n);
cout << "Found in position " << j << "\n";
return 0;
}

Търсене и сортиране на реални данни
// esearch.cpp
#include <iostream>
#include <vector>
using namespace std;

#include "ccc_empl.cpp"

int binary_search(vector<Employee> v, int from, int to, string n)
{
if (from > to) return -1;
int mid = (from + to) / 2;
if (v[mid].get_name() == n)  return mid;
else if (v[mid].get_name() < n)
return binary_search(v, mid + 1, to, n);
else
return binary_search(v, from, mid - 1, n);
}

int main()
{
vector<Employee> staff(5);
staff[0] = Employee("Cracker, Carl", 48000.0);
staff[1] = Employee("Hacker, Harry", 35000.0);
staff[2] = Employee("Lam, Larry", 78000.0);
staff[3] = Employee("Reindeer, Rudolf", 63000.0);
staff[4] = Employee("Sandman, Susan", 51500.0);

cout << "Enter name of employee to search for: ";
string name;
getline(cin, name);

int i = binary_search(staff, 0, staff.size() - 1, name);

if (i >= 0)  cout << staff[i].get_name() << " "
<< staff[i].get_salary() << "\n";

return 0;
}

Бързо сортиране
А. Разделяне на дялове:
1. Избираме случаен елемент x от масива a
2. Преглеждаме масива отляво (от началото), докато достигнем до елемент >x
3. Преглеждаме масива отдясно (от края), докато достигнем до елемент <x
4. Разменяме местата на двата елемента
vector<int> a(n);
void partition(int x)
{
int i=1, j=n;
do
{
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i<=j)
{ swap(a[i], a[j]);  i++; j--; }
}
while (i<=j);
}
Б. Сортиране - след като масивът се раздели, двата му дяла се подлагат на същата обработка и това продължава, докато се получат дялове само с по един елемент.
void quicksort(int left, int right)
{
int i=left, j=right;
int x=a[(i + j)/2];
do
{
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i<=j)
{ swap(a[i], a[j]); i++; j--; }
}
while (i<=j);
if (left<j) quicksort(left, j);
if (i<right) quicksort(i, right);
}

Непряка рекурсия
Хилбертови криви

int x,y,h=512;
void Hilbert();
void A(int i);
void B(int i);
void C(int i);
void D(int i);

void Hilbert()
{ int i=0;
x=h/2; y=h/2;
do
{ i++; h/=2;
x=h/2; y=h/2;
A(i);
} while (h==2);
}

void A(int i)
{ if (i==0) return;
D(i-1); x-=h; plot();
A(i-1); y-=h; plot();
A(i-1); x+=h; plot();
B(i-1);
}
void B(int i)
{ if (i==0) return;
C(i-1); y+=h; plot();
B(i-1); x+=h; plot();
B(i-1); y-=h; plot();
A(i-1);
}
void C(int i)
{ if (i==0) return;
B(i-1); x+=h; plot();
C(i-1); y+=h; plot();
C(i-1); x-=h; plot();
D(i-1);
}
void D(int i)
{ if (i==0) return;
A(i-1); y-=h; plot();
D(i-1); x-=h; plot();
D(i-1); y+=h; plot();
C(i-1);
}
Hilbert.cpp

Ефективност на рекурсията
// fibtime.cpp
#include <iostream>
using namespace std;
#include "ccc_time.cpp"

long fib(int n)
{  if (n <= 2) return 1;
return fib(n - 1) + fib(n - 2);
}

int main()
{  cout << "Enter n: ";
int n;
cin >> n;
Time before;
long f = fib(n);
Time after;
cout << "fib(" << n << ") = " << f << "\n";
cout << "Elapsed time = " << after.seconds_from(before)
<< " seconds\n";
return 0;
}

// fibtrace.cpp
#include <iostream>
using namespace std;

long fib(int n)
{  cout << "Entering fib: n = " << n << "\n";
long f;
if (n <= 2) f = 1;
else f = fib(n - 1) + fib(n - 2);
cout << "Exiting fib: n = " << n
<< " return value = " << f << "\n";
return f;
}

int main()
{  cout << "Enter n: ";
int n;
cin >> n;
long f = fib(n);
cout << "fib(" << n << ") = " << f << "\n";
return 0;
}

// fibloop.cpp
#include <iostream>
using namespace std;
#include "ccc_time.cpp"

long fib(int n)
{  if (n <= 2) return 1;
long fold = 1;
long fold2 = 1;
int i;
long fnew;
for (i = 3; i <= n; i++)
{  fnew = fold + fold2;
fold2 = fold;
fold = fnew;
}
return fnew;
}

int main()
{  cout << "Enter n: ";
int n;
cin >> n;
Time before;
long f = fib(n);
Time after;
cout << "fib(" << n << ") = " << f << "\n";
cout << "Elapsed time = " << after.seconds_from(before)
<< " seconds\n";
return 0;
}
* Нерекурсивният вариант е по-ефективен.
* За пресмятане на  n! и двата варианта са еднакво ефективни.
* Двоичното търсене може да се направи нерекурсивно.
* Сортиране чрез сливане е трудно да се направи нерекурсивно.
* Бързата сортировка може да си направи нерекурсивна