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";
   else         cout << "Not found.\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! и двата варианта са еднакво ефективни.
* Двоичното търсене може да се направи нерекурсивно.
* Сортиране чрез сливане е трудно да се направи нерекурсивно.
* Бързата сортировка може да си направи нерекурсивна