算法设计与分析常见题

这道题目可以用递归的方法解决。基本思路是：

以 D( r, j)表示第 r行第 j 个数字(r，j都从 1开始算 )，以 MaxSum(r, j) 代表从第 r 行的第 j 个数字到底边的最佳路径的数字之和，则本题是要求 MaxSum(1, 1) 。

从某个 D(r, j)出发，显然下一步只能走 D(r+1, j)或者 D(r+1, j+1)。

i.如果走 D(r+1, j)，那么得到的 MaxSum(r, j)就是 MaxSum(r+1, j) + D(r, j)；

ii.如果走 D(r+1, j+1)，那么得到的 MaxSum(r, j)就是 MaxSum(r+1, j+1) + D(r, j)。

所以，选择往哪里走，就看 MaxSum(r+1, j)和 MaxSum(r+1, j+1)哪个更大了。程序如下：

#include

#define MAX_NUM 100   

int D[MAX_NUM + 10][MAX_NUM + 10];   

int N;   

int MaxSum( int r, int j){   

if( r == N )   

return D[r][j];   

int nSum1 = MaxSum(r+1, j);   

int nSum2 = MaxSum(r+1, j+1);   

if( nSum1 > nSum2 )

return nSum1+D[r][j];   

return nSum2+D[r][j];   

}   

main(){   

int m;   

scanf("%d", &N);   

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

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

scanf("%d", &D[i][j]);   

printf("%d", MaxSum(1, 1));   

}  

动态规划：

动态规划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的，并且将中间结果保存以避免重复计算的办法。从 aMaxSum[N-1]这一行元素开始向上逐行递推，就能求得最终 aMaxSum[1][1]的值了。程序如下： 

#include

#include

 #define MAX_NUM 100   

 int D[MAX_NUM + 10][MAX_NUM + 10];   

 int N;   

 int aMaxSum[MAX_NUM + 10][MAX_NUM + 10];   

 main(){   

 inti,j;   

 scanf("%d", & N);   

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

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

 scanf("%d", &D[i][j]);   

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

 aMaxSum[N][j] = D[N][j];   

for( i = N ; i > 1 ; i -- )

for( j = 1; j < i ; j ++ ) {

if( aMaxSum[i][j] > aMaxSum[i][j+1] )

 aMaxSum[i-1][j] = aMaxSum[i][j] + D[i-1][j];   

 else   

 aMaxSum[i-1][j] = aMaxSum[i][j+1] + D[i-1][j];   

 }   

 printf("%d", aMaxSum[1][1]);   

 }

2.马的走法

问题描述：在4×5的棋盘上已知马的起始坐标(x,y)，求马能够返回到起始位置的不重复的所有不同走法的总数。

算法思想：回溯法，马当前所在的位置是当前扩展结点，每个活结点可能有八个孩子结点。

问题所在：如何记录马行走的路径？

程序如下：

class Horse{

private:

    int chess[5][6];

    int d[2][8]={{1,2,2,1-1,-2,-2,-1},{2,1,-1,-2,-2,-1,1,2}};

    int sx,sy;

    int count;

public:

    Horse(int x,int y) { 

         sx=x; sy=y;

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

for(int j=0;j<5;j++) chess[i][j]=0;

    }

    static long computer(){

        count=0;

if(sx<0||sy<0||sx>=6||sy>=5) return ;

        backtrack(sx,sy);

        return count;

    }

Private static void backtrack(int p1,int p2);

};

Private static void Horse:: backtrack(int p1,int p2){

    int pi,pj;

for(int i=0;i<7;i++){

                                 pi=p1+d[0][i]; 

                                 pj=p2+d[1][j];

if(pi>=0&&pi<6&&pj>=0&&pj<5&&ch[pi][pj]==0) {

                  chess[pi][pj]=1;

                  backtrack(pi,pj);

                  chess[pi][pj]=0;

           } else if(pi==sx&&pj==sy)  

                         count++;

        }

};

3.会餐交友

算法思想：

构造一个对称邻接矩阵Friend[Max][Max]，第i行第j列的值为1代表i和j认识。具体步骤很简单。统计每一行值为1的个数，找出个数最大的行k，记录下来，然后把第k行和第k列的元素全置为0（对称矩阵）。循环执行以上描述的步骤，直到邻接矩阵所有元素为0跳出循环。

程序如下：

#include

#define Max 500

