一步步学算法(算法题解)---2

深藏阁楼爱情的钟 2022-10-31 12:26 130阅读 0赞

**本人大二，最近开始自学算法，在此记录自己学习过程中接触的习题。与君共勉。**

**水平有限，目前涉及的题目都比较水。**

**题目分布为5+1. 5为自己学习的5道水题。 1为从网上找到的比较有水平的相关题目。**

**一步步学算法(算法题解)---2**

经典问题回顾。

# 1。河内之塔(Hanoi) #

**问题描述:**

说明河内之塔(Towers ofHanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;1883年法国数学家 EdouardLucas曾提及这个故事,据说创世纪时Benares有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘(Disc),并命令僧侣将所有的金盘从第一根石棒移至第三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬运完毕之时,此塔将毁损,而也就是世界末日来临之时。

**问题分析:**

解法如果柱子标为ABC,要由A搬至C,在只有一个盘子时,就将它直接搬至C,当有两个盘

子,就将B当作辅助柱。如果盘数超过2个,将第三个以下的盘子遮起来,就很简单了,每次处理两个盘子,也就是:A->B、A ->C、B->C这三个步骤,而被遮住的部份,其实就是进入程式的递回处理。事实上,若有n个盘子,则移动完毕所需之次数为2^n - 1,所以当盘数为64时,则所需次数为:264\- 1 =18446744073709551615为5.05390248594782e+16年,也就是约5000世纪,如果对这数字没什幺概念,就假设每秒钟搬一个盘子好了,也要约5850亿年左右。

问题比较简单，也比较经典。 下面直接看代码

#include <stdio.h>
    
    void Move(int n,char a,char b)
    {
        printf("%d:%c-->%c\n",n,a,b);
    }
    
    void Hanoi(int n,char a,char b,char c)
    {
        if(n==1)//将A上的1个圆盘直接移到C,递归退出条件
            Move(n,a,c);
        else
        {
            Hanoi(n-1,a,c,b);//将A上n-1个圆盘借助C移到B
            Move(n,a,c);//将A上剩下的1个圆盘直接移到C
            Hanoi(n-1,b,a,c);//将B上n-1个圆盘借助A移到C
        }
    }
    
    int main()
    {
        int n;
        printf("\ninput   number:");
        scanf("%d",&n);
        Hanoi(n,'A','B','C');
        return 0;
    }
    /* 打印结果
     
     input   number:3
     1:A-->C
     2:A-->B
     1:C-->B
     3:A-->C
     1:B-->A
     2:B-->C
     1:A-->C
    */

# 2。Algorithm Gossip: 费式数列 #

**问题描述:**

说明Fibonacci为1200年代的欧洲数学家,在他的着作中曾经提到:「若有一只免子每个月生一只小免子,一个月后小免子也开始生产。起初只有一只免子,一个月后就有两只免子,二个月后有三只免子,三个月后有五只免子(小免子投入生产)......。如果不太理解这个例子的话,举个图就知道了,注意新生的小免子需一个月成长期才会投入生产,类似的道理也可以用于植物的生长,这就是Fibonacci数列,一般习惯称之为费氏数列,例如以下: 1、1 、2、3、5、8、13、21、34、55、89......

**问题分析:**

解法依说明,我们可以将费氏数列定义为以下:

f(n) = f(n-1)+f(n-2)---- if n>1

f(n) = n ------if n = 0, 1

..斐波那契数列，应该是每个写代码的都接触过了。虽然简单，不过还是罗列出来，谁叫它经典呢。

#include <stdio.h>
    #define N 10
    
    int main()
    {
        int Fib[N] = {0};
        int i;
        Fib[0] = 0;
        Fib[1] = 1;
        for(i = 2; i < N; i++)
            Fib[i] = Fib[i-1] + Fib[i-2];
        for(i = 0; i < N; i++)
            printf("%d ", Fib[i]);
        printf("\n");
        return 0;
    }/* 打印结果
      0 1 1 2 3 5 8 13 21 34
    */

# 3.三色旗 #

**问题描述:**

三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰人)，而多数的作者则使用Three-Color Flag来称之。假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。

**问题分析:**

在一条绳子上移动，在程式中也就意味只能使用一个阵列，而不使用其它的阵列来作辅助，问题的解法很简单，您可以自己想像一下在移动旗子，从绳子开头进行，遇到蓝色往前移，遇到白色留在中间，遇到红色往后移  
  
只是要让移动次数最少的话，就要有些技巧：  
  
如果图中W所在的位置为白色，则W+1，表示未处理的部份移至至白色群组。  
如果W部份为蓝色，则B与W的元素对调，而B与W必须各+1，表示两个群组都多了一个元素。  
如果W所在的位置是红色，则将W与R交换，但R要减1，表示未处理的部份减1。  
  
