小猴爬台阶问题:
有一只小猴很顽皮,喜欢爬台阶,但由于小猴太小,所以它只能一步爬1个或2个台阶。请计算该小猴所有可能的爬行路径。
package shuai.study.steps;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
/**
* @author shengshu
*
*/
public class MonkeyCrawl {
// Get paths, which will be permutated
public static Set<String> getPathsSet(int steps) {
Set<String> pathsSet = new HashSet<String>();
for (int i = 0; i <= steps / 2; i++) {
int twoStepSum = i * 2;
int oneStepTimes = steps - twoStepSum;
StringBuffer pathStringBuffer = new StringBuffer();
for (int x = 0; x < oneStepTimes; x++) {
// "-" represent one step
pathStringBuffer.append("-");
}
for (int y = 0; y < i; y++) {
// "=" represent two steps
pathStringBuffer.append("=");
}
pathsSet.add(pathStringBuffer.toString());
}
return pathsSet;
}
// Permutate all possible paths
public static void permutatePaths(String path, List<String> list) {
if (path.length() == 1) {
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i));
}
System.out.println(path);
} else {
int index[] = new int[path.length()];
for (int i = 0; i < index.length; i++) {
index[i] = path.indexOf(path.charAt(i));
}
for (int i = 0; i < path.length(); i++) {
String subPath = path.substring(1, path.length());
if (i == index[i]) {
list.add("" + path.charAt(0));
permutatePaths(subPath, list);
list.remove(list.size() - 1);
}
path = subPath + path.charAt(0);
}
}
}
public static void main(String[] args) {
// Set steps as 15, or others
Set<String> pathsSet = MonkeyCrawl.getPathsSet(15);
Iterator<String> iterator = pathsSet.iterator();
while (iterator.hasNext()) {
String path = iterator.next();
MonkeyCrawl.permutatePaths(path, new ArrayList<String>());
}
}
}
分享到:
相关推荐
中班体育教案:小猴爬.doc
幼儿园教案2021-中班体育教案:小猴爬.doc
c语言枚举算法的标程,你啊,一定要下啊 拜托了哈哈哈
全国信息奥林匹克竞赛noip2008试题--笨小猴参考程序
小班语言小猴请客PPT课件.pptx
油小猴工具箱 - 上网神器 1.8.1.crx
语言小猴请客PPT课件.pptx
小学数学数学故事自作聪明的小猴v
看图写话知错的小猴作文.doc
Scratch小猴数草莓 Scratch四级真题 小猴摘了一筐草莓,它拿出来数一数有多少颗。第一行放1颗,第二行放2颗,第三行放3颗,第四行放4颗,第五行放5颗。一边摆一边数,最后,说出草莓的总数。 视频演示可以观看:...
中班韵律音乐教案:猴子爬树.doc
语言小猴的出租车PPT课件.pptx
笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大! 这种方法的具体描述如下:假设maxn是单词中出现次数最多的字母的出现...
学习软件
2021年幼儿园大班体育教案《小猴运桃》.pdf
大班语言七只小猴去旅行教案反思.docx
2021年《小猴分桃子》幼儿园小班体育课教案.pdf
小猴与香蕉.cpp
可爱的小猴作文.doc