Образовательный портал Павла Добряка

8. ЗАКОНОМЕРНОСТИ, ПРОГРЕССИИ И РЕКУРСИИ

Мы встретили много задач на поиск закономерностей, прогрессии и рекурсии. Объединим их усложненные варианты в этой главе и добавим несколько олимпиадных задач. Хотя обучение программированию не входит в задачи этой книги (этому посвящена другая книга автора), тем не менее, начнем эту главу с задач на программирование, как наиболее простых. Предполагается, что читатель знаком с такими языковыми конструкциями, как условия, массивы, циклы и функции, на одном из алгоритмических языков. Если нет, вы можете почитать ход решения. Если программы по-прежнему будут вам непонятны, то  можете пропустить два параграфа с задачами на программирование.

8.1. Программы с прогрессиями

Задача 8.1.1. Определите, что будет напечатано в результате выполнения программы, записанной ниже на разных языках программирования.

Бейсик

Python

DIM N, S AS INTEGER

 N = 1

 S = 0

 WHILE N <= 1000

    S = S + 30

    N = N * 2

 WEND

 PRINT S

n = 1

s = 0

while n <= 1000:

    s = s + 30

    n = n * 2

print(s)

Паскаль

Алгоритмический язык

var n, s: integer;

begin

    n := 1;

    s := 0;

    while n <= 1000 do

    begin

        s := s + 30;

        n := n * 2

    end;

    write(s)

end.

алг

нач

цел n, s

n := 1

s := 0

нц пока n <= 1000

    s := s + 30

    n := n * 2

кц

вывод s

кон

Си++

#include <iostream>

using namespace std;

int main()

{

    int n, s;

    n = 1;

    s = 0;

    while (n <= 1000)

    {

        s = s + 30;

        n = n * 2;

    }

    cout « s « endl;

}

Задача 8.1.2. Определите, что будет напечатано в результате работы следующего фрагмента программы:

Бейсик

Python

DIM K, S AS INTEGER

 S = 0

 K = 1

 WHILE S < 1000

    K = K + 3

    S = S + K

WEND

PRINT K

s = 0

k = 1

while s < 1000:

    k += 3

    s += k

print(k)

Паскаль

Алгоритмический язык

var k, s: integer;

begin

       s:=0;

       k:=1;

      while s < 66 do begin

             k:=k+3;

            s:=s+k;

       end;

      write(k);

end.

алг

нач

    цел k, s

    s := 0

    k := 1

    нц пока s < 66

        k := k + 3

        s := s + k

    кц

    вывод k

кон

Си++

#include <iostream>

using namespace std;

int main() {

    int s, k;

    s = 0, k = 1;

    while (s < 1000)  {

        k = k + 3;

        s = s + k;

    }

    cout << k << endl;

    return 0;

}

Задача 8.1.3. Определите, что будет напечатано в результате работы следующего фрагмента программы:

Бейсик

Python

DIM K, S AS INTEGER

 S = 0

 K = 1

 WHILE S < 1000

    K = K * 3

    S = S + K

WEND

PRINT K

s = 0

k = 1

while s < 1000:

    k *= 3

    s += k

print(k)

Паскаль

Алгоритмический язык

var k, s: integer;

begin

       s:=0;

       k:=1;

      while s < 66 do     

      begin

             k:=k*3;

            s:=s+k;

       end;

      write(k);

end.

алг

нач

    цел k, s

    s := 0

    k := 1

    нц пока s < 66

        k := k * 3

        s := s + k

    кц

    вывод k

кон

Си++

#include <iostream>

using namespace std;

int main() {

    int s, k;

    s = 0, k = 1;

    while (s < 1000)  {

        k = k * 3;

        s = s + k;

    }

    cout << k << endl;

    return 0;

}

Задача 8.1.4. Определите, что будет напечатано в результате работы следующего фрагмента программы:

Бейсик

Python

DIM K, S AS INTEGER

 S = 1

 K = 0

 WHILE S < 1000

    K = K + 1

    S = S * K

WEND

PRINT K

s = 1

k = 0

while s < 1000:

    k += 1

    s *= k

print(k)

Паскаль

Алгоритмический язык

var k, s: integer;

begin

       s:=1;

       k:=0;

      while s < 1000 do   

begin

             k:=k+1;

            s:=s*k;

       end;

      write(k);

end.

алг

нач

    цел k, s

    s := 1

    k := 0

    нц пока s < 1000

        k := k + 1

        s := s * k

    кц

    вывод k

кон

Си++

#include <iostream>

using namespace std;

int main() {

    int s, k;

    s = 1, k = 0;

    while (s < 1000)  {

        k = k + 1;

        s = s * k;

    }

    cout << k << endl;

    return 0;

}

Задача 8.1.5. Определите, что будет напечатано в результате работы следующего фрагмента программы:

Бейсик

Python

DIM K, S, p AS INTEGER

 P = 1

 S = 0

 K = 0

 WHILE S < 100

    K = K + 1

    P = P * K

    S = S + P

WEND

PRINT s

s = 0

k = 0

p = 1

while s < 100:

    k += 1

    p *= k

    s += p

print(s)

Паскаль

Алгоритмический язык

var k, s: integer;

begin

       s:=0;

       p:=1;

       k:=0;

      while s < 100 do 

begin

             k:=k+1;

            p:=p*k;

            s:=s+p;

       end;

      write(s);

end.

алг

нач

    цел k, s

    s := 0

    k := 0

    p := 1

    нц пока s < 100

        k := k + 1

        p := p * k

        s := s + p

    кц

    вывод s

кон

Си++

#include <iostream>

using namespace std;

int main() {

    int s, k, p;

    s = 0, p = 1, k=0;

    while (s < 100)  {

        k = k + 1;

        p = p * k;

        s = s + p;

    }

    cout << s << endl;

    return 0;

}

Задача 8.1.6. Определите, что будет напечатано в результате работы следующего фрагмента программы:

Бейсик

Python

DIM a, b, c, i AS INTEGER

 a = 1

 b = 1

 c = 1

 i = 2

 WHILE i < 10

    i = i + 1

    a = b + c

    c = b

    b = a

WEND

PRINT a

a = 1

b = 1

c = 1

i = 2

while i < 10:

    i += 1

    a = b + c

    c = b

    b = a

   print(a)

Паскаль

Алгоритмический язык

var a, b, c, i: integer;

begin

   a := 1

   b := 1

   c := 1

   i := 2

  while i < 10 do    

begin

    i := i + 1

    a := b + c

    c := b

    b := a

end;

      write(a);

end.

алг

нач

    цел a, b, c, i

   a := 1

   b := 1

   c := 1

   i := 2

нц пока i < 10

    i := i + 1

    a := b + c

    c := b

    b := a

кц

    вывод a

кон

Си++

#include <iostream>

using namespace std;

int main() {

    int a, b, c, i;

    a = 1;

    b = 1;

    c = 1;

    i = 2;

    while (i < 10)     {

        i = i + 1;

        a = b + c;

        c = b;

        b = a;

    }

    cout << a << endl;

    return 0;

}

Задача 8.1.7. Значения элементов массива A[1..10] задаются с помощью следующего фрагмента программы: 

Бейсик

Паскаль

A(1) = 1

A(2) = 1

FOR i= 3 TO 10

   A(i)=A(i-1)+A(i-2)

NEXT i

A[1]:=1;

A[2]:=1;

for i:=3 to 10 do

    A[i] := A[i-1]+A[i-2];

Си++

Алгоритмический язык

A[1]=1;

A[2]=1;

for (i=3;i<=10;i++) {

    A[i] = A[i-1]+A[i-2];

}

A[1]:=1

A[2]:=1

нц для i от 3 до 10

      A[i] := A[i-1]+A[i-2]

    кц

кц

Python

A[1]=1

A[2]=1 

for i in range(3, 11):

    A[i] = A[i-1]+A[i-2]

Задача 8.1.8. Массив А заполнен одними нулями. Далее значения элементов массива A[1..10] задаются с помощью следующего фрагмента программы: 

Бейсик

Паскаль

A(1) = 1

FOR i= 1 TO 9

   A(i+1)=A(i+1)+A(i)

   A(i+2)=A(i+2)+A(i)

NEXT i

A[1]:=1;

for i:=1 to 9 do

begin

    A[i+1] := A[i+1]+A[i];

    A[i+2] := A[i+2]+A[i];

end;

Си++

Алгоритмический язык

A[1]=1;

for (i=1;i<=9;i++) {

    A[i+1] = A[i+1]+A[i];

    A[i+2] = A[i+2]+A[i];

 

}

A[1]:=1

нц для i от 1 до 9

      A[i+1] := A[i+1]+A[i]

      A[i+2] := A[i+2]+A[i]

    кц

кц

Python

A[1]=1

for i in range(1, 10):

    A[i+1] = A[i+1]+A[i]

    A[i+2] = A[i+2]+A[i]

Задача 8.1.9. Ниже представлен записанный на разных языках программирования фрагмент одной и той же программы, обрабатывающей одномерный целочисленный массив с индексами от 0 до 10.

Бейсик

Python

s = 27

n = 10

 FOR i = 0 TO n-1

    s = s+A(i)-A(i+1)+2

 NEXT i

s = 27

n = 10

for i in range(0,n):

    s = s + A[i] - A[i+1]+2

Алгоритмический язык

Паскаль

s := 27

n := 10

нц для i от 0 до n-1

    s:=s+A[i]-A[i+1]+2

кц

s := 27;

n := 10;

for i:=0 to n-1 do begin

    s:=s+A[i]-A[i+1]+2

end;

Си++

s = 27;

n = 10;

for (i = 0; i <= n-1; i++) {

    s=s+A[i]-A[i+1]+2;

}

Задача 8.1.10. Значения элементов двумерного массива A[1..100,1..100] задаются с помощью следующего фрагмента программы: 

Бейсик

Паскаль

FOR i= 1 TO 100

    FOR k=1 TO 100

    IF i > k THEN A(i,k) = i

    ELSE

        A(i,k) = -k

    NEXT k

 NEXT i

for i:=1 to 100 do

    for k:=1 to 100 do

        if i > k then

        A[i,k] := i

    else A[i,k] := -k;

Си++

Алгоритмический язык

for (i=1;i<=100;i++) {

    for (k=1;k<=100;k++) {

        if (i > k) {

            A[i,k] = i;

        }

        else A[i,k] = -k;

    }

}

нц для i от 1 до 100

    нц для k от 1 до 100

        если i > k

        то A[i,k] := i

        иначе A[i,k] := -k

    кц

кц

Python

 

for i in range(1, 101):

    for k in range(1, 101):

        if i > k:

            A[i][k] = i

        else:

            A[i][k] = -k

Задача 8.1.11. Массив А заполнен следующими значениями, как показано в таблице:

Индекс i

0

1

2

3

4

5

А[i]

1

3

5

0

4

2

 

Ниже представлен записанный на разных языках программирования фрагмент одной и той же программы, обрабатывающей этот массив.

Бейсик

Python

j=0

 FOR i = 1 TO 100

    j=a[j]

 NEXT i

j=0

for i in range(1,101):

    j=a[j]

Алгоритмический язык

Паскаль

j=0

нц для i от 1 до 100

    j=a[j]

кц

j=0;

for i:=1 to 100 do begin

    j=a[j];

end;

Си++

j = 0;

for (i = 1; i <= 100; i++) {

    j=a[j];

}

 

Чему равно значение j после выполнения фрагмента программы?

Задача 8.1.12. Массив А заполнен следующими значениями, как показано в табличке:

Индекс i

0

1

2

3

4

5

А[i]

1

3

5

0

4

2

 

Ниже представлен записанный на разных языках программирования фрагмент одной и той же программы, обрабатывающей этот массив.

Бейсик

Python

j=0

 FOR i = 1 TO 100

    j=a[a[a[j]]]

 NEXT i

j=0

for i in range(1,101):

    j=a[a[a[j]]]

Алгоритмический язык

Паскаль

j=0

нц для i от 1 до 100

    j=a[a[a[j]]]

кц

j=0;

for i:=1 to 100 do begin

    j=a[a[a[j]]];

end;

Си++

j = 0;

for (i = 1; i <= 100; i++) {

    j=a[a[a[j]]];

}

 


Подробнее

8.2. Программы и алгоритмы с рекурсиями

Задача 8.2.1. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n – 1) * n, при n >1

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

Задача 8.2.2. Последовательность чисел задается рекуррентным соотношением:

F(1) = 1

F(2) = 1

F(n) = F(n – 2) + F(n – 1), при n >2, где n – натуральное число.

Чему равно восьмое число в последовательности? 

В ответе запишите только натуральное число.

Задача 8.2.3. Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(1) = 1;

F(n) = F(n − 1) + n, если n > 1

Чему равно значение функции F(40)? В ответе запишите только натуральное число.

Задача 8.2.4. Алгоритм вычисления значения функции F(n) и G(n), где n – натуральное число, задан следующими соотношениями: 

