算法设计实验报告

1.hanoi

package syy;

import java.util.*;

publicclass Hanoi {

    publicstaticvoid move(int n,int a,int b)

    {

       System.out.println("把第"+n+"个盘子"+"从第"+a+"个塔座移到第"+b+"个塔座");

    }

    publicstaticvoid hanoi(int n,int a,int b,int c)

    {

       if(n>0)

       {

           hanoi(n-1,a,c,b);

           move(n,a,b);

           hanoi(n-1,c,b,a);

       }

    }

    publicstaticvoid main(String[] args)

    {

       System.out.println("请输入一个人不小于0的盘子的个数!");

       Scanner scan=new Scanner(System.in);

       int n=scan.nextInt();

       int x=1,y=2,z=3;

       hanoi(n,x,y,z);

    }

}

2.Stassen矩阵乘法:

package syy;

import java.io.*;

import java.util.*;

class matrix

{

    public int[][] m = new int[32][32];

}

public class jzcf

{

    public int judgment(int n)

    {

        int flag = 0,temp=n;

        while(temp%2==0)

        {

            if(temp%2==0)

                temp/=2;

            else flag=1;

        }

        if(temp==1)

            flag=0;

        return flag;

    }

    public void Divide(matrix d,matrix d11,matrix d12,matrix d21,matrix d22,int n)/*分解矩阵方法*/

    {

        int i,j;

        for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

        {

            d11.m[i][j]=d.m[i][j];

            d12.m[i][j]=d.m[i][j+n];

            d21.m[i][j]=d.m[i+n][j];

            d22.m[i][j]=d.m[i+n][j+n];

        }

    }

    public matrix Merge(matrix a11,matrix a12,matrix a21,matrix a22,int n)/*合并矩阵方法*/

    {

        int i,j;

        matrix a = new matrix();

        for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

        {

            a.m[i][j]=a11.m[i][j];

            a.m[i][j+n]=a12.m[i][j];

            a.m[i+n][j]=a21.m[i][j];

            a.m[i+n][j+n]=a22.m[i][j];

        }

        return a;

    }

    public matrix AdhocMatrixMultiply(matrix x,matrix y) /*阶数为2的矩阵乘法方法*/

    {

        int m1,m2,m3,m4,m5,m6,m7;

        matrix z = new matrix();

        m1=(y.m[1][2] - y.m[2][2]) * x.m[1][1];

        m2=y.m[2][2] * (x.m[1][1] + x.m[1][2]);

        m3=(x.m[2][1] + x.m[2][2]) * y.m[1][1];

        m4=x.m[2][2] * (y.m[2][1] - y.m[1][1]);

        m5=(x.m[1][1] + x.m[2][2]) * (y.m[1][1]+y.m[2][2]);

        m6=(x.m[1][2] - x.m[2][2]) * (y.m[2][1]+y.m[2][2]);

        m7=(x.m[1][1] - x.m[2][1]) * (y.m[1][1]+y.m[1][2]);

        z.m[1][1] = m5 + m4 - m2 + m6;

        z.m[1][2] = m1 + m2;

        z.m[2][1] = m3 + m4;

        z.m[2][2] = m5 + m1 - m3 - m7;

        return z;

    }

    public matrix MatrixPlus(matrix f,matrix g,int n) /*矩阵加法方法*/

    {

        int i,j;

        matrix h = new matrix();

        for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

        h.m[i][j]=f.m[i][j]+g.m[i][j];

        return h;

    }

    public matrix MatrixMinus(matrix f,matrix g,int n) /*矩阵减法方法*/

    {

        int i,j;

        matrix h = new matrix();

        for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

        h.m[i][j]=f.m[i][j]-g.m[i][j];

        return h;

    }

    public matrix MatrixMultiply(matrix a,matrix b,int n) /*矩阵乘法方法*/

