Algorithm exercise log

One-half search (binary search)

/** ** The binary search algorithm is used to find a number in an array
#include <iostream>
using namespace std;
int binSearch(int a[],int low,int high,int num)
{
    int mid;
    if(low<high)  
    {
      mid = (low+high)/2;   // Find the middle of the interval
      if(a[mid]==num)
            return mid;
      if(a[mid]>num)
        return binSearch(a,low,mid- 1,num);
      else
        return binSearch(a,mid+1,high,num);
    }
    return - 1;
}
int main(a)
{
    int n;
    cout<<"Input array length :";
    cin>>n;
    int a[n];
    cout<<"Input array (sorted):"<<endl;
    for(int i=0; i<n; i++)cin>>a[i];
    int num;
    cout<<"Enter the number to find :";
    cin>>num;
    int i =binSearch(a,0,n,num);
    if(i>=0)
        cout<<num<<"A ["<<i<<"]"<<endl;
    else
        cout<<"Not found"<<num<<endl;

    return 0;
}

Copy the code

Two, quicksort

/* * Do a quick sort on arrays */
#include <iostream>
using namespace std;
void display(int a[],int n)
{
    for(int i=0; i<n; i++)cout<<a[i]<<"";
    cout<<endl;
}
int position(int a[],int s,int e)
{
    int i =s,j =e;
    int temp = a[s];
    while(i! =j) {while(j>i&&a[j]>=temp)
            j--;// Scan from right to left
        a[i] = a[j];
        while(i<j&&a[i]<=temp)
            i++;
        a[j] = a[i];
    }
    a[i] = temp;
    return i;
}
void quickSort(int a[],int s,int e)
{   if(s<e)
    {
        // Have at least two elements, recursively sort
        int i = position(a,s,e);
        quickSort(a,s,i- 1);/ / the left subtree
        quickSort(a,i+1,e);/ / right subtree}}int main(a)
{
    int n;
    cout<<"Input array length :";
    cin>>n;
    int a[n];
    cout<<Input array (unsorted):<<endl;
    for(int i=0; i<n; i++)cin>>a[i];
    quickSort(a,0,n- 1);
    cout<<"Sorted array :"<<endl;
    display(a,n);

    return 0;
}

Copy the code

Incremental exhaustive power set

** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
#include <iostream>
#include<vector>
using namespace std;
vector<vector<int>> ps;
void PSet(int n)
{
    vector<vector<int>> ps1;
    vector<vector<int>>::iterator it;
    vector<int> s;
    ps.push_back(s);
    for(int i=1; i<=n; i++) { ps1=ps;for(it = ps1.begin(); it! =ps1.end(); it++) it->push_back(i);for(it = ps1.begin(); it! =ps1.end(); it++) ps.push_back(*it); }}void displays(a)
{
    vector<vector<int>>::iterator it;
    vector<int>::iterator sit;
    for(it = ps.begin(); it! =ps.end(); it++) {cout<<"{";
        for(sit = it->begin(); sit ! =it->end(); sit++)cout<<*sit<<"";
        cout<<"}"<<endl; }}int main(a)
{
    int n;
    cout<<"Enter the integer n:";
    cin>>n;
    PSet(n);
    cout<<"1 ~"<<n<<The power set of "is :"<<endl;
    displays();
    return 0;
}


Copy the code

Results:

Four, greedy algorithm (container problem)

/* *【 problem description 】 There are n containers to be loaded on a ship of deadweight W, in which container I (L < I 
#include <iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define MAXN 20       // Maximum number of containers

int w[] = {0.5.2.6.4.3};   // The weight of each box is ignored
int n =5,W=10;
int maxW;
int x[MAXN];

void solve(a)
{
  memset(x,0.sizeof(x));
  sort(w+1,w+n+1);  //w[1..n] Sequential sequence
  maxW =0;
  int restw = W;
  for(int i =1; i<=n&&w[i]<=restw; i++) { x[i]=1;   // Select container I
      restw-=w[i];    // Reduce the residual weight
      maxW+=w[i];	  // Load the total mass}}int main(a)
{
    solve();
    cout<<"Best solution :"<<endl;
    for(int i=0; i<=n; i++)if(x[i]==1)
          cout<<"Select container"<<i<<"Weight"<<w[i]<<endl;
    cout<<Gross weight:<<maxW<<endl;
    return 0;
}


Copy the code

Running result: