Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат три кучи камней. Иг-роки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в три раза. Например, пусть в первой куче 10 камней, во второй 7, а в третьей 4 камня; такую позицию в игре будем обозначать (10, 7, 4). Тогда за один ход можно получить любую из шести позиций: (12, 7, 4), (30, 7, 4), (10, 9, 4), (10, 21, 4), (10, 7, 6), (10, 7, 12). Для того чтобы делать ходы, у каждого игрока есть не-ограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 57. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что в кучах всего будет 57 или больше камней.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Задание 1. Для каждой из начальных позиций (10, 7, 13), (9, 12, 10) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, по-чему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 2. Для каждой из начальных позиций (12, 7, 10), (7, 11, 10) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, по-чему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 3. Для начальной позиции (10, 10, 7) укажите, кто из игроков имеет выигрышную стра-тегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выиг-рыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами вы-игрышной стратегии. Представьте дерево в виде рисунка или таблицы.
procedure MatInput(a:array[,] of integer);
begin
Writeln('Вводите элементы матрицы построчно, в конце нажимая Enter');
for var i:=0 to Length(a,0)-1 do begin
Write(i+1,': ');
for var j:=0 to Length(a,1)-1 do Read(a[i,j]);
end
end;
procedure MatPrint(a:array[,] of integer);
begin
for var i:=0 to Length(a,0)-1 do begin
for var j:=0 to Length(a,1)-1 do Print(a[i,j]);
Writeln
end
end;
function IsEqual(a:array[,] of integer; j1,j2:integer;
flag:array of boolean):boolean;
// равны ли столбцы с индексами j1 и j2
begin
if flag[j2]=False then begin
Result:=True;
for var i:=0 to Length(a,0)-1 do
if a[i,j1]<>a[i,j2] then begin Result:=False; Break end;
flag[j2]:=Result
end
end;
begin
var n:=ReadInteger('Задайте число строк (столбцов) матрицы:');
var a:array[,] of integer;
var m:=ArrFill(n,False);
SetLength(a,n,n);
MatInput(a);
Writeln('*** Принятая матрица ***');
MatPrint(a);
var k:=1;
for var i:=0 to n-2 do
for var j:=i+1 to n-1 do
if IsEqual(a,i,j,m) then Inc(k);
if k>1 then Writeln('Количество совпадающих столбцов равно ',k)
else Writeln('нет совпадающих столбцов')
end.
Тестовое решение
Задайте число строк (столбцов) матрицы: 3
Вводите элементы матрицы построчно, в конце нажимая Enter
1: 1 2 2
2: 3 5 5
3: 2 2 2
*** Принятая матрица ***
1 2 2
3 5 5
2 2 2
Количество совпадающих столбцов равно 2
1) разбить все столбцы на группы одинаковых столбцов и посчитать внутри них число пар. Затем суммировать.
2) разбить столбцы на группы одинаковых столбцов и суммировать количество элементов в каждой из групп, если оно больше 1. То есть найти количество столбцов, для которых среди других столбцов найдется хотя бы один идентичный ему
3) разбить столбцы на группы одинаковых столбцов и вывести количество элементов в каждой группе, если оно больше 1.
Для n=3 дело проще, потому что таких групп максимум одна, поэтому тут, по сути, неоднозначности не возникает (за исключением того, что в первом пункте...)
В общем, решил делать как во втором пункте. ответ в любом случае будет верным.*/
#include <iostream>
using namespace std;
int n, result = 0;
int **ar;//указатель на указатель для создания динамического двумерного массива
bool *Flag;//указатель на первый элемент массива флагов
void create(int n)//создание динамического массива
{
ar = new int*[n];
for (int i = 0; i < n; i++)
ar[i] = new int[n];
Flag = new bool[n];
for (int i = 0; i < n; i++)
Flag[i] = false;
}
void inp(int n) //ввод элементов массива
{
cout << "Input rows of matrix:\n";
for (int i = 0; i < n; i++)
{
cout << i + 1 << ": ";
for (int j = 0; j < n; j++)
cin >> ar[i][j];
}
}
void outp(int n) //вывод элементов массива
{
cout << "Elements of matrix:\n";
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << ar[i][j] << " ";
cout << endl;
}
}
bool isEqual(int n, int j1, int j2)//проверка на равенство столбцов
{
bool res = true;
for (int i = 0; i < n; i++)
{
if (ar[i][j1] != ar[i][j2])
{
res = false;
break;
}
}
if (res)//если столбцы равны
Flag[j2] = true; /*отмечаем столбец как просмотренный, чтобы в следующий раз его не сравнивать с другими столбцами*/
return res;
}
void calculate(int n)//считаем количество совпадающих столбцов
{
int k = 1;
for (int j1 = 0; j1 < n; j1++)
if (!Flag[j1])
{
k = 1;
for (int j2 = j1 + 1; j2 < n; j2++)
if (!Flag[j2] && isEqual(n, j1, j2))
k++;
if (k > 1)//имеется k одинаковых стобцов по типу столбца j1
result += k;//плюсует к итоговому результату
}
}
int main(){
cout << "Input n: ";
cin >> n;
create(n);
inp(n);//ввод массива
outp(n);//вывод массива
calculate(n);//расчет того, что требуется
if (result > 0)/*количество столбцов, которые совпадают, по крайней мере, с одним из других столбцов*/
cout << "The number of columns, coinciding with at least one other column, is " << result << endl;
else //все столбцы разные
cout << "There is no matching columns\n";
return 0;
}