Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

программирование_занятие_9

.doc
Скачиваний:
10
Добавлен:
14.05.2015
Размер:
251.9 Кб
Скачать

изучается:

Решение задач повышенной сложности: случай нескольких элементарных заданий в одном (количественная сложность); задания на исправление ошибок: задания на упрощение текста программ (непривычность).

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

«решение задач повышенной сложности».

Задачи повышенной сложности

Опишите алгоритм поиска трех последовательных элементов, сумма которых максимальна, в числовом массиве из 30 элементов. Решение запишите в словесной форме или на алгоритмических языках Бейсик или Паскаль.

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

Сначала составим программу поиска максимума из потока чисел.

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

Начало

Max=t – первый элемент

нет

Очередной элемент t существует

да

Max<t

Да

Max=t

конец

Первый элемент набора – сумма трех первых элементов массива.

Второй элемент набора может быть получен добавлением к первому четвертого элемента массива и вычитанию первого, вообще, очередной элемент набора, начиная с номера i=4, может быть получен из предыдущего элемента исследуемого набора путем добавления i-го и вычитания i-3-го элемента массива.

Начало

t=m[1]+m[2]+m[3], max=t, i=4

нет

i<=30

да

t=t+m[i]-m[i-3]

Max<p

Да

Max=p

конец

На языке Паскаль программа может иметь вид:

const n=30; type tm=array[1..n]of integer;

{создаем массив из 30 «случайных» чисел}

procedure create(var m:tm); var i:word;

begin for i:=1 to n do m[i]:=random(30); end;

{вывод элементов массива}

procedure vivod(var m:tm); var i:word;

begin for i:=1 to n do write(m[i]:3); writeln; end;

var m:tm; max,t,i:integer;

begin

randomize; create(m); vivod(m);{создали и вывели массив}

t:=m[1]+m[2]+m[3]; max:=t; {первый исследуемый элемент}

for i:=4 to n do

begin

t:=t+m[i]-m[i-3]; {очередной исследуемый элемент}

if t>max then max:=t; {определяем максимальный}

end;

writeln('max=',max); readln;{вывод результата и задержка}

end.

Создание и вывод массива оформлены как отдельные процедуры, что позволяет в основной программе иметь решение поставленной задачи.

/пауза/

Для проверки рекомендуется выводить все промежуточные элементы t.

На вход программе подаются сведения об участии в олимпиаде.

В первой строке сообщается количество учащихся N, каждая из следующих N строк имеет формат: <Фамилия> <Инициалы> <номер школы>, где <Фамилия> – строка, до 20 символов, <Инициалы> – строка, состоящая из 4-х символов (буква, точка, буква, точка), <номер школы> – не более чем двузначный номер. <Фамилия> и <Инициалы>, а также <Инициалы> и <номер школы> разделены одним пробелом. Пример входной строки:

Иванов П.С. 57

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

Следует учитывать, что N>=1000.

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

Искомый результат – номера школ, пославших минимальное число участников. Их может быть несколько. То есть в процессе работы мы должны хранить информацию о каждой школе. Всего школ не более 100, так как их номера двузначны. Для хранения промежуточных данных используем массив счетчиков. Индекс этого массива соответствует номеру школы. Изначально все элементы массива – нули.

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

Осталось определить минимальные, но не равные 0 элементы массива и вывести их индексы.

Var f:text m:array[1..99]of word; n,i,p,k,c,min:word; s:string;

begin

for i:=1 to 99 do m[i]:=0; {начальное значение счетчиков}

assign(f,’imf’); reset(f); readln(f,n); {извлечено количество участников}

for i:=1 to n do

begin

readl(f,s); {очередная строка данных}

p:=length(s); while s[p]<>’ ‘ do dec(p); {поиск первого справа пробела}

delete(s,1,p); val(s,k,c); inc(m[k]); {выделение цифр – номера школы и преобразование в число}

end;

min=n;

for i:=1 to 99 do if (m[i]>0)and(mim>m[i]) then min:=m[i]; {поиск ненулевого минимума}

for i:=1 to 99 do if m[i]=mim then write(i:3); {поиск ненулевого минимума}

writeln(min); readln; {}

end.

Программа, текст которой представлен, большое количество данных N из файла просматривает только один раз. Сформированный массив из 100 элементов просматривается дважды: первый раз для поиска минимума, второй – для выписывания ответа. Количество шагов при выполнении алгоритма пропорционально числу N+200. Это число всего на 200 больше обязательного минимума – требуется просмотреть все исходные данные.

На вход программе подаются 366 строк, которые содержат информацию о среднесуточной температуре всех дней 2004 года. В каждой строке сначала записана дата в виде dd.mm (на запись номера дня и номера месяца в числовом формате отводится строго два символа, день от месяца отделен точкой), затем через пробел записано значение температуры — число со знаком плюс или минус, с точностью до 1 цифры после десятичной точки. Данная информация отсортирована по значению температуры, то есть хронологический порядок нарушен. Требуется написать программу на языке Паскаль или Бейсик, которая будет выводить на экран информацию о месяце (месяцах), среднемесячная температура у которого (которых) наименее отклоняется от среднегодовой. В первой строке вывести среднегодовую температуру. Найденные значения для каждого из месяцев следует выводить в отдельной строке в виде: номер месяца, значение среднемесячной температуры, отклонение от среднегодовой температуры.

