黑马程序员技术交流社区

标题: 一道算法题，求解 [打印本页]

---

作者: 李跃达    时间: 2013-1-30 13:45
标题: 一道算法题，求解


输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来.

---

作者: 李跃达    时间: 2013-1-30 14:36
所有和都等于M是没问题的，但是要全排列，这个不太会有没有会的同学帮个忙

---

作者: 黄鸿达    时间: 2013-1-30 22:14


写一个这个程序，居然写了我一个下午+一个晚上，无语。不过也程序也实现了楼主的要求，而且不会有重复~~
里面注释的，下面是我的大体思想，那些各种打印语句是我调试的时候用到的，因为刚写完很多问题，通过
打印语句，慢慢推敲出错误的代码。该程序大循环嵌套小循环，小循环是个递归程序，通过return返回，并通过各种真假标记判断。

1. import java.util.*;
   
2. public class 使其和等于 {
   
3. 
   
4. public static void main(String[] args) {
   
5. 
   
6. 使其和等于 a=new 使其和等于();
   
7. a.user();
   
8. //a.get(9,8);
   
9. System.out.println(a.showNum.toString());
   
10. //System.out.print(a.wantNumBank.toString());
    
11. //System.out.print(a.showNum.toString());
    
12. }
    
13. // int 给的x开始的数=1;
    
14. int mark=1;
    
15. // int 目标数=0;
    
16. int target=0;
    
17. // int 送入数组其中数=0;
    
18. int wantNum=0;
    
19. int length=0;
    
20. String tempString;
    
21. boolean flag=false;
    
22. boolean bigflag=false;
    
23. int bigtarget=0;
    
24. //读取东西A的ALL东西出来
    
25. StringBuffer wantNumBank=new StringBuffer();
    
26. //按照表示应该是 组合：XX,XX,送入数组其中数,给的X开始的数
    
27. StringBuffer showNum=new StringBuffer();
    
28. 
    
29. void sum(int toMark,int toTarget){
    
30. //这个事小循环模组
    
31. // System.out.println("你好像现在中层的x"+toMark);
    
32. mark=toMark;
    
33. // System.out.println("传入了个mark角标"+mark);
    
34. target=toTarget;
    
35. // System.out.println("传入了个target我要求和的数"+target);
    
36. for(int x=mark;x<=length;x++){
    
37. mark=x;
    
38. //下面if都是不满足条件跳出，并且打开能进入修改标记的大循环中的if语句
    
39. if(!(target-mark>0)){
    
40. // System.out.println("不符合1：将重新定位target为----"+toTarget);
    
41. // System.out.println("不符合1：将重新定位mark为----"+toMark);
    
42. // System.out.println("我将眺望"+x+"-1");
    
43. flag=true;
    
44. bigflag=true;
    
45. return;
    
46. }
    
47. if((target-mark)==mark){
    
48. // System.out.println("不符合2：将重新定位target为----"+target);
    
49. // System.out.println("不符合2：将重新定位mark为----"+mark);
    
50. // System.out.println("我将眺望"+x+"-1");
    
51. flag=true;
    
52. bigflag=true;
    
53. return;
    
54. }
    
55. if((target-mark)<mark){
    
56. // System.out.println("不符合2：将重新定位target为----"+target);
    
57. // System.out.println("不符合2：将重新定位mark为----"+mark);
    
58. // System.out.println("我将眺望"+x+"-1");
    
59. flag=true;
    
60. bigflag=true;
    
61. return;
    
62. }
    
63. wantNum=target-mark;
    
64. // System.out.println("x="+x+"wantNUm="+wantNum);
    
65. for(int y=1;y<=length;y++){
    
66. // System.out.println("你好现在中层的x"+toMark+"里层的y"+y);
    
67. // System.out.println("y="+y+"wantNUm="+wantNum);
    
68. //找到你要找的数
    
69. if(y==wantNum){
    
70. // System.out.println(wantNumBank.toString());
    
71. // System.out.println(mark);
    
72. //把可能的组合加进去
    
73. showNum.append("组合:"+wantNumBank+mark+"+"+wantNum+"="+bigtarget+"\n");
    
74. wantNumBank.append(mark+"+");
    
75. // System.out.println(tempString.toString());
    
76. // System.out.println(showNum.toString());
    
77. toMark=mark+1;
    
78. toTarget=wantNum;
    
79. //递归
    
80. sum(toMark,toTarget);
    
81. }
    
82. //有可能递归从这里跳出，这里就可以再次判断跳出~
    
83. if(flag){
    
84. return;
    
85. }
    
86. }
    
87. }
    
88. 
    
89. }
    
90. void get(int target,int length){
    
91. //大循环
    
92. for(int x=1;x<length;x++){
    
93. //修改判断标记全假，不然内循环某些地方还没弄完就跳出，
    
94. //这个语句是内层跳出来改写bigflag为true才能进入，
    
95. if(bigflag){
    
96. flag=false;
    
97. bigflag=false;
    
98. }
    
99. // System.out.println("我是最外层，现在第"+x);
    
100. wantNum=0;
     
101. //每次出来都要清空
     
102. wantNumBank.delete(0, wantNumBank.length());
     
103. // System.out.println(wantNumBank.toString());
     
104. sum(x,target);
     
105. 
     
106. }
     
107. 
     
108. //System.out.println(mark+"+"+target+"+"+length);
     
109. }
     
110. void user(){
     
111. System.out.print("输入你所给与数列最大数");
     
112. this.length=new Scanner(System.in).nextInt();
     
113. System.out.print("输入你的和");
     
114. this.target=new Scanner(System.in).nextInt();
     
115. bigtarget=target;
     
116. get(target,length);
     
117. }
     
118. }
     
