• Математические основы информатики А. Гейн. Алгоритм и свойства алгоритма

Текст задания

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

4.1. Дан алгоритм:

алг Последовательность (арг цел М, рез цел Z)
нач цел: X, Y
ввод М;
X := 1
Y := 3
Z := Y
нц пока Z < М
Z := Y - 2 * X
X := Y
Y := Z
кц
вывод Z
кон

Верно ли, что при любом целом М этот алгоритм конечен?

4.2. Рассмотрите следующий алгоритм:

алг Сумма (арг цел М, рез цел N)
нач вещ: S
S := 1
N := 1
вывод "Введите натуральное число М"
ввод М
нц пока S < М
N := N + 1
S := S + 1/N
кц
вывод N
кон

а) Для решения какой задачи предназначен этот алгоритм?

б) Ясно, что при М = 1 тело цикла не выполняется ни разу и, следовательно, алгоритм конечен. При любом ли значении М данный алгоритм конечен?

4.3. Рассмотрите следующий алгоритм, преобразующий натуральные числа.

алг Преобразование (арг цел а, b, n, рез цел m)
нач
ввод n
ввод а
ввод b
m := n
нц пока (m  a) и (m  b)
m : = СКВ(m)
кц (*конец цикла*)
вывод m
кон
алг цел СКВ (арг цел n)
нач
если n < 10
то знач := n * n
иначе знач := СКВ (n div 10) +
(n mod 10)*(n mod 10)
все
кон

При каких a и b этот алгоритм конечен? Перечислите все возможные здесь варианты.

4.4. Рассмотрите следующий алгоритм.

алг Половинчатый (арг цел K, М)
нач
ввод K
ввод М
нц пока (K mod 2 = 0 или M mod 2 = 0)
если K mod 2 = 0
то K := K/2
M := M + K
все
если (M mod 2 = 0)
то М := M/2
M := M + K
все
кц
вывод M * K
кон

Определите, для каких пар натуральных чисел K и М этот алгоритм завершает работу за конечное число шагов.

4.5. Даны два массива К и М с целочисленными элементами, расположенными в каждом из них в порядке возрастания. Рассмотрите следующий алгоритм:

алг Количество (арг цел таб К[1:20], М[1:30], рез цел с)
нач цел: a, b
a := 1
b := 1
c := 1
нц пока (a  20 и b  30)
выбор
при K(a) < M(b)
a := a + 1
при K(a) > M(b)
b := b + 1
при K(a) = M(b)
a := a + 1
b := b + 1
c := c + 1
все
кц
вывод c
кон

а) Для решения какой задачи предназначен этот алгоритм?

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

Решение

Решение контрольной работы оформлено в виде документа Word. Для получения решения необходимо оформить заказ и оплатить его.


Написать отзыв

Внимание: HTML не поддерживается! Используйте обычный текст!
    Плохо           Хорошо

Математические основы информатики А. Гейн. Алгоритм и свойства алгоритма

  • Дисциплина: Информатика
  • Код работы: КО-94
  • Работу выложил: Администратор
  • 200.00 р.




Смотрите также

Математические основы информатики А. Гейн. Графы

Математические основы информатики А. Гейн. Графы

Все графы, фигурирующие в контрольной работе, обыкновенные, без петель и кратных ребер.4.1. Существу..

450.00 р.

Математические основы информатики А. Гейн. Надежность кодов экономное кодирование

Математические основы информатики А. Гейн. Надежность кодов экономное кодирование

1.1. Символы a, b, c, d закодированы следующим образом: a→000000, ..

300.00 р.

Математические основы информатики А. Гейн. Математические модели формальных исполнителей

Математические основы информатики А. Гейн. Математические модели формальных исполнителей

2.1. Для автомата, изображенного на рис. 1, определите, в каком состоянии он будет находиться п..

300.00 р.

Математические основы информатики А. Гейн. Машина Тьюринга

Математические основы информатики А. Гейн. Машина Тьюринга

3.1 Работа машины Тьюринга описана следующей функциональной схемой:Определите, какое сообщение будет..

450.00 р.

Не подошла работа?

Узнайте стоимость написания работы по Вашему заданию

(это быстро и бесплатно)

Узнать стоимость

Спасибо, не надо