鱼C论坛

 找回密码
 立即注册
查看: 2536|回复: 6

C\C++数字排列问题

[复制链接]
发表于 2019-4-13 12:28:19 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
输入任意正整数n(n>=3),要求输出由1,1,2,2,3,3,......,n,n等2n个数组成的数列,使得:
    两个“1”之间有1个数
    两个“2”之间有2个数
    两个“3”之间有3个数
    ......
    两个“n”之间有n个数
    如输入3,则输出231213或312132

可能没有或者有多种排列方式,要求全部输出。

我能想到的唯一思路是将这2n个数字全排列,然后把不符合要求的排序剔除掉。虽然空间复杂度只有O(n),但这样的算法时间复杂度足足有O(n!),这显然是不可接受的。希望有大家能帮萌新解决一下这个问题。谢谢大家!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-4-13 16:00:23 | 显示全部楼层
我有一个思路,你可以参考下,比方说n=3,1[]1, 2()()2, 3{}{}{}3, 31[2](1)(3)2,成对出现去拼,n=4也同理41312432可以很快的拼出结果。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-4-13 16:07:14 | 显示全部楼层
你可以弄一个字符串,然后写一个函数。
  1. void func(int n, string s){
  2. 找到s第一个空位,
  3. 放下数字n,
  4. 然后隔n个位置把n放下。
  5. 如果该位置有数字,重新寻找第一位。
  6. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-4-14 10:19:15 | 显示全部楼层
千公子 发表于 2019-4-13 16:07
你可以弄一个字符串,然后写一个函数。

那这样的话是不是需要用到递归?先插入n,再插入n-1,一直到最后插入1?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-4-14 15:41:51 | 显示全部楼层
Swarm 发表于 2019-4-14 10:19
那这样的话是不是需要用到递归?先插入n,再插入n-1,一直到最后插入1?

都可以吧,但是需要回溯,也就是全排列的思想,只不过是成对的排,用这个思路应该就排除112233这种情况,
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-4-22 09:07:00 | 显示全部楼层
目前能够做到的就是这样……输入3和4都可以得到正确结果……
但当我输入5,的时候,本应该是没有结果,但是却告诉我程序运行出错……
应该有可能是内存溢出了?求大家帮忙看一下到底是怎么回事?
  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. #define Max 100
  4. int array[Max*2]={0};
  5. int visit[Max][Max*2]={0};

  6. typedef struct
  7. {
  8.         int no[Max];
  9.         int posi[Max*2];
  10.         int top;
  11. }Stack;





  12. void Inite(Stack *&s,int n)
  13. {
  14.         int i;
  15.         s=(Stack *)malloc(sizeof(Stack));
  16.         s->top=-1;
  17.         for(i=n*2;i<Max*2;i++)
  18.                 array[i]=-1;
  19. }





  20. void Destroy(Stack *&s)
  21. {
  22.         free(s);
  23. }





  24. void Push(Stack *&s,int i,int p)                //入栈,填数字,将visit[p]记为1
  25. {
  26.         //入栈常规操作
  27.         s->top++;
  28.         s->no[s->top]=i;
  29.         s->posi[s->top]=p;

  30.         //将数字放进数组里
  31.         array[p]=array[p+i+1]=i;

  32.         //这个位置i试过了
  33.         visit[i-1][p]=1;
  34. }





  35. void Pop(Stack *&s,int n)                                //出栈,数组恢复,重置visit
  36. {
  37.         int i,p;
  38.         int j,k;

  39.         //出栈常规操作
  40.         i=s->no[s->top];
  41.         p=s->posi[s->top];
  42.         s->top--;

  43.         //将数字从数组里取出
  44.         array[p]=array[p+i+1]=0;

  45.         //将出栈元素之前的所有元素的visit重置
  46.         for(k=0;k<i-1;k++)
  47.                 for(j=0;j<n*2;j++)
  48.                         visit[i-2][j]=0;
  49. }





  50. bool Empty(Stack *&s)
  51. {
  52.         return s->top==-1;
  53. }





  54. void PopAll(Stack *&s,int n)
  55. {
  56.         while(!Empty(s))
  57.                 Pop(s,n);
  58. }





  59. void Disp(int n)
  60. {
  61.         int i;
  62.         int p,q;
  63.         for(i=0;i<2*n;i++)
  64.         {
  65.                 printf("%d ",array[i]);
  66.         }
  67.         printf("\n");
  68.         for(p=0;p<n-1;p++)
  69.                 for(q=0;q<2*n;q++)
  70.                         visit[p][q]=0;
  71.         for(p=0;p<2*n;p++)
  72.                 array[p]=0;
  73. }





  74. void sort(Stack *&s,int n)
  75. {
  76.         int i=n,p,j;
  77.         int count=0;
  78.         while(1)
  79.         {
  80.                 for(i;i>0;i--)                                //i用于计数
  81.                 {
  82.                         for(p=0;p<2*n-i-1;p++)        //p用来定位
  83.                         {
  84.                                 if(array[p]==0 && array[p+i+1]==0 && visit[i-1][p]==0)//这个位置和间隔i个位置都有空而且这个位置以前没放过
  85.                                 {
  86.                                         Push(s,i,p);        //入栈,填数字,将visit[p]记为1
  87.                                         break;
  88.                                 }
  89.                         }
  90.                         if(p==2*n-i-1)                                //所有位置都试过一遍了
  91.                         {
  92.                                 Pop(s,n);                        //出栈,数组恢复,重置visit
  93.                                 i+=2;                                //重新排出栈的那个元素
  94.                         }
  95.                 }


  96.                 //判断是否要打印
  97.                 for(j=0;j<n*2;j++)
  98.                         if(array[j]==0)
  99.                                 goto next;
  100.                 Disp(n);
  101.                 i=n;
  102.                 PopAll(s,n);
  103.                 count++;


  104.                 //判断是否全都循环过一遍
  105. next:        for(j=0;j<n-1;j++)
  106.                         if(visit[n-1][j]==0)
  107.                                 goto end;
  108.                 break;
  109. end:        ;
  110.         }
  111.         if(count==0)
  112.                 printf("无\n");
  113. }





  114. int main()
  115. {
  116.         int n;
  117.         Stack *s;
  118.         printf("Input a number:( must more than 0 and less than 101 )\n");
  119.         scanf("%d",&n);
  120.         Inite(s,n);
  121.         sort(s,n);
  122.         Destroy(s);
  123.         return 0;
  124. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-18 01:08:45 | 显示全部楼层
本帖最后由 千公子 于 2019-5-18 01:10 编辑

我今天做题做到了这个,就写了代码!你可以参考下!
  1. 标题:扑克序列

  2.     A A 2 2 3 3 4 4, 一共4对扑克牌。请你把它们排成一行。
  3.     要求:两个A中间有1张牌,两个2之间有2张牌,两个3之间有3张牌,两个4之间有4张牌。

  4.     请填写出所有符合要求的排列中,字典序最小的那个。

  5. 例如:22AA3344 比 A2A23344 字典序小。当然,它们都不是满足要求的答案
复制代码

  1. #include <iostream>

  2. using namespace std;
  3. struct num {
  4.         int n;
  5.         char c;
  6. }A[4];

  7. //结果
  8. char arr[9];
  9. // 使用过的字符标记上
  10. bool used[4];
  11. // 已经使用的字符数
  12. int used_count = 0;
  13. // 递归次数
  14. int deep_num = 0;

  15. void init() {
  16.         for (int i = 0; i < 9; ++i) {
  17.                 arr[i] = '\0';
  18.                 if(i<4)
  19.                         used[i] = false;
  20.         }
  21. }
  22. void shift(int j) {
  23.         ++deep_num;
  24.         for (int i = j; i < 7; ++i) {

  25.                 for (int k = 0; k <= 3; ++k) {
  26.                         if (used[k]) continue;
  27.                         int nextidx = i + A[k].n;
  28.                         if (nextidx > 7) continue;
  29.                         // 找到合适位置
  30.                         if (arr[i] == '\0' && arr[nextidx] == '\0') {
  31.                                 arr[i] = A[k].c;
  32.                                 arr[nextidx] = A[k].c;
  33.                                 used_count += 1;
  34.                                 used[k] = true;

  35.                                 shift(j + 1);

  36.                                 arr[i] = '\0';
  37.                                 arr[nextidx] = '\0';
  38.                                 used_count -= 1;
  39.                                 used[k] = false;
  40.                         }
  41.                 }
  42.         }
  43.        
  44.         if(used_count==4)
  45.                 cout << arr << endl;
  46. }
  47. int main() {
  48.        
  49.         A[0].n = 2;
  50.         A[0].c = 'A';

  51.         A[1].n = 3;
  52.         A[1].c = '2';

  53.         A[2].n = 4;
  54.         A[2].c = '3';

  55.         A[3].n = 5;
  56.         A[3].c = '4';

  57.         init();
  58.         shift(0);
  59.         cout << deep_num << endl;
  60.         return 0;
  61. }
复制代码


思路还是上次和你说的思路!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 17:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表