Выполнение и анализ простых алгоритмов

• Название: Выполнение и анализ простых алгоритмов
• Дата: 18.06.2022
• Размер: 190.3 Kb.
• Имя файла: ege5.docx
• Тип: Документы; #601056
• страница: 2 из 13

Ещё пример задания:

Р-12. Автомат обрабатывает трёхзначное натуральное число N по следующему алгоритму.

1. Из цифр, образующих десятичную запись N, строятся наибольшее и наименьшее
возможные двузначные числа (числа не могут начинаться с нуля).

2. На экран выводится разность полученных двузначных чисел.

Пример. Дано число N = 351. Алгоритм работает следующим образом.

1. Наибольшее двузначное число из заданных цифр – 53, наименьшее – 13.

2. На экран выводится разность 53 – 13 = 40.

Чему равно наименьшее возможное трёхзначное число N, в результате обработки которого на экране автомата появится число 40?

Решение:

1. 
   расставим цифры числа в порядке возрастания: a, b, c (среди них могут быть и одинаковые)
   
2. 
   сначала рассмотрим случай, когда a = b = 0, c  0; при этом максимальное и минимальное двузначные числа совпадают и равны 10c, а их разность равна 0
   
3. 
   пусть теперь a = 0, b  0 и c  0; тогда максимальное двузначное число – 10c + b, а минимальное – 10b; их разность равна 10(c – b) + b; чтобы эта разность была равна 40, необходимо, чтобы b = 0, а это противоречит исходному предположению
   
4. 
   остаётся один случай – среди цифр нет нулей; тогда максимальное двузначное число – 10c + b, а минимальное – 10a + b;
   
5. 
   их разность равна 10(c – a); чтобы эта разность была равна 40, необходимо, чтобы c – a = 4, то есть минимальные значения цифр – c = 5, a = 1; поскольку все цифры ненулевые, то b = 1
   
6. 
   для получения минимального числа цифры 5, 1 и 1 нужно расставить в порядке неубывания
   
7. 
   Ответ: 115.
   

Ещё пример задания:

Р-11. Автомат обрабатывает натуральное число N по следующему алгоритму.

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

2. Удаляются первая слева единица и все следующие непосредственно за

ней нули. Если после этого в числе не остаётся цифр, результат этого

действия считается равным нулю.

3. Полученное число переводится в десятичную запись.

4. Новое число вычитается из исходного, полученная разность выводится на экран.

Пример. Дано число N = 11. Алгоритм работает следующим образом.

1. Двоичная запись числа N: 1011.

2. Удаляется первая единица и следующий за ней ноль: 11.

3. Десятичное значение полученного числа 3.

4. На экран выводится число 11 – 3 = 8.

Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 500 до 5000?.

Решение:

1. 
   при удалении первой единицы и всех стоящих сразу за ней нулей фактически из числа вычитается 2 в степени, равной номеру старшего разряда в двоичной записи числа
   
2. 
   именно это число и будет выведено на экран
   
3. 
   таким образом, нужно найти количество степеней числа 2, которые находятся между заданными начальным и конечным значениями
   
4. 
   если начальное число не равно степени числа 2, в двоичной записи первых чисел старший разряд будет соответствовать предыдущей степени двойки, которая не входит в заданный диапазон, поэтому к результату необходимо добавить 1
   
5. 
   на заданном отрезке [500; 5000] находятся следующие степени числа 2: 512 = 2⁹, 1024 = 2¹⁰, 2048 = 2¹¹, 4096 = 2¹² – всего 4 числа
   
6. 
   так как 500 – не степень двойки, добавляем ещё одну степень 256 = 2⁸
   
7. 
   Ответ: 5.
   

Решение (программа на Python, перебор):

1. 
   полная программа:
   

def alg(x):

s = "{:b}".format(x)

return x - int( s[1:], 2 )
allResults = set()

for x in range(500, 5001):

allResults.add(alg(x))
print(len(allResults))

2. 
   Ответ: 5.
   

Решение (программа на С++, автор – Артур Д.):

1. 
   полная программа:
   

#include

#include

#include

#include
unsigned long f(unsigned long N)

{

// Множество для хранения битов и счетчик их сдвигов

// (размер 13 выбираем т.к. большее число из отрезка

// 5000 содержит 13 бит)

std::bitset<13> R(N);

int shiftCounter = 0;

// Двигаем влево все биты пока первым слева не окажется 1,

// попутно запоминая кол-во сдвигов

for (int i = 13; i > 0; i--) {

if (R[i] == 0 && R[12] != 1) {

shiftCounter++;

R <<= 1;

}

// Если встретилась единица первым битом слева - выход

// из цикла

if (R[12] == 1) break;

}

// Сдвигаем биты еще раз влево, чтобы избавиться от

// первой 1

R <<= 1;

// Сдвигаем биты обратно вправо на то же кол-во

// проделанных сдвигов

R >>= shiftCounter + 1;

// Возвращаем результат вычитания

return N - R.to_ulong();

}
int main()

{

// Множество разных значений автомата

std::set<unsigned long> solutionSet;

// Вставляем значения в множество

for (int i = 500; i <= 5000; i++)

solutionSet.insert(f(i));

// Выводим количество этих значений

std::cout << "Кол-во значений: " << solutionSet.size()

<< '\n';

}

2. 
   Ответ: 5.