ЕГЭ-05. Анализ простых алгоритмов

561 задача
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: успешные, неуспешные.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются ещё несколько разрядов по следующему правилу:
а) Если N чётное, то к нему справа приписывается в двоичном виде удвоенная сумма цифр его двоичной записи;
6) Если N нечётное, то к нему справа приписывается 110, а слева 10.
Например, двоичная запись числа 1110 будет преобразована в 1110110.
Полученная таким образом запись (в ней как минимум на один разряд больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Сколько существует различных чисел N, для которых результат работы данного алгоритма принадлежит отрезку [1000; 1500]?
39469#39469

Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.

1. Перемножаются первая и третья, а также вторая и третья цифры исходного числа.
2. Полученные два числа записываются друг за другом в порядке неубывания (без разделителей).

Пример. Исходное число: 631. Произведения: 6 × 1 = 6; 3 × 1 = 3. Результат: 36.

Укажите разность между наибольшим и наименьшим числом, при обработке которых автомат выдаст число 1218.
 

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются ещё несколько разрядов по следующему правилу:
а) вычисляется количество нулей, стоящих на четных разрядах (разряды нумеруются слева направо, начиная с 1) - k1.
б) вычисляется количество единиц, стоящих на нечетных разрядах (разряды нумеруются слева направо, начиная с 1) - k2.
в) двоичная запись суммы чисел k1 и k2 дописывается в конец числа (справа).
Полученная таким образом запись является двоичной записью результирующего числа R.
Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 300. В ответе это число запишите в десятичной системе счисления.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются ещё несколько разрядов по следующему правилу:
а) складываются все цифры, стоящие на четных местах (разряды нумеруются слева направо, начиная с 1) - S1.
б) складываются все цифры, стоящие на нечетных местах (разряды нумеруются слева направо, начиная с 1) - S2.
в) двоичная запись большего из чисел S1 и S2 дописывается в начале числа (слева), меньшее - в конец числа (справа).
Полученная таким образом запись является двоичной записью результирующего числа R.
Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 500. В ответе это число запишите в десятичной системе счисления.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Если количество цифр в двоичной записи числа N четное, то справа к числу приписывается число 5 в двоичной системе счисления, иначе это число приписывается слева.
Полученная таким образом запись является двоичной записью искомого числа R.
Сколько существует различных чисел N, для которых результат работы данного алгоритма принадлежит отрезку [300; 500]?
Автомат обрабатывает десятичное натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа N.
2. Вычисляется сумма S1 всех цифр, стоящих на четных местах в двоичной записи. Разряды нумеруются справа налево, начиная с 0.
3. Вычисляется сумма S2 всех цифр, стоящих на нечетных местах в двоичной записи. 
4. Вычисляется разность (по модулю) R=|S2-S1|. является результатом работы алгоритма.
При каком минимальном значении N, результатом работы будет число 3?
39292#39292

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1)    Строится двоичная запись числа N.

2)    К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

б) в полученной записи последняя цифра удваивается. Например, запись 111001 преобразуется в запись 1110011.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите минимальное число N, результат обработки которого превышает 60.

