Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Алгоритмы и теория программирования

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 295 RSS
←   Сентябрь 2011   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rfpro.ru/
Открыта: 11-11-2009

Автор
Калашников О.А.

Статистика

295 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Алгоритмы и теория программирования


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка
Статус: Академик
Рейтинг: 8509
∙ повысить рейтинг » 		Роман Селиверстов
Статус: Советник
Рейтинг: 2856
∙ повысить рейтинг » 		Boriss
Статус: Академик
Рейтинг: 2636
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / Алгоритмы и теория программирования

Номер выпуска:147
Дата выхода:24.09.2011, 14:01
Администратор рассылки:Калашников О.А. (Руководитель)
Подписчиков / экспертов:326 / 164
Вопросов / ответов:1 / 2

Консультация # 184054: Здравствуйте! У меня возникли сложности с таким вопросом: 1. Указать, что вычисляет следующий фрагмент программы: дано: цел n; цел x, y; x := 1; y := 4; цикл пока y <= n | инвариант: y = (x + 1)2; | x := x + 1; | y := y + 2*x + 1; конец цикла ответ := x; 2. Указать, что вычисляет следующий фрагмент программы...

Консультация # 184054:

Здравствуйте! У меня возникли сложности с таким вопросом:
1. Указать, что вычисляет следующий фрагмент программы:
дано: цел n;
цел x, y;
x := 1; y := 4;
цикл пока y <= n
| инвариант: y = (x + 1)2;
| x := x + 1;
| y := y + 2*x + 1;
конец цикла
ответ := x;

2. Указать, что вычисляет следующий фрагмент программы:
дано: цел n;
цел s, k;
s := 10; k := 0;
цикл пока s <= n
| инвариант: s = 10 * (k + 1)
| s := s + 10; k := k + 1;
конец цикла
ответ := k;

3. Рассмотрим следующий фрагмент программы:
цел m, n;
цел a, b, p;
. . .
a := m; b := n;
p := 0;
цикл пока b != 0
| если b четное
| | то
| | b := b / 2;
| | a := a * 2;
| | иначе
| | b := b - 1;
| | p := p + a;
| конец если
конец цикла
ответ := p;
Какое условие является инвариантом цикла?
Равенство ab p = mn.
Равен ство a b + p = m n.

4. Рассмотрим следующий фрагмент программы, вычисляющей частное 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
Какое условие является инвариантом цикла?
Число e является степенью двойки, а также выполняются равенства a - q∙b = r и m = e∙b.
Число e является степенью двойки, а также выполняются равенства a - q∙m = r и m = e∙b.

5. Какое утверждение является инвариантом для следующего фрагмента программы (т.е. из справедливости утверждения до выполнения фрагмента программы вытекает справедливость утверждения пос ле выполнения)? Предполагается, что n > 0.
вещ r, x; цел n;
. . .
r := -r * x;
r := r * n / (n + 1);
n := n + 1;

Утверждение r = (-1)n xn/n!, где восклицательным знаком обозначен факториал числа n.
Утверждение r = (-1)n-1 xn/n.

6. Оценить сверху время работы (т.е. количество выполнений тела цикла) алгоритма быстрого возведения в степень:
дано: основание a и показатель степени n >= 0
надо: вычислить a в степени n
вещ b, p; цел k;
b := a; p := 1.0; k := n;

цикл пока k > 0
| инвариант: bk p = an
| если k четное
| | то
| | k := k / 2;
| | b := b * b;
| | иначе
| | k := k - 1;
| | p := p * b;
| конец если
конец цикла

ответ := p;

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

7. Пусть f(x) — целочисленная функция от целочисленного аргумента. Определить, содержит ли следующий фрагмент программы ошибку (т.е. действительно ли тело цикла сохраняет инвариант):
// Программа корень функции
цел a, b, c;
. . .
утверждение: a < b и f(a) * f(b) <= 0;
// Значения функции на концах отрезка [a,b] разных знаков

цикл пока b - a > 1
| инвариант: f(a) * f(b) <= 0
| // Делим отрезок [a, b] пополам
| c := (a + b) / 2; // c -- целая часть (a+b)/2
| если f(a) * f(c) < 0
| | то b := c; // выбираем левую половину отрезка
| | иначе a := c; // выбираем правую половину отрезка
| конец если
конец цикла

утверждение: a == b - 1 и f(a) * f(b) <= 0;

Дата отправки: 19.09.2011, 13:38
Вопрос задал: Заречнева Вера Михайловна (Посетитель)
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Асмик Гаряка (Академик):

Здравствуйте, Заречнева Вера Михайловна!
1. Указать, что вычисляет следующий фрагмент программы:
дано: цел n;
цел x, y;
x := 1; y := 4;
цикл пока y <= n
| инвариант: y = (x + 1)^2;
| x := x + 1;
| y := y + 2*x + 1;
конец цикла
ответ := x;
Квадратный корень из n

2 После выполнения цикла s > n и s = 10 * (k + 1), k=n div 10

3) Равенство a b + p = m n.
4) Число e является степенью двойки, а также выполняются равенства a - q∙b = r и m = e∙b.
5)Утверждение r = (-1)n-1 xn/n.
6) Время работы не больше, чем C∙log2 n, где C — некоторая константа (т.е. время пропорционально количеству цифр в двоичной или десятичной записи числа n).
7) Инвариант сохраняется.

Консультировал: Асмик Гаряка (Академик)
Дата отправки: 19.09.2011, 14:57
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультирует Орловский Дмитрий (Советник):

Здравствуйте, Заречнева Вера Михайловна!
1) В результате одной итерации цикла величина y становится равной 4x+5, а x заменяется на x+1. Таким образом, цикл совершается пока x≤(n-5)/4. Это значит, что в конце цикла x станет равным целой части от числа (n+3)/4. А это и яляется результатом.
Ответ: целой части от числа (n+3)/4
(например, при n=97,n=98,n=99 и n=100 получим x=25)

P.S. Я понял (x + 1)2 как (x + 1)*2

Консультировал: Орловский Дмитрий (Советник)
Дата отправки: 19.09.2011, 16:03
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2011, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.33 от 10.09.2011
В избранное