2道练习题难倒我了,求助

整数的分划问题。 
如，对于正整数n=6，可以分划为： 
6 
5+1 
4+2, 4+1+1 
3+3, 3+2+1, 3+1+1+1 
2+2+2, 2+2+1+1, 2+1+1+1+1 
1+1+1+1+1+1+1 
现在的问题是，对于给定的正整数n,编写算法打印所有划分。
用户从键盘输入 n （范围1~10）
程序输出该整数的所有划分。

在一个a.txt文件中，放入一下字符串：
a       34
aa      36
aaa     28
ab      17
aab     12
bc      13
bbc     25
cd      20
ccd     18
要求输入一个字符串，输出所有可以用以上字符串组合而成的组合形式，并在其后输出其数字相加之和，如果没有，则不输出。
  例如输入：aaabc
      输出：a aa bc 83
            aa a bc 83
            aaa bc 41
            a a a bc 115
            等

23 个解决方案

#1

第一题 递归？
第二题 回溯？

#2

第一道题可以参考下面的：
http://topic.csdn.net/u/20110426/19/FE639810-7C70-47A4-90DC-B39756747934.html

#3

http://topic.csdn.net/u/20110426/19/FE639810-7C70-47A4-90DC-B39756747934.html
楼主可以看看这里的！

#4

发现不会写递归了....嗯晚上大脑死锁了，明早再玩

#5

第二题：

import java.io.RandomAccessFile;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class stringUnion {

	public static List<List<String>> get(List<String> sl, String s) {
		List<List<String>> result = new ArrayList<List<String>>();
		List<List<String>> subresult;
		List<String> r;
		for (int i=0; i<sl.size(); i++) {
			if (s.indexOf(sl.get(i)) == 0) {
				if (s.length() == sl.get(i).length()) {
					r = new ArrayList<String>();
					r.add(sl.get(i));
					result.add(r);
				} else {
					subresult = get(sl,s.substring(sl.get(i).length()));
					for (int j=0; j<subresult.size(); j++) {
						r = new ArrayList<String>();
						r.add(sl.get(i));
						r.addAll(subresult.get(j));
						result.add(r);
					}
				}
			}
		}
		return result;
	}

	public static void main(String[] args) {
		try {
		HashMap<String,Integer> map = new HashMap<String,Integer>();
		ArrayList<String> ss = new ArrayList<String>();
		RandomAccessFile raf = new RandomAccessFile("d://testin.txt", "r");
		String inputline;
		while ((inputline=raf.readLine())!=null) {
			String[] input = inputline.split("\\s");
			if (input.length == 2) {
				map.put(input[0], Integer.parseInt(input[1]));
				ss.add(input[0]);
			}
		}
		raf.close();
		System.out.println("请输入一个字符串：");
		byte[] bs = new byte[20];
		byte b;
		int c=0;
		while(c<bs.length && (b=(byte)System.in.read())!= 13) bs[c++] = b;
		String s = new String(bs, 0, c);
		List<List<String>> result = get(ss,s);

		for (int i=0; i<result.size(); i++) {
			c = 0;
			for (int j=0; j<result.get(i).size(); j++) {
				System.out.print(result.get(i).get(j) + " ");
				c += map.get(result.get(i).get(j));
			}
			System.out.println(c);
		}
		} catch (Exception e) {System.out.println(e);}
	}

}

#6

一个一个来
问题1

import java.util.*;
public class Qs {
    public static void main(String[] args) {
        question1();
    }


    public static void question1() {
        try {
            Scanner sc = new Scanner(System.in);
            System.out.print("please input a number:");
            int sum = sc.nextInt();
            for (int i=2; i<=sum; i++) {
                divNum(sum, i);
            }
        } catch (Throwable e) {
            e.printStackTrace();
        }        
    }