Автомат обрабатывает десятичное натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа N.
2. Вычисляется значение k равное количеству цифр в двоичной записи числа N.
3. Если k кратно трем, то справа к числу дописывается 111, иначе справа к числу дописывается 10
4. Полученное число переводится обратно в десятичную систему счисления.
При каком минимальном значении исходного числа N результатом работы алгоритма будет число большее 200?
Автомат обрабатывает десятичное натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа N.
2. Вычисляется сумма S1 всех цифр, стоящих на четных местах в двоичной записи. Разряды нумеруются справа налево, начиная с 0.
3. Вычисляется сумма S2 всех цифр, стоящих на нечетных местах в двоичной записи. 
4. Вычисляется разность (по модулю) R=|S2-S1|. является результатом работы алгоритма.
При скольких различных значениях исходного числа N, принадлежащих диапазону [100, 150], результатом работы будет число 0?
Автомат обрабатывает десятичное натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа.
2. К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей, и 1 в обратном случае.
3. К полученному числу справа дописывается бит четности (0, если количество единиц четное, и 1 в обратном случае).
4. Полученное число переводится в десятичную систему счисления и является результатом работы автомата.
При каком наибольшем значении N результатом работы будет число, не превышающее 155?
Автомат обрабатывает десятичное натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа,
2. К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей, и 1 в обратном случае.
3. Действие 2 повторяется еще раз.
4. Из середины двоичного числа убирается 2 разряда, если количество разрядов получилось четным, и 3 разряда, если нечетным.
5. Полученное число переводится в десятичную систему счисления и является результатом работы автомата.
Сколько различных значений может получиться в результате работы, если автомат обработает все значения N, которые принадлежат отрезку [100; 200] ?
Автомат обрабатывает натуральное число N по следующему алгоритму:
1) Строится двоичная запись числа N.
2) Удаляются две последние цифры
3) Полученное число переводится в десятичную запись и выводится на экран.
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 20 до 600?
Автомат обрабатывает натуральное число N по следующему алгоритму:
1) Строится двоичная запись числа N.
2) Из записи удаляются все нули.
3) Полученное число переводится в десятичную запись и выводится на экран.
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 10 до 2500?
Автомат обрабатывает целое число N (0 ≤ N ≤ 255) по следующему алгоритму:
1) Строится восьмибитная двоичная запись числа N.
2) Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0).
3) Полученное число переводится в десятичную запись.
4) Из нового числа вычитается исходное, полученная разность выводится на экран.
Какое число нужно ввести в автомат, чтобы в результате получилось 99?
Автомат обрабатывает целое число N (0 ≤ N ≤ 255) по следующему алгоритму:
1) Строится восьмибитная двоичная запись числа N.
2) Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0).
3) Полученное число переводится в десятичную запись.
4) Из нового числа вычитается исходное, полученная разность выводится на экран.
Какое число нужно ввести в автомат, чтобы в результате получилось 113?
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописывается (дублируется) последняя цифра.
3) Затем справа к числу дописывается бит чётности: 0, если в двоичном коде числа N было чётное число единиц, и 1, если нечётное.
4) К полученному результату дописывается справа ещё один бит чётности: 0, если в двоичном коде, полученного после пункта 3 числа, чётное число единиц, и 1, если нечётное
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число N, после обработки которого автомат получает число, большее 114. В ответе это число запишите в десятичной системе.
 
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописывается справа бит чётности: 0, если в двоичном коде числа N было чётное число единиц, и 1, если нечётное.
3) К полученному результату дописывается ещё один бит чётности.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите количество исходных чисел N, из которых с помощью этого алгоритма могут быть получены числа R, лежащие в диапазоне 64 ≤ R < 72.
 
20194#20194
Требовалось написать программу, при выполнении которой с клавиатуры считывается натуральное число x, не превосходящее 1000, и выводится количество единиц в двоичной записи этого числа. Программист торопился и написал программу неправильно.
Паскаль Си
var x, cnt: integer; 
begin
(*)
(1)  readln(x);
(2)  cnt := 0;
(3)  while x > 0 do begin
(4)    cnt := cnt + 1;
(5)    x := x mod 2;
(6)  end;
(7)  writeln (cnt)
end.
#include<stdio.h>
main(){
  int x, cnt;
(*)
(1)  scanf("%d",&x);
(2)  cnt = 0;
(3)  while (x > 0) {
(4)    cnt = cnt + 1;
(5)    x = x % 2;
(6)  }
(7)  printf("%d", cnt);
}
 
 
Последовательно выполните следующее:
1. Напишите, что выведет эта программа при вводе числа 6.
2. Приведите пример такого числа x, что, несмотря на ошибки, программа печатает правильный ответ.
3. Найдите все ошибки в этой программе (их может быть одна или несколько). Известно, что каждая ошибка затрагивает только одну строку и может быть исправлена без изменения других строк. Для каждой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, т.е. приведите правильный вариант строки.


