免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 来自减压群的猴子失足撞树枝

v6mm131(4744*****)  0:04:21
QQ截图20190220005942.jpg
2019-2-20 01:00

话说这题我初看时连题都没看懂,还以为有啥笑点,刚才突然明白了,题意大概就是要求 A、B、C 顺次排列,而且中间可能还有其他东西,其余的也一样,求排列个数,这样还是可以算嘀。

首先 H、I 的瓜葛少,自由些,先不管它们。
根据五条排列要求,可以排出 A~G 只有两种可能的排列:
G A B C D E F
G A B D C E F
然后再将 H、I 放进去,因 I 要在 C 前,H 在要 D 后,所以:
对于第一种排列,I 有 4 个位,H 有 3 个位;
对于第二种排列,I 有 5 个位,H 有 4 个位;
所以结果就是 4*3+5*4=32?不,还有一点容易漏掉。
注意第二种排列中 H、I 都可以放在 D C 之间,有 D H I C 和 D I H C 两种情况,因此需要再 +1。
所以结果是 33。

不过,这样的方法总感觉很笨,还容易漏,有没有更具一般性的计算方法?
又或者,如果用程序,比如 Mathematica,怎么编程把排列都列出来?
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
$\href{https://kuingggg.github.io/}{\text{About Me}}$

或許畫一個有向圖出來就可以完全沒有幫助地裝一次逼呢

$\begin{align*}
I\rightarrow & C\rightarrow E\rightarrow F\\
~ & \uparrow ~~~~~ \uparrow & ~\\
G\rightarrow A\rightarrow & B\rightarrow D\rightarrow H\\
\end{align*}$
1

评分人数

    • realnumber: 那I,G一样高呢?题目最后一行暗示? ...威望 + 1

TOP

用算法的话,这个问题的规模,用回溯法是小case.

这个问题的状态空间是一颗 (不完整的)排列树。

初始状态 0, 第一个分别选 A-H 得到 8个子状态,就像一颗树分的叉。不失一般性,我们考察子树 A.

A 已选,下一步可以选 B-H 7个中之一,于是这一层有7颗子树。 不失一般性,考察 子树 D.

A,D已经排好(前缀), 剩下可选的为{B,C,E,F,G,H} 6个之一,于是这一层有6颗子树。不是一般性,考察子树 B.

ADB里面,D在B前,不满足合法性,从这个分枝已经不可能得到合法的解,所以可以把这颗分枝剪去。这种剪枝叫合法性剪枝。还有一种称为最优性剪枝,对本问题并不适用。

B分枝剪掉,或考察完毕后,回溯到其父节点,即D节点,考察 C. 前缀 ADC, 剩下5个派生出 5颗子树...

注意到每层的子树数比上层少1,如果没有剪枝,其状态空间最底层有 $n!$ 个节点,正是 $n$ 个数的全排列。所以这种状态空间树称为排列树。

阶乘是一种非常可怕的增长方式,所以这个问题虽然好解,如果再增加10来个节点,剪枝又不够有效的话,问题就可能无法在有效时间内求解了。
1

评分人数

    • realnumber: 虽然不太懂,但大概了解点,谢谢高手 ...威望 + 1

TOP

回复 2# tommywong

是的,这是第一感。然后具体观察,G,A,B,C,D,E,F 仅有两种排法

1. GABCDEF

2. GABDCEF

现在只剩两个需要安排的,即 I,H.
1.I =4
1.H=3

2.I=5
2.H=4

综上 总排法 $4\times 3+5\times 4=32$

ps:
噢,漏了一种。觉得用纸笔应该就这样了。

TOP

回复 4# 业余的业余

这1#已经写过,最后果然很容易漏

TOP

  1. #include <iostream>

  2. const int n=9;

  3. int p[n]={'A','B','C','D','E','F','G','H','I'};

  4. int count;


  5. void output()
  6. {
  7.         for(int i=0; i<n; ++i)
  8.                 std::cout<<(char)p[i];
  9.         std::cout<<std::endl;
  10. }

  11. // hard-coded validity check
  12. bool is_valid(int t)
  13. {
  14.         // 可以构建一个map, 这里把逻辑硬编码
  15.         switch(p[t])
  16.         {
  17.         case 'A': // A 前不可有 B,C
  18.                 for(int i=0; i<t; ++i)
  19.                         if(p[i]=='B' || p[i]=='C')
  20.                                 return false;
  21.                 break;
  22.         case 'B':
  23.                 for(int i=0; i<t; ++i)
  24.                         if(p[i]=='D' || p[i]=='H' || p[i]=='C')
  25.                                 return false;
  26.                 break;
  27.         case 'C':
  28.                 for(int i=0; i<t; ++i)
  29.                         if(p[i]=='E')
  30.                                 return false;
  31.                 break;
  32.         case 'D':
  33.                 for(int i=0; i<t; ++i)
  34.                         if(p[i]=='E' || p[i]=='F' || p[i]=='H')
  35.                                 return false;
  36.                 break;
  37.         case 'E':
  38.                 for(int i=0; i<t; ++i)
  39.                         if(p[i]=='F')
  40.                                 return false;
  41.                 break;
  42.         //case 'F':
  43.         //        break;
  44.         case 'G':
  45.                 for(int i=0; i<t; ++i)
  46.                         if(p[i]=='A' || p[i]=='C')
  47.                                 return false;
  48.                 break;
  49.         //case 'H':
  50.         //        break;
  51.         case 'I':
  52.                 for(int i=0; i<t; ++i)
  53.                         if(p[i]=='E' || p[i]=='C')
  54.                                 return false;
  55.                 break;
  56.         }
  57.         return true;
  58.        
  59. }


  60. void backtrack(int t)
  61. {
  62.         if(t==n)
  63.         {
  64.                 ++count;
  65.                 output();
  66.         }
  67.         else
  68.                 for(int i=t; i<n; ++i)
  69.                 {
  70.                         std::swap(p[t],p[i]);
  71.                         if(is_valid(t))
  72.                                 backtrack(t+1);
  73.                         std::swap(p[t],p[i]);
  74.                 }
  75. }

  76. int main()
  77. {
  78.         backtrack(0);
  79.        
  80.         std::cout<<count<<std::endl;
  81.         return 0;
  82. }
复制代码
33 正确。第33中情形容易忽略,但程序没有盲点。

TOP

回复 5# kuing

思路一样,只是我的差之毫厘了

TOP

一个可以一样高的2346(应该远小于这个值,程序没编好),都不一样高的33,

var
a,b,c,d,e,f,g,h,i,k:longint;
begin
k:=0;
for a:=3 to 9 do
  for b:=3 to 9 do
    for c:=1 to 9 do
      for d:=1 to 9 do
        for e:=1 to 9 do
          for f:=1 to 9 do
            for g:=4 to 9 do
               for h:=1 to 9 do
                 for i:=3 to 9 do
                 if (a>b)and(b>c)and(d>e)and(e>f)and(g>a)and(a>c)and(b>d)and(d>h)and(i>c)and(c>e) then k:=k+1;
writeln(k);
end.


var
a,b,c,d,e,f,g,h,i,m:longint;
begin
m:=0;
for a:=1 to 9 do
  for b:=1 to 9 do
    for c:=1 to 9 do
      for d:=1 to 9 do
        for e:=1 to 9 do
          for f:=1 to 9 do
            for g:=1 to 9 do
               for h:=1 to 9 do
                 for i:=1 to 9 do
                 begin
                 if (a-d)*(a-e)*(a-f)*(a-h)*(a-i)*(b-e)*(b-f)=0 then continue;
                 if (b-g)*(b-i)*(c-d)*(c-f)*(c-h)*(d-g)*(d-i)*(e-g)=0 then continue;
                 if (e-h)*(e-i)*(f-g)*(f-h)*(f-i)*(g-h)*(g-i)*(h-i)=0 then continue;
                 if (a>b)and(b>c)and(d>e)and(e>f)and(g>a)and(a>c)and(b>d)and(d>h)and(i>c)and(c>e) then m:=m+1;
                 end;
writeln(m);
end.

TOP

回复 8# realnumber 都好6!orz

TOP

够狠!

TOP

回复 8# realnumber

谢谢

TOP

返回列表 回复 发帖