用 A,B,C,D,E 五色给 1,2,3 三个区域涂色，相邻区域不能同色，共有几种涂色方法？

luyuanhong

这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子，

欢迎大家一起来想想如何解答：

luyuanhong

天山草@

我用编程的方法做，答案跟陆教授的一样。
编程思路如下——
由五种颜色涂□□□□□的中间三个格子，其中最左（第一格）和最右（第五格）已涂好色（五色中的两种）。
现在要涂中间三个格子，相邻格子颜色不能相同，但是颜色可以重复使用。问：有几种不同的涂法？
     用 1、2、3、4、5 代表五种颜色。假定第一格已涂有颜色 1，第五格已涂有颜色 3。
     用 1、2、3、4、5 填在五个格子中，如果不限制条件，最小的数是 11111，最大的是 55555。
     从上面所有的数字中选出符合要求的，即高位数是 1，最低位是 3，相邻位数字都不一样。


VB 程序如下：

Private Sub form_Click()
     Open "共有几种涂色方法.txt" For Output As #1
     Dim x, a As String
   
     m = 5   '五位数
     x = 11111
     n = 0
     For i = 1 To 1000000000 '实际上达不到这么多循环。
         x = x + 1        '从最小的数字开始依次加 1，把不符合要求的去掉，符合要求者写入文件。
        For j = m To 2 Step -1 '将字符串变换成“五进制”串(由1，2，3，4，5 组成，不是由 0，1，2，3，4 组成)
         If Mid(x, j, 1) = 6 Then
           Mid(x, j, 1) = 1      '本位减 4 变为 1
           Mid(x, j - 1, 1) = 1 + Mid(x, j - 1, 1)   '前位加上进位 1
         End If
        Next j
        
         a = Val(x)
                 
        If Mid(a, 1, 1) = 2 Then GoTo 999 '控制结束的语句，最高位变成 2，则结束运行。
                 
     
         '以下筛选出不符合要求的字串：
        If Mid(a, 1, 1) <> 1 Then GoTo 222   '第一格不等于 1 的不要。
        If Mid(a, 5, 1) <> 3 Then GoTo 222   '第五格不等于 3 的不要。
        If Mid(a, 1, 1) = Mid(a, 2, 1) Then GoTo 222  '第一格与第二格相等的不要。
        If Mid(a, 2, 1) = Mid(a, 3, 1) Then GoTo 222  '第二格与第三格相等的不要。
        If Mid(a, 3, 1) = Mid(a, 4, 1) Then GoTo 222  '第三格与第四格相等的不要。
        If Mid(a, 4, 1) = Mid(a, 5, 1) Then GoTo 222  '第四格与第五格相等的不要。
              
      n = n + 1
      Print n; "=>"; Trim(a)
      Print #1, n; "=>"; Trim(a)
      
222:  Next i
999:  Print #1, " n ="; n
      Close
      End Sub
   
程序运行时间小于 1 秒，运行结果是：

1 =>12123
2 =>12143
3 =>12153
4 =>12313
5 =>12323
6 =>12343
7 =>12353
8 =>12413
9 =>12423
10 =>12453
11 =>12513
12 =>12523
13 =>12543
14 =>13123
15 =>13143
16 =>13153
17 =>13213
18 =>13243
19 =>13253
20 =>13413
21 =>13423
22 =>13453
23 =>13513
24 =>13523
25 =>13543
26 =>14123
27 =>14143
28 =>14153
29 =>14213
30 =>14243
31 =>14253
32 =>14313
33 =>14323
34 =>14343
35 =>14353
36 =>14513
37 =>14523
38 =>14543
39 =>15123
40 =>15143
41 =>15153
42 =>15213
43 =>15243
44 =>15253
45 =>15313
46 =>15323
47 =>15343
48 =>15353
49 =>15413
50 =>15423
51 =>15453
n = 51

   

   

天山草@

说明一下，上面的程序运行时间是一瞬间，如果时间很长，可以将程序再优化，就是把五位数改成三位数，从 212 到 545。

程序如下——
Private Sub form_Click()
     Open "共有几种涂色方法.txt" For Output As #1
     Dim x, a As String
   
     m = 3   '三位数（不是三进制！）
     x = 210 '最小数减 1
     n = 0
     For i = 1 To 1000000000 '实际上达不到这么多循环。
         x = x + 1        '从最小的数字开始依次加 1，把不符合要求的去掉，符合要求者写入文件。
        For j = m To 2 Step -1 '将字符串变换成“五进制”串组成的三位数(其中的数字由 1，2，3，4，5 组成，而非 0，1，2，3，4 组成)
         If Mid(x, j, 1) = 6 Then
           Mid(x, j, 1) = 1      '本位减 4 变为 1
           Mid(x, j - 1, 1) = 1 + Mid(x, j - 1, 1)   '前位加上进位 1
         End If
        Next j
        
         a = Val(x)
     
         '以下筛选出不符合要求的字串：
        If Mid(a, 1, 1) = Mid(a, 2, 1) Then GoTo 222  '第二格与第三格相等的不要。
        If Mid(a, 2, 1) = Mid(a, 3, 1) Then GoTo 222  '第三格与第四格相等的不要。
        If Mid(a, 3, 1) = 3 Then GoTo 222   '第四格为 3 的不要。
                     
      n = n + 1
      Print n; "=>"; "1" + Trim(a) + "3"
      Print #1, n; "=>"; "1" + Trim(a) + "3"
      
      If Mid(a, 1, 1) = 5 And Mid(a, 2, 1) = 4 And Mid(a, 3, 1) = 5 Then GoTo 999 '控制结束的语句。
                    
222:  Next i
999:  Print #1, " n ="; n
      Close
      End Sub

运行结果同上。

王守恩

此题等同“三位数“：
1，百位数字是1,2,3,4，个位数字是2,3,4,5，共4×4=16种可能。
     其中百位数字与个位数字相同的3种，百位数字与个位数字不同的13种，
2，百位数字与个位数字相同的，十位数字是1,2,3,4,5中的4种，计4×3，
     百位数字与个位数字不同的，十位数字是1,2,3,4,5中的3种，计3×13，
3，合计：4×3+3×13=51。

天山草@

现在中国大力研究发展人工智能了，我想智能机器人很适合做这一类题目。

luyuanhong

谢谢楼上 天山草 和 王守恩 的解答。

我已将帖子转贴到“陆老师的《数学中国》园地”。