Главная | Обратная связь | Поможем написать вашу работу!

Рекомендации по отработке основных приемов программирования

Всюду далее помету # следует читать так: «рекомендуется задача с номером...» При этом # III.2 есть ссылка на задачу 2 из § III.

На вводных занятиях при отработке первичных приемов программирования используется ограничение на вид арифметических и логических выражений – не более одной операции (стандартного Паскаль) для арифметических выражений и только «сравнения» для логических. Рекомендуется ограничиться типовыми структурами управления(begin-end, if-then, if-then-else, for, while, repeat), уделяя им внимание пропорционально. А использование got o выделить в отдельную тему и рекомендовать его использование как «выход из процесса по исключительной (в локальном смысле) ситуации». Представляется особо важным специальная отработка навыков написания разнообразных глубоких вложений типовых структур управления.

На начальном этапе нотация блок-схем и линейная Паскаль-нотация представляются не столько взаимозаменяющими друг друга, сколько взаимодополняющими:

· блок-схемы акцентируют внимание на динамике (которую можно «мышечно» ощутить, двигаясь пальцем по путям), однако провоцируют способ рассуждений “по путям”;

· Паскаль-нотация акцентирует внимание на структуре вложенности действий, динамическая же сущность описываемого процесса остается в тени.

Осознанию единства динамики процесса и статики его описанной структуры помогают упражнения по построению трассировочной таблицы и по конвертации схем описаний процессов “БлокСхема↔СхемаПрограммы” (# II.1 (а-б), 4).

Последовательная структура управления:

1) экономия переменных (если значение переменной далее не используется): # III.2;

2) экономия вычислений сохранением значений переменных для дальнейшего использования: # III.3;

3) оптимизация организацией вычислений: # III.4, III.6;

4) задачи в неявной постановке: # III.5;

5) выражения регулярной структуры («развернутый цикл» – составление программ, содержащих повторение идентичных участков): # III.7-8.

Условная структура управления:

1) условный оператор: a) if-then-else: # III.10 (а,б); б) if- then: # III.10 (в,г);

2) условный в составном (рассуждение сведением к последовательности подзадач): # III.10 (д-ж), 11 (а-в), 12 (а,б), 14;

3) условный в условном (рассуждение разбором случаев): # III.10(ж), 11(в-г), 13(б);

4) вложения условного и составного: # III.11 (д), 12 (в-д).

Циклическая структура управления (без индексации).

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

· отработка навыков тестирования (построение трассировочной таблицы);

· отработка понятия «итерационная переменная» (переменные состояния процесса).

Пример 1. Вычислить значение .

Вычисление основано на регулярностях:

n: (0), 1, 2,...	n:=n+1
f: (1), 11, (11)2, (112)3,…	f:=f*n
z: (x), x³, x⁵,…	z:=zxx
p: (1), 3, 5, …	p:=p+2
s: (x), x+ х³/((11)3), x+х³/((11)3) + х⁵/((112)*5),…	s:=s+z/(f*p)

В этой задаче граф информационной связи между переменными заметно сложнее графа связей по управлению (между операторами):

Пример 2. Вычислить значение

y = (x + n) + (x + n)(x + (n –1)) +… (x + n)(x + (n –1))…(x + 2)(x + 1) x.

· Вычисление сводится к формированию последовательности:

(x+n),
(x+n)+(x+n)(x+(n–1)),
(x+n)+(x+n)(x+(n–1))+(x+n)(x+(n–1))(x + (n–2)), …

· Знак вопроса закрываем переменной t, которая должна последовательно получать значения:

(x+n)(x+(n–1)),
(x+n)(x+(n–1))(x+(n–2)),
(x+n)(x+(n–1))(x+(n–2))(x+(n–3)), …

Поэтому «y:=y+?» можно детализировать диаграммой информационных связей:

· Новый знак вопроса закрываем переменной r, которая должна последовательно получать значения: (x+(n–2)), (x+(n–3)), (x+(n–4))… Поэтому «t:=t*?» можно детализировать диаграммой информационных связей:

· В итоге выявлены дополнительные переменные, которые позволяют реализовать информационную зависимость y от (x, n), а также выявлены действия по вычислению их значений.

Пример 3. В предыдущих примерах существо задачи в том, чтобы найти отсутствующие в явном виде дополнительные «итерационные переменные». Но в них (почти) явно прописаны соответствующие последовательности, уже в постановке задачи.

Подход к решению задач типа «Найти целочисленное (с недостатком) значение » (I.4, 10.), видимо, естественно трактуется как «сведение к поиску»:

· линейный поиск: выбрать перечисление «кандидатов в решение» (в задаче – это 0,1,2,3,…) и проверить их в порядке этого перечисления;

· дихотомический поиск: выбрать ограниченную область поиска (в задаче – это интервал [ a, b), первоначально равный [0, n +1)) и, деля ее пополам, монотонно сокращать её объем.

1) Цикл и составной в цикле:

1.1) простейшие:

а) for- цикл: # I.1 (а),3; IV.1-3, 4 (а), 5 (а), 6 (а), 9 (а), 20 (а);

б) while- цикл: # I.2,4,6 (а); IV.4 (б), 5 (б), 6 (б), 7, 8;

в) repeat- цикл: # IV.25, 30.

1.2) выделение итерационных переменных:

а) for- цикл: # III.7-8(обобщенные на N); IV. 9 (б-г), 10, 11, 19, 20 (б-д), 21, 22 (а-в);

б) while-, repeat -циклы: # IV. 12-14, 23, 24, 27-29, 32.

2) Условный в цикле:

2.1) f or-цикл: # IV. 15-17;

2.2) while- цикл: # I.1 (б), 5, 6(б), 7-9; IV. 22 (г), 26, 31, 33.

3) Кратные циклы:

3.1) постоянной длины: # IV.34-35, 36 (б); I.13, 14;

3.2) переменной длины: # I.10; IV.36 (а).

4) Управление потоками: #V.

ЛИТЕРАТУРА

1. Ахо А.В., Хопкрофт Дж.Э., Ульман Дж.Д. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.

2. Ахо А.В., Хопкрофт Дж.Э., Ульман Дж.Д. Структуры данных и алгоритмы. – М.: Вильямс, 2000.

3. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ. – М.: Мир, 1981.

4. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985. Он же. Алгоритмы и структуры данных. – М.: Мир, 1989.

5. Вирт Н. Систематическое программирование. Введение. – М.: Мир. 1977.

6. Грогоно П. Программирование на языке Паскаль. – М.: Мир, 1982.

7. Йeнсен К., Вирт Н. Паскаль. Руководство для пользователя и описание языка. – М.: Финансы и статистика, 1982.

8. Кнут Д. Искусство программирования для ЭВМ. – М.: Мир. T.1: Основные алгоритмы. – 1976; Т.2: Получисленные алгоритмы. – 1977; Т.3: Сортировка и поиск. – 1978.

9. Кормен К., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: НЦНМО, 2001.

10. Малоземов В.Н., Певный А.Б. Рекуррентные вычисления. – Л.: Изд-во ЛГУ, 1976.

11. Мейер Б., Бодуэн К. Методы программирования, т.1, 2. – M.: Мир, 1982.

⇐ Предыдущая 1 2 3 4 56