В качестве ответа загрузите исправленную программу, в которой добавлена строка на место (*). Строка должна содержать оператор вывода (с переходом на новую строку после выполнения) номеров строк, в которых допущена ошибка (выводить нужно ТОЛЬКО номера слитно без пробелов и запятых)
например:
Паскаль
Си
...
begin
(*)  writeln('123');

... далее исправленная программа

end.
#include<stdio.h>
main(){
...
(*)  printf("123\n");
... далее исправленная программа
}
20193#20193
Требовалось написать программу, при выполнении которой с клавиатуры считывается натуральное число x, не превосходящее 1000, и выводится количество значащих цифр в двоичной записи этого числа. Программист торопился и написал программу неправильно.
Паскаль Си
var x, cnt: integer; 
begin
(*)
(1)  readln(x);
(2)  cnt := 0;
(3)  while x > 0 do begin
(4)    cnt := cnt + x mod 2;
(5)    x := x div 10;
(6)  end;
(7)  writeln (cnt)
end.
#include<stdio.h>
main(){
  int x, cnt;
(*)
(1)  scanf("%d",&x);
(2)  cnt = 0;
(3)  while (x > 0) {
(4)    cnt = cnt + x % 2;
(5)    x = x / 10;
(6)  }
(7)  printf("%d", cnt);
}
 

Последовательно выполните следующее:
1. Напишите, что выведет эта программа при вводе числа 15.
2. Приведите пример такого числа x, что, несмотря на ошибки, программа печатает правильный ответ.
3. Найдите все ошибки в этой программе (их может быть одна или несколько). Известно, что каждая ошибка затрагивает только одну строку и может быть исправлена без изменения других строк. Для каждой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, т.е. приведите правильный вариант строки.


В качестве ответа загрузите исправленную программу, в которой добавлена строка на место (*). Строка должна содержать оператор вывода (с переходом на новую строку после выполнения) номеров строк, в которых допущена ошибка (выводить нужно ТОЛЬКО номера слитно без пробелов и запятых)
например:
Паскаль Си
...
begin
(*)  writeln('123');

... далее исправленная программа

end.
#include<stdio.h>
main(){
...
(*)  printf("123\n");
... далее исправленная программа
}
 
20192#20192
Требовалось написать программу, при выполнении которой с клавиатуры считывается натуральное число N, не превосходящее 109, и выводится сумма цифр этого числа.   Программист торопился и написал программу неправильно:
 
Паскаль Си
var N: longint;
    sum, d: integer; 
begin
(*)
(1)  readln(N);
(2)  sum := 1;
(3)  while N > 0 do begin
(4)    d := N mod 10;
(5)    N := N div 10;
(6)    sum := d;
(7)  end;
(8)  writeln ( sum )
end.
#include<stdio.h>
main(){
  int N;
  int sum, d;
(*)
(1)  scanf("%d",&N);
(2)  sum = 1;
(3)  while (N > 0) {
(4)    d = N % 10;
(5)    N = N / 10;
(6)    sum = d;
(7)  }
(8)  printf("%d", sum);
}
 
Последовательно выполните следующее.
1.       Напишите, что выведет эта программа при вводе числа 256.
2.       Приведите пример такого трёхзначного числа, при вводе которого программа выдаёт правильный результат.
3.       Найдите все ошибки в этой программе (их может быть одна или несколько). Для каждой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, т. е. приведите правильный вариант строки.


В качестве ответа загрузите исправленную программу, в которой добавлена строка на место (*). Строка должна содержать оператор вывода (с переходом на новую строку после выполнения) номеров строк, в которых допущена ошибка (выводить нужно ТОЛЬКО номера слитно без пробелов и запятых)
например:
Паскаль Си
...
begin
(*)  writeln('123');

... далее исправленная программа

end.
#include<stdio.h>
main(){
...
(*)  printf("123\n");
... далее исправленная программа
}
 
Поделиться
Класснуть