Итак, требуется подсчет средних значений. Не одного среднего, а средних значений температур для каждого из 12 месяцев.

Среднее значение – это величина отношения суммы элементов к их количеству. Для каждого месяца будем вести подсчет суммы температур и количества дней. С этой целью используем два массива, mt и mk. Изначально эти массивы нулевые, по мере обработки исходных данных они соответственно заполняются.

После заполнения, отношения элементов массивов с одинаковыми индексами даст среднемесячное значение температуры.

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

Теперь начинаем искать месяц со средней температурой, наиболее близкой к среднегодовой – поиск минимума соответствующих разностей. Как обычно, изначально считаем минимальной разность среднегодовой и среднемесячной для 1 месяца температур. Затем, определяем разность для следующих месяцев и запоминаем наименьшую из новой и имеющейся.

Усложнением задачи является необходимость выделения цифровой информации из строки знаков. Но из-за строгого регламентирования элементов строки эта подзадача легко решается стандартными функциями обработки строк.

Вот как может выглядеть программа на языке паскаль.

var mt:array[1..12]of real; mk:array[1..12]of word;

s:string; n,m,i,j,c,sk:word; t,st,sr,r:real; f:text;

begin

for i:=1 to 12 do begin mt[i]:=0; mk[i]:=0; end; {счетчики обнулены}

assign(f,’imf’); reset(f); n:=366;

for i:=1 to n do

begin

readln(f,s); writeln(s); {исходные данные}

val(copy(s,4,2),m,c); {выделены и преобразованы в число цифры месяца}

delete(s,1,5); val(s,t,c); {выделена и преобразована в число температура}

inc(mk[m]); mt[m]:=mt[m]+t; {сумма температур и количество дней месяца}

end;

st:=0; sk:=0; for i:=1 to 12 do

begin

st:=st+mt[i]; sk:=sk+mk[i]; {подсчет дней всего и суммы всех температур}

writeln(i:3,mt[i]/mk[i]:6:3); {вывод среднемесячных температур}

end;

sr:=st/sk; writeln(' sr=',sr:3:3); readln; {подсчет и вывод среднегодовой температуры}

for i:=1 to 12 do

begin

if i=1 then r:=abs(sr-mt[i]/mk[i]) {min = разница средних года и 1 месяца}

else {поиск минимальной разницы и соответствующего номера месяца}

if abs(sr-mt[i]/mk[i])<r then begin r:=abs(sr-mt[i]/mk[i]); end;

end;

writeln(‘ответ:’);

for i:=1 to 12 do if sr=mt[i]/mk[j] then

writeln(i:3,mt[j]/mk[j]:7:3,sr-mt[j]/mk[j]:6:3);

readln;

end.(**)

Задачи на исправление ошибок

Предлагается программа, содержащая, ошибки. По замыслу, она должна определять день недели для произвольного дня месяца. В ней считается, что первое число данного месяца — понедельник. Взяв эту программу за основу, напишите программу, которая будет решать ту же задачу при условии, что w1 — день недели для первого числа месяца. Значение w1 (целое число от 1 до 7) должно запрашиваться программой. Интересующее нас число месяца d (от 1 до 31) также должно запрашиваться. Предполагается, что ввод данных будет корректным.

Программа на языке Паскаль

Программа на языке Бейсик

Var d,w:integer;

begin

readln(d);

w:=d div 7;

case w of

1:writeln(’понедельник’);

2:writeln(’вторник’);

3:writeln(’среда’);

4:writeln(’четверг’);

5:writeln(’пятница’);

6:writeln(’суббота’);

7:writeln(’воскресенье’);

end

end.

DIM w, d AS INTEGER

INPUT d

w = d \ 7

IF w = 1 THEN PRINT “понедельник”

IF w = 2 THEN PRINT “вторник”

IF w = 3 THEN PRINT “среда”

IF w = 4 THEN PRINT “четверг”

IF w = 5 THEN PRINT “пятница”

IF w = 6 THEN PRINT “суббота”

IF w = 7 THEN PRINT “воскресенье”

END

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

Первая ошибка – вместо целочисленного деления нужно использовать нахождение остатка от деления.

Вторая ошибка заключается в том, что остатки от деления начинаются с нуля, а в задаче счет требуется с 1.

Правильные варианты программ:

Программа на языке Паскаль

Программа на языке Бейсик

Var d,w:integer;

begin

readln(d);

w:=d mod 7 + 1;

case w of

1:writeln(’понедельник’);

2:writeln(’вторник’);

3:writeln(’среда’);

4:writeln(’четверг’);

5:writeln(’пятница’);

6:writeln(’суббота’);

