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

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

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 295 RSS
←   Декабрь 2021   →
 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
31


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


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

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

Статистика

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

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


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

Лучшие эксперты в разделе

Алексеев Владимир Николаевич
Статус: Мастер-Эксперт
Рейтинг: 1182
∙ повысить рейтинг » 		Лысков Игорь Витальевич
Статус: Мастер-Эксперт
Рейтинг: 42
∙ повысить рейтинг » 		Gluck
Статус: 9-й класс
Рейтинг: 41
∙ повысить рейтинг »

Алгоритмы и теория программирования

Номер выпуска:245
Дата выхода:11.12.2021, 22:45
Администратор рассылки:Зенченко Константин Николаевич (Старший модератор)
Подписчиков / экспертов:2 / 17
Вопросов / ответов:3 / 4

Консультация # 144128: Помогите, пожалуйсто: Предполжим, что вам прислали программу про которую известно, что она детерменирована, и про кторую утверждается, что она работает правильно и использует число операций меньшее чем линейный поиск. Придумайте набор тестов, который определенно покажет, что программа работает не быстрее линейного поиска или ошибается...
Консультация # 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. Указать, что вычисляет следующий фрагмент программы...
Консультация # 113855: Здравствуйте уважаемые эксперты!!! Решил заняться изучением языков программирования, с чего мне начать, с какого языка? Говорят что самый клевый ассамблер, с помощью него можно много чего ломать! ..

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

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

Дата отправки: 16.09.2008, 20:15
Вопрос задал: Капранов Павел Павлович
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Гнедов Андрей:

Здравствуйте, Капранов Павел Павлович!
В такой постановке задачу не решить. Если заменить проверку при всех возможных начальных условиях на конечный набор тестов, то легко построить программу, которая просто распознает тест из набора и выдает ответ, который "знает" заранее. Это будет очень быстро. Примерно так, как легко умножать по таблице умножения.

Консультировал: Гнедов Андрей
Дата отправки: 17.09.2008, 14:47
Рейтинг ответа:

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

Консультация # 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
Вопрос задал: Заречнева Вера Михайловна
Всего ответов: 1
Страница онлайн-консультации »

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

Здравствуйте, Заречнева Вера Михайловна!
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 одобряю!

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

Здравствуйте уважаемые эксперты!!!
Решил заняться изучением языков программирования, с чего мне начать, с какого языка?
Говорят что самый клевый ассамблер, с помощью него можно много чего ломать!

Дата отправки: 13.12.2007, 18:06
Вопрос задал: Смирнов Руслан Юрьевич
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Виктор Пырлик:

Здравствуйте, Смирнов Руслан Юрьевич!

Начинать надо не с языков а с теории программирования...
Сомнительно, что вы будите писать на ассемблере под Windows (да и под *nix).
Наверно, в этом плане лучше все же С/С++. Да и потом легче будет «перейти» на скриптовые, типа PHP, Java*, Perl и т.д. (WEB ориентированные, например)
Но ассемблер действительно стоит в начале – это язык «человек/машина», но применим весьма в узких кругах, в основном это системное программирование (что требует кучу дополнительных знаний) или «тонкой» доводки алгоритмов, но знать его никому не мешает.
Начните с ассемблера.. Если не хватит терпения – переходите на С/С++.
С прикладной точки зрения, ассемблер сегодня мало применим. В плане обучения достаточно сложен. В ВУЗах, как правило, начинают с Pascal.. но его синтаксис и подход не так распространен как у С/С++.

Консультировал: Виктор Пырлик
Дата отправки: 13.12.2007, 18:43
Рейтинг ответа:

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

Консультирует Кэр Лаэда:

Здравствуйте, Смирнов Руслан Юрьевич!
Согласен с Виктором Пырликом для того чтобы начать программировать на Ассемблере нужно понимать очень много в программировании, но не только в программировании но и в организации компьютера, его строении, структуры памяти и т.д. поэтому все же советую начинать либо с Pascal либо с C, однако если желание очень велико, и вы все же хотите писать на ассемблере то лучший по моему выход в этой ситуации это рассылка Калашникова "Ассемблер это просто"

можете ознакомится тут

Консультировал: Кэр Лаэда
Дата отправки: 13.12.2007, 18:55
Рейтинг ответа:

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

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

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

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