注意B、W、R并不是三色旗的个数，它们只是一个移动的指标；什幺时候移动结束呢？一开始时未处理的R指标会是等于旗子的总数，当R的索引数减至少于W的索引数时，表示接下来的旗子就都是红色了，此时就可以结束移动，如下所示：

#include<stdio.h>
    #include<stdlib.h>
    #include<string>
    #include<iostream>
    using namespace std;
    char c[]={'r','b','w','w','b','b','r','w','b'};
    void swap(int i,int j)
    {
        char t=c[i];
        c[i]=c[j];
        c[j]=t;
    }
    int main(int argc, char* argv[])
    {
        
        int w=0;
        int b=0;
        string s=c;
        int r=s.length()-1;
        while(w<=r)
        {
            if(c[w]=='w')
                w++;
            else if(c[w]=='b')
            {
                swap(b,w);
                b++;
                w++;
            }
            else
            {
                while(r>=w&&c[r]=='r')
                    r--;
                swap(w,r);
                r--;
            }
        }
        cout<<c;
        return 0;
    }

# 4.Algorithm Gossip: 老鼠走迷官(一) #

**问题描述:**

说明老鼠走迷宫是递回求解的基本题型,我们在二维阵列中使用2表示迷宫墙壁,使用1来表示老鼠的行走路径,试以程式求出由入口至出口的路径。

**问题分析:**

解法老鼠的走法有上、左、下、右四个方向,在每前进一格之后就选一个方向前进,无法前进时退回选择下一个可前进方向,如此在阵列中依序测试四个方向,直到走到出口为止,这是递回的基本题,请直接看程式应就可以理解。

#include <stdio.h>
    #include <stdlib.h>
    
    int startI = 1, startJ = 1; // 入口
    int endI=5,endJ=5; //出口
    int success = 0;
    
    int maze[7][7] =
    {
        {2, 2, 2, 2, 2, 2, 2},
        {2, 0, 0, 0, 0, 0, 2},
        {2, 0, 2, 0, 2, 0, 2},
        {2, 0, 0, 2, 0, 2, 2},
        {2, 2, 0, 2, 0, 2, 2},
        {2, 0, 0, 0, 0, 0, 2},
        {2, 2, 2, 2, 2, 2, 2}
    };
    
    int visit(int i, int j)
    {
        maze[i][j] = 1;
        if(i == endI && j == endJ)
            success = 1;
        if(success != 1 && maze[i][j+1] == 0)
            visit(i, j+1);
        if(success != 1 && maze[i+1][j] == 0)
            visit(i+1, j);
        if(success != 1 && maze[i][j-1] == 0)
            visit(i, j-1);
        if(success != 1 && maze[i-1][j] == 0)
            visit(i-1, j);
        if(success != 1)
            maze[i][j] = 0;
        
        return success;
    }
    
    int main()
    {
        int i, j;
        printf("显示迷宫:\n");
        for(i = 0; i < 7; i++)
        {
            for(j = 0; j < 7; j++)
                if(maze[i][j] == 2)
                    printf("█");
                else
                    printf(" "); printf("\n");
        }
        if(visit(startI, startJ) == 0)
            printf("\n没有找到出口!\n");
        else
        {
            printf("\n显示路径:\n");
            for(i = 0; i < 7; i++)
            {
                for(j = 0; j < 7; j++)
                {
                    if(maze[i][j] == 2)
                        printf("█");
                    else if(maze[i][j] == 1)
                        printf("◇");
                    else
                        printf(" ");
                }
                printf("\n");
            }
        }
        return 0;
    }

# 5.Algorithm Gossip: 老鼠走迷官(二) #

**问题描述：**

说明由于迷宫的设计,老鼠走迷宫的入口至出口路径可能不只一条,如何求出所有的路径呢?

**问题分析：**

解法求所有路径看起来复杂但其实更简单,只要在老鼠走至出口时显示经过的路径,然后退回上一格重新选择下一个位置继续递回就可以了,比求出单一路径还简单,我们的程式只要作一点修改就可以了。

