幻想森林

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 2949|回复: 3

[通用编程] 对回溯法提问

[复制链接]

313

主题

1574

帖子

1万

积分

⑧专业

*永恒国度*

积分
14145
QQ
发表于 2009-2-5 17:07:48 | 显示全部楼层 |阅读模式
看严蔚敏书上树的那章,最后提到了一下回溯法,看完不太懂,不知有否简单一点的完整实现的程序,可以参考一下呢(最好是求幂集的)?谢了。
[img][/img] http://shop33698673.taobao.com被别人嫉妒,证明你优秀,嫉妒别人说明你无能
回复

使用道具 举报

20

主题

197

帖子

2641

积分

⑥精研

积分
2641
QQ
发表于 2009-2-8 22:37:28 | 显示全部楼层
关于回溯算法,最简单的应该就是8皇后问题了吧,就是指在8*8的国际象棋盘上摆8个皇后,且符合每个皇后的横,竖,斜线不存在其它皇后
#include <stdio.h>
#define MAX 8
int kpos[MAX];
int place(int count)
{
    int i;
    for(i=0;i<count;i++)
    {
        if(abs(i-kpos)==abs(count-kpos[count] || kpos==kpos[count])
            return 0;
    }
    return 1;
}
int main()
{
    
    int kcount=0;
    while(kcount<MAX)
    {
        kpos[kcount]++;
        for(kpos[kcount];kpos[kcount]<=8;kpos[kcount]++)
        {
            if(placs(kcount))
            {
                kcount++;
                break;
            }
        }
        if(kpos[kcount]>MAX)
    {   
                kpos[kcount]=0;
        kcount--;
        }
    }
     int i;
     for(i=0;i<MAX;i++)
            printf("No.%d:%d",i,kpos);
    return 0;
}
签名要少于60,SO,i haven't upload my pic
回复 支持 反对

使用道具 举报

313

主题

1574

帖子

1万

积分

⑧专业

*永恒国度*

积分
14145
QQ
 楼主| 发表于 2009-2-8 23:26:04 | 显示全部楼层
怎么感觉好像只是很单纯的递归?
[img][/img] http://shop33698673.taobao.com被别人嫉妒,证明你优秀,嫉妒别人说明你无能
回复 支持 反对

使用道具 举报

20

主题

197

帖子

2641

积分

⑥精研

积分
2641
QQ
发表于 2009-2-9 10:40:09 | 显示全部楼层
呃,递归与回溯的区别不大,要说区别的话,递归是不会有回退再选择其它路径的
签名要少于60,SO,i haven't upload my pic
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|幻想森林

GMT+8, 2024-11-1 07:50 , Processed in 0.026189 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表