积累系统性知识
积聚技术精华
  首页    个人中心    撰写积文    建立课题    订立目标    整理积文    管理课题    管理目标    技能Get    代码积累 
回溯法-经典问题C程序
error997 (error997)    2014-11-20 20:21:07      目标    课题
   回溯法的基本要点参见各算法书籍,这里给出两个简单运用的例子(数的全排列和八皇后问题)

数的全排列(含递归和非递归)
切换到: 纯代码  
   
#include <stdio.h>
#define N 4
void arrange(int rec[],int used[],int depth)
{
    int i;
    if(depth>=N)
    {
        for(i=0;i<N;i++)
        {
            printf("%d",rec[i]);
        }
        printf("/n");
    }
    else
    {
        for(i=0;i<N;i++)
        {
            rec[depth]=i;
            if(used[i]==0)
            {
                used[i]=1;
                arrange(rec,used,depth+1);
                used[i]=0;
            }
            rec[depth]=0;
        }
    }
}

int selectnum(int used[],int start)
{
    int i;
    for(i=start;i<N;i++)
    {
        if(used[i]==0)
        {
            return i;
        }
    }
    return -1;
}

void arrange2(int rec[],int used[])
{
    int i,pos;
    for(i=0;i>-1;)
    {
        if(i>=N)
        {
            for(i=0;i<N;i++)
            {
                printf("%d",rec[i]);
            }
            printf("/n");
            i--;
        }
        pos=selectnum(used,rec[i]+1);
        if(pos!=-1)
        {
            used[pos]=1;
            rec[i]=pos;
            i++;
        }
        else
        {
            if(rec[i]>=0)
            {
                used[rec[i]]=0;
                rec[i]=-1;
                i--;
            }
            if(i>-1)
            {
                used[rec[i]]=0;
            }
        }
    }
}

int main()
{
    int i,rec[N],used[N];
    for(i=0;i<N;i++)
    {
        rec[i]=-1;
        used[i]=0;
    }
    arrange(rec,used,0);
    for(i=0;i<N;i++)
    {
        rec[i]=-1;
        used[i]=0;
    }
    printf("/n");
    arrange2(rec,used);
    return 0;
}

八皇后问题(
   含递归和非递归
   )
切换到: 纯代码  
   
#include <stdio.h>
#define N 8

void eight_queen(int rec[],int used[],int s1[],int s2[],int depth)
{
    int i;
    if(depth>=N)
    {
        for(i=0;i<N;i++)
        {
            printf("%d ",rec[i]);
        }
        printf("/n");
    }
    else
    {
        for(i=0;i<N;i++)
        {
            rec[depth]=i;
            if(used[i]==0&&s1[i+(N-depth)]==0&&s2[i+depth]==0)
            {
                used[i]=1;
                s1[i+(N-depth)]=1;
                s2[i+depth]=1;
                eight_queen(rec,used,s1,s2,depth+1);
                used[i]=0;
                s1[i+(N-depth)]=0;
                s2[i+depth]=0;
            }
            rec[depth]=-1;
        }
    }
}

int selectnum(int used[],int s1[],int s2[],int start,int depth)
{
    int i;
    for(i=start;i<N;i++)
    {
        if(used[i]==0&&s1[i+(N-depth)]==0&&s2[i+depth]==0)
        {
            return i;
        }
    }
    return -1;
}

void eight_queen2(int rec[],int used[],int s1[],int s2[])
{
    int i,pos;
    for(i=0;i>-1;)
    {
        if(i>=N)
        {
            for(i=0;i<N;i++)
            {
                printf("%d ",rec[i]);
            }
            printf("/n");
            i--;
        }
        pos=selectnum(used,s1,s2,rec[i]+1,i);
        if(pos!=-1)
        {
            rec[i]=pos;
            used[pos]=1;
            s1[pos+(N-i)]=1;
            s2[pos+i]=1;
            i++;
        }
        else
        {
            if(rec[i]>=0)
            {
                used[rec[i]]=0;
                s1[rec[i]+(N-i)]=0;
                s2[rec[i]+i]=0;
                rec[i]=-1;
            }
            i--;
            if(i>=0)
            {
                used[rec[i]]=0;
                s1[rec[i]+(N-i)]=0;
                s2[rec[i]+i]=0;
            }
        }
    }
}

int main()
{
    int i;
    int rec[N],used[N],s1[2*N-1],s2[2*N-1];
    for(i=0;i<N;i++)
    {
        rec[i]=-1;
        used[i]=0;
    }
    for(i=0;i<2*N-1;i++)
    {
        s1[i]=0;
        s2[i]=0;
    }
    eight_queen(rec,used,s1,s2,0);
    printf("/n");
    for(i=0;i<N;i++)
    {
        rec[i]=-1;
        used[i]=0;
    }
    for(i=0;i<2*N-1;i++)
    {
        s1[i]=0;
        s2[i]=0;
    }
    eight_queen2(rec,used,s1,s2);
    return 0;
}


转自 http://blog.csdn.net/y___y/article/details/1764280
(+0)技能Get

建议楼主:搜索关键字 |参考其他资源 |回复 |追问
  error997(error997):   个人中心    课题    目标    代码积累