MyException - 我的异常网
当前位置:我的异常网» 编程 » 一步步学算法(算法例题)-2

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

www.MyException.Cn  网友分享于:2013-09-10  浏览:10次
一步步学算法(算法题解)---2

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

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

题目分布为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


文章评论

什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
老程序员的下场
老程序员的下场
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
代码女神横空出世
代码女神横空出世
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
那些争议最大的编程观点
那些争议最大的编程观点
程序员应该关注的一些事儿
程序员应该关注的一些事儿
程序员的鄙视链
程序员的鄙视链
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
如何成为一名黑客
如何成为一名黑客
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员必看的十大电影
程序员必看的十大电影
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员都该阅读的书
程序员都该阅读的书
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
10个调试和排错的小建议
10个调试和排错的小建议
总结2014中国互联网十大段子
总结2014中国互联网十大段子
编程语言是女人
编程语言是女人
鲜为人知的编程真相
鲜为人知的编程真相
 程序员的样子
程序员的样子
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
Java程序员必看电影
Java程序员必看电影
我是如何打败拖延症的
我是如何打败拖延症的
每天工作4小时的程序员
每天工作4小时的程序员
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
我的丈夫是个程序员
我的丈夫是个程序员
旅行,写作,编程
旅行,写作,编程
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有