算法分析与设计实验报告

阶乘(Factorial)

#include
using namespace std;
int factorial(int n)
{
    if (n==1)
    {
        return 1;
    }
    else{
        return n*factorial(n-1);
    }
}
int main()
{
    cout<<"求阶乘"<  
斐波那契数列(Fibonacci)
 
#include
using namespace std;
int fibonacci(int n)
{
    if (n==0||n==1)
    {
        return 1;
    }
    else
    {
        return fibonacci(n-1)+fibonacci(n-2);
    }
}
int main()
{
    cout<<"斐波那契数列"<  
汉诺塔(Hanoi)
 
#include
using namespace std;
int sum=0;
int hanoi(int n)
{
    if (n==1)
    {
        sum++;
    }
    else{
        hanoi(n-1);
        sum++;
        hanoi(n-1);
    }
    return sum;
}
int main()
{
    cout<<"Hanoi"<>n;
    cout<  
整数分解(Integer)
 
#include
using namespace std;
int res_num;
int res[100];
int p_res=0;
void integer(int n)
{
    if (n<=0)
    {
        for (int i=0; i>n;
    cout<<"拆分结果如下："<  
整数全排列(Perm)
 
#include
using namespace std;
inline void Swap(int &a,int &b)
{

    int temp=a;
    a=b;
    b=temp;
}
void Perm(int list[],int k,int m)
{

    if(k==m)
    {
        for(int i=0;i<=m;i++)
        {

            cout<>n;
    cout<<"请依次输入"<>list[i];
    cout<<"全排列为"< 

MergeSort

#include 
#include 
#include 
#include 
using namespace std;

void Merge(vector &A, int p, int q, int r)
{
    vector::iterator iter = A.begin();
    vector L(iter + p, iter + q + 1);
    vector R(iter + q + 1, iter + r + 1);
    int i = 0, j = 0;
    while (i < L.size() && j < R.size())
    {
        if (L[i] < R[j])
            A[p++] = L[i++];
        else
            A[p++] = R[j++];
    }
    if (i == L.size())
    {
        while (j < R.size())
            A[p++] = R[j++];
    }
    else
    {
        while (i < L.size())
            A[p++] = L[i++];
    }
}

void MergeSort(vector &A, int p, int r)
{
    if (p < r)
    {
        int q = (p + r) / 2;
        MergeSort(A, p, q);
        MergeSort(A, q + 1, r);
        Merge(A, p, q, r);
    }
}

int main()
{    
    srand((unsigned)time(NULL));
    int times = rand() % 20 + 10;
    cout << "排序组成元素个数: "< A(times, 0);
    cout << "所排列元素："<  
QuickSort
 
#include 
using namespace std;

void QuickSort(int *arr, int left, int right)
{
    if (left > right)
        return;

    int i = left, j = right;

    int flag = arr[left];
    while (i != j)
    {
        while (arr[j] > flag && i < j)
            j--;
        while (arr[i] <= flag && i < j)
            i++;

        if (i < j)
            swap(arr[i], arr[j]);
    }

    arr[left] = arr[i];
    arr[i] = flag;

    QuickSort(arr, left, i - 1);
    QuickSort(arr, i + 1, right);
}

int main()
{
    srand((unsigned)time(NULL));
    int times = rand() % 20 + 10;
    cout << "排序组成元素个数: " << times << endl;
    int array[times];
    cout<<"排序的数组："< 

最长公共子序列

#include
using namespace std;

void LCS(string s1,string s2);

int main()
{
    string s1,s2;
    cout<<"请输入第一个字符串"<>s1;
    cout<<"请输入第二个字符串"<>s2;
    LCS(s1,s2);
    return 0;
}

void LCS(string s1,string s2)
{
    int m=s1.length()+1,n=s2.length()+1;
    int **c,**b;
    c=new int* [m],b=new int* [m];
    for(int i=0; i=c[i+1][j])
            {
                c[i+1][j+1]=c[i][j+1];
                b[i+1][j+1]=2;
            }
            else
            {
                c[i+1][j+1]=c[i+1][j];
                b[i+1][j+1]=3;
            }
        }
    }
    stack same;
    stack same1,same2;
    for (int i=m-1,j=n-1; i>=0&&j>=0;)
    {
        if(b[i][j]==1)
        {
            i--,j--;
            same.push(s1[i]);
            same1.push(i),same2.push(j);
        }
        else if(b[i][j]==2)
            i--;
        else
            j--;
    }
    cout<  
凸多边形最优三角剖分
 
#include
using namespace std;

const int M=1111;
int n;
int s[M][M];
double t[M][M],weight[M][M];

void MinWeightTriangulation()
{
    for(int i=1; i<=n; i++)
        t[i][i]=0,s[i][i]=0;
    for(int r=2; r<=n; r++)
    {
        for(int i=1; i<=n-r+1; i++)
        {
            int j=i+r-1;
            t[i][j]=t[i+1][j]+weight[i-1][i]+weight[i][j]+weight[i-1][j];
            s[i][j]=1;
            for(int k=i+1; ku)
                    t[i][j]=u,s[i][j]=k;
            }
        }
    }
}

void Traceback(int i,int j)
{
    if(i==j)    return ;
    Traceback(i,s[i][j]);
    Traceback(s[i][j]+1,j);
    cout<<"三角划分顶点：V"<>weight[i][j];
    MinWeightTriangulation();
    cout<