서브 세트 합계 TI 기본 프로그래밍

Question

서브 세트 합계 검색을하기 위해 TI-83을 프로그래밍하려고합니다. 그래서 길이 N의 목록이 주어지면 주어진 길이의 모든 목록을 찾으려고합니다. 주어진 값으로 합한 길이의 V를 찾습니다.

이것은 내가 검색하기 때문에 정규 서브셋 합계 문제와 조금 다릅니다. 주어진 길이의 서브셋, 모든 길이가 아닌 재귀 그리고 반드시 재귀가 첫 번째 선택 인 것은 아니다. 내가 작업하고있는 프로그램을 호출 할 수 없기 때문이다.

중첩 된 루프로 작업을 쉽게 수행 할 수있다. 5보다 큰 L 값에 대해 성가신 상태가됩니다. 동적 인 솔루션을 찾으려고 노력하고 있지만 어디에도 가지 않습니다.

정말이 시점에서 나는 목록 참조를 올바르게 얻으려고하고 있습니다. 그래서 그것은 제가보고있는 것입니다. 다음의 예제와 함께 가자 :

L1={p,q,r,s,t,u} 

그렇게

N=6 

가의 상대적으로 짧은 그것을 유지하기 위해 길이 3의 모든 부분 집합에 대해 살펴 보자, L = 3 (6c3 = 20 개 총 출력) 그래서.

이상적으로 검색 할 것 목록 참조는 다음과 같습니다

FOR A,1,N-2 
    FOR B,A+1,N-1 
     FOR C,B+1,N 
      display {A,B,C} 
     END 
    END 
END 

내가 처음을 단축 기준을 검색 할 날 수 있습니다 N의 하강의 데이터를 정렬 :

{1,2,3} 
{1,2,4} 
{1,2,5} 
{1,2,6} 
{1,3,4} 
{1,3,5} 
{1,3,6} 
{1,4,5} 
{1,4,6} 
{1,5,6} 
{2,3,4} 
{2,3,5} 
{2,3,6} 
{2,4,5} 
{2,4,6} 
{2,5,6} 
{3,4,5} 
{3,4,6} 
{3,5,6} 
{4,5,6} 

분명히하여 수행 search를 사용하고 FOR 루프를 사용하면 루프 내에서 A, B 및 C 값을 증가시킬 때 조금씩 다른 위치에서 나사를 조입니다.

나는 또한 더 나은 동적 솔루션을 찾고 있습니다. 나는 웹에 대한 연구를 해왔지만, 내 특별한 상황에 어떤 영향을 미칠 것 같지 않다.

도움을 주시면 감사하겠습니다. 나는 소설을 쓰지 않을 정도로 충분히 짧게하려고 노력하지만, 나는 무엇을 얻으려고하는지 설명한다. 필요에 따라 더 자세한 정보를 제공 할 수 있습니다.

Answer 1

최적화를 위해 이미 V 값을 초과하는 검색 하위 트리를 건너 뛰기 만하면됩니다. 재귀가 이동하는 방법이지만 이미 배제 했으므로 ' 허용 된 깊이의 상한을 설정하는 것이 가장 좋습니다.

I (3의 깊이)이 같은 가고 싶어 : 그 꽤 복잡한입니다 이제

N is the total number of array elements. 
L is the desired length (3). 
V is the desired sum 
Y[] is the array 
Z is the total 

Z = 0 
IF Z <= V 
    FOR A,1,N-L 
    Z = Z + Y[A] 
    IF Z <= V 
     FOR B,A+1,N-L+1 
     Z = Z + Y[B] 
     IF Z <= V 
      FOR C,B+1,N-L+2 
      Z = Z + Y[C] 
      IF Z = V 
       DISPLAY {A,B,C} 
      END 
      Z = Z - Y[C] 
      END 
     END 
     Z = Z - Y[B] 
     END 
    END 
    Z = Z - Y[A] 
    END 
END 

하지만 기본적으로 당신이 이미 원하는 값을 초과하는 것을 거부했는지 모든 단계에서 확인 효율성 측정으로 하위 트리를 확인하십시오. 또한 현재 레벨의 누적 합계를 유지하므로 더 낮은 레벨에서 확인할 때 많은 추가 작업을 수행 할 필요가 없습니다. 즉, 추가 및 Z를

에 대한 배열 값의 감산을의

그것도 더 얻을 것 당신이 (D에서 K 11 레벨에 변수를 사용하여 (당신이 있다면 더 깊이를 더 처리하기 위해 수정할 때 복잡 N 및 L을 W 및 X으로 이동 시키거나 TI BASIC이 변수 이름에 둘 이상의 문자를 허용하는 경우).내가 그 일을 생각할 수

유일한 다른 비 재귀 방법은 반복과 재귀를 에뮬레이션 값 그룹의 배열을 사용하는 것입니다, 그것은 모양 만 약간 덜 털이 (코드 덜 중첩해야하지만) .