    public static void divNum(int sum, int n) {
        int tmp = 0;
        int[] idx = new int[n];
        for (int i=0; i<n-1; i++) {
            idx[i] = 1;
            tmp += idx[i];
            System.out.printf("%d+", idx[i]);
        }
        idx[n-1] = sum-tmp;
        System.out.printf("%d=%d\r\n", idx[n-1], sum);

        while (true) {
            idx[n-2]++;
            for (int i=n-2; i>0; i--) {
                tmp = 0;
                for (int j=0; j<i; j++) {tmp+=idx[j];}
                if (idx[i] > (sum-tmp)/(n-i)) {
                    idx[i-1]++;
                }
            }
            if (idx[0] > sum/n) {break;}
            tmp = 0;
            for (int i=1; i<n-1; i++) {
                tmp += idx[i-1];
                if (idx[i] > (sum-tmp)/(n-i)) {
                    idx[i] = idx[i-1];
                }
            }
            tmp = 0;
            for (int i=0; i<n-1; i++) {
               tmp += idx[i];
               System.out.printf("%d+", idx[i]);
            }
            idx[n-1] = sum-tmp;
            System.out.printf("%d=%d\r\n", idx[n-1], sum);
        }
    }
}

#7

第2问

import java.util.*;
import java.io.*;
public class Qs {
    public static void main(String[] args) {
        //question1();
        question2();
    }


    public static void question1() {
        try {
            Scanner sc = new Scanner(System.in);
            System.out.print("please input a number:");
            int sum = sc.nextInt();
            for (int i=2; i<=sum; i++) {
                divNum(sum, i);
            }
        } catch (Throwable e) {
            e.printStackTrace();
        }        
    }

    public static void divNum(int sum, int n) {
        int tmp = 0;
        int[] idx = new int[n];
        for (int i=0; i<n-1; i++) {
            idx[i] = 1;
            tmp += idx[i];
            System.out.printf("%d+", idx[i]);
        }
        idx[n-1] = sum-tmp;
        System.out.printf("%d=%d\r\n", idx[n-1], sum);

        while (true) {
            idx[n-2]++;
            for (int i=n-2; i>0; i--) {
                tmp = 0;
                for (int j=0; j<i; j++) {tmp+=idx[j];}
                if (idx[i] > (sum-tmp)/(n-i)) {
                    idx[i-1]++;
                }
            }
            if (idx[0] > sum/n) {break;}
            tmp = 0;
            for (int i=1; i<n-1; i++) {
                tmp += idx[i-1];
                if (idx[i] > (sum-tmp)/(n-i)) {
                    idx[i] = idx[i-1];
                }
            }
            tmp = 0;
            for (int i=0; i<n-1; i++) {
               tmp += idx[i];
               System.out.printf("%d+", idx[i]);
            }
            idx[n-1] = sum-tmp;
            System.out.printf("%d=%d\r\n", idx[n-1], sum);
        }
    }

    public static void question2() {
        try {
            BufferedReader br = new BufferedReader(new FileReader("data.txt"));
            Map<String, Integer> map = new HashMap<String, Integer>();
            String buf;
            while ((buf=br.readLine()) != null) {
                String[] ss = buf.split("\\s+");
                map.put(ss[0], Integer.valueOf(ss[1]));  
            }
            br.close();
            Scanner sc = new Scanner(System.in);
            System.out.print("please input a string:");
            buf = sc.nextLine();
            List<List<String>> list = divString(buf, map);
            if (list.size() == 0) {
                System.out.println("no combinations.");
            } else {
                for (List<String> l : list) {
                    int sum = 0;
                    for (String s : l) {
                        System.out.printf("%s ", s);
                        sum += map.get(s);
                    }
                    System.out.printf("%d\n", sum);
                 }
            }
        } catch (Throwable e) {
            e.printStackTrace();
        }
    }

    public static List<List<String>> divString(String buf, Map<String, Integer> map) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (buf.length() == 1) {
            if (map.containsKey(buf)) {
                List<String> list = new ArrayList<String>();
                result.add(list);
            }
            return result;
        }

