Algorithms-Part1
Recursion.java
package tiei.aads.recursion;import java.util.*;/*** A class for practicing recursion*/
public class Recursion {/ printing binary words/*** Print out all binary words of length k*/public static void binary(int k) {for (int i = 0; i < Math.pow(2, k); i++) {StringBuffer str = new StringBuffer(Integer.toBinaryString(i));while (str.length() < k) {str.insert(0, "0");}System.out.print(str + " ");}}/// printing A-B wordspublic static String listToString(List<Character> list) {StringBuilder sb = new StringBuilder();for (Character ch : list) {sb.append(ch);}return sb.toString();}public static Set<String> fullPermutations(Set<String> set, List<Character> cur, boolean[] used, char[] word) {if (cur.size() == word.length) {// 使用 listToString 方法将当前排列转为字符串并添加到 set 中set.add(listToString(cur));return set;}for (int i = 0; i < word.length; i++) {if (!used[i]) {used[i] = true;cur.add(word[i]);fullPermutations(set, cur, used, word);// 回溯cur.remove(cur.size() - 1);used[i] = false;}}return set;}/*** Print out all words made of* x letters 'A' and y letters 'B'*/public static void words(int x, int y) {char[] word = new char[x + y];for (int i = 0; i < x; i++) {word[i] = 'A';}for (int j = x; j < x + y; j++) {word[j] = 'B';}// 输出nums的全排列// 使用 Set 来存储去重后的排列Set<String> set = new HashSet<>();List<Character> cur = new ArrayList<>();boolean[] used = new boolean[x + y];Set<String> res = fullPermutations(set, cur, used, word);for (String permutation : res) {System.out.println(permutation);}}/ printing all permutations of { 1, 2, ..., n }/*** Print out all permutations of* (1, 2, 3, ..., n)*/public static void fullPermutations(List<List<Integer>> list, List<Integer> cur, boolean[] used, int[] nums) {if (cur.size() == nums.length) {System.out.println(cur);list.add(cur);return;}for (int i = 0; i < nums.length; i++) {if (!used[i]) {used[i] = true;cur.add(nums[i]);fullPermutations(list, cur, used, nums);// 回溯cur.remove(cur.size() - 1);used[i] = false;}}}public static void permutations(int n) {int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = i + 1;}// 输出nums的全排列List<List<Integer>> list = new ArrayList<>();List<Integer> cur = new ArrayList<>();boolean[] used = new boolean[n];fullPermutations(list, cur, used, nums);}/ checks if a given value can be found by summing up items in an array/*** Check if N can be found by adding* some values taken inside A*/public static int sumArray(List<Integer> a) {int sum = 0;for (int i = 0; i < a.size(); i++) {sum += a.get(i);}return sum;}public static boolean sum(int[] A, int N) {List<List<Integer>> list = new ArrayList<>();list.add(new ArrayList<>());for (int i = 0; i < A.length; i++) {int num = A[i];int len = list.size();for (int j = 0; j < len; j++) {List<Integer> l = new ArrayList<>(list.get(j));l.add(num);list.add(l);}}for (List<Integer> l : list) {
// System.out.println(l);if (N == sumArray(l)) return true;}return false;}////*** A short main for quick testing. For more testing* run the class TestRecursion*/public static void main(String[] args) {binary(3);System.out.println();System.out.println();words(2, 3);System.out.println();System.out.println();permutations(3);System.out.println();System.out.println();int[] A = {3, 5, 7, 11};if (sum(A, 21))System.out.println("sum(A,21) is true");elseSystem.out.println("sum(A,21) is false");if (sum(A, 13))System.out.println("sum(A,13) is true");elseSystem.out.println("sum(A,13) is false");}// expected output://// 000 001 010 011 100 101 110 111//// AABBB ABABB ABBAB ABBBA BAABB BABAB BABBA BBAAB BBABA BBBAA//// (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)//// sum(A,21) is true// sum(A,13) is false
}下面是 Test 代码：
TestClass.java
package tiei.aads.util;import java.lang.reflect.*;
import java.util.*;/*** A class for interactive class testing*/
public abstract class TestClass<C> {private Object x;private Scanner input;private static final String prompt = ">>>>> ";public TestClass() {input = new Scanner(System.in);}private void writeln(String s) {System.out.println(prompt + s);}final private void afficherTitre(String s) {writeln("");writeln(s);writeln("");}final private void executer(Method m, String n, Class<?> c) {Object[] args = new Object[0];try {m.invoke(x,args);}catch ( IllegalAccessException iae ) {writeln("cannot make an instance");}catch ( IllegalArgumentException iarge ) {writeln("problem with arguments");}catch ( InvocationTargetException ite ) {writeln("the method " + n + " raised exception: " + ite.getTargetException());printStack(ite.getStackTrace());}catch ( NullPointerException npe ) {writeln("bad instanciation");}}private String[] lesMethodes(Class<?> laClasse) {TreeSet<String> v = new TreeSet<String>();Method[] m = null;try {m = laClasse.getDeclaredMethods();for ( int i = 0; i < m.length; i++ ) {Class<?>[] pt = m[i].getParameterTypes();Class<?> rt = m[i].getReturnType();if ( pt.length == 0 && rt.getName().equals("void") && Modifier.isPublic(m[i].getModifiers()) )v.add(m[i].getName());}}catch ( Exception e ) {}String[] s = new String[v.size()];int i = 0;for ( Iterator<String> it = v.iterator(); it.hasNext(); )s[i++] = it.next();return s;}private void dispo(String[] les_methodes) {if ( les_methodes.length == 0 )writeln("no test method found!");else {writeln("available methods are: ");writeln("");writeln((String) les_methodes[0]);for ( int i = 1; i < les_methodes.length; i++ )writeln((String) les_methodes[i]);writeln("");}}private String readString(String prompt) {System.out.println(prompt);return input.nextLine();}final protected void tester() {x = this;Class<?> laClasse = x.getClass();Method methode = null;Class<?>[] args = new Class[0];String nom = "";String fin = "q";String[] les_methodes = lesMethodes(laClasse);afficherTitre("Testing " + laClasse.getName());dispo(les_methodes);nom = readString(prompt + "method to test ('q' to quit) : ");while ( ! nom.equals(fin) ) {if ( nom.length() == 0 )dispo(les_methodes);else try {methode = laClasse.getMethod(nom,args);if ( methode.getReturnType().getName().equals("void") ) {executer(methode,nom,laClasse);}else {writeln("the return type of " + nom + " is not void");}}catch ( SecurityException se ) {writeln("no method found");}catch ( NoSuchMethodException nsme ) {writeln("unknown method: " + nom);}nom = readString(prompt + "name of the method to test ('q' to quit) : ");}}private void printStack(StackTraceElement[] ste) {for ( int i = 0; i < ste.length; i++ ) {writeln(ste[i].toString());}}
}TestRecusion.java
package tiei.aads.recursion;import tiei.aads.util.TestClass;
import java.util.Scanner;/*** A class for interactive testing recursive methods from class Recursion*/
public class TestRecursion extends TestClass<TestRecursion> {private Scanner input;public TestRecursion() {input = new Scanner(System.in);}public void binary() {System.out.print("how many digits ? ");int d = input.nextInt();Recursion.binary(d);System.out.println();}public void words() {System.out.print("how many 'A' ? ");int a = input.nextInt();System.out.print("how many 'B' ? ");int b = input.nextInt();Recursion.words(a, b);System.out.println();}public void permutations() {System.out.print("size of the permutation ? ");int n = input.nextInt();Recursion.permutations(n);System.out.println();}public void sum() {System.out.print("size of the array ? ");int n = input.nextInt();int[] A = new int[n];for ( int i = 0; i < A.length; i++ ) {System.out.print("integer #" + (i + 1) + " ? ");A[i] = input.nextInt();}System.out.print("the sum to make ? ");int N = input.nextInt();if ( Recursion.sum(A, N) )System.out.println("you can make " + N + " from these values!");elseSystem.out.println("impossible to make " + N + " from these values");}public static void main(String[] args) {TestRecursion test = new TestRecursion();test.tester();}
}完整题目
