1 ~ 10 개의 요소로 구성된 4 개의 숫자가 주어진다. 합계가 4 개의 숫자를 모두 생성 할 수있는 3 개의 숫자를 찾으십니까?

Question

4 개의 난수 (1부터 10까지)의 목록을 포함하는 배열이 제공됩니다. 생성 된 목록의 3 개의 숫자를 추가하여 초기 목록의 4 개의 숫자를 모두 생성 할 수 있도록 3 개의 숫자 (1-10 포함)의 목록을 생성해야합니다.

누군가이 작업을 수행하는 알고리즘을 제공해주십시오.

Answer 1

솔루션에 1..10 범위의 숫자가 3 개만 포함되어 있기 때문에 무차별 공격 이 여기에 효과적인 알고리즘입니다 (순진한 구현에서도 검사 할 가능성이 최대 1000 개). 그래서 C# 코드는

public static int[] BruteForce(int[] data) { 
    HashSet<int> hs = new HashSet<int>(); 

    for (int x = 1; x <= 10; ++x) 
    for (int y = x; y <= 10; ++y) 
     for (int z = y; z <= 10; ++z) { 
     hs.Clear(); 

     for (int i = 0; i < data.Length; ++i) 
      hs.Add(data[i]); 

     hs.Remove(x); 
     hs.Remove(y); 
     hs.Remove(z); 

     hs.Remove(x + y); 
     hs.Remove(x + z); 
     hs.Remove(y + z); 

     hs.Remove(x + y + z); 

     if (hs.Count <= 0) 
      return new int[] { x, y, z }; // <- Solution 
     } 

    return new int[] {}; // <- No solution found 
} 

일부 테스트 케이스 같을 수

1. BruteForce (새 INT [{1, 3, 7, 8}); // < - [1, 2, 5]
2. BruteForce (new int [] {1, 3, 7, 9}); // < - [1, 2, 6]
3. BruteForce (new int [] {1, 6, 7, 9}); // < - [1, 2, 6]; 이전 사례와 동일
4. BruteForce (new int [] {4, 6, 7, 9}); // < - [1, 3, 6]
5. BruteForce (new int [] {5, 6, 7, 9}); // < - [2, 3, 4]
6. BruteForce (new int [] {1, 2, 4, 8}); // < - 해결책은

심지어 문제 무력 알고리즘에 의해 해결 될만큼 작은 (10000 항목) 인 (1 ~ 10에 4 개 항목의 모든 가능한리스트) 설정 발견 위에 구현되었습니다. 은 10000의 768 개의 4 항목 목록 만 3 항목 목록에 의해 생성 될 수 없음을 쉽게 알 수 있습니다.