Тестовый скрипт для задачи про 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];
                }
            }
        }
    }
}

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

4 Коммент. : “Тестовый скрипт для задачи про 12 монет”

  1. Гудстейн указал метод определения фальшивой монеты и её типа за n взвешиваний, n≥3, если число монет
    m ≤ ½(3n – 2n + 3) для n=3 количество монет равно 12
    Алгоритм на C++

    #include <iostream.h>
    int main(){
    int m[12]={1,1,1,1,1,1,1,1,1,1, 1, 1};
    int p1,p2,p3,p8;
    if (m[0]+m[4]+m[5]+m[6]==m[2]+m[9]+m[10]+m[11])p3=0;
    if (m[0]+m[4]+m[5]+m[6]>m[2]+m[9]+m[10]+m[11])p3=1;
    if (m[0]+m[4]+m[5]+m[6]<m[2]+m[9]+m[10]+m[11])p3=2;
    if (m[4]+m[7]+m[8]+m[11]==m[1]+m[5]+m[6]+m[10])p2=0;
    if (m[4]+m[7]+m[8]+m[11]>m[1]+m[5]+m[6]+m[10])p2=1;
    if (m[4]+m[7]+m[8]+m[11]<m[1]+m[5]+m[6]+m[10])p2=2;
    if (m[1]+m[2]+m[6]+m[8]==m[3]+m[4]+m[5]+m[9])p1=0;
    if (m[1]+m[2]+m[6]+m[8]>m[3]+m[4]+m[5]+m[9])p1=1;
    if (m[1]+m[2]+m[6]+m[8]<m[3]+m[4]+m[5]+m[9])p1=2;
    p8=p1*9+p2*3+p3;
    switch (p8){
    case 0:{cout << "All Money true"<<endl;break;}
    case 1:{cout << "Money #1 false and heavy"<<endl;break;}
    case 2:{cout << "Money #1 false and light"<<endl;break;}
    case 15:{cout << "Money #2 false and heavy"<<endl;break;}
    case 21:{cout << "Money #2 false and light"<<endl;break;}
    case 11:{cout << "Money #3 false and heavy"<<endl;break;}
    case 19:{cout << "Money #3 false and light"<<endl;break;}
    case 18:{cout << "Money #4 false and heavy"<<endl;break;}
    case 9:{cout << "Money #4 false and light"<<endl;break;}
    case 22:{cout << "Money #5 false and heavy"<<endl;break;}
    case 17:{cout << "Money #5 false and light"<<endl;break;}
    case 25:{cout << "Money #6 false and heavy"<<endl;break;}
    case 14:{cout << "Money #6 false and light"<<endl;break;}
    case 16:{cout << "Money #7 false and heavy"<<endl;break;}
    case 23:{cout << "Money #7 false and light"<<endl;break;}
    case 3:{cout << "Money #8 false and heavy"<<endl;break;}
    case 6:{cout << "Money #8 false and light"<<endl;break;}
    case 12:{cout << "Money #9 false and heavy"<<endl;break;}
    case 24:{cout << "Money #9 false and light"<<endl;break;}
    case 20:{cout << "Money #10 false and heavy"<<endl;break;}
    case 10:{cout << "Money #10 false and light"<<endl;break;}
    case 8:{cout << "Money #11 false and heavy"<<endl;break;}
    case 4:{cout << "Money #11 false and light"<<endl;break;}
    case 5:{cout << "Money #12 false and heavy"<<endl;break;}
    case 7:{cout << "Money #12 false and light"<<endl;break;}
    }
    return 0;
    }
    • Галина says:

      Решение верное. Протестировано, правда на C#, так. Для полного теста скрипт вызывался 2 раза: фальшивая монета легче/тяжелее.

      PS: Оформлять функции стоит все-таки – не все в main помещать.

       
          static void Main(string[] args)
            {
       
              int CoinsNumber = 12;int p1,p2,p3,p8;
       
              int[] m = new int[CoinsNumber];
       
              for (int i = 0; i < CoinsNumber; i++)
              {
       
                for (int j = 0; j < CoinsNumber; j++)
                {
                  m[j] = 10;
                }
       
                m[i] = 2;
       
                p1 = 0; p2 = 0; p3 = 0;
       
                if (m[0] + m[4] + m[5] + m[6] == 
                        m[2] + m[9] + m[10] + m[11]) p3 = 0;
                if (m[0] + m[4] + m[5] + m[6] > 
                        m[2] + m[9] + m[10] + m[11]) p3 = 1;
                if (m[0] + m[4] + m[5] + m[6] < 
                        m[2] + m[9] + m[10] + m[11]) p3 = 2;
                if (m[4] + m[7] + m[8] + m[11] == 
                        m[1] + m[5] + m[6] + m[10]) p2 = 0;
                if (m[4] + m[7] + m[8] + m[11] > 
                        m[1] + m[5] + m[6] + m[10]) p2 = 1;
                if (m[4] + m[7] + m[8] + m[11] < 
                        m[1] + m[5] + m[6] + m[10]) p2 = 2;
                if (m[1] + m[2] + m[6] + m[8] == 
                        m[3] + m[4] + m[5] + m[9]) p1 = 0;
                if (m[1] + m[2] + m[6] + m[8] > 
                        m[3] + m[4] + m[5] + m[9]) p1 = 1;
                if (m[1] + m[2] + m[6] + m[8] < 
                        m[3] + m[4] + m[5] + m[9]) p1 = 2;
       
                p8 = p1 * 9 + p2 * 3 + p3;
                  switch (p8)
                {
                  case 0: { Console.WriteLine("All Money true"); break; }
                  case 1: { Console.WriteLine("Money #1 false and heavy"); break; }
                  case 2: { Console.WriteLine("Money #1 false and light"); break; }
                  case 15: { Console.WriteLine("Money #2 false and heavy"); break; }
                  case 21: { Console.WriteLine("Money #2 false and light"); break; }
                  case 11: { Console.WriteLine("Money #3 false and heavy"); break; }
                  case 19: { Console.WriteLine("Money #3 false and light"); break; }
                  case 18: { Console.WriteLine("Money #4 false and heavy"); break; }
                  case 9: { Console.WriteLine("Money #4 false and light"); break; }
                  case 22: { Console.WriteLine("Money #5 false and heavy"); break; }
                  case 17: { Console.WriteLine("Money #5 false and light"); break; }
                  case 25: { Console.WriteLine("Money #6 false and heavy"); break; }
                  case 14: { Console.WriteLine("Money #6 false and light"); break; }
                  case 16: { Console.WriteLine("Money #7 false and heavy"); break; }
                  case 23: { Console.WriteLine("Money #7 false and light"); break; }
                  case 3: { Console.WriteLine("Money #8 false and heavy"); break; }
                  case 6: { Console.WriteLine("Money #8 false and light"); break; }
                  case 12: { Console.WriteLine("Money #9 false and heavy"); break; }
                  case 24: { Console.WriteLine("Money #9 false and light"); break; }
                  case 20: { Console.WriteLine("Money #10 false and heavy"); break; }
                  case 10: { Console.WriteLine("Money #10 false and light"); break; }
                  case 8: { Console.WriteLine("Money #11 false and heavy"); break; }
                  case 4: { Console.WriteLine("Money #11 false and light"); break; }
                  case 5: { Console.WriteLine("Money #12 false and heavy"); break; }
                  case 7: { Console.WriteLine("Money #12 false and light"); break; }
                }
      }
      • #include <iostream>
        #include <string>
        using namespace std;
         
        #define weighting1 	if (m[0]+m[4]+m[5]+m[6]==m[2]+m[9]+m[10]+m[11])p3=0;\
        					if (m[0]+m[4]+m[5]+m[6]> m[2]+m[9]+m[10]+m[11])p3=1;\
        					if (m[0]+m[4]+m[5]+m[6]< m[2]+m[9]+m[10]+m[11])p3=2;
         
        #define weighting2 	if (m[4]+m[7]+m[8]+m[11]==m[1]+m[5]+m[6]+m[10])p2=0;\
        					if (m[4]+m[7]+m[8]+m[11]> m[1]+m[5]+m[6]+m[10])p2=1;\
        					if (m[4]+m[7]+m[8]+m[11]< m[1]+m[5]+m[6]+m[10])p2=2;
         
        #define weighting3 	if (m[1]+m[2]+m[6]+m[8]==m[3]+m[4]+m[5]+m[9])p1=0;\
        					if (m[1]+m[2]+m[6]+m[8]> m[3]+m[4]+m[5]+m[9])p1=1;\
        					if (m[1]+m[2]+m[6]+m[8]< m[3]+m[4]+m[5]+m[9])p1=2;
         
        //class of coin
        class Coin{
        public:
        	Coin(){SetI(-1);SetS("null");}
        	int GetI(){return i;}
        	string GetS(){return s;}
        	void SetI(int set_i){i=set_i;}
        	void SetS(string set_s){s=set_s;}
        private:
        	int i;//index of false coin
        	string s;//property money (light or heavy)
        };
         
        //class of etalon coins 
        class Coins {
        	public:
        		Coins();
        		Coin etalon[27];
        };
         
        //constructor of etalon class
        Coins::Coins()
        {
        	int i,p1,p2,p3,p;
        	int m[12]={1,1,1,1,1,1,1,1,1,1,1,1};
        	string s;
         
        //fill etalon for coin light
        	s="light";
        	for (i=0;i<12;i++){
        		m[i]=0;//coin number i - light
        		weighting1;		weighting2;		weighting3;
        		p=p1*9+p2*3+p3;//unique kod after weighting, transfer from figurative system in the decimal
        		etalon[p].SetI(i);//fill etalon number coins
        		etalon[p].SetS(s);//fill condition - light
        		m[i]=1;//return coin number i in initial condition
        	}
        //fill etalon for coin heavy
        	s="heavy";
        	for (i=0;i<12;i++){
        		m[i]=2;// coin number i-heavy
        		weighting1;		weighting2;		weighting3;
        		p=p1*9+p2*3+p3;//unique kod after weighting, transfer from figurative system in the decimal
        		etalon[p].SetI(i);//fill etalon number coins
        		etalon[p].SetS(s);//fill condition - heavy
        		m[i]=1;//return coin number i initial condition
        	}
        }
         
        int main(){
        	Coins E;
        	int p1,p2,p3,p;
        //index of coin:0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11
        	int m[12]={ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};//array of coins test
         
        	weighting1;	weighting2;	weighting3;
         
        	p=p1*9+p2*3+p3;//unique kod after weighting, transfer from figurative system in the decimal
         
        	if (p!=0) cout<<"Code - "<<p<< ".  Coin number - "<<E.etalon[p].GetI() << " false - "<<E.etalon[p].GetS() <<endl;
        	else cout << "All coins true"<<endl;
         
        /*	
        	cout << "---------Etalon value "<<endl;
        	for (int i=0;i<27;i++) if (E.etalon[i].GetI()!=-1) cout << "Etalon code - "<<i<< ".  Coin number - "<<E.etalon[i].GetI() << " false - "<<E.etalon[i].GetS() <<endl;
        */	
         
        	return 0;
        }
  2. на с#

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
     
    namespace Coin12
    {
        class Coin
        {
            private int i; //index false coin
            private string s;//property coin (light or heavy)
            public Coin() { this.i = -1; this.s = "null"; }
            public int I 
            {
                set { i = value;}
                get {return i;} 
            }
            public string S 
            {
                set { s = value; }
                get { return s; } 
            }
        }
     
        class Coins
        {
            public Coin[] etalon=new Coin[27]; // array etalon codes for coin
     
            public Coins()
            {
                int p1, p2, p3, p, i;
                int[] m = new int[12];
                for (i = 0; i < 27;i++ ) { etalon[i] = new Coin(); }
     
                for (i = 0; i < 12; i++) { m[i] = 1; }//initial condition all coin even
     
                //coin - light
                for (i = 0; i < 12; i++)
                {
                    m[i] = 0;//coin number i - light
                    //Weigthing 1
                    p1 = -1; p2 = -1; p3 = -1;
                    if (m[0] + m[4] + m[5] + m[6] == m[2] + m[9] + m[10] + m[11]) p3 = 0;
                    if (m[0] + m[4] + m[5] + m[6] > m[2] + m[9] + m[10] + m[11]) p3 = 1;
                    if (m[0] + m[4] + m[5] + m[6] < m[2] + m[9] + m[10] + m[11]) p3 = 2;
     
                    //Weigthing 2
                    if (m[4] + m[7] + m[8] + m[11] == m[1] + m[5] + m[6] + m[10]) p2 = 0;
                    if (m[4] + m[7] + m[8] + m[11] > m[1] + m[5] + m[6] + m[10]) p2 = 1;
                    if (m[4] + m[7] + m[8] + m[11] < m[1] + m[5] + m[6] + m[10]) p2 = 2;
     
                    //Weigthing 3
                    if (m[1] + m[2] + m[6] + m[8] == m[3] + m[4] + m[5] + m[9]) p1 = 0;
                    if (m[1] + m[2] + m[6] + m[8] > m[3] + m[4] + m[5] + m[9]) p1 = 1;
                    if (m[1] + m[2] + m[6] + m[8] < m[3] + m[4] + m[5] + m[9]) p1 = 2;
     
                    p = p1 * 9 + p2 * 3 + p3;//unique kod after weighting, transfer from figurative system in 
     
                    etalon[p].I = i;//fill etalon number coins
                    etalon[p].S = "light";//fill condition - light
                    m[i] = 1;//return coin number i in initial condition
     
                }
     
                //coin - heavy
                for (i = 0; i < 12; i++)
                {
                    m[i] = 2;//coin number i - heavy
                    //Weigthing 1
                    p1 = -1; p2 = -1; p3 = -1;
                    if (m[0] + m[4] + m[5] + m[6] == m[2] + m[9] + m[10] + m[11]) p3 = 0;
                    if (m[0] + m[4] + m[5] + m[6] > m[2] + m[9] + m[10] + m[11]) p3 = 1;
                    if (m[0] + m[4] + m[5] + m[6] < m[2] + m[9] + m[10] + m[11]) p3 = 2;
     
                    //Weigthing 2
                    if (m[4] + m[7] + m[8] + m[11] == m[1] + m[5] + m[6] + m[10]) p2 = 0;
                    if (m[4] + m[7] + m[8] + m[11] > m[1] + m[5] + m[6] + m[10]) p2 = 1;
                    if (m[4] + m[7] + m[8] + m[11] < m[1] + m[5] + m[6] + m[10]) p2 = 2;
     
                    //Weigthing 3
                    if (m[1] + m[2] + m[6] + m[8] == m[3] + m[4] + m[5] + m[9]) p1 = 0;
                    if (m[1] + m[2] + m[6] + m[8] > m[3] + m[4] + m[5] + m[9]) p1 = 1;
                    if (m[1] + m[2] + m[6] + m[8] < m[3] + m[4] + m[5] + m[9]) p1 = 2;
     
                    p = p1 * 9 + p2 * 3 + p3;//unique kod after weighting, transfer from figurative system in 
     
                    etalon[p].I = i;//fill etalon number coins
                    etalon[p].S = "light";//fill condition - light
                    m[i] = 1;//return coin number i in initial condition
                }
            }
     
            public void Print() 
            {
                Console.WriteLine("****************Etalon codes******************");
                for (int i = 0; i < 27; i++)
                    if(etalon[i].I!=-1) 
                    {
                        Console.Write("Code - ");
                        Console.Write(i);
                        Console.Write(".  Coin number - ");
                        Console.Write(etalon[i].I);
                        Console.Write(" false - ");
                        Console.WriteLine(etalon[i].S); 
                    }
            }
        }
     
        class Program
        {
            static int Main(string[] args)
            {
                Coins E = new Coins();
                int p1, p2, p3, p, i;
                int[] m = new int[12];
                for (i = 0; i < 12; i++) { m[i] = 1; }
     
                m[0] = 2; //test coin
     
                //Weigthing 1
                p1 = -1; p2 = -1; p3 = -1;
                if (m[0] + m[4] + m[5] + m[6] == m[2] + m[9] + m[10] + m[11]) p3 = 0;
                if (m[0] + m[4] + m[5] + m[6] > m[2] + m[9] + m[10] + m[11]) p3 = 1;
                if (m[0] + m[4] + m[5] + m[6] < m[2] + m[9] + m[10] + m[11]) p3 = 2;
     
                //Weigthing 2
                if (m[4] + m[7] + m[8] + m[11] == m[1] + m[5] + m[6] + m[10]) p2 = 0;
                if (m[4] + m[7] + m[8] + m[11] > m[1] + m[5] + m[6] + m[10]) p2 = 1;
                if (m[4] + m[7] + m[8] + m[11] < m[1] + m[5] + m[6] + m[10]) p2 = 2;
     
                //Weigthing 3
                if (m[1] + m[2] + m[6] + m[8] == m[3] + m[4] + m[5] + m[9]) p1 = 0;
                if (m[1] + m[2] + m[6] + m[8] > m[3] + m[4] + m[5] + m[9]) p1 = 1;
                if (m[1] + m[2] + m[6] + m[8] < m[3] + m[4] + m[5] + m[9]) p1 = 2;
     
                p = p1 * 9 + p2 * 3 + p3;
     
                if (p != 0)
                {
                    Console.Write("Code - ");
                    Console.Write(p);
                    Console.Write(".  Coin number - ");
                    Console.Write(E.etalon[p].I);
                    Console.Write(" false - ");
                    Console.WriteLine(E.etalon[p].S); 
                }
                else Console.WriteLine("All coins true");
     
                E.Print();
                Console.ReadLine(); 
                return 0; 
            }
        }
    }

Оставить комментарий

Ваш адрес email не будет опубликован.


*