Experimental report on algorithm design and analysis

Experiment 1 recursive algorithm

[experiment purpose]

Master the concept and basic idea requirements of recursive algorithm:

  1. Write the recursive algorithm and program of the corresponding problem
  2. It is required to output the whole moving process.

[experimental principle]

recursive algorithm

[experiment content]

N-order Hanoi Tower problem

[analysis of experimental results]

Hanoi Tower problem adopts recursive algorithm. The end condition of recursion is to move it from A to C when there is only one plate. If it is not A plate, it only needs to be simplified into three actions, moving n-1 plates from A to B, n plates from A to C, and N-1 plates from B to C.

#include<stdio.h>
int count=1;
void move(char x,int n,char y){
    printf("%2d. Move disk %d from %c to %c\n",count++,n,x,y);
}
void hanoi(int n,char x,char y,char z){
    if (n==1)
    move(x,1,z);
    else{
        hanoi(n-1,x,z,y);
        move(x,n,z);
        hanoi(n-1,y,x,z);
    }
}
int main()
{
    int n;
    while (scanf("%d",&n)!=EOF){
        hanoi(n,'A','B','C');
        count=1;
        printf("\n");
    }
    return 0;
}

[calculation results of experimental data]

Experimental bisection algorithm

[experiment purpose]

  1. Using divide and conquer strategy programming to realize merge sorting;
  2. Basically master the principles and methods of divide and conquer strategy.

[experimental principle]

Divide and conquer algorithm

[experiment content]

Let a[0:n-1] be an ordered array. Please rewrite the binary search algorithm so that when the search element x is not in the array, the position i of the largest element less than x and the position J of the smallest element greater than x are returned. When the search element is in the array, i and j are the same, both of which are the positions of x in the array.

[analysis of experimental results]

Binary search is adopted. When there is a difference between left and right, if it is found, it will be output. Otherwise, the range of this value will be output.

#include<stdio.h>
#define N 100
int a[N];
void BinarySearch(int left,int right,int x,int &i,int &j)
{
    while(left<=right){
        int mid=(left+right)/2;
        if(left==right-1){
            if(a[mid]==x){
                i=j=mid;
            }
            else if(a[mid+1]==x){
                i=j=mid+1;
            }
            else{
                i=left;
                j=right;
            }
            return;
        }
        if(x<a[mid]){
            right=mid-1;
        }
        else if(x>a[mid]){
            left=mid+1;
        }
        else{
            i=j=mid;
            break;
        }
    }
}
int main()
{
    int x;
    int i,j;   //Store less than x at the maximum element i and the minimum element position j greater than x
    int k,n;
    scanf("%d",&n);
    for(k=0;k<n;k++){
        scanf("%d",&a[k]);
    }
    while(scanf("%d",&x)!=EOF){
        BinarySearch(0,n-1,x,i,j);
        if(i==j){
            printf("Location found:%d\n",i);
        }
        else{
            printf("Location not found at location%d And location%d between\n",i+1,j+1);
        }
    }
    return 0;
 }

[calculation results of experimental data]

Experiment 3 greedy algorithm

[experiment purpose]

  1. Master Kruskal algorithm of minimum spanning tree;
  2. Master the general design method of greedy algorithm;

[experimental principle]

Greedy Algorithm

[experiment content]

It is known that there are n independent jobs J1, J2... And Jn are processed by m identical machines. The processing time required for job i is ti. It is agreed that any job Ji can be processed on any machine, but it is not allowed to be interrupted or divided before it is completed.
A scheduling scheme is designed by greedy method. n jobs are allocated to m machines for completion. The required time T=max{Ti} (1 ≤ i ≤ m), where Ti is the sum of the processing jobs allocated to machine i. The goal is to make T as small as possible. (load balancing of each machine)

[analysis of experimental results]

N jobs need to be assigned to m machines. When n<m, the required time is the longest processing time t among the n jobs (I have omitted this step here). When n>m, assign jobs to each machine first, and then process the remaining n-m jobs. For each job, select the machine with the shortest processing time to process the work.

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int m,n,time,min,min_pos;//m machines n tasks, time is the maximum time
    cout<<"Please enter the number of machines and jobs:"<<endl;
    cin>>m>>n;
    int *pro=new int[m]; //Processing time per machine
    int *t  =new int[n]; //Processing time per task
    cout<<"Please enter the job duration:"<<endl;
    for(int i=0;i<n;i++)
        cin>>t[i];
    sort(t, t+n,greater<int>());//Sort processing times in descending order
    time=t[0]; //The initial value is the maximum working time
    if(n>m){      //In general, the number of jobs is greater than the number of machines
        for(int i=0;i<m;i++){ //Assign a value to each machine first
            pro[i]=t[i];
            cout<<"Section"<<i+1<<"The working time of machine No. 1 is"<<t[i]<<endl;
        }
        for(int i=m ;i<n ;i++){ //If there are n-m jobs left, you must find the machine with the minimum processing time each time
            min=pro[0];
            min_pos=0;
            for(int j=1;j<m;j++){//Find the machine with the minimum processing time among m machines
                if(pro[j]<min){
                    min=pro[j];
                    min_pos=j;
                }
            }
            pro[min_pos]+=t[i]; //Give the task to the machine with the least processing time and update its processing time
            cout<<"Section"<<min_pos+1<<"The working time of machine No. 1 is"<<pro[min_pos]<<endl;
            if(time<pro[min_pos]) //Compare with the overall time to ensure the maximum time
                time= pro[min_pos];
        }
    }
    cout<<"The minimum time is:"<<time<<endl;
    return 0;
}

