精华内容
下载资源
问答
  • 排列的字典序问题

    2019-09-28 14:16:15
    排列的字典序问题 欢迎进入二阳的学习课堂!!!此次排列字典序问题与上次不一样,这道理解计算过程也非常简单。首先二阳给各位小哥哥小姐姐看看题目 还不太理解这种字典序朋友可以看看它的百科字典序 1.问题分析...
                  排列的字典序问题
    

    欢迎进入二阳的学习课堂!!!此次排列字典序问题与上次不一样,这道理解计算过程也非常简单。首先二阳给各位小哥哥小姐姐看看题目
    在这里插入图片描述在这里插入图片描述
    还不太理解这种字典序朋友可以看看它的百科字典序
    1.问题分析:
    给出一个排列,求排列的字典序值和下一个排列。这题需搞清楚这个字典序值是如何求得的,再想办法用何种算法。
    字典序值求法:
    给出一个排列p(0)p(1)p(2)···p(n-1);
    字典值sum=b[0] * (n-1)!+b[1] * (n-2)!+b[2] * (n-3)!+…+b[n-2]
    b[i]是p(i)对应的‘序数’,它代表着p(i)的右边比p(i)小的个数。
    下一个序列的求法:
    找到从右侧最大降序列p(i+1)p(i+2)…p(n-1),记录这序列的前一位下标i,再求p(i)最右侧值大于p(i)的p(k);交换p(i)和p(k)。操作后的序列也就是下一个序列
    2.算法设计
    采用分治法,利用函数递归求解各个b[i] * (n-1-i)!的值,然后再求和。
    3.算法实现:

    #include<iostream>
    using namespace std;
    int sum = 0;
    int f = 1;
    int n;
    /*数组的引用:
    https://www.cnblogs.com/flowingwind/p/8446360.html
    */
    //求数组b
    void qiub(int a[], int(&b)[30], int n)
    {
    	int i, j;
    	for (i = 0; i < n; i++)
    	{
    		for (j = i + 1; j < n; j++)
    		{
    			if (a[i] > a[j])
    			{
    				b[i]++;
    			}
    		}
    	}
    }
    //用数组b求得字典序
    void getxu(int z, int a[], int b[])//z从n-2开始,0到n-2为n-1个数,b[n-1]为0
    {
    	if (f == n)
    		return;
    	for (int i = 1; i <= f; i++)
    	{
    		b[z] = b[z] * i;
    	}
    	sum += b[z];
    	f++;
    	z--;
    	getxu(z, a, b);
    }
    //求下一个
    void getxia(int n, int a[])
    {
    	int i, m, k, f;//m记录从右侧最大降序列的左端第一个数
    	for (i = n - 1; i >= 0; i--)
    	{
    		if (a[i - 1] > a[i])
    			continue;
    		else
    		{
    			m = i - 1;;
    			break;
    		}
    	}
    	for (i = m + 1; i < n; i++)
    	{
    		if (a[i] > a[m])
    		{
    			k = i;
    		}
    	}
    	f = a[m];
    	a[m] = a[k];
    	a[k] = f;
    	for (i = 0; i < n; i++)
    	{
    		cout << a[i] << " ";
    	}
    	cout << endl;
    }
    
    int main()
    {
    	int i;
    	int a[30], b[30] = { 0 };
    	cin >> n;
    	for (i = 0; i < n; i++)
    	{
    		cin >> a[i];
    	}
    	qiub(a, b, n);
    	getxu(n - 2, a, b);
    	cout << sum << endl;
    	getxia(n, a);
    	return 0;
    }
    

    运行结果:
    在这里插入图片描述

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,106
精华内容 442
关键字:

排列的字典序问题