Є n монет (2<n<32000), серед яких одна фальшива, ваща чи легша - не відомо. Скласти прграму, що обчислить скільки необхідно найменше зважувань, щоб відшукати цю монету. Фактор випадковості не враховувати.
Вхідні дані для тесту:
Monet.dat
12
Вихідні дані:
Monet.sol
3

Бажаю успіху!

#include <iostream>
#include <fstream>
#define n 13 //Не используем нулевой индекс
using namespace std;
int main ()
{
int p[n],i,j,k;
string t;
fstream fin;
fin.open ("moneta.dat", ios::in); //проверка открытия файла
if (!fin)
{
cout << "No file...";
system ("PAUSE");
exit (-1);
} //=======================================================
for (i = 1; i < n; i++) fin >> p[i]; //чтение веса
fin.close();
//========================= Взвесим по 4 1-й вариант ============
if ((p[1]+p[2]+p[3]+p[4]) == (p[5]+p[6]+p[7]+p[8])) //1 a vzveshifnie
{
if ((p[9]+p[10]+p[11]) == (p[1]+p[2]+p[3])) //2 a.1(variant)
{
k = 12;
if (p[12]>p[1]) t = "Tiagelei "; //3 a.1
else if (p[12]<p[1]) t = "Legche ";
}
else if ((p[9]+p[10]+p[11]) > (p[1]+p[2]+p[3])) //2 a.2
{
t = "Tiagelei ";
if (p[9] > p[10]) k = 9; //3 a.2
else if (p[9] < p[10]) k = 10;
else k = 11;
}
else //2 a.3
{
t = "Legche ";
if (p[9] < p[10]) k = 9; //3 a.3
else if (p[9] > p[10]) k = 10;
else k = 11;
}
}
//========================= Взвесим по 4 2-й вариант =================
else if ((p[1]+p[2]+p[3]+p[4]) > (p[5]+p[6]+p[7]+p[8])) //1 b
{
if ((p[1]+p[2]+p[9]) == (p[3]+p[4]+p[5])) //2 b.1
{
t = "Legche ";
if (p[6] < p[7]) k = 6; //3 b.1
else if (p[6] > p[7]) k = 7;
else k = 8;
}
else if ((p[1]+p[2]+p[9]) < (p[3]+p[4]+p[5])) //2 b.2
{
if (p[3] == p[4]){k=5;t = "Legche ";} //3 b.2
else if (p[3] > p[4]) {k=3; t = "Tiagelei ";}
else {k = 4; t = "Tiagelei ";}
}
else if ((p[1]+p[2]+p[9]) > (p[3]+p[4]+p[5])) //2 b.3
{
if (p[1] == p[2]){k=5;t = "Legche ";} //3 b.3
else if (p[1] > p[2]) {k=1; t = "Tiagelei ";}
else {k = 2; t = "Tiagelei ";}
}
}
//========================= Взвесим по 4 3-й вариант =================
else if ((p[1]+p[2]+p[3]+p[4]) < (p[5]+p[6]+p[7]+p[8])) //1 c
{
if ((p[1]+p[2]+p[9]) == (p[3]+p[4]+p[5])) //2 c.1
{
t = "Tiagelei ";
if (p[6] < p[7]) k = 7; //3 c.1
else if (p[6] > p[7]) k = 6;
else k = 8;
}
else if ((p[1]+p[2]+p[9]) < (p[3]+p[4]+p[5])) //2 c.2
{
if (p[1] == p[2]){k=5;t = "Tiagelei ";} //3 c.2
else if (p[1] > p[2]) {k=2; t = "Legche ";}
else {k = 1; t = "Legche ";}
}
else if ((p[1]+p[2]+p[9]) > (p[3]+p[4]+p[5])) //2 c.3
{
if (p[3] == p[4]){k=5;t = "Legche ";} //3 c.3
else if (p[3] > p[4]) {k=4; t = "Legche ";}
else {k = 3; t = "Legche ";}
}
}
fstream fout;
fout.open ("moneta.sol", ios::out);
if (!fin)
{
cout << "No file...";
system ("PAUSE");
exit (-1);
}
fout<<t<<k;
/*cout<<t<<k<<endl;
system ("PAUSE");*/
return 0;
}
//Протестировано на Dev-C++ и Builder 6.0 (для В_3.1_С++ изменить начало)

в принципі правильно (є деякі нюанси), а тепер ускладнимо точно знаємо шо таких стінок є декілька. потрібно знайти ту, шлях через яку буде найкоротший.

Это уже за дополнительную плату...
(Будет время подумаю.)
_______
dpi

тут і думати немає чого. принцип такий - за одне зважування відкинути найбільшу масу монет. це можливо коли ми поділимо всі монети на три кучки і дві з них зважимо (важимо однакові кучки). в залежності від результатів зважування залишаємо одну з трьох (тобто відкидаємо приблизно 1/3 монет) і так ділі...
приклад:
є 100 монет
100=33+33+34
1 зважування - важимо перших 33 і других 33 після зважування залишаємо або 33 або 34
візьмемо 34=11+11+12
2 зважуваня важимо перших 11 і других 11 після зважування залишаємо або 11 або 12
візьмемо 12=4+4+4
3 зважування - важимо перших 4 і других 4 після зважування залишаємо 4
візьмемо 4=1+1+2
4 зважування - важимо першу 1 і другу 1 після зважування залишаємо або 1 або 2
візьмемо 2=1+1
5 зважування - важимо першу 1 і другу 1 після зважування залишаємо 1

а тепер рахуємо кількість зважувань
1 100:3=34 (заокр до більшого)
2 34:3=12 (заокр до більшого)
3 12:3=4 (заокр до більшого)
4 4:3=2 (заокр до більшого)
5 2:3=1 (заокр до більшого)
от вам і кількість зважувань.
тепер узагальнюємо для N.

N ділимо на 3 (рез заокр до більшого) результат ділимо на 3 і так далі поки не отримаємо 1. кількість ділень і буде кількість зважувань.

Тут ы заокруглювати не тра!!!