[calculation results of experimental data]

Experiment 4 dynamic programming algorithm

[experiment purpose]

  1. Master the dynamic programming recursive algorithm for solving 0-1 knapsack problem;
  2. Master the principle and method of dynamic programming

[experimental principle]

Greedy Algorithm

[experiment content]

Solving 0-1 knapsack problem by dynamic programming

[analysis of experimental results]

In dynamic programming, we consider the sub problem of putting the first I items into the backpack with the capacity of J, and only consider the first I items. If we put them, the problem will be transformed into "putting the first i-1 items into the rest of the backpack with the capacity of j-w[i]. If we don't put them, the problem will be transformed into" putting the first i-1 items into the backpack with the capacity of J.

#include<iostream>
#include<algorithm>
using namespace std;
int V[100][100] = { 0 }; //The optimal solution of the subproblem of making tables and records
int Knapsack(int w[], int v[], int n, int C);//Actual number of items, Backpack Capacity
int main()
{
    int C,n;
    cout<<"Please enter the backpack capacity and item quantity:"<<endl;
    cin>>C>>n;
   int w[100]={0};
   int v[100]={0};
   cout<<"The weights of objects put into the backpack are:"<<endl;
   for (int i=1;i<=n;i++){
           cin>>w[i];
    }
    cout<<"The values of items put into the backpack are:"<<endl;
    for (int i=1;i<=n;i++){
        cin>>v[i];
    }
   int maxValue = Knapsack(w, v, n, C);
    cout<<"The maximum total value of items in the backpack is:"<< maxValue<<endl;
    int j=C;
    for(int i=n;i>0;i--){
        if(V[i][j]!=V[i-1][j]){
            cout<<"goods"<<i<<"Add Backpack"<<endl;
            j=j-w[i];
        }
    }
   return 0;
}
int Knapsack(int w[], int v[], int n, int C) {
   for(int i=1;i<=n;++i)
      for (int j = 1; j <= C; ++j){
          if (j < w[i])
            V[i][j] = V[i - 1][j];
         else
            V[i][j] = max(V[i - 1][j], V[i - 1][j - w[i]] + v[i]);
      }
   return V[n][C];
}

[calculation results of experimental data]

Experiment 5 backtracking algorithm

[experiment purpose]

  1. Master the basic idea of backtracking;
  2. Master the design method of backtracking algorithm;
  3. For subset and number problems, master the design and implementation of backtracking recursive algorithm and iterative algorithm.

[experimental principle]

Backtracking algorithm

[experiment content]

A backtracking algorithm is designed to solve the 0-1 knapsack problem.

[analysis of experimental results]

The backtracking method is used to solve the problem, the complete binary tree is used to represent the solution space, and the depth first method is used to systematically search the solution of the problem. Access the root node. If the backpack still has capacity, set x1[1] to 1 to load. Update the weight and search for the next one. If you can't go on, go back.

#include<iostream>
using namespace std;
int w[100],v[100];//Weight and value of items
int x1[100], x[100];    //x storage best case x1 is the case represented by the current branch
int maxValue;                //max is the value and
int total;                //total is the weight and weight of the selected items in the scheme represented by the current branch
int  C,n;       //C is the upper limit of backpack capacity, n is the number of items
void back_search(int i);//Is a recursive function that considers all items from subscript i to n-1
int main()
{
    int i;
    cout<<"Please enter the backpack capacity and item quantity:"<<endl;
    cin>>C>>n;
    cout<<"The weights of objects put into the backpack are:"<<endl;
    for (int i=0;i<n;i++)
        cin>>w[i];
    cout<<"The values of items put into the backpack are:"<<endl;
    for (int i=0;i<n;i++)
        cin>>v[i];
    //The following is the code of backtracking method
    maxValue = 0;
    total = 0;
    back_search(0);
    //Output results
    for(i=0; i<n; i++)
        printf("%d ",x[i]);
    printf("\n");
    printf("Maximum value=%d\n",maxValue);
    return 0;
}

void back_search(int i)
{
    int j;
    int sum = 0;
    if(i == n)    //Reach leaf node
    {
        for(j=0; j<n; j++)
            sum += x1[j]*v[j];
        if(sum > maxValue)
        {
            maxValue = sum;
            for(j=0; j<n; j++)
                x[j] = x1[j];
        }
        return;
    }
    x1[i] = 0;    //Do not load items with subscript i
    back_search(i+1);
    if(total+w[i] <= C)    //Items with subscript i can be loaded
    {
        x1[i] = 1;        //Load items with subscript i
        total += w[i];
        back_search(i+1);
        x1[i] = 0;            //Clean up the site before backtracking
        total -= w[i];
    }
    return;
}

[calculation results of experimental data]


Are some relatively simple algorithm problems, I believe you can!

Tags: Algorithm Dynamic Programming

Posted by Divine Winds on Tue, 31 May 2022 05:33:50 +0530