119. 
     
120. //
     
121. // void reout(int target,int mark){
     
122. // if(!(target-mark>0)){
     
123. // System.out.println("不符合1：将重新定位target为----"+toTarget);
     
124. // System.out.println("不符合1：将重新定位mark为----"+toMark);
     
125. //
     
126. // return;
     
127. // }
     
128. // if((target-mark)==mark){
     
129. // System.out.println("不符合2：将重新定位target为----"+target);
     
130. // System.out.println("不符合2：将重新定位mark为----"+mark);
     
131. //
     
132. // return;
     
133. // }
     
134. // }
     
135. //}
     
136. 
     
137. // void sum(){
     
138. // int 给的x开始的数=1;
     
139. // int 目标数=0;
     
140. // int 送入数组其中数=0;
     
141. // final int 最大长度=目标数;
     
142. // for(int x=给的x开始的数;x<最大长度;x++){
     
143. // 送入数组其中数=目标数-给的x开始的数;
     
144. // 17=18-1
     
145. //
     
146. // //读取东西A的ALL东西出来
     
147. // //读取出来的格式为 XX,XX,
     
148. // //再用个东西wantNumBank存给的x开始的数
     
149. // //存入格式为 XX,
     
150. // //把 ALL东西+送入数组其中数+给的X开始的数 都送进 一个东西
     
151. // //按照表示应该是 组合：XX,XX,送入数组其中数,给的X开始的数
     
152. //
     
153. // //(给的x开始的数+1)传给下面调用的函数
     
154. // //目标数=送入数组其中数
     
155. //
     
156. // void sum(int 给的x开始的数,int 目标数){
     
157. //
     
158. // }
     
159. // }
     
160. // }
     
161. //}
     
162. //
     
163. //
     
164. //17=18-1
     
165. //
     
166. //1 17 送数组
     
167. //1临时数组
     
168. //
     
169. //15=17-2
     
170. //1 2 15 songshuzu
     
171. //
     
172. //1 2

复制代码

---

作者: 许晓华    时间: 2013-1-30 23:20

1. import java.util.Scanner;
   
2. public class x
   