    {

        int k;

        matrix a11,a12,a21,a22;

        a11 = new matrix();

        a12 = new matrix();

        a21 = new matrix();

        a22 = new matrix();

        matrix b11,b12,b21,b22;

        b11 = new matrix();

        b12 = new matrix();

        b21 = new matrix();

        b22 = new matrix();

        matrix c11,c12,c21,c22,c;

        c11 = new matrix();

        c12 = new matrix();

        c21 = new matrix();

        c22 = new matrix();

        c = new matrix();

        matrix m1,m2,m3,m4,m5,m6,m7;

        k=n;

        if(k==2)

        {

            c=AdhocMatrixMultiply(a,b);

            return c;

        }

        else

        {

            k=n/2;

            Divide(a,a11,a12,a21,a22,k); //拆分A、B、C矩阵

            Divide(b,b11,b12,b21,b22,k);

            Divide(c,c11,c12,c21,c22,k);

           

            m1=MatrixMultiply(MatrixMinus(b12,b22,n/2),a11,k);

            m2=MatrixMultiply(b22,MatrixPlus(a11,a12,k),k);

            m3=MatrixMultiply(MatrixPlus(a21,a22,k),b11,k);

            m4=MatrixMultiply(a22,MatrixMinus(b21,b11,k),k);

            m5=MatrixMultiply(MatrixPlus(a11,a22,k),MatrixPlus(b11,b22,k),k);

            m6=MatrixMultiply(MatrixMinus(a12,a22,k),MatrixPlus(b21,b22,k),k);

            m7=MatrixMultiply(MatrixMinus(a11,a21,k),MatrixPlus(b11,b12,k),k);

            c11=MatrixPlus(MatrixMinus(MatrixPlus(m5,m4,k),m2,k),m6,k);

            c12=MatrixPlus(m1,m2,k);

            c21=MatrixPlus(m3,m4,k);

            c22=MatrixMinus(MatrixMinus(MatrixPlus(m5,m1,k),m3,k),m7,k);

           

            c=Merge(c11,c12,c21,c22,k); //合并C矩阵

            return c;

        }

    }

    public static void main(String[] args)throws IOException

    {

        jzcf instance = new jzcf();

        int i,j,num;

        matrix A,B,C;

        A = new matrix();

        B = new matrix();

        C = new matrix();

        Scanner in = new Scanner(System.in);

        System.out.print("输入矩阵的阶数: ");

        num = in.nextInt();

        if(instance.judgment(num)==0)

        {

            System.out.println("输入矩阵A:");

            for(i=1;i<=num;i++)

                for(j=1;j<=num;j++)

                    A.m[i][j] = in.nextInt();

            System.out.println("输入矩阵B:");

            for(i=1;i<=num;i++)

                for(j=1;j<=num;j++)

                    B.m[i][j] = in.nextInt();

            if(num==1)

                C.m[1][1]=A.m[1][1]*B.m[1][1]; //矩阵阶数为1时的特殊处理

            else

                C=instance.MatrixMultiply(A,B,num);

            System.out.println("矩阵C为:");

            for(i=1;i<=num;i++)

            {

                for(j=1;j<=num;j++)

                    System.out.print(C.m[i][j] + "     ");

                System.out.println();

            }

        }

        else

            System.out.println("输入的阶数不是2的N次方");

    }

}

3.合并排序:

package syy;

publicclass  hebingpaixu

{

    publicvoid merge_sort(int[] arrays,int start,int end){

        if(start<end){

            int m=(start+end)/2;

            merge_sort(arrays,start,m);

            merge_sort(arrays,m+1,end);

            combin_arrays(arrays,start,m,end);   

        }

    }

    publicvoid combin_arrays(int[] arrays,int start,int m,int end){

        int length=end-start+1;

        int temp[]=newint[length];//用来存放比较的数组,用完复制回到原来的数组

        int i=start;

        int j=m+1;

        int c=0;

        while(i<=m &&j<=end){

            if(arrays[i]<arrays[j]){

                temp[c]=arrays[i];

                i++;

                c++;

            }else{

                temp[c]=arrays[j];

                j++;

                c++;

            }

        }

        while(i<=m){

            temp[c]=arrays[i];

            i++;

        }

        while(j<=end){

        temp[c]=arrays[j];

        j++;

        }

        c=0;

        for(int t=start;t<=end;t++,c++){

            arrays[t]=temp[c];

        }

        snp(arrays);

    }

    publicvoid snp(int[] arrays){

        for(int i=0;i<arrays.length;i++){

        System.out.print(arrays[i]+" ");

        }

        System.out.println();

    }

   

    publicstaticvoid main(String[] args)

    {

        hebingpaixu m=new hebingpaixu();

        int a[]={6,4,3,10,7,5};

        m.merge_sort(a,0,a.length-1);

       

    }

}

