429
小猴爬台階問題
小猴爬台階問題：
有一隻小猴很頑皮，喜歡爬台階，但由於小猴太小，所以它隻能一步爬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>());
}
}
}
最後更新：2017-04-03 05:38:56