黑马程序员技术交流社区

标题: 一道小算法题,求答案 [打印本页]
作者: ssy1939    时间: 2014-8-7 15:17
标题: 一道小算法题,求答案
从键盘录入一个整数, 计算这个数有多少中方法可以得出,并打印出 具体的方法
如 1=1  一种;2 =1+1 一种; 3 =1+2 ,3=2+1, 3 = 1+1+1 三种;4 =1+3,4=2+2, 4 = 3+1; 4 =1+1+1+1 四种;  等
作者: 杨庆雷    时间: 2014-8-7 15:26
4=1+1+1+1
4=1+1+2
4=1+2+1
4=2+1+1
4=2+2
4=1+3
4=3+1

这是好多种啊
作者: 桂何钢    时间: 2014-8-7 15:40
这有什么意义吗
作者: ssy1939    时间: 2014-8-7 16:42
杨庆雷 发表于 2014-8-7 15:26
4=1+1+1+1
4=1+1+2
4=1+2+1

我貌似少写了,有代码吗?
作者: 曾宇    时间: 2014-8-7 17:13
本帖最后由 曾宇 于 2014-8-7 17:24 编辑

这是你要的代码：
  1. class  AddDemo
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 add(9);
  6.         }
  7.         public static void add(int num){
  8.                 StringBuilder sbd = new StringBuilder(num+"=1");
  9.                 for(int s=1;s<num;s++){
  10.                         sbd.append("+1");
  11.                 }
  12.                 System.out.println(sbd);
  13.                 for(int i=1;i<num;i++){
  14.                         for(int j = num-1;j>0;j--){
  15.                                 if((i+j)==num){
  16.                                         System.out.println(num+"="+i+"+"+j);
  17.                                 }
  18.                                
  19.                         }
  20.                 }
  21.         }
  22. }
复制代码



作者: fantacyleo    时间: 2014-8-7 17:58
递归
  1. import java.util.ArrayList;

  3. /**
  4. * 给定一个正整数，输出有多少种加法方式可以得到这个数，例如
  5. * 4=1+1+1+1
  6. * 4=1+1+2
  7. * 4=1+2+1
  8. * 4=2+1+1
  9. * 4=2+2
  10. * 4=1+3
  11. * 4=3+1
  12. * @author think
  13. *
  14. */

  16. public class AddDecomposition {

  18.         public static void main(String[] args) {
  19.                 decompose(4);
  20.         }

  22.         private static void decompose(int n) {
  23.                 if (n == 1)
  24.                         System.out.println("1=1");
  25.                 else {
  26.                         ArrayList<Integer> adders = new ArrayList<Integer>(); // 存放最初的数和分解出来的加数
  27.                         adders.add(n);
  28.                         executeDecomposition(n, adders);
  29.                 }
  30.         }

  32.         private static void executeDecomposition(int n, ArrayList<Integer> adders) {
  33.                 // 分解完毕，打印结果
  34.                 if (n == 0) {
  35.                         int adderNum = adders.size();
  36.                         System.out.print(adders.get(0) + "=");
  37.                         for (int i = 1; i < adderNum; i++) {
  38.                                 if (i == adderNum - 1)
  39.                                         System.out.println(adders.get(i));
  40.                                 else
  41.                                         System.out.print(adders.get(i) + "+");
  42.                         }
  43.                         return;
  44.                 }
  45.                
  46.                
  47.                 // 加数取值范围：1到n
  48.                 for (int i = 1; i <= n; i++) {
  49.                         if (i == adders.get(0)) // 跳过n = 0 + n的情形
  50.                                 break;
  51.                         adders.add(i); // 将i放入加数集合中
  52.                         executeDecomposition(n - i, adders); // 继续寻找加数
  53.                         adders.remove(adders.size() - 1); // 将i从加数集合中删除，尝试下一个i
  54.                 }
  55.         }
  56. }
复制代码
作者: wawsc5354524    时间: 2014-8-8 02:11
曾宇 发表于 2014-8-7 17:13
这是你要的代码：

你是用什么软件写的？Eclipse?
作者: m313786372    时间: 2014-8-8 03:30
  1. class FunctionDemo2 {
  2.         public static void main(String[] args) {
  3.                 int i = 6;                //需要拆分的数
  4.                 List<String> li = numSplit(6);
  5.                 for(String s : li) {
  6.                         System.out.println(s);
  7.                 }
  8.         }
  9.        
  10.         /*
  11.          * 一个整数n的所有不同拆分，等于：
  12.          * 1 + （n-1的所有拆分）
  13.          * 2 + （n-2的所有拆分）
  14.          * .....
  15.          * n-2 + （2的所有拆分）
  16.          * n-1 + （1）
  17.          *
  18.          * 因此，用递归做
  19.          */
  20.        
  21.         //numSplit方法中，放入n，将返回一个n的不同拆分的String集合
  22.         static ArrayList<String> numSplit(int n) {
  23.                 ArrayList<String> li = new ArrayList<String>();
  24.                 ArrayList<String> lin_1 = null;
  25.                 if(n==1){
  26.                         li.add("1");
  27.                         return li;
  28.                 }
  29.                 for(int i=1; i<n; i++) {
  30.                         lin_1 = numSplit(n-i);                //递归，返回n-i的拆分集合
  31.                         for(String s : lin_1) {
  32.                                 li.add(i+"+"+s);                //把n-i的拆分挨个连接"i"，装入n的拆分集合
  33.                         }
  34.                 }
  35.                 li.add(""+n);
  36.                 return li;
  37.         }
  38. }

  40. /* 没有做去重，如果考虑1+1+2、1+2+1、2+1+1为重复，需要去重，可以考虑：
  41. * 把每个拆分字符串拆解为int数组，排序，然后比较去重。
  42. */
复制代码
作者: xbz1986    时间: 2014-8-8 07:50
真不觉得有什么意义呀！
作者: 曾宇    时间: 2014-8-8 19:28
wawsc5354524 发表于 2014-8-8 02:11
你是用什么软件写的？Eclipse?

Edit plus3



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2