        for (int i=0; i<buf.length()-1; i++) {
            for (int j=i+1; j<buf.length(); j++) {
                if (map.containsKey(buf.substring(i, j))) {
                    if (map.containsKey(buf.substring(j))) {
                        List<String> list = new ArrayList<String>();
                        list.add(buf.substring(i, j));
                        list.add(buf.substring(j));
                        result.add(list);
                    } else {
                        List<List<String>> list = divString(buf.substring(j), map);
                        if (list.size() == 0) {
                            List<String> l = new ArrayList<String>();
                            l.add(buf.substring(i, j));
                            result.add(l);
                        } else {
                            for (List<String> l : list) {
                                l.add(0, buf.substring(i, j));
                                result.add(l);
                            }
                        }
                        
                    }
                }
            }
        }
        return result;
    }
}

#8

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

public class Test {
	private static Map<String,Integer> result = new TreeMap<String, Integer>();

	public static void main(String[] args) throws IOException {
		Scanner input = new Scanner(System.in);
		System.out.println("请输入一个字符串:");
		String str = input.next();
		Set<String> set = combination(str, read());
		for(String s : set) {
			System.out.println(s);
		}
	}

	/**
	 * 读取文件内容，存入map中
	 * @return
	 * @throws IOException
	 */
	private static Map<String,Integer> read() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("a.txt")));
		Map<String,Integer> map = new TreeMap<String,Integer>();
		String str;
		while((str = br.readLine()) != null) {
			String[] temp = str.split("\\s++");
			map.put(temp[0], Integer.parseInt(temp[1]));
		}
		return map;
	}

	/**
	 * 分隔字符串，返回存结果字符串的set（主要是取出重复的情况），“aa a”和“a aa”认为是同一种情况
	 * @param str
	 * @param map
	 * @return
	 */
	private static Set<String> combination(String str, Map<String,Integer> map) {
		Set<String> set = new TreeSet<String>();
		String[] array = new String[map.keySet().size()];
		map.keySet().toArray(array);
		int sum = 0;
		int i = 0, j =0;
		StringBuffer sb = new StringBuffer();
		while(i < array.length) {
			j = i;
			sum = 0;
			String temp = str;
			boolean flag = false;
			while(j < array.length) {
				String s = array[j];
				int index = temp.indexOf(s);
				if(index > -1) {
					j = 0;
					sb.append(s + " ");
					sum += map.get(s);
					temp = temp.substring(index + s.length());
					if(index == 0)
						flag = true;
					if(temp.length() == 0 && flag) {
						set.add(sb.toString() + "  " + sum);
						break;
					}
				} else {
					j ++;
				}
			}
			sb.delete(0, sb.length());
			i++;
		}
		return set;
	}
}

#9

这是国信蓝点杯的试题
第一道题：

package GXLDB;

import java.util.Scanner;

public class PrintNumToDivide1 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入所要拆解的整数：");
		int num = sc.nextInt();
		if (num <= 0 || num >10) {
			System.out.println("输入的整数不在范围（0-10）内！");
			System.exit(0);
		}
		divideNum(num);
	}

	private static void divideNum(int num) {		
		int[] arr = new int[num];
		int index = 0;
		divideNum(arr, index, num, num);
	}

	private static void divideNum(int[] arr, int index, int maxNum, int remnantNum) {	
		if (remnantNum == 0) {
			for (int i = 0; i < index - 1; i++) 
				System.out.print(arr[i] + "+");

			System.out.println(arr[index - 1]);
		} else {
			for (int i = 1; i <= maxNum && i <= remnantNum; i++) {
				arr[index] = i;
				divideNum(arr, index + 1, i, remnantNum - i);
			}
		}
	}
}

#10

引用 8 楼 hudie1234567 的回复:

Java code

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.Scanner;
import java.ut……

哈哈 大哥也来凑热闹哈

#11

引用 7 楼 qybao 的回复:

第2问
Java code

import java.util.*;
import java.io.*;
public class Qs {
    public static void main(String[] args) {
        //question1();
        question2();
    }