F(1) = 1

F(n) = 2 * G(n – 1) + 5 * n, при n > 1

G(1) = 1

G(n) = F(n – 1) + 2 * n, при n > 1 

Чему равно значение функции F(4) + G(4)? 

Задача 8.2.5. Последовательность чисел задается рекуррентным соотношением:

F(a,0) = 1

F(a,n) = F(a, n/2) * F(a, n/2), при n > 1, где n – четное натуральное число.

F(a,n) = F(a, n – 1) * a, при n > 1, где n – нечетное натуральное число.

Чему равно пятнадцатое число в последовательности при а = 2? 

В ответе запишите только натуральное число.

Задача 8.2.6. Последовательность чисел задается рекуррентным соотношением:

F(a,0) = 1

F(a,n) = F(a*a, n/2), при n > 1, где n – четное натуральное число.

(a,n) = F(a, n – 1) * a, при n > 1, где n – нечетное натуральное число.

Чему равно шестое число в последовательности при а = 3? 

В ответе запишите только натуральное число.

Задача 8.2.7. Ниже на пяти языках программирования записана рекурсивная функция (процедура) F.

  

Бейсик

Python

SUB F(n)

    PRINT n,

    IF n > 2 THEN

       F(n − 1)

       F(n − 2)

       F(n − 3)

    END IF 

END SUB

def F(n):

    print (n, end='')

    if n > 2:

        F(n − 1)

        F(n − 2)

        F(n − 3)

Паскаль

Алгоритмический язык

procedure F(n: integer); 

begin

    write(n);

    if n > 2 then

    begin

      F(n − 1);

      F(n − 2);

      F(n − 3)

    end

end;

алг F(цел n)

нач

    вывод n

    если n > 2 то

      F(n − 1)

      F(n − 2)

      F(n − 3)

    все

кон

Си

void F(int n ){

    cout « n « endl;

    if (n > 2) {

        F(n - 1);

        F(n - 2);

        F(n - 3);

    }

}

 

Что выведет программа при вызове F(5)? В ответе запишите последовательность выведенных цифр слитно (без пробелов).

Задача 8.2.8. Ниже на пяти языках программирования записан рекурсивный алгоритм F.

 

Бейсик

Python

DECLARE SUB F(n)

SUB F (n)

    IF n > 0 THEN

        F(n \ 4)

        PRINT n

        F(n - 1)

    END IF

END SUB

