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

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

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

第二题：
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);}
}}

一个一个来
问题1import 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);
        }
    }
}

第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;
    }
}

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;
}
}

这是国信蓝点杯的试题
第一道题：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);
}
}
}
}

第一题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+"+");
}
}
}
}

第一题比较简洁写法    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);
        }
    }

第二题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);
}
}
}
}

这么多人给的都是递归的，就给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;
    }
}

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

调试易

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

解决方案 »