    public static void questi……

又见阿宝前辈  顶顶

#12

引用 2 楼 hudie1234567 的回复:

第一道题可以参考下面的：
http://topic.csdn.net/u/20110426/19/FE639810-7C70-47A4-90DC-B39756747934.html

顶这个

#13

引用 9 楼 tkd03072010 的回复:

这是国信蓝点杯的试题
第一道题：

Java code

package GXLDB;

import java.util.Scanner;

public class PrintNumToDivide1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System……

这个我以前也遇见过，还给我笔试了。

#14

第一题

public class zzz1 {
	public static void main(String[] args) {
		try {
			Scanner scn = new Scanner(System.in);
			int num = Integer.parseInt(scn.next());
			splitNum(1,num,"");
		} catch (NumberFormatException e) {
			System.err.println("输入数据不是整数！");
		}

	}
	public static void splitNum(int startNum,int Num,String str){
		if(Num == 0){
			System.err.println(str.substring(0,str.length()-1));//去掉最后一个“+”号
		}else {
			for(int i = startNum;i<=Num ;i++){
				splitNum(i,Num-i,str+i+"+");
			}						
		}
	}
}

#15

第一题 比较简洁写法

    public static void solve(int i){
        innerSolve(i, i, 1, "");
    }

    private static void innerSolve(int tatol, int n, int min, String result){
        if (n == 0){
            System.out.println(tatol + " = " + result.substring(1));
        }
        else if (n >= min){
            innerSolve(tatol, n - min, min, result + "+" + min);
            innerSolve(tatol, n, min + 1, result);
        }
    }

#16

算法严重弱项啊，有待锻炼！

#17

第二题

public class zzz2 {
	public static void main(String[] args) {
		try {
			File file = new File("E:/111.txt");
			BufferedReader reader = new BufferedReader(new InputStreamReader(
					new FileInputStream(file)));
			String str = null;
			Map<String,Integer> map = new HashMap<String,Integer>();
			while ((str = reader.readLine())!= null) {
				String[] strs = str.split("\\s+");
				map.put(strs[0], Integer.valueOf(strs[1]));
			}

			Scanner scn = new Scanner(System.in);
			str  = scn.next();
			splitStr(str, new ArrayList<String>(),map);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static void splitStr(String str ,List<String> list, Map<String,Integer> map) {
		if(str.length() == 0){
			int totalNum = 0;
			for(int i = 0;i<list.size();i++){
				if(map.get(list.get(i))== null){
					return;
				}else {
					totalNum += map.get(list.get(i));
				}
			}
			for(int i = 0;i<list.size();i++){
				System.err.print(list.get(i)+" ");
			}
			System.err.println(totalNum);
		}else {
			for(int i = 1;i<=str.length() ;i++){
				list.add(str.substring(0,i));
				splitStr(str.substring(i),list,map);
				list.remove(list.size()-1);
			}			
		}
	}
}

#18

引用 16 楼 linmarklin 的回复:

算法严重弱项啊，有待锻炼！

这个只是纯递归罢了。。。。真正项目中很少能用到，更多的是禁止用..因为写的不好很容易死循环溢出啥的，还不好排错..

上升不到算法的高度吧..=.=

#19

这么多人给的都是递归的，就给Lz非递归的吧，修正了一下我在上面的回答中的一些不足
另，问题2不知道LZ要的组合是全组合，还是必须包括输入字符串的所有组合
全组合的意思是 输入 aaabc
那么单独一个a 也算， 即结果有
a 34
a a 68
a a a 102
a aa 70
...

如果是必须包括输入字符串的所有组合，则必须满足所有的输入的字符都要出现，即
a a a bc
a aa bc
aa abc
aaa bc

这里暂时以第二种理解为例，即必须包括输入字符串的所有组合

import java.util.*;
import java.io.*;
public class Qs {
    public static void main(String[] args) {
        question1();
        question2();
    }


    public static void question1() {
        try {
            Scanner sc = new Scanner(System.in);
            System.out.print("Q1, please input a number:");
            int sum = sc.nextInt();
            for (int i=1; i<=sum; i++) {
                divNum(sum, i);
            }
        } catch (Throwable e) {
            e.printStackTrace();
        }        
    }

    public static void divNum(int sum, int n) {
        if (n == 1) {
            System.out.printf("%d=%d\n", sum, sum);
            return;
        }
        int tmp = 0;
        int[] idx = new int[n];
        for (int i=0; i<n-1; i++) {
            idx[i] = 1;
            tmp += idx[i];
            System.out.printf("%d+", idx[i]);
        }
        idx[n-1] = sum-tmp;
        System.out.printf("%d=%d\r\n", idx[n-1], sum);

        while (true) {
            idx[n-2]++;
            for (int i=n-2; i>0; i--) {
                tmp = 0;
                for (int j=0; j<i; j++) {tmp+=idx[j];}
                if (idx[i] > (sum-tmp)/(n-i)) {
                    idx[i-1]++;
                }
            }
            if (idx[0] > sum/n) {break;}
            tmp = 0;
            for (int i=1; i<n-1; i++) {
                tmp += idx[i-1];
                if (idx[i] > (sum-tmp)/(n-i)) {
                    idx[i] = idx[i-1];
                }
            }
            tmp = 0;
            for (int i=0; i<n-1; i++) {
               tmp += idx[i];
               System.out.printf("%d+", idx[i]);
            }
            idx[n-1] = sum-tmp;
            System.out.printf("%d=%d\r\n", idx[n-1], sum);
        }
    }

    public static void question2() {
        try {
            BufferedReader br = new BufferedReader(new FileReader("data.txt"));
            Map<String, Integer> map = new HashMap<String, Integer>();
            String buf;
            while ((buf=br.readLine()) != null) {
                String[] ss = buf.split("\\s+");
                map.put(ss[0], Integer.valueOf(ss[1]));  
            }
            br.close();
            Scanner sc = new Scanner(System.in);
            System.out.print("Q2, please input a string:");
            buf = sc.nextLine();
            List<List<String>> list = divString(buf, map);
            if (list.size() == 0) {
                System.out.println("no combinations.");
            } else {
                for (List<String> l : list) {
                    for (String s : l) {
                        System.out.printf("%s ", s);
                    }
                    System.out.println();
                 }
            }
        } catch (Throwable e) {
            e.printStackTrace();
        }
    }

    public static List<List<String>> divString(String buf, Map<String, Integer> map) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (buf.length() == 1) {
            if (map.containsKey(buf)) {
                List<String> list = new ArrayList<String>();
                list.add(buf);
                list.add(map.get(buf).toString());
                result.add(list);
            }
            return result;
        }

        Stack<String> val = new Stack<String>();
        Stack<String> mem = new Stack<String>();
        String s1, s2, s, bak = buf;
        int sum, i=1;
        while (true) {
            for (; i<=buf.length(); i++) {
                s1 = buf.substring(0, i);
                s2 = buf.substring(i);
                if (map.containsKey(s1)) {
                    if (map.containsKey(s2)) {
                        List<String> list = new ArrayList<String>();
                        list.add(s1);
                        list.add(s2);
                        sum = map.get(s1) + map.get(s2);
                        while (val.size() > 0) {
                            s = val.pop();
                            sum += map.get(s);
                            list.add(0, s);
                            mem.push(s);
                        }
                        while (mem.size() > 0) {
                            val.push(mem.pop());
                        }
                        list.add(String.valueOf(sum));
                        result.add(list);
                        continue;
                    } else {
                        val.push(s1);
                        buf = s2;
                        i = 1;
                        break;
                    }
                } else {
                    if (i == buf.length()) {
                        if (val.size() > 0) {
                            s = val.pop();
                            buf = s + buf;
                            i = s.length()+1;
                            break;
                        } else {
                            i = bak.length();
                            break;
                        }
                    }
                }
            }

            if (i == bak.length()) {break;}
        }
        return result;
    }
}

#20

引用 15 楼 keeya0416 的回复:

第一题 比较简洁写法
Java code

    public static void solve(int i){
        innerSolve(i, i, 1, "");
    }

    private static void innerSolve(int tatol, int n, int min, String result){
        if (n == 0){……

呵呵 total啦~~  不是 tatol哦~~

#21

太复杂了

#22

两道题都不难吧，搞得这么复杂

#23

对于我这种菜鸟来说，确实太复杂了