Босова (Сам и контр)

Вариант 2 Самостоятельная работа 6 ГДЗ Самостоятельные и контрольные работы Босова 9 класс (Информатика)

Босова, Босова, Лобанов

9 класс

Класс

Предмет

Информатика

Автор

Босова, Босова, Лобанов

Оцени решение

← Предыдущий Следующий →

Сообщить об ошибке

Вариант 2 Самостоятельная работа 6 ГДЗ Самостоятельные и контрольные работы Босова 9 класс (Информатика)

Задача

ВАРИАНТ 2

Для исполнителя Чертёжник в среде программирования КуМир составьте программу рисования слова «БАОБАБ». Для изображения букв воспользуйтесь вспомогательными алгоритмами.
Для подсчёта минимального числа ходов в задаче «Ханойская башня» используется функция $$S(n)$$, которая вычисляется по следующему алгоритму: $$S(1)=1$$, $$S(n)=2\cdot S(n-1)+1$$ при натуральном $$n>1$$. Вычислите $$S(9)$$ — минимальное число ходов для перекладывания башни из 9 колец.
Дополнительное задание. В среде программирования Паскаль напишите и отладьте программу для нахождения наибольшего общего делителя двух чисел с помощью алгоритма Евклида. Используйте её для нахождения наибольшего общего делителя следующих шести чисел: 6, 12, 30, 42, 80, 132.

Подробный ответ

1. Для рисования слова БАОБАБ удобно использовать вспомогательные алгоритмы для букв Б, А и О. Основная программа последовательно вызывает эти алгоритмы и смещает Чертёжник в нужные точки.

использовать Чертежник
алг
нач
  сместиться в точку(2,4)
  ББ
  сместиться на вектор(5,2)
  БА
  сместиться на вектор(1,0)
  БО
  сместиться на вектор(5,0)
  ББ
  сместиться на вектор(5,2)
  БА
  сместиться на вектор(3,0)
  ББ
кон
алг ББ
нач
  опустить перо
  сместиться на вектор(-2,0)
  сместиться на вектор(0,-4)
  сместиться на вектор(2,0)
  сместиться на вектор(0,2)
  сместиться на вектор(-2,0)
  поднять перо
кон
алг БА
нач
  опустить перо
  сместиться на вектор(-2,-2)
  сместиться на вектор(0,-2)
  сместиться на вектор(0,1)
  сместиться на вектор(2,0)
  сместиться на вектор(0,-1)
  сместиться на вектор(0,4)
  поднять перо
кон
алг БО
нач
  опустить перо
  сместиться на вектор(0,-4)
  сместиться на вектор(2,0)
  сместиться на вектор(0,4)
  сместиться на вектор(-2,0)
  поднять перо
кон

2. Минимальное число ходов в задаче о Ханойской башне задаётся рекуррентной формулой:

$$S(1)=1,$$

$$S(n)=2\cdot S(n-1)+1 \quad \text{при } n>1.$$

Последовательно вычислим значения:

$$n$$	1	2	3	4	5	6	7	8	9
$$S(n)$$	1	3	7	15	31	63	127	255	511

3. Для нахождения НОД шести чисел используем алгоритм Евклида. Сначала находим НОД первых двух чисел, затем последовательно включаем остальные.

var
  a, b, c, d, e, f, nd: integer;
function nod(x, y: integer): integer;
begin
  while x <> y do
    if x > y then x := x — y
    else y := y — x;
  nod := x
end;
begin
  writeln(‘Введи 6-ть целых числа>>’);
  readln(a, b, c, d, e, f);
  nd := nod(nod(a, b), c);
  nd := nod(nod(nd, d), e);
  nd := nod(nd, f);
  writeln(‘NOD=’, nd)
end.

Проверка для чисел $$6, 12, 30, 42, 80, 132$$ даёт:

$$\gcd(6,12,30,42,80,132)=2.$$