黑马程序员技术交流社区

标题: 求高手指教：代码设计，整数划分的问题 [打印本页]

---

作者: 王小丑    时间: 2013-2-3 22:12
标题: 求高手指教：代码设计，整数划分的问题


有道很有趣的问题：整数的分划问题。
如，对于正整数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
这是一道java程序设计大赛题，我看着很有意思，我只能实现部分，求高手指教，能不能给出全部可运行的程序！
补充：现在的问题是，对于给定的正整数n,编写算法打印所有划分。
用户从键盘输入 n （范围1~10）
程序输出该整数的所有划分。

---

作者: 郭孟涛    时间: 2013-2-3 22:23
当 n = 6时， 数组arr等于 1-5，即 1，2，3，4，5

求 1，2，3，4，5 在这n-1个整数中找到相加之和为n=6的所有组合


往后又转到了这个题， 在n个整数中找到相加之和为t的所有组合 http://bbs.itheima.com/thread-37306-1-1.html

---

作者: 许晓华    时间: 2013-2-3 22:27


  代码见下楼

fff.jpg (14.8 KB, 下载次数: 13)

下载附件

2013-2-3 23:16 上传

---

作者: 许晓华    时间: 2013-2-4 07:36

1. import java.util.Scanner;
   
2. public class c
   
3. {
   
4.         static int n;
   
5.         static int []d = new int [10];
   
6.         static void divide(int number,int idx)
   
7.         {
   
8.                 if(number==0)
   
9.                 {               
   
10.                         for(int i=0;i<idx;i++)
    
11.                         {
    
12.                                 if(i>0)
    
13.                                         System.out.print("+");//输出+号
    
14.                                 System.out.print(d[i]);
    
15.                         }
    
16.                         if(idx-1==n-d[0])
    
17.                                 System.out.println();
    
18.                         else
    
19.                                 System.out.print(",");//输出,号
    
20.                         return;
    
21.                 }
    
22.                 for(int i=number;i>=1;i--)//从大到小开始选数
    
23.                 {
    
24.                         if(idx==0||i<=d[idx-1])//用来保证右边的数不大于左边的
    
25.                         {
    
26.                                 d[idx]=i;
    
27.                                 divide(number-i,idx+1);
    
28.                         }
    
29.                 }
    
30.         }
    
31.     public static void main(String[] args)
    
32.     {
    
33.             Scanner sc=new Scanner(System.in);
    
34.                 while(sc.hasNextInt())
    
35.                 {
    
36.                         n=sc.nextInt();
    
37.                         divide(n,0);//求整数n的分划
    
38.                 }
    
39.         }
    
40. }

复制代码

---

作者: 王小丑    时间: 2013-2-6 18:40

许晓华 发表于 2013-2-4 07:36

我们想的差不多 我今天也运行出来了 呵呵 其实我一直进入一个误区 不过今天解决了

---

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

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