| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 726 人关注过本帖
标题:N 皇后问题,回溯
只看楼主 加入收藏
kwxx
Rank: 8Rank: 8
等 级:蝙蝠侠
帖 子:309
专家分:913
注 册:2009-5-11
收藏
得分:0 
你的程序能运行出合理的结果吗?void queue(int n)中的m就没赋初值。
2014-05-04 13:47
top398
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:2
帖 子:427
专家分:857
注 册:2014-5-2
收藏
得分:0 
有 m 这一行改为:
int i,k,m=0;
即可。
试运行结果:
(输入)8
92

2014-05-04 14:24
top398
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:2
帖 子:427
专家分:857
注 册:2014-5-2
收藏
得分:0 
另外一个建议,既然 n 由用户输入,而 main 并不会用到数组 x,因此把数组 x 在外部声明以及指定其有100个元素是不妥的。应该在 queen 函数中用 VLA 定义:
int x[n+1];
当然那个 place 函数也就得改写一下,给它传递一个 int * 指针。
注意你的数组没有使用下标为0的元素,因此实际定义的数组要比n大1。

但在保证 n 小于 100 的前提下,可以不用这样改了。


[ 本帖最后由 top398 于 2014-5-4 14:33 编辑 ]
2014-05-04 14:30
top398
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:2
帖 子:427
专家分:857
注 册:2014-5-2
收藏
得分:0 
不过还是有个疑问:
     else printf("%d\n",m/8);
这里为什么是除以8?
我测试也用的是8,因为我知道共92种可能。对楼主的算法我不熟悉,因此不太肯定此处是否有问题。

前面几行:
        if(x[k]<=n&&k==n)
        {
            for(i=1;i<=n;i++)
            m=m+1;
        }
是否应理解为:在找到一个可能时,就把 m 加上 n 次 1(也就是加上 n)?
那么后面这个除以8就实在有些奇怪了。
2014-05-04 15:10
top398
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:2
帖 子:427
专家分:857
注 册:2014-5-2
收藏
得分:0 
尝试简化为:
程序代码:
#include<stdio.h>
#include<math.h>
#include <stdbool.h>

bool place_ok( int *px, int k )
{
    int i;
    for ( i = 1; i < k; i++ ) {
        if ( px[k] == px[i] || abs( k - i ) == abs( px[k] - px[i] ) )
            return false;
    }
    return true;
}

void queen( int n )
{
    int x[n + 1];
    int i, k = 1, m = 0;
    for ( i = 1; i <= n; i++ )
        x[i] = 0;
    while ( k >= 1 ) {
        x[k]++;
        while ( x[k] <= n && !place_ok( x, k ) )
            x[k]++;
        if ( x[k] > n ) {
            x[k] = 0;
            k--;
        } else if ( k == n ) {
            m++;
        } else {
            k++;
        }
    }
    if ( n == 1 )
        printf( "1\n" );
    else
        printf( "%d\n", m );
}

int main(void)
{
    int n;
    printf( "Input n:" );
    scanf( "%d", &n );
    queen( n );
    return 0;
}

2014-05-04 15:44
top398
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:2
帖 子:427
专家分:857
注 册:2014-5-2
收藏
得分:0 
R:\>gcc z.c

R:\>a
Input n:8
92

R:\>a
Input n:9
352

R:\>a
Input n:10
724

R:\>a
Input n:11
2680

不知以上结果是否都正确?
2014-05-04 15:47
top398
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:2
帖 子:427
专家分:857
注 册:2014-5-2
收藏
得分:0 
再稍作修改:
程序代码:
#include<stdio.h>
#include<math.h>
#include <stdbool.h>

bool place_ok( int *px, int k )
{
    int i;
    for ( i = 1; i < k; i++ ) {
        if ( px[k] == px[i] || abs( k - i ) == abs( px[k] - px[i] ) )
            return false;
    }
    return true;
}

int queen( int n )
{
    int x[n + 1];
    int i, k = 1, m = 0;
    for ( i = 1; i <= n; i++ )
        x[i] = 0;
    while ( k >= 1 ) {
        x[k]++;
        while ( x[k] <= n && !place_ok( x, k ) )
            x[k]++;
        if ( x[k] > n ) {
            x[k] = 0;
            k--;
        } else if ( k == n ) {
            m++;
        } else {
            k++;
        }
    }

    return n == 1 ? 1 : m;
}

int main(void)
{
    int n;
    printf( "Input n:" );
    scanf( "%d", &n );
    printf( "Methods: %d\n", queen( n ) );
    return 0;
}

主要是把 queen 函数的输出语句移出来,并返回可能的方法数,成为一个单纯的函数。
试运行结果:

R:\>a
Input n:12
Methods: 14200

R:\>a 13
Input n:13
Methods: 73712

R:\>a
Input n:14
Methods: 365596

R:\>a 15
Input n:15
Methods: 2279184

建议不要轻易尝试14以上的求解。

2014-05-04 16:05
快速回复:N 皇后问题,回溯
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018372 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved