Задача 2.
Вокруг считающего стоит N человек, из которых выделен первый, а остальные занумерованы по часовой стрелке числами от 2 до N. Считающий, начиная с кого-то, ведет счет до M. Человек на котором остановился счет, выходит из круга. Счет продолжается со следующего человека и так до тех пор, пока не останется один человек.
Определить
a) номер оставшегося человека, если известно M и то, что счет начинался с первого человека;
b) номер человека c которого начинался счет, если известно M и номер оставшегося человека L.
|
Решение задачи 2.
Для решения этой задачи используем структуру данных 'список'. Каждый элемент списка указывает на следующий за ним элемент (другими словами - хранит информацию о расположении следующего элемента).
a). Заведем массив A из N ячеек - по числу людей в круге. В каждую из ячеек A[i] занесем номер стоящего следующим за i-ым человека. Первоначально A[i]=i+1, i=1,...,.N-1, A[N]=1. Начиная счет от текущего человека (человека с номером IndTek, с самого сначала IndTek=1) будем делать ход - отсчитывать M ячеек, двигаясь по кругу в поисках человека, который должен выйти из круга. С учетом определения массива A это будет выглядеть следующим образом:
{IndTek - это номер человека, с которого начинается счет}
for i:=1 to M-1 do {Отсчитываем M человек, начиная с IndTek}
begin
IndPred:=IndTek; {в IndPred сохраняем номер текущего человека в круге}
IndTek:=A[IndTek]; {и вычисляем номер следующего за ним}
end;
После выполнения этого цикла в переменной IndTek будет номер человека, на котором остановился счет (т.е. номер человека, который покинул круг), а в переменной IndPred - номер предшествующего ему человека в круге.
Удалим человека с номером IndTek. Для этого мы просто изменим ссылку A[IndPred] у предшествующего ему человека так, чтобы он указывал не на IndTek, а на следующего за IndTek, т.е. на A[IndTek], и новый отсчет M-того человека начнем со следующего за удаленным:
A[IndPred]:=A[IndTek];
IndTek:=A[IndTek];{Новый номер начального человека}
Все вышеописанные операции мы будем повторять до тех пор, пока в круге не останется одного единственного человека, т.е. до тех пор, пока A[IndTek] не станет равным IndTek, что означает, что следующим за человеком с номером IndTek является он сам.
Полностью весь фрагмент программы будет выглядеть так:
{Инициализация массива A}
for i:=1 to N-1 do
A[i]:=i+1;
A[N]:=1;
{IndTek - это номер человека, с которого начинается счет}
IndTek:=1;
while A[IndTek] <> IndTek do
begin
for i:=1 to M-1 do {Отсчитываем M человек, начиная с IndTek}
begin
IndPred:=IndTek; {в IndPred сохраняем номер текущего человека в круге}
IndTek:=A[IndTek]; {и вычисляем номер следующего за ним}
end;
A[IndPred]:=A[IndTek];
IndTek:=A[IndTek]; {Новый номер начального человека}
end;
writeln('Номер последнего оставшегося человека ',IndTek);
Решения пункта b).
Будем считать, что человек с номером N+i - это то же самое, что и человек с номером i.
Предположим, что как и в пункте a), что мы начали счет с первого человека, выбрасывали из круга M-того, и последний оставшийся в круге человек имеет номер K. Очевидно, что если бы мы начали счет со второго человека, то последний оставшийся в круге человек имел бы номер K+1, ..., если с j-го, то K+j-1.
Если номер оставшегося человека L, то из равенства L=K+j-1 определяем номер j первого человека (если j<=0, то заменим j на j+N, считая как и раньше, что человек с номером N+j - это то же самое, что и человек с номером j).
|