7:writeln(’воскресенье’);

end

end.

DIM w, d AS INTEGER

INPUT d

w = d mod 7 + 1

IF w = 1 THEN PRINT “понедельник”

IF w = 2 THEN PRINT “вторник”

IF w = 3 THEN PRINT “среда”

IF w = 4 THEN PRINT “четверг”

IF w = 5 THEN PRINT “пятница”

IF w = 6 THEN PRINT “суббота”

IF w = 7 THEN PRINT “воскресенье”

END

Рассматривается стандартная шахматная доска размером 8х8. Примем, что i – номер вертикали, j – номер горизонтали. В левом нижнем углу, (это поле черного цвета) стоит черный король. В правом нижнем углу, стоит белый король. Введены обозначения: P(i,j) ‑ минимальное число ходов, за которое черный король может попасть на поле (i,j); V(i,j) ‑ минимальное число ходов, за которое белый король может попасть на поле (i,j).

Напомним, что король может ходить на 1 клетку в любом направлении (по горизонтали, вертикали или диагонали).

Программист написал программу, в которой требовалось определить все такие поля (i,j), для которых P(i,j) = V(i,j), и выдать на экран соответствующие значения i,j (текст программы приведен ниже).

1) Выдаст ли программа, написанная программистом, поле, для которого i=4, j=5 ?

2) Указать все из перечисленных ниже полей, которые удовлетворяют постановке задачи, т.е. для таких полей должно быть выполнено P(i,j) = V(i,j)

(i=1, j=8), (i=2, j=8), (i=1, j=7), (i=5, j=5), (i=8, j=6)

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

Программа на языке Паскаль

Программа на языке Бейсик

VAR i,j: integer;

BEGIN

writeln(‘искомые поля’);

for j:=5 to 8 do

for i:=1 to 8 do

begin

if (i=9-j) OR (i=j)

then writeln(‘i=’,i, ‘j=’,j);

end;

END.

PRINT “Искомые поля”

FOR J=5 TO 8

FOR I=1 TO 8

IF (I=9-J) OR (I=J) THEN

PRINT “I=”; I

PRINT “J=”; J

ENDIF

NEXT I

NEXT J

END

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

7 7

7 7

7 7

7 7

7 7

7 7

7 7

7 7

8

6 7

6 6

6 6

6 6

6 6

6 6

6 6

7 6

7

5 7

5 6

5 5

5 5

5 5

5 5

6 5

7 5

6

4 7

4 6

4 5

4 4

4 4

5 4

6 4

7 4

5

3 7

3 6

3 5

3 4

4 3

5 3

6 3

7 3

4

2 7

2 6

2 5

3 4

4 3

5 2

6 2

7 2

3

1 7

1 6

2 5

3 4

4 3

5 2

6 1

7 1

2

7

1 6

2 5

3 4

4 3

5 2

6 1

7

1

1

2

3

4

5

6

7

8

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

Программа на языке Паскаль

Программа на языке Бейсик

VAR i,j: integer;

BEGIN

writeln(‘искомые поля’);

for j:=5 to 8 do

for i:=1 to 8 do

begin

if (i=9-j) OR (i=j)

then writeln(‘i=’,i, ‘j=’,j);

end;

END.

PRINT “Искомые поля”

FOR J=5 TO 8

FOR I=1 TO 8

IF (I=9-J) OR (I=J) THEN

PRINT “I=”; I

PRINT “J=”; J

ENDIF

NEXT I

NEXT J

END

Попробуем выполнить программу.

При j=5 выделяются клетки i=4 i=5

7 7

7 7

7 7

7 7

7 7

7 7

7 7

7 7

8

6 7

6 6

6 6

6 6

6 6

6 6

6 6

7 6

7

5 7

5 6

5 5

5 5

5 5

5 5

6 5

7 5

6

4 7

4 6

4 5

4 4

4 4

5 4

6 4

7 4

5

3 7

3 6

3 5

3 4

4 3

5 3

6 3

7 3

4

2 7

2 6

2 5

3 4

4 3

5 2

6 2

7 2

3

1 7

1 6

2 5

3 4

4 3

5 2

6 1

7 1

2

7

1 6

2 5

3 4

4 3

5 2

6 1

7

1

1

2

3

4

5

6

7

8

При j=6, выделяются i=3 i=6

7 7

7 7

7 7

7 7

7 7

7 7

7 7

7 7

8

6 7

6 6

6 6

6 6

6 6

6 6

6 6

7 6

7

5 7

5 6

5 5

5 5

5 5

5 5

6 5

7 5

6

4 7

4 6

4 5

4 4

4 4

5 4

6 4

7 4

5

3 7

3 6

3 5

3 4

4 3

5 3

6 3

7 3

4

2 7

2 6

2 5

3 4

4 3

5 2

6 2

7 2

3

1 7

1 6

2 5

3 4

4 3

5 2

6 1

7 1

2

7

1 6

2 5

3 4

4 3

5 2

6 1

7

1

1

2

3

4

5

6

7

8