快速排序:

package syy;

publicclass QSort

{

    publicstaticvoid main(String[] args)

    {

        // TODO 自动生成方法存根

        quicksort qs = new quicksort();

        int data[] = {14,26,84,65,76,49,53,39};

        qs.data = data;

        qs.sort(0, qs.data.length-1);

        qs.display(); 

        }

}

class quicksort

{

    publicint data[];

    

    privateint partition(int sortArray[],int low,int hight)

    {

        int key = sortArray[low];

        while(low<hight)

        {

            while(low<hight && sortArray[hight]>=key)

                hight--;

            sortArray[low] = sortArray[hight];

            

            while(low<hight && sortArray[low]<=key)

                low++;

            sortArray[hight] = sortArray[low];

        }

        sortArray[low] = key;

        return low;

    }

    

    publicvoid sort(int low,int hight)

    {

        if(low<hight)

        {

            int result = partition(data,low,hight);

            sort(low,result-1);

            sort(result+1,hight);

        }

        

    }

    

    publicvoid display()

    {

        for(int i=0;i<data.length;i++)

        {

            System.out.print(data[i]);

            System.out.print(" ");

        }

    }

}

 

第二篇:算法设计实验报告

《算法设计》课程报告

课题名称: 算法设计与实现

课题负责人名(学号): 张樱紫 0743111317 同组成员名单(角色): 无

指导教师: 左劼

评阅成绩:

评阅意见:

提交报告时间:2009 年 12 月 23 日

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

算法设计与实现课程设计

软件工程 专业

学生 张樱紫 指导老师 左劼

[摘要] 课程设计报告实现了算法设计课程中5个的主要算法,包括分治法,动态规划,贪心算法,回溯法以及分支限界法。每种算法用一个问题描述应用解决,包括源程序代码及执行结果还有算法复杂度以及问题描述,分析、证明,测试数据和运行结果。

关键词:算法设计 分治法 动态规划 贪心算法 回溯法 分支限界法

对计算机科学来说,算法的概念至关重要。通俗的讲,算法是指解决问题的一种方法或一个过程。算法实由若干条指令组成的有穷序列,且满足确定性,有限性,输入满足:有零个或多个由外部提供的量作为算法的输入。输出满足:算法产生至少一个量作为输入。通过在课程中,学习掌握了一些主要算法并了解了一些新型算法。

本课程设计报告中,主要实现了五种算法,包括分治法,包括分治法,动态规划,贪心算法,回溯法以及分支限界法。下面是每种算法的详细设计实现:

一、 分治法:

问题描述

赛程问题: 有N个运动员进行单循环赛,即每个运动员要和所有其他运动员进行一次比赛。

-1-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

?试用分治法为这N个运动员安排比赛日程。

?要求每个运动员每天只进行一场比赛,

?n是偶数时循环进行n-1天,n是奇数时循环进行n天。

?将运动员从1到N编号。

分析、证明

整个赛程,当N为偶数的时候,N-1天能够结束,

而当N为奇数的时候,只能在至少N天结束,、

因为,由已知 “每个运动员要和所有其他运动员进行一次比赛”则 每个运动员总共进行N-1场,又由每一场有两个运动员参加,N个运动员就进行了M=[N*(N-1)]/2,又因为已知“要求每个运动员每天只进行一场比赛”则没人每天只能进行1场,所有运动员为N,每一场由两个运动员参加,当N为偶数的时候,每天只能出现的场数为N/2场,推出至少的天数为M/(N/2)=N-1场。 当N为奇数的时候,由于每个运动员每天只能进行一场,所以每天能进行的总场数最多只能为(N-1)/2场,则整个赛程的天数最少需要 天数 M/[(N-1)/2]=N天

总体思路:按分治策略,将所有分为两半,n个选手可以通过n/2个选手设计的比赛日程表来决定。递归地用一分为二的略对选手进行分割,直到只剩下两个选手。

对于N为奇数的情况可以虚拟多一个选手,使其编程N+1个选手的日程表,最然后忽略虚拟运动员参与的比赛。对于分割时候N/2的情况也做特殊处理, 前n/2轮比赛空选手与下一个未参赛的选手进行比赛

代码实现

