삼형제-수의 곱하기, 가방 문제, 조합의 자바 구현

귀환은 방법 호출 방법 자체가 문제를 해결하는 것이 신기하고 실용적인 기능이다.이 편은 이라는 책 6장 귀착에서 마지막으로 남긴'세 가지 재미있는 문제'를 해결하기 위한 것이다.
문제1: 한 수의 곱셈을 구하다
휴대용 계산기에서 한 수의 곱셈을 구할 수 있는데, 보통 X^Y로 X의 Y를 구하는 것을 나타낸다.그런데 이 키가 없으면 어떻게 해요?
해석: 이것은 세 문제 중 가장 간단한 것으로 귀속으로 하나의 곱셈을 구한다.코드는 다음과 같습니다.

package test.recursion;

public class PowerQ 
{
	public int power(int x,int y) throws Exception
	{
		int result = 0;
		if(y < 0)
			throw new Exception("y 0");
		else if(y == 0){// y=0 ， 1;
			result = 1;
		}
		else if(y/2 == 1)// y/2 ， X*X;
			result = x*x;
		else // 
			result = power(x,y/2)*power(x,y/2);
		if(y%2 == 1)// y 2 1 ， X;
			result = result*x; 
		return result;
	}
	
	public static void main(String[] args) throws Exception {
		PowerQ pq = new PowerQ();
		System.out.println(pq.power(10, 0));
		System.out.println(pq.power(10, 1));
		System.out.println(pq.power(10, 2));
		System.out.println(pq.power(10, 3));
		System.out.println(pq.power(10, 4));
		System.out.println(pq.power(10, 5));
	}
}

결과는 다음과 같습니다.

1
10
100
1000
10000
100000

문제2: 가방 문제
배낭 문제는 컴퓨터 과학의 대표적인 문제다.가장 간단한 형식에는 서로 다른 무게의 데이터 항목을 가방에 넣어 가방이 마지막에 지정한 총 무게에 도달하도록 시도하는 것이 포함된다.모든 옵션을 가방에 넣을 필요가 없습니다.만약 배낭 하나에 최대 20근의 물건을 넣을 수 있다면, 현재 다섯 개의 데이터 항목이 있는데, 각각 11근, 8근, 7근, 6근, 5근이다.어떻게 하면 딱 20근에 이를 수 있습니까?
해석: 꼭 20근이 필요하고 데이터 항목의 수량에 대한 요구가 없습니다.하나하나 다 돌아다닐 수밖에 없어요.코드는 다음과 같습니다.

package test.recursion;

import java.util.ArrayList;

public class BackpackQ 
{
	public int[] numbs;
	public ArrayList<Integer> adaptNumbs;
	
	public BackpackQ(int[] numbs)
	{
		this.numbs = numbs;
		adaptNumbs = new ArrayList<Integer>();
	}
	
	public boolean adapt(int start,int max)
	{
		boolean flag = false;
		for (int i = start; i < numbs.length; i++) 
		{
			int temp = max - numbs[i];
			if(temp == 0) flag = true;
			else if(temp < 0) flag = false;
			else flag = adapt(i+1,temp);
			if(flag)
			{
				adaptNumbs.add(numbs[i]);
				return true;
			}
		}
		return flag;
		
	}
	
	public static void main(String[] args) {
		int[] numbs = {11,8,7,6,5};
		BackpackQ bq = new BackpackQ(numbs);
		boolean adapt = bq.adapt(0, 20);
		System.out.println(bq.adaptNumbs.toString()+ adapt);
	}
}

결과는 다음과 같습니다.

[5, 7, 8]

문제3: 한 팀을 선택한다
수학에서 조합은 사물에 대한 선택이지 순서를 고려하는 것이 아니다.예를 들어 ABCDE인 5명의 등산대원이 있다.5명 중 3명을 선발해 선두 부대를 구성하려면 가능한 모든 조합을 열거해야 한다.
해석: 대학에서 조합의 지식을 배웠는데 만약에 (n,k)로 n개 중 K개를 선택하면 표현식이 있다는 것을 알고 있다.
(n,k)=(n-1,k-1)+(n-1,k)
그러면 5선3은 (5,3)=(4,2)+(4,3)로 바뀌고 n중 1개와 n중 n개를 선택할 때까지 각 하위 항목을 계속 귀속시킬 수 있다.코드는 다음과 같습니다.

package test.recursion;

import java.util.HashSet;
import java.util.Set;

public class TeamQ {
	public String[] items; // 
	public Set<String> rs; //set  
	
	public TeamQ(String[] items,int k){
		this.items = items;
		String temp="";
		rs = new HashSet<String>();
		seek(items.length,k,temp); // 
	}	
	
	public void seek(int n,int k,String temp){
		if(k>1)//  k>1 ，(n-1,k-1)
			seek(n-1,k-1,temp+items[items.length-n]); 
		if(n>k)//   n>k ,(n-1,k)
			seek(n-1,k,temp);
		if(k == 1){ // k==1, n 1 ， ， set 
			for (int i = items.length- n ; i < items.length; i++) {
				String tempIn = temp +items[i];
				rs.add(tempIn);
			}
		}
		if(k == n && k != 1){// k==n k!=1, n n ， ， set 
			String tempIn = temp;
			for (int i = items.length- n ; i < items.length; i++) {
				tempIn = tempIn +items[i];
			}
			rs.add(tempIn);
		}
	}
	
	public static void main(String[] args) {
		String[] sa = {"A","B","C","D","E"};
		TeamQ tq = new TeamQ(sa, 3);
		StringBuffer sb = new StringBuffer(" ：");
		boolean isFirst = true;
		for (String str : sa) {
			if(!isFirst){
				sb.append(",");
			}
			sb.append(str);
			isFirst = false;
		}
		sb.append("
 "+sa.length+" "+3+"
 ：");
		isFirst = true;
		for (String str : tq.rs) {
			if(!isFirst){
				sb.append(",");
			}
			sb.append(str);
			isFirst = false;
		}
		
		System.out.println(sb.toString());
	}
}

결과는 다음과 같습니다.

 ：A,B,C,D,E
 5 3
 ：BCD,ABD,ABC,ACE,ACD,BDE,BCE,ABE,ADE,CDE