Question

3.(использовать рекурсию) Даны числа a и b. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом. Паскаль!!!

Answer 1

Ответ:

• var a,b,c: integer;
• procedure f(a1,b1,c1: integer);
• begin
• if (a1=a) and (b1=b) then c:=c+1;
• if (a1<>a) and (c1<>0) then f(a1+1,b1,0);
• if b1<>b then f(a1,b1+1,1);
• end;
• begin
• Read(a,b);
• f(0,0,10);
• Write(c);
• end.

Пример работы:

0110 1010 0101

Answer 2

Для решения этой задачи с использованием рекурсии можно воспользоваться тем фактом, что последовательность из a нулей и b единиц, в которой никакие два нуля не стоят рядом, может начинаться либо с нуля, либо с единицы. Если она начинается с нуля, то оставшаяся часть должна быть последовательностью из (a - 1) нулей и b единиц. Если она начинается с единицы, то оставшаяся часть должна быть последовательностью из a нулей и (b - 1) единиц.

Следовательно, количество таких последовательностей можно выразить через рекурсивное соотношение:

cssCopy code
count(a, b) = count(a - 1, b) + count(a, b - 1)

где count(a, b) - количество последовательностей из a нулей и b единиц.

Базовые случаи:

scssCopy code
count(0, b) = 1  # Если нет нулей, то есть только одна последовательность - из единиц
count(a, 0) = 1  # Если нет единиц, то есть только одна последовательность - из нулей

Вам также понадобится остановить рекурсию, когда a или b становятся отрицательными числами.

Пример кода на языке Pascal:

pascalCopy code
function CountSequences(a, b: Integer): Integer;
begin
  if (a = 0) or (b = 0) then
    Result := 1
  else
    Result := CountSequences(a - 1, b) + CountSequences(a, b - 1);
end;

Вызов функции CountSequences(a, b) вернет количество последовательностей из a нулей и b единиц, где никакие два нуля не стоят рядом.