| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 359 人关注过本帖
标题:期中考最后一题,应该是有关排列组合的
取消只看楼主 加入收藏
mahuaguan
Rank: 1
等 级:新手上路
帖 子:38
专家分:4
注 册:2011-9-13
结帖率:62.5%
收藏
已结贴  问题点数:20 回复次数:1 
期中考最后一题,应该是有关排列组合的
给定n个不同的数,问这n个数可以组成多少个不同的序列且序列中相邻的元素之差大于一。
一开始我用递归进行全排列,然后逐个比较。后来看到最多有25个数,就知道肯定超时了(时间复杂度已经达到O(n!)了)。不知各位大牛有何建议?这肯定是有简便方法的,不过我就是没想出来。。。
附上我超时的代码:
#include<iostream>
using namespace std;
int fabs(int n)
{
    if(n<0)
        return -n;
    else
        return n;
}
int counter=0;
void Swap(int& a,int& b)
{
    int temp=a;
    a=b;
    b=temp;
}
void pai(int a[],int n,int k,int end)
{
    int flag=1;
    if(k==end)
    {
        //cout<<"yes.\n";
        /*for(int i=0;i<n-1;i++)
        {
            if((a[i]-a[i+1]==1)||(a[i]-a[i+1]==-1))
                return;
        }*/
        counter++;
        return;
        /*for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
        cout<<endl;*/
    }
    for(int i=k;i<n;i++)
    {
        Swap(a[k],a[i]);
        if(fabs(a[k]-a[k+1])>1)
        {
            if(k>=1)
            {
                if(fabs(a[k]-a[k-1])>1)
                    pai(a,n,k+1,end);
            }
            else
                pai(a,n,k+1,end);
        }
        
        //pai(a,n,k+1,end);
        Swap(a[k],a[i]);
    }
}

int main()
{
    int T,num;
    int a[26];
    cin>>T;
    while(T--)
    {
        counter=0;
        cin>>num;
        for(int i=0;i<num;i++)
            cin>>a[i];
        pai(a,num,0,num-1);
        cout<<counter<<endl;
        
    }
    return 0;
}
搜索更多相关主题的帖子: 肯定 counter include return 
2012-05-04 12:24
mahuaguan
Rank: 1
等 级:新手上路
帖 子:38
专家分:4
注 册:2011-9-13
收藏
得分:0 
回复 3楼 pangding
给出n个数。。
2012-05-11 22:32
快速回复:期中考最后一题,应该是有关排列组合的
数据加载中...
 
   



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

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