private static void lottery(int a[], int start_index, int end_index, int needed_balls, Set<Integer> already_chosen) { if (needed_balls == 0) { System.out.println(already_chosen); return; } for (int i = start_index; i <= end_index - needed_balls + 1; i++) { already_chosen.add(a[i]); lottery(a, i + 1, end_index, needed_balls - 1, already_chosen); already_chosen.remove(a[i]); } }
}
数学上的组合排列知识也忘的差不多了；一些常见的算法问题也还得继续学习； 不多说了，给个示例，实现了单线程查找，和多线程查找，楼主也可尝试先排序再组合优化查找：import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List;public class AlgorithmicDemo { public static void main(String[] args) { //从控制台获取数字 (略) // Scanner input = new Scanner(System.in); // while(true){ // // } int[] data = {4,3,5,7,1}; int target = 5; int offset = 3; System.out.println("范围在 " + (target-offset) + " 到 " + (target+offset) + "的数字组合有："); DataStore dataStore = new DataStore(data); for(int i = 1; i <= data.length; i++){ AlgorithmicThread thread = new AlgorithmicThread(dataStore,i,offset,target); thread.getResult();//单线程查找 //thread.start();//多线程查找 } dataStore.display(); }}class DataStore{ int[] data;//原始数字列表 int size;//数子个数
List<String> list;//符合要求的数字组合列表
public DataStore(int[] data){ if(data == null) throw new NullPointerException(); this.data = data; this.size = data.length; list = new ArrayList<String>(); }
1接近100吗？通常人的理解来说，不是。但是从自然数/Integer的角度来说，1和100又是接近的。
其中，array为待求数组，min为范围的最小值，max为范围的最大值，rank为级别（为了输出清晰，先可不考虑）
算法如下：
1、排序
2、算法调用：
当前数组长度是否为1？
是：判断当前值是否符合要求，是则输出。无论是否，方法返回。
否：（1）判断当前值是否有符合要求的，有则输出；
（2）由大到小，依次取出当前数组中小于max的最大值，不妨设其为V(为了叙述方便)。
每次取出之后，subArray等于array除了V的子数组。
int subMin = min-V;
int subMax = max-V;
递归调用algorithm(subArray,subMin,subMax,tempRank);（最后一个参数可以先不
考虑，只是为了输出格式而定义的）
源代码如下：
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*//**
*
* @author afunx
*/
public class Algorithm {
public static void main(String args[]){
Algorithm a = new Algorithm();
int[] array = {5,4,3,2,1};
//排序
a.sort(array);
for(int b:array)
System.out.print(b+",");
System.out.println();
//算法调用
a.algorithm(array, 3, 8,1);
System.out.println();
}
/**
*
* @param array 数组
* @param min 最小值
* @param max 最大值
* @param rank 级别，为了显示清晰，最初为1，
*/
public void algorithm(int[] array,int min,int max,int rank){
//如果数组为一维，递归结束
if(array.length==1){
if(min<=array[0]&&array[0]<=max)
System.out.println("("+rank+")"+array[0]);
else
return;
}
else{
//再加1元素即可达到要求
for(int a:array){
if(min<=a&&a<=max){
System.out.print("("+rank+")");
System.out.print(a+",");
}
}
System.out.println();
//优先取最外维（即数组中小于max的最大值）为一元素，其余递归调用algorithm
for(int i=array.length-1;i>0;i--){
if(array[i]<max){
for(int k=0;k<rank;k++){
System.out.print(" ");
}
System.out.println("("+rank+")"+array[i]+":");
//子数组
int[] subArray= new int[i];
//把array中下标从0到i的值复制到subArray
copy(array,subArray,i);
//递归调用
int subMin = min-array[i];
int subMax = max-array[i];
int tempRank = rank+1;
algorithm(subArray,subMin,subMax,tempRank);
}
}
}
} //数组copy,origin为源数组，target为目标数组，length为源数组从0开始的个数。
/**
* 子数组拷贝
* @param origin 源数组
* @param target 目标数组
* @param length 源数组从0开始的个数
*/
private void copy(int[] origin,int[] target,int length){
for(int i=0;i<length;i++){
target[i] = origin[i];
}
} //数组排序(这里采用最简单的冒泡法)
private void sort(int[] array){
for(int i=array.length;i>0;i--)
for(int j=1;j<i;j++){
if(array[j-1]>array[j])
swap(array,j-1,j);
}
} //交换数组的位置
private void swap(int[] array,int x,int y){
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
}
输出结果：
1,2,3,4,5,
(1)3,(1)4,(1)5,
(1)5:
(2)1,(2)2,(2)3,
(2)2:
(3)1
(1)4:
(2)1,(2)2,(2)3,
(2)3:
(3)1,
(2)2:
(3)1
(1)3:
(2)1,(2)2,
(2)2:
(3)1
(1)2:
(2)1
输出含义：顶格的为可能组合的最后那个元素，“（）”中的数为rank值，这样可以显示清除多重结构。此输出解释：此输入数组为{5,4,3,2,1}，求其组合值在[3,8]（包括3和8）。
此输出结果含义：
3;4;5;
5,1;5,2;5,3;
5,2,1;
4,1;4,2;4,3
4,3,1;4,2,1
3,1,;3,2;
3,2,1;
2,1;
（不同的组合用";"区别，同一组合中的不同数用","间隔）
max = N+M,min = N-M;
还有就是输入一连串的数，最后用Q来结束。
这两个挺简单的，楼主自己再改下代码即可。
public class SumComArithmetic { /**
* @param args
*/
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in );
System.out.print("Please input you target number:");
int targetNumber = input.nextInt();
int[] num = null ;
int index = 0;
while(true){
System.out.print("input: ");
String t = input.next();
if(t.trim().equals("Q"))
break;
else
if(SumComArithmetic.checkInput(t)){
if(num == null)
{
num = new int[1];
num[0] = new Integer(t).intValue();
}
else
{
index ++;
int[] temp = new int[num.length + 1];
for(int i=0; i<num.length; i++)
{
temp[i] = num[i];
}
num = temp;
num[index] = new Integer(t).intValue();;
}
}
else
{
System.out.println("input error, please again");
continue;
}
}
System.out.println("you input target Number is: " + targetNumber);
printArray(num);
Arrays.sort(num);
System.out.print("\n");
printArray(num);
}
/**
* 判断输入 内容的合法性 ,必须是 数字 和 "Q"
*
* @param str
* @return boolean
*/
private static boolean checkInput(String str){
int len = str.length();
int i = 0;
while(i < len)
{
//不是字符Q执行
if(!str.equals("Q"))
//不是数字执行
if(!Character.isDigit((str.charAt(i))))
return false;
i++;
}
return true;
}
/***
* 打印要组合的 数组,并判断目标数字是否小于要组合的数组元素
* @param arrays
* @return boolean 目标数是否 小于数组中的数
*/
public static boolean printArray(int[] arrays){
System.out.print("you input number is: ");
for(int i=0; i<arrays.length; i++)
{
System.out.print(arrays[i] + " ");
}
return false;
}
/**
* 接近目标数的组合，返回 List集合
* @param num 目标数
* @param arrays 输入的数组
*/
public static void complay(int num,int[] arrays){
}
}
package arithmetic;import java.util.*;
public class SumComArithmetic { /**
* @param args
*/
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in );
System.out.print("Please input you target number:");
int targetNumber = input.nextInt();
int[] num = null ;
int index = 0;
while(true){
System.out.print("input: ");
String t = input.next();
if(t.trim().equals("Q"))
break;
else
if(SumComArithmetic.checkInput(t)){
if(num == null)
{
num = new int[1];
num[0] = new Integer(t).intValue();
}
else
{
index ++;
int[] temp = new int[num.length + 1];
for(int i=0; i<num.length; i++)
{
temp[i] = num[i];
}
num = temp;
num[index] = new Integer(t).intValue();;
}
}
else
{
System.out.println("input error, please again");
continue;
}
}
System.out.println("you input target Number is: " + targetNumber);
Arrays.sort(num);
System.out.print("\n");
printArray(num);
complay(targetNumber,num);
}
/**
* 判断输入 内容的合法性 ,必须是 数字 和 "Q"
*
* @param str
* @return boolean
*/
private static boolean checkInput(String str){
int len = str.length();
int i = 0;
while(i < len)
{
//不是字符Q执行
if(!str.equals("Q"))
//不是数字执行
if(!Character.isDigit((str.charAt(i))))
return false;
i++;
}
return true;
}
/***
* 打印要组合的 数组,并判断目标数字是否小于要组合的数组元素
* @param arrays
* @return boolean 目标数是否 小于数组中的数
*/
public static boolean printArray(int[] arrays){
System.out.print("you input number is: ");
for(int i=0; i<arrays.length; i++)
{
System.out.print(arrays[i] + " ");
}
return false;
}
/**
* 接近目标数的组合，返回 List集合
* @param num 目标数
* @param arrays 输入的数组
*/
public static void complay(int num,int[] arr){
for(int i= 0;i<arr.length;i++)
{
lottery(arr , 0, arr.length-1, i,new HashSet<Integer>());
}
System.out.print("[");
for(int i= 0;i<arr.length;i++)
{
System.out.print(arr[i]+" ");
}
System.out.print("]");
}
private static void lottery(int a[], int start_index, int end_index,
int needed_balls, Set<Integer> already_chosen) {
if (needed_balls == 0) {
System.out.println(already_chosen);
return;
}
for (int i = start_index; i <= end_index - needed_balls + 1; i++) {
already_chosen.add(a[i]);
lottery(a, i + 1, end_index, needed_balls - 1, already_chosen);
already_chosen.remove(a[i]);
}
}
}
不多说了，给个示例，实现了单线程查找，和多线程查找，楼主也可尝试先排序再组合优化查找：import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;public class AlgorithmicDemo { public static void main(String[] args) {
//从控制台获取数字 (略)
// Scanner input = new Scanner(System.in);
// while(true){
//
// }
int[] data = {4,3,5,7,1};
int target = 5;
int offset = 3;
System.out.println("范围在 " + (target-offset) + " 到 " + (target+offset) + "的数字组合有：");
DataStore dataStore = new DataStore(data);
for(int i = 1; i <= data.length; i++){
AlgorithmicThread thread = new AlgorithmicThread(dataStore,i,offset,target);
thread.getResult();//单线程查找
//thread.start();//多线程查找
}
dataStore.display();
}}class DataStore{
int[] data;//原始数字列表
int size;//数子个数
List<String> list;//符合要求的数字组合列表
public DataStore(int[] data){
if(data == null) throw new NullPointerException();
this.data = data;
this.size = data.length;
list = new ArrayList<String>();
}
/**
* 获取一个线程安全的列表list
* @return 线程安全的List
*/
public List<String> getResultList(){
return Collections.synchronizedList(list);
}
/**
* @return 原始的数字数组
*/
public int[] getData(){
return data;
}
public int getSize(){
return size;
}
/**
* 展示符合要求的数字组合结果
*/
public void display(){
for(int i = 0; i < list.size(); i++){
System.out.println(list.get(i));
}
System.out.println("一共 " + list.size()+ " 个数字组合符合 要求 .");
}
}class AlgorithmicThread extends Thread{ DataStore dataStore;
int count;//数字组合个数
int offset;//范围宽度
int target;//目标数字
List<String> list;
public AlgorithmicThread(DataStore dataStore,int count,int offset,int target){
this.dataStore = dataStore;
this.count = count;
this.offset = offset;
this.target = target;
this.list = dataStore.getResultList();
}
/**
* 这是数字组合算法,根据传递的数字组合个数count,创建一个数组array,用于存储可能的数字组合,
* 每次从dataStore中选择一个数字放入array时判断结果是否合格，合格存入dataStore的列表list中;
*/
public void getResult(){
int[] array = new int[count];
int forntIndex = 0;
int rearIndex = count-1;
int nCount = dataStore.getSize() - count;
for(int i = 0; i <= nCount; i++){
int tempIndex = 0;
tempIndex = forntIndex;
for(int m = 0; m < count; m++){
array[m] = dataStore.getData()[tempIndex++];
}
getSumResult(list, array, (target - offset), (target + offset));
rearIndex++;
forntIndex++;
tempIndex = 0;
int index = rearIndex;
for(int n = (count-1); n > 0; n--){
for(int j = (nCount-i); j > 0; j--){
array[n] = dataStore.getData()[index++];
getSumResult(list, array, (target - offset), (target + offset));
}
index = rearIndex-(++tempIndex);
}
}
}
@Override
public void run() {
super.run();
getResult();
}
/**
* 判断数字组合是否符合要求
* @param resultList
* @param array
* @param start
* @param end
*/
public void getSumResult(List<String> resultList,int[] array, int start, int end){
int sum = 0;
for(int i = 0; i < array.length; i++){
sum += array[i];
}
if(sum >= start && sum <= end){
resultList.add(Arrays.toString(array));
}
}
}