#include <stdio.h>
    #include <stdlib.h>
    
    int startI = 1, startJ = 1; // 入口
    int endI=7,endJ=7; //出口
    
    int maze[9][9] =
    {
        {2, 2, 2, 2, 2, 2, 2, 2, 2},
        {2, 0, 0, 0, 0, 0, 0, 0, 2},
        {2, 0, 2, 2, 0, 2, 2, 0, 2},
        {2, 0, 2, 0, 0, 2, 0, 0, 2},
        {2, 0, 2, 0, 2, 0, 2, 0, 2},
        {2, 0, 0, 0, 0, 0, 2, 0, 2},
        {2, 2, 0, 2, 2, 0, 2, 2, 2},
        {2, 0, 0, 0, 0, 0, 0, 0, 2},
        {2, 2, 2, 2, 2, 2, 2, 2, 2}
    };
    
    void visit(int i, int j)
    {
        int m, n;
        maze[i][j] = 1;
        if(i == endI && j == endJ)
        {
            printf("\n显示路径:\n");
            for(m = 0; m < 9; m++)
            {
                for(n = 0; n < 9; n++)
                    if(maze[m][n] == 2)
                        printf("█");
                    else if(maze[m][n] == 1)
                        printf("◇");
                    else
                        printf(" ");
                printf("\n");
            }
        }
        if(maze[i][j+1] == 0)
            visit(i, j+1);
        if(maze[i+1][j] == 0)
            visit(i+1, j);
        if(maze[i][j-1] == 0)
            visit(i, j-1);
        if(maze[i-1][j] == 0)
            visit(i-1, j);
        maze[i][j] = 0;
    }
    
    int main(void)
    {
        int i, j;
        printf("显示迷宫:\n");
        for(i = 0; i < 7; i++)
        {
            for(j = 0; j < 7; j++)
                if(maze[i][j] == 2)
                printf("█");
                else
                    printf(" ");
            printf("\n");
        }
        visit(startI, startJ);
        return 0;
    }

# 6\*\* 坐旋转字符串 #

**问题描述：**

定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。

**问题分析：**

如果不考虑时间和空间复杂度的限制，最简单的方法莫过于把这道题看成是把字符串分成前后两部分，通过旋转操作把这两个部分交换位置。于是我们可以新开辟一块长度为n+1的辅助空间，把原字符串后半部分拷贝到新空间的前半部分，在把原字符串的前半部分拷贝到新空间的后半部分。不难看出，这种思路的时间复杂度是O(n)，需要的辅助空间也是O(n)。

接下来的一种思路可能要稍微麻烦一点。我们假设把字符串左旋转m位。于是我们先把第0个字符保存起来，把第m个字符放到第0个的位置，在把第2m个字符放到第m个的位置…依次类推，一直移动到最后一个可以移动字符，最后在把原来的第0个字符放到刚才移动的位置上。接着把第1个字符保存起来，把第m+1个元素移动到第1个位置…重复前面处理第0个字符的步骤，直到处理完前面的m个字符。

该思路还是比较容易理解，但当字符串的长度n不是m的整数倍的时候，写程序会有些麻烦，感兴趣的朋友可以自己试一下。由于下面还要介绍更好的方法，这种思路的代码我就不提供了。

我们还是把字符串看成有两段组成的，记位XY。左旋转相当于要把字符串XY变成YX。我们先在字符串上定义一种翻转的操作，就是翻转字符串中字符的先后顺序。把X翻转后记为XT。显然有(XT)T=X。

我们首先对X和Y两段分别进行翻转操作，这样就能得到XTYT。接着再对XTYT进行翻转操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是我们期待的结果。

分析到这里我们再回到原来的题目。我们要做的仅仅是把字符串分成两段，第一段为前面m个字符，其余的字符分到第二段。再定义一个翻转字符串的函数，按照前面的步骤翻转三次就行了。时间复杂度和空间复杂度都合乎要求。

参考代码如下：

#include "string.h"
    
    ///
    // Move the first n chars in a string to its end
    ///
    char* LeftRotateString(char* pStr, unsigned int n)
    {
        if(pStr != NULL)
        {
            int nLength = static_cast<int>(strlen(pStr));
            if(nLength > 0 || n == 0 || n > nLength)
            {
                char* pFirstStart = pStr;
                char* pFirstEnd = pStr + n - 1;
                char* pSecondStart = pStr + n;
                char* pSecondEnd = pStr + nLength - 1;
                
                // reverse the first part of the string
                ReverseString(pFirstStart, pFirstEnd);
                // reverse the second part of the strint
                ReverseString(pSecondStart, pSecondEnd);
                // reverse the whole string
                ReverseString(pFirstStart, pSecondEnd);
            }
        }
        
        return pStr;
    }
    
    ///
    // Reverse the string between pStart and pEnd
    ///
    void ReverseString(char* pStart, char* pEnd)
    {
        if(pStart == NULL || pEnd == NULL)
        {
            while(pStart <= pEnd)
            {
                char temp = *pStart;
                *pStart = *pEnd;
                *pEnd = temp;
                
                pStart ++;
                pEnd --;
            }
        }
    }
    
    
    
    PS：(XTYT)T=(YT)T(XT)T=YX