3. {
   
4. static int Max=1000;
   
5. static int n,m;//n个数中选出若干数，总和为m
   
6. static int []a=new int[Max];//存放n个数
   
7. static int []flag=new int[Max];//标记n个数是否被选，1选，0不选
   
8. static void f(int sum,int idx)
   
9. {
   
10. if(sum==0)
    
11. {
    
12. for(int i=0;i<idx;i++)
    
13. if(flag[i]==1)
    
14. System.out.print(a[i]+" ");
    
15. System.out.println();
    
16. return;
    
17. }
    
18. if(sum<0||idx==n)
    
19. return;
    
20. flag[idx]=1;//选第idx号
    
21. f(sum-a[idx],idx+1);//递归
    
22. flag[idx]=0;//不选第idx号
    
23. f(sum,idx+1);//递归
    
24. }
    
25. public static void main(String[] args)
    
26. {
    
27. Scanner sc=new Scanner(System.in);
    
28. n=sc.nextInt();
    
29. m=sc.nextInt();
    
30. for(int i=0;i<n;i++)
    
31. a[i]=i+1;
    
32. f(m,0);//递归
    
33. 
    
34. }
    
35. }

复制代码

当n=5,m=6 时，结果如下：

---

作者: 梁永奇    时间: 2013-1-31 03:12
你题目中说想要算法，所以我把m，n的值直接赋给了，如果需要的话可以改成从键盘录入。

public class HelloWorld
{
        public static void main(String args[])
        {
                int[] shuzu = {1,2,3,4,5,6,7,8,9};//n=9,这里的n如果是需要手动输入的话，那么久生成新的数组，长度是n，然后依次赋值，你只是要算法，所以我把这里的n直接赋值了
                int jieguo = 7;//这是你题目中的m的值
                qiuHe(shuzu,jieguo);
        }
       
        public static void  qiuHe(int[] shuzu,int jieguo)
        {
                int len = shuzu.length;
                for(int m=0;m<len-1;m++)
                {
                        for(int n=m+1;n<len;n++)
                        {
                                if((shuzu[m]+shuzu[n])==jieguo)
                                {
                                        System.out.println("组合:"+shuzu[m]+"+"+shuzu[n]);
                                }
                                else if((shuzu[m]+shuzu[n])<jieguo)
                                {
                                        int he = shuzu[m]+shuzu[n];
                                        int[] arr = {shuzu[m],shuzu[n]};
                                        qiuHe2(shuzu,n,he,jieguo,arr);
                                }
                        }
                }
                for(int x=0;x<len;x++)
                {
                        if(shuzu[x]==jieguo)
                        {
                                System.out.println("组合:"+jieguo);
                        }
                }
        }
        public static void qiuHe2(int[] shuzu,int kaishiweizhi,int he,int jieguo,int[] xinshuzu)//这个函数用来求出组合
        {
                for(int position=kaishiweizhi+1;position<shuzu.length;position++)
                {
                        if((he+shuzu[position])==jieguo)
                        {
                                System.out.print("组合：");
                                for(int x=0;x<xinshuzu.length;x++)
                                {
                                        System.out.print(xinshuzu[x]+"+");
                                }
                                System.out.println(shuzu[position]);
                        }
                        else if((he+shuzu[position])<jieguo)
                        {
                                int temp = xinshuzu.length+1;
                                int[] newarry = new int[temp];
                                for(int lennewarry=0;lennewarry<temp-1;lennewarry++)
                                {
                                        newarry[lennewarry] = xinshuzu[lennewarry];
                                }
                                newarry[temp-1] = shuzu[position];
                                int he1 = he+shuzu[position];
                                qiuHe2(shuzu,position,he1,jieguo,newarry);
                        }
                }
        }
}

---

作者: 周发建    时间: 2013-2-1 14:43
这里的牛人很多啊

---

作者: 周发建    时间: 2013-2-1 14:43
看到你们的回答问题，我就感觉我真是个不够认真的人

---

作者: 周发建    时间: 2013-2-1 14:43
我向你们致敬，和向你们学习

---

作者: 周发建    时间: 2013-2-1 14:44
谢谢你们的辛苦付出，真心希望你们能不断牛

---

作者: 周发建    时间: 2013-2-1 14:44
祝福你们能够更加幸福，快乐

---

作者: 周发建    时间: 2013-2-1 14:45
你们的付出，不是白付出的，我们这些新来的会从你们的经验中收获很多

---

作者: 周发建    时间: 2013-2-1 14:45
你们的经验，就是可以让我们，学习少走弯路

---

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

黑马程序员IT技术论坛 X3.2