当前位置: 代码迷 >> 综合 >> 1254: [蓝桥杯2015初赛]手链样式 JAVA
  详细解决方案

1254: [蓝桥杯2015初赛]手链样式 JAVA

热度:52   发布时间:2023-12-01 17:12:24.0

题目描述

小明有3颗红珊瑚,4颗白珊瑚,5颗黄玛瑙。
他想用它们串成一圈作为手链,送给女朋友。
现在小明想知道:如果考虑手链可以随意转动或翻转,一共有多少不同的组合样式?

输出格式

请你输出该整数。不要输出任何多余的内容或说明性的文字。

解题思路:       

        1,数学方法组合解决:利用组合公式,然后再排除掉翻转,移动的重复的组合次数,得出答案,网上有很多我就不再写出来了。

        2,编程解决,利用dfs得出所有排列的方式,然后利用str+str的方法去除圆排列的次数((45条消息) 如何判断字符串S1是不是字符串S的旋转字符串【S+S去重原理】_菜瓜变菜鸟-CSDN博客)最后得出答案1170

代码:

import java.util.ArrayList;public class Main {static int ans=0;public static void main(String[] args) {int[] color={3,4,5};ArrayList<String> list=new ArrayList();dfs(color,"",list,0);System.out.println(ans);}public static void dfs(int[] count,String str,ArrayList<String> list,int len){//截至条件if(len==12){//去重for (String c:list) {if(c.indexOf(str)!=-1) return;//查找子字符串,没有就返回-1,有就直接寻找下一个}StringBuffer ss=new StringBuffer(str+str);list.add(ss.toString());ss.reverse();list.add(ss.toString());ans++;return;}//候选节点for (int i = 0; i < 3; i++) {if(count[i]!=0){count[i]--;dfs(count,str+i,list,len+1);//str不用在后面回溯count[i]++;}}}
}