康拓展开和康拓展开逆运算

Posted by

注:康拓照片 一个集合中{1,2,3,4,…,n},他的全排列必定有n!项,若n=4,那么就有24项。如下:   问题如下: 求4 2 1 3是的几个排列? 根据表格是第21个,可是具体如何算呢?我也想了好久才懂得的。。。 总共n个数,此时n=4,ans=0。 第一个数是4,比4小的但是没出现过的是1,2,3。所以ans:=ans+ 3*(n-1)!=18 第二个数是2,比2小但是没出现过的是1.所以ans:=ans+ 1*(n-2)!=2。此时ans=20 第三个数是1,比1小但是没出现过的没有,所以ans不变 第四个数是3,比3小但是没出现过的没有,但是ans表示的是这个数之前有多少个排列,所以ans最终+=1,ans=21。 康拓展开还是蛮简单的,但是个人认为逆序就有点…. 让我们来分析: 我把之前的div改为/,div是pascal语言的运算符号,/是C++的,意思都一样就是求两个整数除法运算后的商(不理会余数) 其实逆序就是把康拓展开进行移项,利用倒推思路。 问题如下: 在1-5的排列中找出第69个排列。 怎么办呢???(黑人问号脸 记住我的话,倒推出奇迹。 让我们设这五位数分别为X1X2X3X4X5,先减去1,代表着X1X2X3X4X5之前有68个序列。 我们再次假设:第一个数X1,有k个小于X1且未出现的数字。 根据X=a[n]*(n-1)!+a[n-1]*(n-2)!+…+a[i]*(i-1)!+…+a[1]*0! k=68/(n-1)!=68/24得2余20,余数不管,所以当X1=3时,前面才会有2个比它小且不重复的数字。 此时全排列的个数就要被减去,缩小范围,即num=68-2*24=20 第二个数X2,k=20/(n-2)!=20/6得3余2,余数不管,那么X2=5.(有3个数比它小的数是3,但3已经在之前出现过了,所以是5) 此时num=20-3*6=2。 第三个数X3,k=2/(n-3)!=1,所以X3=2,num=2-1*2=0 第四个数X4,k=0/(n-4)!=0,所以X4=1,num=1-0*0=1 最后一个未选的数就是只剩4;所以第69个就是3 5 2 1 4。 你是否已经理解了呢,接下来直接上代码

#include 
#include <string.h>
long long a[20],d[17],n;
long long kangtuo()
{
    bool qwq[20];
    memset(qwq,false,sizeof(qwq));//初始化 
    long long sum=0;
    for(long long i=1;i<=n-1;i++)
    {
        long long k=0;
        for(long long j=1;j<a[i];j++)if(!qwq[j]) k++;//判断比它小且为被出现的数字 
        sum=sum+k*d[n-i];//运用公式计算当前的全排列个数 
        qwq[a[i]]=true;//标记为已经出现 
    }
    sum++;
    return sum;//返回值 
}
void kang_tuo(long long sum)
{
    sum--;
    bool qwq[20];
    memset(qwq,true,sizeof(qwq));//同上初始化 
    for(long long i=1;i<=n;i++)
    {
        long long k=sum/d[n-i];//计算有多少个在它之前的数字 
        sum-=k*d[n-i];//缩小范围 
        long long j;
        for(j=1;j<=n;j++)if(qwq[j])
        {
                if(k==0) break;
                k--;
        }
        /*
        这个if语句我认为是比较核心的代码,之前算出之前有多少个数了,这个的用途
        即为判断是否有存在比它小但是出现过的情况。若未出现k就递减,直至等于0,
        此时的j即为当前这个数的位置。
        */
            qwq[j]=false;
            a[i]=j;//赋值 
    }
    for(long long i=1;i<n;i++) printf("%lld ",a[i]);
    printf("%lld\n",a[n]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      scanf("%lld",&a[i]);
    d[0]=1;
    for(int i=1;i<=15;i++) d[i]=d[i-1]*i;
    printf("%lld\n",kangtuo());
    long long k;
    scanf("%lld",&k);
    kang_tuo(k);
    return 0;
}
 
这是进入宽搜的第一道门槛,只有掌握这个,接下来的数码问题才能搞懂(数码问题会用到康拓优化 下次我会更新新的博客,有关八数码。 再见!   ]]>

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注