首页 > 代码库 > 小猴爬台阶问题
小猴爬台阶问题
小猴爬台阶问题:
有一仅仅小猴非常顽皮,喜欢爬台阶,但因为小猴太小,所以它仅仅能一步爬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>()); } } }
小猴爬台阶问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。