数学研发论坛

 找回密码
 欢迎注册
查看: 441|回复: 20

[讨论] 排队问题

[复制链接]
发表于 2020-10-28 08:20:33 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
有24个高低不同的同学,现要排成三行,每一行从左到右由低到高,每一列从前到后也是由低到高。有多少种排法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-28 09:04:29 来自手机 | 显示全部楼层
应该是3192727797

点评

什么方法  发表于 2020-10-28 10:33
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-28 10:22:02 | 显示全部楼层
每行人数相同还是允许不同?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-10-28 10:57:42 | 显示全部楼层
northwolves 发表于 2020-10-28 10:22
每行人数相同还是允许不同?

每行人数相同啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-10-28 11:09:06 | 显示全部楼层

除了暴力枚举法,还有什么简单算法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-28 12:00:41 来自手机 | 显示全部楼层
动态规划
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2020-10-28 12:03:29 来自手机 | 显示全部楼层
将24个人依次从低到高排好位置,按前k个人使用掉的位置集合进行分类(不区分每个人的具体位置),递推各分类的人数即可
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-10-28 12:22:10 | 显示全部楼层
mathe 发表于 2020-10-28 12:03
将24个人依次从低到高排好位置,按前k个人使用掉的位置集合进行分类(不区分每个人的具体位置),递推各分类 ...

能写出DP公式吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-28 12:35:00 | 显示全部楼层

  1. #include <map>
  2. using namespace std;
  3. typedef struct _PC{
  4.     char cnt[3];
  5.     bool operator<(const struct _PC& x)const{
  6.         int i;
  7.         for(i=0;i<3;i++){
  8.             if(cnt[i]<x.cnt[i])return true;
  9.             if(cnt[i]>x.cnt[i])return false;
  10.         }
  11.         return false;
  12.     }
  13.     bool operator==(const struct _PC& x)const{
  14.         int i;
  15.         for(i=0;i<3;i++){
  16.             if(cnt[i]!=x.cnt[i])return false;
  17.         }
  18.         return true;
  19.     }
  20. }PC;

  21. typedef map<PC, long> PCMAP;

  22. PCMAP pcmap0, pcmap1;
  23. void add_data(PCMAP *next_map, const PC& data, long count)
  24. {
  25.     PCMAP::iterator it = next_map->find(data);
  26.     if(it==next_map->end()){
  27.         next_map->insert(std::make_pair(data, count));
  28.     }else{
  29.         it->second+=count;
  30.         if(it->second<0L){
  31.                 printf("overflow\n");
  32.         }
  33.     }
  34. }

  35. #define N 8
  36. int main()
  37. {
  38.     PCMAP *prev, *next, *tmp;
  39.     int i;
  40.     prev=&pcmap0;
  41.     next=&pcmap1;
  42.     PC pc;
  43.     pc.cnt[0]=1;pc.cnt[1]=pc.cnt[2]=0;
  44.     prev->insert(std::make_pair(pc, 1L));
  45.     for(i=2;i<=3*N;i++){
  46.         next->clear();
  47.         PCMAP::iterator it;
  48.         for(it=prev->begin();it!=prev->end();++it){
  49.             const PC& orig = it->first;
  50.             PC update = orig;
  51.             if(update.cnt[0]<N){
  52.                update.cnt[0]++;
  53.                add_data(next, update, it->second);
  54.             }
  55.             if(orig.cnt[0]>orig.cnt[1]){
  56.                 update=orig;
  57.                 update.cnt[1]++;
  58.                 add_data(next,update, it->second);
  59.             }
  60.             if(orig.cnt[1]>orig.cnt[2]){
  61.                 update=orig;
  62.                 update.cnt[2]++;
  63.                 add_data(next,update, it->second);
  64.             }
  65.         }
  66.         tmp=prev;
  67.         prev=next;
  68.         next=tmp;
  69.     }
  70.     long sum = 0;
  71.     PCMAP::iterator it;
  72.     for(it=prev->begin();it!=prev->end();++it){ sum+=it->second;}
  73.     printf("Total %ld\n",sum);
  74. }

复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-10-28 12:49:34 | 显示全部楼层
进而推到一般情况,m行n列,求通项公式F(m,n).显然有F(m,n)=F(n,m)。F(1,n)=F(n,1)=1,F(2,n)=F(n,2)=C(2n,n)/(n+1)  (卡特兰数)
F(3,n)=?
F(m,n)=?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-12-3 21:23 , Processed in 0.074795 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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