Я понял и вполне достаточно. Зайцам привет!Swetlana писал(а):Source of the post алгоритм с возвратом с отсечением заведомо неподходящих вариантов ...
PS. В смысле код не обязателен. Мне достаточно к какому типу относиться.
Я понял и вполне достаточно. Зайцам привет!Swetlana писал(а):Source of the post алгоритм с возвратом с отсечением заведомо неподходящих вариантов ...
Код: Выбрать все
program NT;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
N = 4; //количество цифр
var
//текущий код, код-решение и загаданный код
X,OptX,X0: array [1..N] of integer;
i: integer;
MinS, MaxS: integer; //минимальная и максимальная допустимая сумма цифр
flag: boolean; //нашли решение
Sum9: integer; //сумма N девяток
procedure search (i,sum,poss: integer);
//i - текущая позиция
//sum - сумма цифр с первой по i-1 -ю позиции
//poss - максимальная сумма, которую получим,
//если все оставшиеся пустые позиции заполним девятками
var
j,k: integer;
mm: integer;
begin
if not(flag) then begin
for j:= 0 to 9 do //выбор цифры для заполнения i-й позиции кода
begin
//проверка допустимости цифры
//если текущая сумма + j >= MaxS, нет смысла увеличивать j
//если poss, максимально возможная сумма, <= MinS, нет смысла продолжать подбор
//поэтому по break выходим из цикла, выходим из рекурсии для i-й позиции
//и возвращаемся на рекурсию для предыдущей i-1-й позиции
if (sum+j >= MaxS) OR (poss-9+j <= MinS) then break;
if i < N then //не последняя цифра
begin
X[i]:= j;
search(i+1,sum+j,poss-9+j);
end
else if i=N then//последняя цифра
begin //проверка на полное решение
X[i]:= j;
flag:= true;
for k:=1 to N do
if X0[k]<>X[k] then flag:= false;
if flag then //нашли решение
begin
for k:= 1 to N do OptX[k]:= X[k];
exit;
end;
end
end;
end;
end; //search
begin //main
//задаём код 1234
X0[1]:= 1; X0[2]:= 2; X0[3]:= 3; X0[4]:= 4;
//задаём минимальную и максимальную сумму цифр
MinS:= 5; MaxS:= 20;
//инициализация текущего и оптимального решения
for i:= 1 to N do
begin X[i]:= -1; OptX[i]:= -1; end;
flag:= false; //решение не найдено
Sum9:= 9*N;
//вызов рекурсии для заполнения 1-й цифры кода
//текущая сумма кодовых цифр равна 0
//по максимуму можно набрать сумму всех девяток
search(1,0,Sum9);
//печать решения
for i:= 1 to N do write(OptX[i],' ');
writeln; readln;
end.
Код: Выбрать все
if (sum+j >= MaxS) then break;
if (poss-9+j <= MinS) then continue;
Код: Выбрать все
procedure search (i,sum,poss,b: integer);
...
for j:= b to 9 do begin
...
search(i+1,sum+j,poss-9+j, j);
alexBlack писал(а):Source of the post
По второму условию нельзя прерывать, т.к. при следующем j условие может выполняться.
Код: Выбрать все
if (sum+j >= MaxS) OR (poss <= MinS) then break;
...
search(i+1,sum+j,poss-9+j);
Можно уменьшить пространство поиска, если ввести ограничение "каждая следующая цифра не меньше предыдущей"
Swetlana писал(а):Source of the post
раз вы предлагаете новую задачу - подбор n-значного цифрового кода при условии, что каждая цифра не меньше предыдущей, оцените размер пространства поиска, сколько различных кодов мы можем загадать при таких условиях
Вернуться в «Computer Science»
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 2 гостей