标准二维表

r囧r小猫 2022-08-02 06:54 156阅读 0赞

问题描述：

设n是一个正整数。2\*n的标准二维表是由正整数1,2,…,2n组成的2\*n数组，该数组的每行从左到右递增，每列从上到下递增。2\*n的标准二维表全体记为tab(n)。例如，当n=3时，tab(3)二维表如下图所示。

<table style="direction:ltr; border-collapse:collapse; border-style:solid; border-color:#A3A3A3; border-width:1pt"> 
 <tbody> 
  <tr> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">1</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">2</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7166in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">3</span></p> </td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">4</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">5</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7166in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">6</span></p> </td> 
  </tr> 
 </tbody> 
</table>

<table style="direction:ltr; border-collapse:collapse; border-style:solid; border-color:#A3A3A3; border-width:1pt"> 
 <tbody> 
  <tr> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">1</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">2</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7166in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">4</span></p> </td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">3</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">5</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7166in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">6</span></p> </td> 
  </tr> 
 </tbody> 
</table>

<table style="direction:ltr; border-collapse:collapse; border-style:solid; border-color:#A3A3A3; border-width:1pt"> 
 <tbody> 
  <tr> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">1</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">3</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7166in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">5</span></p> </td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">2</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">4</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7166in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">6</span></p> </td> 
  </tr> 
 </tbody> 
</table>

<table style="direction:ltr; border-collapse:collapse; border-style:solid; border-color:#A3A3A3; border-width:1pt"> 
 <tbody> 
  <tr> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">1</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">3</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7166in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">4</span></p> </td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">2</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">5</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7166in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">6</span></p> </td> 
  </tr> 
 </tbody> 
</table>

<table style="direction:ltr; border-collapse:collapse; border-style:solid; border-color:#A3A3A3; border-width:1pt"> 
 <tbody> 
  <tr> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">1</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">3</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7166in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">5</span></p> </td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">2</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">4</span></p> </td> 
   <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7166in; padding:4pt 4pt 4pt 4pt"> <p style="margin:0in; font-family:Calibri"><span style="font-size:18px">6</span></p> </td> 
  </tr> 
 </tbody> 
</table>

编程任务：

给定正整数n，试计算tab(n)中2\*n二维表的个数。

参考代码：

全排列改进

该方法难于实现，因为当n值大于5以后，程序消耗的时间就会非常长。

#include<stdio.h>
    #include<stdlib.h>
    int *arr,n;
    long count=0l;
    void swap(int i,int j)
    {
    	int temp=arr[i];
    	arr[i]=arr[j];
    	arr[j]=temp;
    }
    int place()
    {
    	int i;
    	for(i=1;i<n;i++)
    		if(arr[i]<arr[i-1]||arr[i]>arr[i+n])
    			return 0;
    	for(++i;i<2*n;i++)
    		if(arr[i]<arr[i-1])
    			return 0;
    	return 1;
    }
    void print()
    {
    	int m;
    	count++;
    	for(m=0;m<n;m++)
    		printf("%3d\t",arr[m]);
    	putchar('\n');
    	for(;m<2*n;m++)
    		printf("%3d\t",arr[m]);
    	printf("\n***************************\n");
    }
    void perm(int start,int end){
    	if(start==end&&place())
    		print();
    	else{
    		for(int i=start;i<=end;i++)
    			if(start==i||(start!=i&&arr[start]!=arr[i])){//剔除重复项
    				swap(start,i);
    				perm(start+1,end);
    				swap(start,i);
    			}	
    	}
    }
    
    int main(){
    	int i,j;
    	scanf("%d",&n);
    	arr=(int*)malloc(sizeof(int)*n*2);
    	for(i=0;i<2*n;i++)
    		arr[i]=i+1;
    	if(n==1)
    		print();
    	else
    		perm(1,2*n-2);
    	printf("%ld\n",count);
    }

利用catalan数（卡特兰数）

catalan数性质：

令h(0)=1,h(1)=1，卡塔兰数数满足递归式：

