| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1882 人关注过本帖
标题:回溯法求解1....n个整数的所有全排列并输出
取消只看楼主 加入收藏
sunjinlong
Rank: 1
等 级:新手上路
帖 子:19
专家分:0
注 册:2008-11-19
结帖率:100%
收藏
 问题点数:0 回复次数:1 
回溯法求解1....n个整数的所有全排列并输出
请大侠帮忙!
搜索更多相关主题的帖子: 输出 求解 回溯 排列 整数 
2010-03-08 20:57
sunjinlong
Rank: 1
等 级:新手上路
帖 子:19
专家分:0
注 册:2008-11-19
收藏
得分:0 
自己写的,实在落伍太多了。。。
#include <stdio.h>
/*回溯法求解1.....n的全排列问题*/

int isLegal(int B[],int n,int k){
/*若数组元素个数为n并且B中元素各异,则认为是最终解*/
    int i;
    int j;
    int flag=1;
    if(k==(n-1)){
        for(i=0;i<=k;i++){
            j=0;
            while(j<=k){
                 if((i!=j)&&(B[i]==B[j])){
                        flag=0;
                }
                j++;
            }
        }
    }else{
        flag=0;
    }
    return flag;
}

int isPart(int B[],int n,int k){
/*若数组元素个数小于n并且B中元素各异,则认为是部分解*/
    int i;
    int j=0;
    int flag=1;
    if(k<n-1){
        for(i=0;i<=k;i++){
            j=0;
            while(j<=k){

                if((i!=j)&&(B[i]==B[j])){
                        flag=0;
                }
                j++;
            }
        }
    }else{
        flag=0;
    }
    return flag;
}


void  pailie(int B[],int n){
    /*回溯迭代算法*/
    int k,j;
    int count=0;

    k=0;
    while(k>=0){
        while(B[k]<=n-1){
            B[k]=B[k]+1;
            if(isLegal(B,n,k)){
                /*储存或输出解向量*/
                printf("%2d:  ",++count);
                for(j=0;j<n;j++){
                    printf("%2d  ",B[j]);
                }
                printf("\n");
                break;

            }
            else if(isPart(B,n,k)){
                k=k+1;

            }
        }

        B[k]=0;
        k=k-1;
    }
}

void main(){
    int B[4]={0,0,0,0};
    printf("The list is as belows:\n");
    pailie(B,4);

    getch();
}
2010-04-04 19:08
快速回复:回溯法求解1....n个整数的所有全排列并输出
数据加载中...
 
   



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

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