8 pack coins with double side pan problem

[hulala]

Imagine I have 8 pack of coins now, each pack of coins contain 1, 3 , 9 , 27 ,81,243,729, 2187 respectively. Now given double-pan balance scale, given a pack of N coins( N only can be 1 - 3280) put on the left side pan, I need to write an ALGORITHM by using the 8 pack coins to determine number of N coins on the left. I can put the 8 pack coins on the left pan or right pan.

So far, i figure out 1,3,9,27,81.. is actually a ternary number system(3^n). And also to find N, i need to make the both pan to balance.

Beside i saw the pattern of remove coin 1,next step wiil be adding coin 1 to right. Eg.
Left Right
1+3+5 ; 9 (N = 5)
3+6 ; 9 (remove coin 1 from left) (N=6)
7 ; 1+9 (adding coin 1 from right) (N=7)

This repeated algorithm can be used for N=3,4; 6,7; 9,10; 12,13; 15,16....
Unfortunately, i can't determine the pattern of N =1,2,5,8,11,14,17...Is too random when it include more than 3 pack of coin.. I can't write the algorithm if I can't found out this.
Please help me~~~

[exomo]

You could use a recursive algorithm to get the coins you need to form every number.
You can find the highest coin you need if you add up all the coins until the sum is higher than the number you want to build.
e.g. n=5: 1<5, 1+3<5, 1+3+9>5 => the 9 has to be on the right side of the scale. The 9 is now you "base value". Next you have to find out what else you need to get to 5. In the example you have to add 4 to the left side. Now use the same algorithm to get the highest coin needed to make 4, calculate the difference and so on ...

I have implemented my algorithm in C++, it prints the coins you have to put on each side of the scale to balance any coins of a given weight n on the left side.

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;

std::pair< vector<int>, vector<int> > getCoins(int n)
{
    std::pair< vector<int>, vector<int> > result;
    if(n==1)
    {
        result.second.push_back(1);

    }
    else
    {
        // find the highest coin needed
        int high = 1;
        int sum = 1;
        while(n > sum)
        {
            high *= 3;
            sum = 3 * sum + 1;
        }
        result.second.push_back(high);
        int diff = n - high;
        if(diff > 0) {
            // get the coins you need for the difference and append them to the result arrays
            std::pair< vector<int>, vector<int> > diffcoins = getCoins(diff);
            result.first.insert(result.first.end(), diffcoins.first.begin(), diffcoins.first.end());
            result.second.insert(result.second.end(), diffcoins.second.begin(), diffcoins.second.end());
        }
        else if(diff < 0) {
            // get the coins you need for the (negative) difference and append them to the opposite sides of the scale
            std::pair< vector<int>, vector<int> > diffcoins = getCoins(-diff);
            result.first.insert(result.first.end(), diffcoins.second.begin(), diffcoins.second.end());
            result.second.insert(result.second.end(), diffcoins.first.begin(), diffcoins.first.end());
        }
    }

    return result;
}

// overloaded << operator to write vectors of any writable type to a stream formated as a list
template <typename T>
ostream& operator<<(ostream& stream, vector<T> list)
{
    stream << "[";
    for(int i=0; i<list.size();++i) stream << list[i] << (i==list.size()-1?"":", ");
    stream << "]";
}

int main()
{
    for(int n=1;n<=100;++n)
    {
        std::pair< vector<int>, vector<int> > coins = getCoins(n);
        cout << n << ":\t" << coins.first << " - " << coins.second << endl;
    }
    return 0;
}

Now if you have an unknown n on the left side, you can make this into a measuring algorithm. Put coins to the right side, starting with 1, 3, 9, ... until the scale turns right (how do you say this in english?). Then start removing coins from the right side, start at the second highest and go down to 1. If you can remove all the coins, start adding coins to the left ...