h(n)= h(0)\*h(n-1) +h(1)\*h(n-2) + ... + h(n-1)h(0) (其中n>=2),这是n阶递推关系;

还可以化简为1阶递推关系:如h(n)=(4n-2)/(n+1)\*h(n-1)(n>1)  h(1)=h(0)=1

该递推关系的解为：h(n)=C(2n,n)/(n+1)=P(2n,n)/(n+1)!=(2n)!/(n!\*(n+1)!)(n=1,2,3,...)

卡塔兰数列的前几项为(sequence A 0 00 1 0 8 in OEIS) \[注： n = 0, 1, 2, 3, … n\]

1, 1, 2, 5, 14, 42, 132,429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670,129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640,343059613650, 1289904147324, 4861946401452, …

由于int、long型数据存储范围有限，所以该方法也只能计算出范围为n<=16的结果。

#include<stdio.h>
    
    long f(long n)
    {
    	if(n==1)
    		return 1;
    	else
    		return (4*n-2)*f(n-1)/(n+1);
    }
    int main()
    {
    	long n;
    	scanf("%ld",&n);
    	printf("%ld\n",f(n));
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关 mib文件构建，标量，一维表量，二维表量

Net-snmp安装开发流程: [Net-snmp安装开发流程\_cao849861802的博客-CSDN博客][Net-snmp_cao849861802_-CSDN]

雨点打透心脏的1/2处/ 2022年09月16日 04:51/ 0 赞/ 100 阅读

相关二维指针和二维数组

下面三种定义形式怎么理解？怎么动态分配空间？ (1)、int \\Ptr; (2)、int \Ptr\[ 5 \]; 我更喜欢写成 int\ P

柔情只为你懂/ 2022年08月04日 04:24/ 0 赞/ 253 阅读

相关标准二维表

问题描述：设n是一个正整数。2\n的标准二维表是由正整数1,2,…,2n组成的2\n数组，该数组的每行从左到右递增，每列从上到下递增。2\n的标准二维表全体记为tab

r囧r小猫/ 2022年08月02日 06:54/ 0 赞/ 157 阅读

相关二维数组的遍历并按标准格式输出

package day05; /\\ \ java基础:二维数组 \ Author:yangjishun \ Description:二维数组的遍历 \ Da

心已赠人/ 2022年06月07日 14:13/ 0 赞/ 152 阅读

相关 Python3将一维数组按标准长度分隔为二维数组

def trans_data_to_pair(self,data,index): contents=[ data

曾经终败给现在/ 2022年05月29日 08:38/ 0 赞/ 190 阅读

相关运维技能定级标准

本篇文章设计了运维部门岗位专业技能定级标准的一个总体框架。简述了该定级标准体系的设计方法论。以我的理解，有这样一套岗位专业技能定级标准，可以有以下三个好处：可以开拓

╰+攻爆jí腚メ/ 2022年04月23日 03:08/ 0 赞/ 609 阅读

相关 Python实现一维表与二维表之间的相互转化

对已有数据表进行一维和二维之间的转化： import pandas as pd 读入数据： df = pd.read_excel('2

野性酷女/ 2022年04月10日 13:55/ 0 赞/ 882 阅读

相关 EXCEL VBA 二维表转换成一维表

EXCEL VBA 二维表转换成一维表 Sub 按钮2_Click() Rem 初始化 Worksh

曾经终败给现在/ 2022年03月20日 16:10/ 0 赞/ 555 阅读

相关 EXCEL VBA 二维表转换成一维表

EXCEL VBA 二维表转换成一维表 Sub 按钮2_Click() Rem 初始化 Work

素颜马尾好姑娘i/ 2022年03月20日 16:08/ 0 赞/ 248 阅读

相关 Excel2016中二维表转一维表

Excel2016中将二维表转为一维表主要是使用office新版本中集成的“查询编辑器”工具 ![20200730165542533.png][] ![202007

水深无声/ 2021年07月25日 13:02/ 0 赞/ 388 阅读