void match(int a[][N], int k)

{

int n=1, m=1;

for (int i=1; i<=k; i++)

n *= 2;

for(int i=0; i<n; i++)

-2-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

a[i][0]=i+1;

for(int s=0; s<k; s++) // k个阶段,从左到右

{

n /= 2;

for(int t=0; t<n; t++) // 每个阶段有t次循环

{

for(int j=m; j<2*m; j++)

for(int i=m; i<2*m; i++)

{

a[i-m+2*t*m][j] = a[i+2*t*m][j-m]; a[i+2*t*m][j] = a[i-m+2*t*m][j-m]; }

}

m *= 2;

}

}

测试数据、运行结果

Please input:3

The result is:3

Please input:4

The result is:3

复杂度分析

T(n)∈O(n^2)

二、 动态规划算法:

问题描述:数字三角形问题

给定一个由n行数字组成的数字三角形,如图。设计一个算法,计算出从三角形的顶至底的一条路径,是该路径经过的数字 -3-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

总和最大。

分析设计:动态规划:与分治法相似,把问题分解按层次分成子问题,直到可以直接求解的子问题,然后一级一级地向上求解。 与分治法的出别在于:动态规划适用有许多重复子问题出现的问题,它保留已求出问题的解。

满足动态规划需符合的条件

1)最优化原理:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。

对于给定的由n行数字组成的数字三角形,计算从三角形的底至顶的路径经过的数字和的最大值。

代码实现与结果:

#include"stdio.h"

void main()

{

int i,j,n,a[100][100]; int M(int n,int a[100][100]); FILE *fp1,*fp2; if((fp1=fopen("input.txt","r"))==NULL) { } fscanf(fp1,"%d",&n); for(i=0;i<n;i++) { -4- printf("file cannot be opened\n"); //exit(1); for(j=0;j<=i;j++) fscanf(fp1,"%d",&a[i][j]); if((fp2=fopen("output.txt","w"))==NULL)

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

} } printf("file cannot be opened\n"); //exit(1); fprintf(fp2,"%d\n",M(n,a));

int M(int n,int a[100][100])

{

}

int MAX(int a,int b)

{

}

/*

-5- int i,j; int m[100][100]; int MAX(int a,int b); for(i=n-1;i>=0;i--) { } return m[0][0]; if(i==n-1) m[i][j]=a[i][j]; else for(j=0;j<=i;j++) m[i][j]=MAX(m[i+1][j]+a[i][j],m[i+1][j+1]+a[i][j]); if(a>=b) return a; return b; else

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

Input:

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

*/

Output:

算法设计实验报告

30

算法复杂度:O(T(n)∈O(n^2))

三、 贪心算法

问题描述:删数问题

给定n位正整数a,去掉其中期任意k≤n个数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n为正整数a和正 -6-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

整数k,设计一个算法找出剩下的数字组成的新数最小的删数方案。

分析证明:

贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。

虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。 在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。

满足贪心算法两个基本要素

1)、贪心选择性质:

选择具有无后效性,即不依赖与以后将要作出的选择。

问题的整体最优解可通过一系列的局部最优选择来达到。

证明方法:用归纳法证明此问题的最优解包括一个贪心选择的解。

2)、最优子结构性质

一个问题的最优解包括其子问题的最优解。

算法设计:对于给定的正整数a,计算删去k个数字后得到的最小数。

-7-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

数据输入:第一行是1个正整数a。第二行是正整数k

算法实现代码与结果:

#include <iostream>

using namespace std;

char num[ 100 ];

int s,len,i,j,k;

int main( )

{

cin >> num >> s; len = strlen( num ); for ( i = 0; i < s; i++ ) { for ( j = 0; j < len - 1; j++ ) if ( num[ j ] > num[ j + 1 ] ) { } len--; for ( k = j; k < len - 1; k++ ) num[ k ] = num[ k + 1 ]; break;

-8-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

} } if ( len <= 0 ) cout << 0; else for ( i = 0; i < len; i++ ) cout << num[ i ]; cout<<"\n"; return 0;

算法设计实验报告

算法复杂度:T(n)∈O(n^2)

四、 回溯法

问题描述:工作分配问题

设有 n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法为每一个人都分配1件不同的工作,并使总费用达到最小。

-9-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

