Тестовый скрипт для задачи про 12 монет

Опубликовано Aug 14, 2012 в Математика и логика, Олимпиадные задачи, Тестирование (QA) | 4 коммент.

, , , ,

Тестовый скрипт для задачи про 12 монет

В нашем посте для любителей логических задач участник обсуждения Максим придумал интересное программное решение задачи про взвешивание 12 монет.

Предлагается написать на том же C# простейший Unit Test, который автоматически проверит правильность программы, для задачи про взвешивание.

Условие задачи про взвешивание 12 монет

Среди 12 монет есть ровно одна фальшивая. Она отличается от остальных по весу (в какую сторону — неизвестно). Необходимо определить фальшивую монету с помощью аптекарских весов и трёх взвешиваний.  Аптекарские весы позволяют сравнить веса взвешиваемых предметов.

Нужно протестировать код на C# для задачи про 12 монет

enum Mark //Метка подлинности
{
    None,   //Неизвестно
    Light,  //Предположительно легче
    Heavy,  //Предположительно тяжелее
    Real    //Точно настоящая
}
struct Coin
{
    public float Weight { get; set; }
    public Mark Mark { get; set; }
}
//Взвешивает группы монет и возвращает "1" если 1-я группа больше 2-й,
// "-1" если меньше и "0" если равны.
int Weigh(Coin[] left_scale, Coin[] right_scale)
{
    float left_scale_weight = 0;
    foreach (Coin c in left_scale)
        left_scale_weight += c.Weight;
    float right_scale_weight = 0;
    foreach (Coin c in right_scale)
        right_scale_weight += c.Weight;
    if (left_scale_weight == right_scale_weight)
        return 0;
    else
    {
        if (left_scale_weight < right_scale_weight)
            return -1;
        else return 1;
    }
}
Coin GetRealCoin(Coin[] coins)
{
    if (coins.Length != 12) throw new Exception("Должно быть ровно 12 монет");
    int first_weighing = Weigh(new Coin[] { coins[0], coins[1], coins[2], coins[3] },
        new Coin[] { coins[4], coins[5], coins[6], coins[7] });
    if (first_weighing == 0)//первое взвешивание -- равны
    {
        //Взвешенные 8 монет точно настояшие
        for (int i = 0; i < 8; ++i)
            coins[i].Mark = Mark.Real;
        //Сравниваем 2 из 4х оставшихся с двумя точно настояшими
        int second_weighing = Weigh(new Coin[] { coins[8], coins[9] },
            new Coin[] { coins[0], coins[1] });
        if (second_weighing == 0)//второе взвешивание -- равны
        {
            //9я и 10я монеты точно настоящие
            coins[8].Mark = coins[9].Mark = Mark.Real;
            //Взвешиваем одну из 2х оставшихся с точно настоящей
            int third_weighing = Weigh(new Coin[] { coins[10] },
                new Coin[] { coins[0] });
            if (third_weighing == 0)//третье взвешивание -- равны
            {
                coins[10].Mark = Mark.Real;
                //Последняя фальшивая, но к сожелению мы не можем
                //сказать тяжелее она или легче
                return coins[11];
            }
            else //третье взвешивание -- не равны
            {
                //следовательно взвешенная монета фальшивая
                coins[11].Mark = Mark.Real;//оставшаяся
                if (third_weighing == -1)//исследуемая монета легче
                {
                    coins[10].Mark = Mark.Light;
                    return coins[10];
                }
                else //исследуемая монета тяжелее
                {
                    coins[10].Mark = Mark.Heavy;
                    return coins[10];
                }
            }
        }
        else //второе взвешивание -- не равны
        {
            //оставшиеся монеты точно настоящие
            coins[10].Mark = coins[11].Mark = Mark.Real;
            if (second_weighing == -1)//исследуемые(9,10) монеты легче
            {
                coins[8].Mark = coins[9].Mark = Mark.Light;
            }
            else //исследуемые монеты(9,10) тяжелее
            {
                coins[8].Mark = coins[9].Mark = Mark.Heavy;
            }
            int third_weighing = Weigh(new Coin[] { coins[8] },
                new Coin[] { coins[0] });
            if (third_weighing == 0)//3е взвешивание -- равны
            {
                coins[8].Mark = Mark.Real;
                return coins[9];
            }
            else //3е взвешивание -- не равны
            {
                coins[9].Mark = Mark.Real;
                return coins[8];
            }
        }
    }
    else //первое взвешивание -- не равны
    {
        for(int i = 8; i < 12; ++i)//оставшиеся
            coins[i].Mark = Mark.Real;
        if (first_weighing == -1)//легче
        {
            for (int i = 0; i < 4; ++i)
                coins[i].Mark = Mark.Light;
            for (int i = 4; i < 8; ++i)
                coins[i].Mark = Mark.Heavy;
        }
        else//тяжелее
        {
            for (int i = 0; i < 4; ++i)
                coins[i].Mark = Mark.Heavy;
            for (int i = 4; i < 8; ++i)
                coins[i].Mark = Mark.Light;
        }
 
        //по одной из каждой группы откладываем в сторону(3,7)
        //по одной меняем местами(2,4) и одну заменяем настоящей(6 на 8)
        int second_weighing = Weigh(new Coin[] { coins[0], coins[1], coins[4] },
            new Coin[] { coins[2], coins[5], coins[8] });
        if (second_weighing == 0)//второе взвешивание равны
        {
            //значит все они настоящие(0,1,2,4,5)
            //проблема в оставшихся(3,6,7)
            //взвешиваем 2 из ни одну "легкую" и одну "тяжелую"
            //с двумя точно настоящими
            int third_weighing = Weigh(new Coin[] { coins[3], coins[6] },
                new Coin[] { coins[8], coins[9] });
            if (third_weighing == 0)//третье взвеш. равны
            {
                //фальшивая -- оставшаяся(7)
                for (int i = 0; i < 7; ++i)
                    coins[i].Mark = Mark.Real;
                return coins[7];
            }
            else//третье взвеш. не равны
            {
                //если легче, то фальшивая -- "легкая" и наоборот
                if (third_weighing == first_weighing)
                    return coins[3];
                else return coins[6];
            }
        }
        else//второе взвешивание не равны
        {
            if (second_weighing != first_weighing)
            {
                //если чаши весов встали наоборот, то причина в тех монетах
                //которые мы поменяли местами(2 и 4)
                int thirdd_weiging = Weigh(new Coin[] { coins[2], coins[4] },
                    new Coin[] { coins[8], coins[9] });
                if (thirdd_weiging == first_weighing)
                    return coins[2];
                else return coins[4];
            }
            else//если весы стоят также то причина в 0,1 или 5
            {
                //взвешиваем ону "легкую" и одну "тяжелую" с 2мя настоящими
                int third_weighing = Weigh(new Coin[] { coins[0], coins[5] },
                    new Coin[] { coins[8], coins[9] });
                if (third_weighing == 0)//равны
                    return coins[1];
                else//не равны
                {
                    if (third_weighing == first_weighing)
                        return coins[0];
                    else return coins[5];
                }
            }
        }
    }
}

Автор публикации: