Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма Евклидавычисления...

Основы программирования

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма Евклидавычисления НОД двух целых чисел:

дано: целые числа m, n, хотя бы одно отлично от нулянадо: вычислить наибольший общий делитель пары (m, n)цел a, b, r;a := m; b := n;цикл пока b != 0| инвариант: НОД(a, b) == НОД(m, n)| r := a % b;     // находим остаток от деления a на b| a := b; b := r; // заменяем пару (a, b) на (b, r)конец циклаответ := a;

(Отметьте один правильный вариант ответа.)

Варианты ответа

Время работы не больше, чем C·max(m, n), где C — некоторая константа (т.е. время пропорционально максимальному из чисел m, n).

Время работы не больше, чем C·log₂ max(m, n), где C — некоторая константа (т.е. время пропорционально количеству цифр в двоичной или десятичной записи максимального из чисел m, n). (Верный ответ)

Время работы не больше, чем C·r, где C — некоторая константа, r — квадратный корень из max(m, n) (т.е. время пропорционально квадратному корню из максимального числа).

Похожие вопросы

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма быстрого возведения в степень:

дано: основание a и показатель степени n >= 0надо: вычислить a в степени nвещ b, p; цел k;b := a; p := 1.0; k := n;цикл пока k > 0| инвариант: b^k p = aⁿ| если k четное| | то| |   k := k / 2;| |   b := b * b;| | иначе| |   k := k - 1;| |   p := p * b;| конец есликонец циклаответ := p;

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритмаприблизительного вычисления логарифма:

дано: x > 0, a > 1, ε > 0надо: вычислить log_a x с точностью εвещ y, z, t;y := 0.0; z := x; t := 1.0;цикл пока |t| >= ε или z <= 1.0/a или z >= a| инвариант: a^y * z^t = x| если z >= a| | то| |   z := z/a; y := y + t;| иначе если z <= 1.0/a| | то| |   z := z*a; y := y - t;| иначе| |   z := z*z; t := t/2.0;| конец есликонец циклаответ := y;

Рассмотрим следующий фрагмент программы, вычисляющейчастное q и остаток r от деленияцелых чисел a, b:

  дано: целые числа a >= 0, b > 0  цел q, r, e, m;  q := 0; r := a; e := 1; m := b  цикл пока r >= b  | если 2*m <= r  | | то e := e*2; m := m*2;  | иначе если m > r  | | то e := e/2; m := m/2;  | иначе  | | утверждение: m <= r  и  r < 2*m  | | q := q + e; r := r - m;  | конец если  конец цикла  // q и r -- частное и остаток от деления a на b

Какое условие является инвариантом цикла?

Рассмотрим следующий фрагмент программы:

    цел m, n;    . . .    дано: m >= 0 и n >= 0    цел a, b, c;    a := m; b := n;    c := 1;    цикл пока a != 0 и b != 0    | если a четное и b четное    | | то  a := a / 2;    | |     b := b / 2;    | |     c := c * 2;    | иначе если a четное    | | то  a := a / 2;    | иначе если b четное    | | то  b := b / 2;    | иначе    | | если a > b    | | | то    a := a - b;    | | | иначе b := b - a;    | | конец если    | конец если    конец цикла    ответ := c * (a + b);

Какое условие является инвариантом цикла?(Через НОД и НОК обозначены наибольший общий делитель инаименьшее общее кратное.)

Указать, что вычисляет следующий фрагмент программы:

дано: цел n;цел s, k;s := 2; k := 0;цикл пока s <= n| инвариант: s = 2^k+1| s := s * 2; k := k + 1;конец циклаответ := k;

Указать, что вычисляет следующий фрагмент программы:

дано: цел n;цел x, y;x := 1; y := 4;цикл пока y <= n| инвариант: y = (x + 1)²;| x := x + 1;| y := y + 2*x + 1;конец циклаответ := x;

Указать, что вычисляет следующий фрагмент программы:

дано: цел n;цел s, k;s := 10; k := 0;цикл пока s <= n| инвариант: s = 10 * (k + 1)| s := s + 10; k := k + 1;конец циклаответ := k;

На вход следующей программе передаетсяпоследовательность целых чисел в диапазоне от 0 до 9,представляющая цифры десятичной записи целого числа n.Программа определяет, делится ли число n на 75(символом процента '%' обозначается операциянахождения остатка от деления первого числа на второе):

    цел последовательность p; // Цифры числа n    цел s, r, d;    . . .    s := 0; r := 0;    встать в начало последовательности p;    цикл пока есть непрочитанные элементы в посл-ти p    | прочесть очередной элемент посл-ти p в (вых: d);    | s := s + d;             // s -- сумма цифр    | r := (r % 10) * 10 + d; // r -- число из 2-х    конец цикла               //      последних цифр    ответ := (          // n делится на 75, когда        s % 3 == 0  и   //     s делится на 3  и        r % 25 == 0     //     r делится на 25    );

В ней используются три вспомогательные переменныеs, r, d. Можно ли упроститьпрограмму, использовав меньшее количество вспомогательныхпеременных? (Последовательность разрешается читать только один раз.)

Пусть a — целочисленный массив размера n(индекс элементов меняется от 0 до n-1),элементы которого строго возрастают:a[0] < a[1] <... < a[n-1].Определить, содержит ли следующий фрагмент программы ошибку(т.е. действительно ли тело цикла сохраняет инвариант):

// Программа Поискдано: цел n;      цел a[n]; // a[0] < a[1] < ... < a[n-1]цел x;          // искомый элементцел b, e, c;. . .           // рассматриваются исключительные случаиутверждение: a[0] < x  и  x <= a[n-1];  // общий случайb := 0; e := n - 1;цикл пока e - b > 1| инвариант: a[b] < x  и  x <= a[e];| c := (b + e) / 2; // c -- целая часть (b+e)/2| если x < a[c]| | то    e := c;   // выбираем левую половину отрезка| | иначе b := c;   // выбираем правую половину отрезка| конец есликонец циклаутверждение: b == e - 1  и             a[b] < x  и  x <= a[e];

Пусть даны очередь и стек.Рассмотрим фрагмент программы на псевдокоде:

    сделать стек пустым;    цикл пока очередь непуста    | x := взять элемент из начала очереди;    | добавить (вход: x) в стек;    конец цикла    цикл пока стек непуст    | x := взять элемент из стека;    | добавить (вход: x) в конец очереди;    конец цикла

Что произойдет с очередью в результатеего выполнения?