算法设计:设计一个算法,对于给定的工作费用,计算最佳工作分配方案,使总费用达到最小。

输入:第一行有一个正整数n

(1≤n≤20)。接下来的n行,每行n个数,表示工作费用。

分析证明:

回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。

算法代码与结果:

#include "stdio.h"

#include "string.h"

#include "malloc.h"

int **aray;

int *list;

int number;

int final_cost=0;

-10-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

int current_cost=0;

void assign(int);

void swap(int*, int*);

void assign(int k){

int i; if(k>=number){ } else{ for(i=k;i<number;i++){ current_cost+=aray[k][list[i]]; if(current_cost<final_cost){ swap(&list[k],&list[i]); assign(k+1); final_cost=current_cost;

swap(&list[k],&list[i]);

} } } } current_cost-=aray[k][list[i]];

-11-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

void swap(int *a,int *b){

}

main()

{

int m; scanf("%d",&m); while(m--) { int temp; temp=*a; *a=*b; *b=temp;

int i,j;

scanf("%d" ,&number);

aray=(int **)malloc(sizeof(int *)*number); list=(int *)malloc(sizeof(int)*number);

for(i=0;i<number;i++)

list[i]=i;

for(i=0;i<number;i++)

aray[i]=(int *)malloc(sizeof(int)*number);

-12-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

for(i=0;i<number;i++)

{

for(j=0;j<number;j++) { } final_cost+=aray[i][i]; scanf("%d",&aray[i][j]);

}

} }

算法设计实验报告

assign(0); printf("%d\n",final_cost); free(list); free(aray);

算法复杂度:T(n)∈O(n^2)

五、 分支限界法

问题描述:在n*n的国际象棋棋盘上摆下n个后,使所有的后都 -13-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

不能攻击到对方,找出所有符合要求的情况。

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线的棋子。也就是说,n后问题等价于在n×n格的棋盘上放置n个皇后,任何两个皇后不放在同一行或同一列或同一斜线上。n后问题是一个路径问题。国际象棋的规则就是限界函数的约束条件。

分析证明:

分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。

在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。

此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

n后问题的解空间树是一棵排列树,一旦一种组合是一种解,则解与解之间不存在优劣的分别。用分支限界法,在解空间树的第一层就会产生n个活结点,如果不考虑剪枝,将在第二层产生n*(n-1)个活结点,如此下去对队列空间的要求太高。n后问题不适合使用 -14-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

分支限界法处理的根源是它需要找处所有解的组合,而不是某种最优解(事实上也没有最优解可言)。分支限界法则可以被这样表述。拿来一个棋盘,摆下一只后;再拿一个棋盘,再摆一只;待到每个棋盘都有一只后以后,每个棋盘又被分解成更多的盘面。 算法实现代码与结果

#include<iostream>

#include<stdio.h>

using namespace std;

const int N=20;

int a_xy[N][2];

long sum;

int n;

void n_queue(int m)

{

int i,j;

if(m>=n)

{

/*

printf("the %ldth method:\n",sum+1);

for(i=0;i<n;i++,printf("\n"))

-15-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

{

for(j=0;j<n;j++)

if(j==a_xy[i][1])printf("* ");

else printf("0 ");

}

for(i=0;i<n;i++)printf("--");

printf("\n");*/

sum++;

return ;

}

bool t1;

for(i=0;i<n;i++)

{

for(j=0,t1=true;j<m;j++)

if(a_xy[j][1]==i||abs(a_xy[j][0]-m)==abs(a_xy[j][1]-i)) {t1=false;break;}

if(t1)

{

a_xy[m][0]=m;

-16-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

a_xy[m][1]=i;

n_queue(m+1);

}

}

}

int main()

{

while(true)

{

printf("please input n:");

scanf("%d",&n);

sum=0;

n_queue(0);

printf("the result is:%ld\n",sum);

}

return 0;

算法设计实验报告

}

-17-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

算法复杂度: T(n)∈O(n^2)

六、总结:通过本课程的学习,了解了一些基本的算法以及他们的实现和应用,并学会了算法的分析与设计,解决一些基本问题。但更多还有待进一步研究与提高。

参考文献

[1] 计算机算法设计与分析(第三版)王晓东

[2] 算法设计与实验题解 王晓东

[2] 算法分析与设计

-18-

相关推荐