int main(){

    //邻接矩阵（对称矩阵）

    int Friend[Max][Max]={0};

    int n;

cin>>n;

    int i=-1,j=-1;

    while(i!=0||j!=0){

     cin>>i;

     cin>>j;

        Friend[i][j]=Friend[j][i]=1;

    }

    //每次计算记录每行的非零个数

    int count[Max]={0};

    //temp存储临时最大个数，row表示最大个数的行

    int temp,row;

    int result[Max]={0},number=0;

    while(true){

        //统计第i行是1的个数

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

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

                if(j==i){//主对角线置为0

                    Friend[i][j]=0;

                    continue;

                }

                if(Friend[i][j]==1)

                    count[i]++;

            }

        //找出元素最多的行

        temp=count[1];

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

         if(temp                row=i;

                temp=count[i];

            }

        //存储结果

        result[number++]=row;

        //判断矩阵是否全为0

        if(temp==0){

            //输出结果

         cout<            for(i=0;result[i]!=0;i++)

             cout<            break;

        }

        //删除第i行和第i列的元素，并将count数组置零

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

            if(Friend[row][i]==1)

                Friend[row][i]=Friend[i][row]=0;

            count[i]=0;

        }

    }

    return 0;

}

4.赤道大篝火

输入：

第一行输入n

第二行输入m

第三行输入n+1个地点所表示的位置，第一个为0

第四行输入m个点火的地点

第五行输入m个点火地点对应的点火时刻

第六行输入大火蔓延速度v

输出：

n个地方对应的起火时刻

解题思路：

把赤道展开平铺成一条直线，最后一个点和第一个点视为同一个点。初步考虑用两个循环把问题解决，外循环遍历每一个地方，内循环遍历每一个点火处。

假设针对第i个地点探讨它的起火时间，则最关键的问题就是子问题的分割，将多处点火的情形看做多个只有一处点火的情形。这样每个子问题就可以很轻松的计算出每个起火点点火时到达点i的时刻。

回到赤道的概念，假设点火处为点j，则先通过比较点i到点j的顺时针距离和逆时针距离得出最小值value，得出时间间隔为value除以速度v，假设点j的点火时刻为time[j]，点i的起火时间为result[i]，就可以得出在点火处j使点i起火的时刻为

result[i]=value/v+time[j]。内层循环可以通过这种计算，遍历所有的点火处j（即使点i就是点j），以覆盖的方式，将得出最小的result[i]。

程序如下：

#include

#include

#define Max 100

