思维100四年级练习题

bob_2024

一个字母串包含了 11 个字母（这 11 个字母排成一行），所有字母只能从 A、B、C 中选取（有些字母可以不出现，比如某个字母串只包含了 A、B 这两种字母）。要求任意三个相邻的字母不能相同，并且整个字母串是一个回文串，也就是说从左读到右和从右读到左是相同的字母串。不同的排法有________种。

这个题怎么解呢？

SimonYang

帮顶。紫薯紫薯

RuiCosta

怎么感觉题目有问题。

Caltrop

第六位6种第五位5种，再分第三位与第五位同和不同两种情况

guttag

回文，那么第五位和第七位应该一样，怎么任意三个相邻不能相同

来自安卓APP客户端

HKsg

染色问题？

来自安卓APP客户端

pklu

我只想到一个笨办法，分情况讨论。
因为是回文形式的字符串，所以后5个与前5个对称。因此只需考虑前6个字符串的排列组合。又由于是回文，所以第5个和第6个字符串不能相同。因此定下来前5个字符串，那么X2就能包含所有的情况。
前5个字符的选择只能是410,320,311,221。排列分别是1*6，(P5/P3*P2-3)*6,(P5/P3-6)*3,(P5/P2*P2)*3。
=（6+42+42+90）*2=360
我排列组合比较弱，不知道对不对。。。

不知道怎么打上下脚标，Px表示x的全排列

bob_2024

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Test {

        public static void main(String[] args) {
                List<String> chars = new ArrayList<>();
                chars.add("A");
                chars.add("B");
                chars.add("C");
                List<String> list = add("", chars, 1);
                List<String> result = new ArrayList<>();
                for (String temp : list) {
                        if (!invalid(temp)) {
                                result.add(temp);
                        }
                }
                System.out.println(result.size());
                for (String temp : result) {
                        System.out.println(temp);
                }
        }

        private static List<String> add(String str, List<String> chars, int index) {
                if (index > 6) {
                        return Collections.emptyList();
                }
                List<String> result = new ArrayList<>();
                for (String temp : chars) {
                        if (index == 6) {
                                result.add(str + temp);
                        } else {
                                result.addAll(add(str + temp, chars, index + 1));
                        }
                }
                return result;
        }

        public static boolean invalid(String str) {
                char previous = str.charAt(0);
                int duplicateCount = 1;
                for (int i = 1; i < str.length(); i++) {
                        char current = str.charAt(i);
                        if (current != previous) {
                                duplicateCount = 1;
                                previous = current;
                        } else {
                                duplicateCount++;
                                // 从头开始三位相同的排除
                                if (duplicateCount >= 3) {
                                        return true;
                                }
                        }
                }
                // 最后两位相同排除
                if (duplicateCount >= 2) {
                        return true;
                }
                return false;
        }

}

写了一个Java程序，先对6位进行全排列，再排除三个相同的和末两位相同的，答案是360。但是不知道怎么用排列组合来算。
360
AABAAB
AABAAC
AABABA
AABABC
AABACA
AABACB
AABBAB
AABBAC
AABBCA
AABBCB
AABCAB
AABCAC
AABCBA
AABCBC
AABCCA
...

vitem2009

3×2×(3^4-3×(1+2×2)-2×3)=360

pklu

vitem2009 发表于 2024-10-11 21:52
3×2×(3^4-3×(1+2×2)-2×3)=360

简洁，牛啊

bob_2024

vitem2009 发表于 2024-10-11 21:52
3×2×(3^4-3×(1+2×2)-2×3)=360

能说明一下排除的计算思路吗？

vitem2009

pklu 发表于 2024-10-12 08:56
简洁，牛啊

惭愧惭愧。

vitem2009

bob_2024 发表于 2024-10-12 13:19
能说明一下排除的计算思路吗？

不妨固定中间为A，A的邻居为B，之后半边剩4个。这4个，只需从所有可能中去掉恰有3个一样的，去掉恰有4个一样的，去掉恰有两个BB开头的。

bob_2024

谢谢！根据你的思路，整理如下：
从左到右依次标记为： 1  2  3  4  5  6

第一步，排第6位，有3种
第二步，排第5位，只能从剩下两个里面选，有2种
第三步，排1~4位，全排列有3*3*3*3种，需要排除掉以下情况：
     1. 只有3、4位与5位一样，有第1位的2种*第2位的2种*第3位的3种
     2. 只有2、3、4或只有1、2、3连续3位一样，有3*2种
     3. 1、2、3、4都一样，有3种
所以，总数为 3*2*( 3*3*3*3 - 2*2*3 - 3*2 - 3 ) = 360

托尼哥哥

这是四年级的题啊？。。

Runner

谢谢分享。