기초 알고리즘 설계 - 귀속편(二)

2374 단어

앞말


말하자면 저는 이 시리즈의 글을 씁니다. 기술문보다는 수업시간에 했던 내용을 다시 복습하는 것입니다. 이런 문제들을 풀고 나서 한동안 복습을 하면서 자신의 성장과 학습 발자취를 나눠봤습니다. 글쎄요. 어쩌면 한 세대 어른들의 성장의 길일 수도 있습니다.이번에도 차례대로 전편은 하나의 예로 이 편은 자신이 풀었던 모든 문제를 올려놓았는데 상대적으로 간단하다고 한다. 면접에서 이것을 즐겨 본다고 한다.그러나 코드량이 확실히 비교적 적으니 좀 알 수 있다.맨 뒤에도 깊이 있는 제목이 붙어 있다.주: 제목은 우리 친애하는 반에서 온 OJ입니다. 만약에 타당하지 않은 곳이 있으면 반드시 저에게 연락해 주십시오. 저는 즉시 거두어들일 수 있습니다.

귀속 (이해를 돕는 간단한 예제)


예제 1:


제목 설명


주어진 숫자 n, n의 반수 서열 집합은 (1) n의 오른쪽에 자연수를 추가하지만, 이 자연수는 최근에 추가된 수의 반을 초과할 수 없기 때문에 새로운 서열이 생겼다.(2) 자연수를 추가할 수 없을 때까지 이 규칙에 따라 처리합니다.예를 들어 4의 반수 서열 집합은{4,42,421,41}이다.

입력


하나의 정수 n, (0

출력


숫자 강하 순서에 따라 출력은 모든 시퀀스를 집합하고, 시퀀스마다 한 줄씩, 숫자마다 뒤에 공백을 따른다.

샘플 입력



샘플 출력


6 3 1 6 3 6 2 1 6 2 6 1 6

출처


[계과 노반]
처음의 생각부터 말해봐.문제의 뜻이 비교적 뚜렷하다. 만약에 하나의 6을 가정하고 다음에 하나의 수를 추가하면 3(6/2=3>=3>0)이다. 그 다음에 여기 63을 결과로 출력하고 지난번의 수를 3으로 바꾸면 3 뒤에 추가한 수는 1(3/2=1.5;1.5>=1>0)이다.다른 경우를 보면 6 뒤에 조건에 부합되는 수는 2(6/2=3>=2>0)가 있다. 이런 식으로 미루어 보면 최종 결과는 자신 자체를 더한다.지난 장에서 말한 바와 같이 이런 중복으로 한 수 뒤의 수가 요구에 부합되는지 판단하면 귀속으로 실현할 수 있다. 그리고 이 문제는 다음 문제와 비슷하다. 귀속 방법에서 모두 순환해서 귀속을 집행해야 한다. 왜냐하면 두 번째 위치를 채울 수 있는 수가 여러 개이기 때문이다. 이 수를 채운 후에 다음 횟수를 채울 것이다. 여전히 여러 개가 있을 수 있다. 게다가 위의 규칙을 보면우리가 필요로 하는 순환 횟수가 n/2(n은 입력 데이터)임을 판단하기 어렵지 않다.emmm, 약간 혼란스러울 수도 있어요. 어쨌든 이런 조작은 매우 고급스러워요.괜찮아, 문자 사이에 우리는 연락이 없을 수도 있지만, 나는 코드가 우리의 의사소통에 좋은 다리가 될 수 있다고 믿는다.

본문

import java.util.ArrayList;

public class Hyj1476 {
    
    int[] result;
    int n;
    
    public Hyj1476(){
        n = 6;
        result = new int[n];
        result[0] = n;
        addNum(1,n);
        System.out.println(n);
    }
    
    public void addNum(int index,int max){
        for(int i=max/2;i>0;i--)
        {
            result[index] = i;
            addNum(index+1,i);
            for(int k=0;k<=index;k++)System.out.print(result[k]+" ");
            System.out.println();
        }
    }
    
    public static void main(String[] args){
        new Hyj1476();
    }
}

여기에서if조건으로 판단하지 않고 for순환에서 직접 출력하고 매번 들어오는 i를 통해 임계조건에 도달했는지 판단하고 index 커서를 설정하여 현재 결과수조의 위치에 있음을 나타낸다. 그러면 출력할 때 수조 후 필요하지 않은 0을 출력결과로 간주하는 것을 피할 수 있다.이 방법을 호출하는 아래 출력에 주의하십시오. 가장 안쪽에 있는 임계값으로 귀속될 때 조건에 부합되면 출력됩니다. 그러면 위의 출력 예시에 필요한 형식을 표시할 수 있습니다.

좋은 웹페이지 즐겨찾기