조합 하 다

2750 단어 알고리즘
수학 에서 우 리 는 배열 조합, 배열 은 질서 가 있 고 조합 은 순서 가 없다 는 것 을 배 웠 다.알고리즘 문 제 를 풀 때 우리 도 이런 문 제 를 만 날 수 있다.so, 오늘 정리 하고 조합 을 어떻게 쓰 는 지.
예 를 들 어 책상 위 에 공 3 개가 있 는데 A, B, C, 우 리 는 2 개 를 취하 고 놓 지 않 은 것 은 몇 가지 상황 이 있 습 니까?계산 해 보 니 C (3, 2) = 3 이다.
해결 해 야 할 문제
그러면 먼저 생각 을 정리 하고 우 리 는 몇 가지 문 제 를 해결 해 야 합 니까?
  • 세 개의 숫자 가 취 소 됐 는 지 어떻게 표시 해 야 합 니까? int 배열 을 만들어 그들의 초기 값 을 0 으로 설정 하고 int a = {0,0,0} 처럼 그 가 취 소 될 경우 1 로 설정 하고 세 개의 int 는 각각 ABC 를 대표 한다 고 생각 합 니 다.
  • 그리고 상자 에서 공 을 꺼 내 는 거 죠? 조합 이 죠?
  • 마지막 으로 조건 을 만족 시 키 고 우리 가 얻 은 조합 을 수출 한다.

  • 계획
    첫 번 째 단 계 는 우리 가 이미 해결 하 였 는데, 어떻게 공 을 빼 냈 다 는 것 을 표시 합 니까?두 번 째 단계, 조합: 다음 장면 을 생각해 보 자.
  • 책상 에서 A 를 취하 면 바로 BC 구 조합, B 를 취하 면 AC 구 조합, C 를 취하 면 AB 구 조합
  • 이다.
  • 계속 반복 해서 BC 의 조합 을 구 하 는 것 은 바로 B 를 꺼 내 서 C 의 조합 을 구 하 는 것 이다. 이렇게 계속 아 이 를 구 하 는 것 이다...모두 호출 된 같은 방법 으로 짐작 할 수 있 듯 이 재 귀 이다.

  • 그러면 함 수 를 정의 합 니 다. 그 역할 은 a 에서 공 을 뽑 고 조건 을 만족 시 키 는 출력 조합 을 얻 는 것 입 니 다.index 를 하나 더 정의 하면 내 가 어떤 공 을 얻 었 는 지 를 나타 낸다.그 후에 우 리 는 공 을 잡 으 려 면 a [index] 를 1 로 설정 하고 매개 변수 curr 는 이미 몇 개의 공 을 잡 았 는 지 표시 하기 때문에 + 1 이 필요 하 다. 그리고 다음 공 을 찾 으 러 가 야 한다.이렇게 반복 한다.
    물론 우 리 는 이 공 을 취하 지 않 아 도 된다. 이 공 을 취하 지 않 으 면 0 으로 해 야 한다. 그러나 index + 가 필요 하 다. 이 공 을 취하 지 않 으 면 다음 공 을 찾 아야 한다. 예 를 들 어 A 를 취하 지 않 지만 우 리 는 BC 에 가 야 한다.
    이 어 재 귀 출구 를 찾 았 다. 즉, 공 2 개 를 빼 거나 3 개 를 모두 빼 앗 겼 다.얻 은 후에 그것 을 인쇄 해라.쇼 (a []) 방법 을 호출 하 는 것 이다.
    show 방법: i 배열 을 옮 겨 다 니 며 a [i] = 1, 즉 우리 가 가 져 오 면 출력 합 니 다.(char)('A'+i)+" " 이것 도 작은 디 테 일이 다.
    코드
    /* 5          */
    public class    {
        static int count;
        //          ,      ,    ,       
        public static void main(String[] args) {
            int a[] = {0,0,0};
            method1(a,0,2,0);
            System.out.println(count);
        }
    
        /**
         *   :  a   ,  2        
         *
         * @param a   a         
         * @param index           
         * @param sum         
         * @param curr             
         */
        private static void method1(int a[], int index, int sum, int curr) {
            if (curr == sum){
                show(a);
                count++;
                return;
            }
            //        ,     ,   index == a.length,           
            if (index == a.length){
                return;
            }
            //      ,       1
            a[index] = 1;
            //          
            method1(a,index+1,sum,curr+1);
            //        ,       0
            a[index] = 0;
            method1(a,index+1,sum,curr);
    
        }
    
        private static void show(int[] a) {
            for (int i =0; i < a.length;i++){
                if (a[i] == 1 ){
                    System.out.print((char)('A'+i)+" ");//  char int   int,       char
                }
            }
            System.out.println();
        }
    }
    

    좋은 웹페이지 즐겨찾기