int main(){

    int n,m;

cin>>n;

cin>>m;

    //position代表n+1个位置,且第n个点就是第0个点,第一个点值为0(将赤道平铺为直线)

    int position[Max];

    //touch代表选定的点火位置,time对应touch的点火时刻

    int touch[Max],time[Max];

    int i,j;

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

     cin>>position[i];

for(i=0;i     cin>>touch[i];

for(i=0;i     cin>>time[i];

    //速度

    int velocity;

cin>>velocity;

    //输出结果

    int result[Max];

    //最小距离距离,中间结果的时刻

    int length,temp;

    //对于每个点探讨它的起火时刻

for(i=0;i        //比较每个点火处j的地方蔓延到点i的时刻

     for(j=0;j            //初始化result[i]

            if(j==0)

                result[i]=abs(touch[0]-position[i])/velocity+time[0];

            else{//挑选j到i两个方向的较小距离,position[n]指的就是赤道的长度

             length=abs(touch[j]-position[i])<=position[n]-abs(touch[j]-position[i])?

                    abs(touch[j]-position[i]):position[n]-abs(touch[j]-position[i]);

                temp=length/velocity+time[j];

                //通过最小覆盖的方式得出最终的结果

             if(result[i]>temp)

                    result[i]=temp;

            }

        }

    }

for(i=0;i     cout<    return 0;

}

5.钓鱼问题

问题描述： 某人有h小时的时间想钓到数量最多的鱼。这时他已经在一条路边，从他所在的地方开始，放眼望去，n个鱼场一字排开，编号依次是1,2,…,n。他已经知道，从鱼场i走到鱼场i+1需要花ti分钟；他在鱼场i钓鱼，第一个5分钟可钓到重fi的鱼；若他继续在鱼场i钓鱼，每过5分钟，鱼量将减少di。请你给他设计一个最佳钓鱼方案。

算法思想：贪心算法

问题描述： 某人有h小时的时间想钓到数量最多的鱼。这时他已经在一条路边，从他所在的地方开始，放眼望去，n个鱼场一字排开，编号依次是1,2,…,n。他已经知道，从鱼场i走到鱼场i+1需要花ti分钟；他在鱼场i钓鱼，第一个5分钟可钓到重fi的鱼；若他继续在鱼场i钓鱼，每过5分钟，鱼量将减少di。请你给他设计一个最佳钓鱼方案。

思想：贪心算法

把每钓5分钟鱼称为钓一次鱼。首先枚举这个人需要走过的池塘的数目X，即从池塘1走到池塘X。减去路上花去的时间T=sum(Ti) i=1...X-1，这样我们可以认为这个人能从一个池塘"瞬间转移"到另一个池塘，即在任意一个时刻都可以在池塘1到池塘X中任选一个钓一次鱼(很重要)。每次选择鱼最多的池塘钓一次鱼。对于每个池塘来说，由于在任何时候鱼的数目只和这个人在该池塘里钓鱼的次数有关，和钓鱼的总次数无关，所以这个策略是最优的。假设一共允许钓k次鱼，那么每次在N个池塘中选择鱼最多的一个钓。总的时间复杂度为O(kn^2)。结题步骤如下：

1.在枚举了走过的池塘数目下，分别计算(总时间s-花在路上的时间t)/5=times就是钓鱼的次数。

2.首先选取当前池塘鱼数最多的池塘，然后可掉鱼数max+鱼数，然后次数减一，当池塘中的鱼<0时赋值为0，并退出本次枚举，或者次数为0时，退出本次枚举，然后记录鱼数。如果还有次数，但是没有鱼了，把剩余次数加在第一个池塘。

#include

using namespace std;//f[]为每个池塘的鱼数，d[]为每次减少的条数，t[]为路上花费的时间

int n,h,f[30],f1[30],d[30],t[30];//用来查找当前鱼数最多的池塘

int chazhao(int n){

    int i,falg=1;

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

if(f[falg]    falg=i;

    return falg;

}

int main(){

    int i,j,max,Max,falg,time,times;

    int count[30],count1[30];//记录每个湖钓的次数

cout<<"输入总的池塘数"<    while(scanf("%d",&n)!=EOF&&n){

     cout<<"输入小时："<        scanf("%d",&h);

        Max=-1;

        memset(count1,0,sizeof(count1));

        memset(f,0,sizeof(f));

        memset(d,0,sizeof(d));

        memset(t,0,sizeof(t));//数据的输入

     cout<<"输入每个池塘的鱼数"<     for(i=1;i<=n;i++){

            scanf("%d",&f[i]);

            f1[i]=f[i];//f1用来保存每个鱼塘的鱼数么

        }

     cout<<"输入每个池塘的减少的鱼数"<     for(i=1;i<=n;i++)

            scanf("%d",&d[i]);

     cout<<"输入每个池塘的行走时间"<     for(i=1;i            scanf("%d",&t[i]);

     for(i=1;i<=n;i++){//依次枚举贪心

            time=0;//花在路上的总时间

            max=0;

            memset(count,0,sizeof(count));

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

                time+=t[j-1]*5;

            times=(h*60-time)/5;//可钓鱼的次数

         if(times<=0)//如果本次钓鱼次数为0，则结束本次枚举

                continue;

            while(1){

                falg=chazhao(i);//找出本次枚举中，每次选择当前鱼数最多的池塘。

             if(f[falg]<=0)//如果最多池塘的鱼数也小于等于0了，则也同样跳出本次枚举。

                break;

                max+=f[falg];//这个是在本次枚举中，每选择一次就要把钓到的鱼加起来。

                count[falg]++;//记录每个池塘钓鱼的次数

                times--;

                f[falg]-=d[falg];

             if(f[falg]<0)

                f[falg]=0;

                if(times==0)//如果次数等于0了，则跳出本次枚举

                break;

            }

            if(times){//这里是因为，还有可以钓鱼的次数，但是因为池塘没有鱼了。

                /*min=1;

             for(j=2;j<=i;j++)

             if(count[min]                min=j;

                count[min]+=times;*/

                count[1]+=times;//就把所有的次数都加到

            }

         if(Max                Max=max;

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

                    count1[j]=count[j];//把每个池塘钓鱼的次数赋值给count1.

            }

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

                f[j]=f1[j];//f1[]数组保存的是最原始的每个池塘的鱼数，这样每次枚举必须用的是初始值。

        }

     for(i=1;i            printf("%d, ",count1[i]*5);

        printf("%d\\n",count1[n]*5);

        printf("%s%d\\n\\n

    }

    return 0;

}