def F(n):

    if n > 0:

        F(n // 4)

        print(n)

        F (n - 1)

Паскаль

Алгоритмический язык

procedure F(n: integer);

begin

    if n > 0 then

    begin

        F(n div 4);

        write(n);

        F(n - 1);

    end

end;

алг F(цел n)

нач

    если n > 0 то

        F(div(n, 4))

        вывод n

        F(n - 1)

    все

кон

Си++

void F(int n){

    if (n > 0){

        F(n / 4)

        std::cout << n;

        F(n - 1);

    }

}

 

В качестве ответа укажите последовательность цифр, которая будет напечатана на экране в результате вызова F(5).



Подробнее

8.3. Разные задачи

Задача 8.3.1. На какую цифру оканчивается десятичное число 2111

Задача 8.3.2. Последовательность рядов формируется следующим образом. Первый ряд состоит из одной цифры 0. Второй ряд – первый ряд записывается два раза, и к концу приписывается 1. Далее каждый ряд записывается два раза, и в его конец приписывается число, равное номеру ряда минус 1:

Номер ряда

Ряд

1

2

3

4

5

6

0

001

0010012

001001200100123

0010012001001230010012001001234

001001200100123001001200100123400100120010012300100120010012345

 

Какая цифра стоит в 10 ряду под номером 504, считая слева.

Задача 8.3.3. Найдите сумму десятичных чисел, не превосходящих 1000, запись которых в системе счисления с основанием три оканчивается на 12.

Задача 8.3.4. Сколько стобуквенных слов можно составить из букв A, B, если буква A встречается в каждом слове ровно два раза.

Задача 8.3.5. Полным графом называют граф, у которого любая пара вершин соединена ребром. Граф состоит из 200 вершин. Сколько ребер в графе?   

Задача 8.3.6. Исполнитель Ювелир собирает бусы. В его запасе есть бусины всех цветов радуги (красного, оранжевого, жёлтого, зелёного, голубого, синего, фиолетового). Бусины нанизываются на нитку фрагментами в порядке их формирования по определенному правилу: Сначала берутся три бусины одинакового цвета. Каждый следующий фрагмент формируется так: левая крайняя бусина копии предыдущего фрагмента заменяется на бусину предыдущего цвета радуги, а крайняя правая – на бусину последующего цвета радуги (при этом цвета радуги расположены по кругу: после фиолетового идет красный, и перед красным, соответственно, фиолетовый). Затем к средней бусине в получившемся фрагменте добавляются две бусины такого же цвета. Пример. 1 фрагмент: сначала берутся три бусины желтого цвета (ЖЖЖ). 2 фрагмент: левая крайняя бусина копии предыдущего фрагмента заменяется на бусину предыдущего цвета радуги, а крайняя правая – на бусину последующего цвета радуги. Затем к средней бусине в получившемся фрагменте добавляются две бусины такого же цвета (ОЖЖЖЗ) 3 фрагмент: КЖЖЖЖЖГ Пусть Ювелир начал формирование первого фрагмента с трёх зелёных бусин. Сколько всего зеленых бусин будет в первых 100 фрагментах? 

Задача 8.3.7. Исполнитель преобразует число на экране.У исполнителя есть две команды, которым присвоены номера:1. Прибавить 1.2. Прибавить 2.Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2.Программа для исполнителя— это последовательность команд.Сколько существует программ, которые преобразуют исходное число 1 в число 11?

Задача 8.3.8. Исполнитель может складывать любые натуральные числа.Сколько существует программ, которые преобразуют исходное число 1 в число 12?Программой называется сумма любого числа слагаемых, например, 1 + 2 + 3 + 4 + 2 = 12.Перестановка слагаемых приводит к новой программе (1 + 2 + 3 + 4 + 2 и 2 + 1 + 2 + 3 + 4 – это разные программы)

Задача 8.3.9. Какая строка получится в результате применения приведённой ниже программы к строке вида 1…12…2 (1000 единиц и 1000 двоек)? НАЧАЛОПОКА нашлось (111)    заменить (111, 2)    заменить (222, 1)КОНЕЦ ПОКАКОНЕЦ

Задача 8.3.10. Азбука Морзе поз­во­ля­ет кодировать сим­во­лы для со­об­ще­ний по радиосвязи, за­да­вая комбинацию точек и тире. Сколь­ко различных сим­во­лов (цифр, букв, зна­ков пунктуации и т. д.) можно закодировать, ис­поль­зуя код аз­бу­ки Морзе дли­ной от 1 до 10 сигналов (точек и тире)?







Подробнее

8.4. Прогрессии и рекурсии в логических уравнениях

Задача 8.4.1. Сколько различных решений имеет система логических уравнений:

(x1 x2) → (x2 → x3) = 1

(x2 → x3) → (x3 → x4) = 1

(x97 → x98) → (x99 → x100) = 1

Задача 8.4.2. Сколько различных решений имеет система логических уравнений:

(x1 → x2) → (x3 → x4) = 1

(x3 → x4) → (x5 → x6) = 1

(x28 → x29) → (x29 → x30) = 1

Задача 8.4.3. Сколько различных решений имеет система логических уравнений:

x1 ∧ x2 ∨ x3 = 1

x2 ∧ x3 x4 = 1

x7 ∧ x8 ∨ x9 = 1

x8 ∧ x9 ∨ x10 = 1

Задача 8.4.4. Сколько различных решений имеют логические уравнения

А)

x1y1 = 1

(x2(x1 ∧ y2)) ∧ (y21) = 1

(x3(x2 ∧ y3)) ∧ (y3y2) = 1

(x9(x8 ∧ y9)) ∧ (y9y8) = 1

B)

x1y1 = 1

(x2(x1 ∧ y2)) ∧ (y2y1) = 1

(x3(x2 ∧ y3)) ∧ (y3y2) = 1

(x99(x98 ∧ y99)) ∧ (y99y98) = 1





Подробнее

8.5. Комбинаторно-рекурсивная задача

Задача 8.5.1. Пусть номер билета состоит из n десятичных цифр (n-четное). Билет называется счастливым, если сумма левой половины цифр равна сумме правой половины цифр.

Например, билет 4563 счастливый, так как 4 + 5 = 6 + 3.

Сколько возможно различных счастливых билетов при:

  1. n = 4,
  2. n = 6,
  3. n = 8.


Подробнее