当前位置:Gxlcms > mysql > 输入两个整数n和m,从数列1,2,3,……n中随意取几个数,使其和等

输入两个整数n和m,从数列1,2,3,……n中随意取几个数,使其和等

时间:2021-07-01 10:21:17 帮助过:120人阅读

100题之21题:编程求解,输入两个整数n和m,从数列1,2,3,……n中随意取几个数,使其和等于m。要求将所有的可能组合列出来。实际上就是一个背包问题。 求解思路: 1.首先判断,如果nm,则n中大于m的数不可能参与组合,此时置n = m; 2.将最大数n加入且n == m,

100题之21题:编程求解,输入两个整数n和m,从数列1,2,3,……n中随意取几个数,使其和等于m。要求将所有的可能组合列出来。实际上就是一个背包问题。

求解思路:

1.首先判断,如果n>m,则n中大于m的数不可能参与组合,此时置n = m;

2.将最大数n加入且n == m,则满足条件,输出;

3.将n分两种情况求解,(1)n没有加入,取n = n - 1; m = m;递归下去;(2)n加入,取n = n - 1l, m = m - n,递归下去

[java] view plaincopyprint?

  1. public class s21 {
  2. private static LinkedList list = new LinkedList();
  3. /**
  4. * 求解思路:
  5. * 1.首先判断,如果n>m,则n中大于m的数不可能参与组合,此时置n=m;
  6. * 2.将最大的数n加入且n==m,则满足条件,输出;
  7. * 3.将n分两种情况求解:n没有加入,取n=n-1,m=m,递归;
  8. * 4.n加入,取n=n-1,m=m-n,递归。
  9. * 5.结束。
  10. * @param sum
  11. * @param n
  12. */
  13. public static void findSum(int sum, int n)
  14. {
  15. if ( n < 1 || sum < 1)
  16. return;
  17. if (sum > n)
  18. {
  19. list.add(n);
  20. findSum(sum - n, n - 1);// n加入,取n=n-1,m=m-n
  21. list.pop();
  22. findSum(sum, n - 1); // n没有加入,取n=n-1,m=m
  23. }
  24. else
  25. {
  26. System.out.print(sum); // sum < n ,直接输出n就可以满足了
  27. for (int i = 0; i < list.size(); i ++)
  28. System.out.print(" "+ list.get(i));
  29. System.out.println();
  30. }
  31. }
  32. /**
  33. * @param args
  34. */
  35. public static void main(String[] args) {
  36. // TODO Auto-generated method stub
  37. int sum = 10;
  38. int n = 6;
  39. findSum(sum,n);
  40. }
  41. }

人气教程排行