분동 무게 측정 1

참고 자료https://blog.csdn.net/linhaiyun_ytdx/article/details/50629743
만약 5개의 분동만 있다면, 무게는 각각 1, 3, 9, 27, 81이다.그것들이 조합해서 1에서 121 사이의 임의의 정수 무게를 측정할 수 있다는 것을 이미 알고 있다.본 문제는 프로그래밍 실현을 요구한다. 사용자가 정한 무게에 대해 분동 조합 방안을 제시한다.예를 들어 사용자 입력: 5 프로그램 출력: 9-3-1 사용자 입력: 19 프로그램 출력: 27-9+1 프로그램 출력의 조합은 항상 앞의 소수가 뒤에 있어야 한다.사용자가 입력한 숫자가 범위 1 ~ 121에 부합한다고 가정할 수 있습니다.판권 성명: 본문은 CSDN 블로거인'소소우쉬 '의 오리지널 기사는 CC 4.0 BY-SA 저작권 협의에 따라 원문의 출처 링크와 본 성명을 첨부하여 전재합니다.텍스트 링크:https://blog.csdn.net/linhaiyun_ytdx/article/details/50629743
자료를 조사할 때 이 문제에 부딪히면 아예 모든 분동과 관련된 알고리즘 문제를 한쪽으로 정리한다.다음은 자신이 실현한 방안이다.
가장 간단한 빈거법

    char a[] = { 1, 3, 9, 27, 81 };
    int num = 0;
    cin >> num;
    for (int i0 = -1; i0 < 2; i0++)
    {
        for (int i1 = -1; i1 < 2; i1++)
        {
            for (int i2 = -1; i2 < 2; i2++)
            {
                for (int i3 = -1; i3 < 2; i3++)
                {
                    for (int i4 = -1; i4 < 2; i4++)
                    {
                        if (num == (a[0] * i0 + a[1] * i1 + a[2] * i2 + a[3] * i3 + a[4] * i4))
                        {
                            cout << i0 << i1 << i2 << i3 << i4;
                        }
                    }
                }
            }
        }
    }

빈거법 을 귀속 으로 바꾸다

bool test(char* a, int index, int nownum, int num, char* b)
{
    if (index == 5)
    {
        return false;
    }
    int tmp = nownum;
    b[index] = 0;
    if (nownum == num)
    {
        return true;
    }
    else if (test(a, index + 1, nownum, num, b))
    {
        return true;
    }

    b[index] = -1;
    nownum = tmp - a[index];
    if (nownum == num)
    {
        return true;
    }
    else if (test(a, index + 1, nownum, num, b))
    {
        return true;
    }

    b[index] = 1;
    nownum = tmp + a[index];
    if (nownum == num)
    {
        return true;
    }
    else if (test(a, index + 1, nownum, num, b))
    {
        return true;
    }
    b[index] = 0;
    return false;
}

int main()
{
    char a[] = { 1, 3, 9, 27, 81 };
    char b[5] = { 0 };
    int num = 0;
    cin >> num;
    test(a, 0, 0, num, b);
}

이렇게 하면 중복된 계산이 매우 많다는 것을 알 수 있다. 그러면 정해진 문제에 규칙이 있는가?상기 작가의 사고방식을 참고하여 우리는 1이 1만을 나타낼 수 있다는 것을 발견했다.1과 3은 최대 4까지 표시할 수 있다.1, 3, 9는 13을 나타낼 수 있다. 바로 피보나치 수열과 같이 하나의 구간을 얻으면 각 구간에서, 예를 들어 숫자가 1과 3이 생성된 구간 1-4에 있으면 1과 3으로 구성되고 1보다 큰 숫자가 반드시 필요하다.모두 단지 하나의 분동만 있기 때문에 분동 a는 a보다 자신의 품질이 큰 물품이라고 할 수 없다.5-13 사이의 숫자라면?그럼 9가 꼭 필요할 거예요.그래서 우리는 먼저 가장 큰 숫자를 찾은 다음에 입력한 숫자로 가장 큰 숫자를 빼고 정수라면 더 크다는 것을 표시하고 두 번째 작은 숫자를 뺀다.음수라면 작다는 뜻으로 다음 숫자를 더해라.천평에 올려도 물품이 4라면 우리 하나 셋, 하나 더 넣자.만약 5라면 우리는 먼저 9를 하나 넣는다. 1과 3을 더해도 4를 누를 수 없기 때문에 더 큰 9를 넣고 9를 넣으면 천평조 분동이 기울어져서 많다는 것을 나타낸다. 그래서 물품 이쪽에 분동을 넣고 남은 무게(즉 상감된 마이너스)를 상쇄해야 한다.기왕 분동이 상쇄를 돕는 무게이기 때문에 계산할 때 이 부분에 물품을 입력하지 않는 분동의 무게를 줄여야 한다.

int main()
{
    int a[] = { 1, 3, 9, 27, 81 };
    int b[5] = { 0 };
    for (int i = 0; i < 5; i++)
    {
        if (i > 0)
        {
            b[i] = a[i] + b[i - 1];
        }
        else
        {
            b[i] = a[i];
        }
    }
    int num = 0;
    cin >> num;
    while (num != 0)
    {
        int index = 0;
        for (int i = 0; i < 5; i++)
        {
            if (std::abs(num) <= b[i])
            {
                index = i;
                break;
            }
        }
        if (num > 0)
        {
            cout << "+" << a[index];
        }
        else if (num < 0)
        {
            cout << "-" << a[index];
        }
        if (num > 0)
        {
            num = num - a[index];
        }
        else if (num < 0)
        {
            num = num + a[index];
        }
    }
    char inchar;
    cin >> inchar;
}