Ответы на задачи С4

Название	Ответы на задачи С4
страница	1/9
Дата конвертации	17.09.2012
Размер	1.53 Mb.
Тип	Документы

1 2 3 4 5 6 7 8 9

Ответы на задачи С4:

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

{ ввод данных, накопление сумм по месяцам и за год }

{ вычисление средних по месяцам и по году }

{ поиск месяца с минимальным отклонением t
от средней по году }

{ вывод всех месяцев с таким же отклонением }

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

for i:=1 to 12 do tMonth[i]:= 0;

tYear := 0;

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

for i:=1 to DAYS do begin

repeat read (c); until c = '.';

read (month);

readln (t);

tMonth[month] := tMonth[month] + t;

tYear := tYear + t;

end;

Далее находим средние по каждому месяцу и по году (важно! месяцы имеют разное число дней, 2008-ой год – високосный, поэтому в феврале 29 дней)

for i:=1 to 12 do

case i of

2: tMonth[i] := tMonth[i] / 29;

4,6,9,11: tMonth[i] := tMonth[i] / 30;

else tMonth[i] := tMonth[i] / 31;

end;

tYear := tYear / DAYS;

Определить среднюю температуру по месяцам можно более красиво, если ввести массив констант – дней в каждом месяце:

const days: array[1..12] of integer =

(31,29,31,30,31,30,31,31,30,31,30,31);

а потом сделать так:

for i:=1 to 12 do

tMonth[i] := tMonth[i] / days[i];

но PascalABC, например, не поддерживает константные массивы.

Теперь можно искать минимальное отклонение среднемесячной температуры от среднегодовой (важно! не забываем ставить модуль):

min := abs(tMonth[1] - tYear);

for i:=2 to 12 do

if abs(tMonth[i] - tYear) < min then

min := abs(tMonth[i] - tYear);

Вывод результата очевиден, приведем сразу полную программу:

const DAYS = 366;

var tMonth: array[1..
12] of real;

i, month: integer;

t, tYear, min: real;

c: char;

begin

for i:=1 to 12 do tMonth[i]:= 0;

tYear := 0;

for i:=1 to DAYS do begin

repeat read(c); until c = '.';

read (month);

readln (t);

tMonth[month] := tMonth[month] + t;

tYear := tYear + t;

end;

for i:=1 to 12 do

case i of

2: tMonth[i] := tMonth[i] / 29;

4,6,9,11: tMonth[i] := tMonth[i] / 30;

else tMonth[i] := tMonth[i] / 31;

end;

tYear := tYear / DAYS;

min := abs(tMonth[1] - tYear);

for i:=2 to 12 do

if abs(tMonth[i] - tYear) < min then

min := abs(tMonth[i] - tYear);

writeln(tYear:0:2);

for i:=1 to 12 do

if abs(tMonth[i] - tYear) = min then

writeln(i,' ',tMonth[i]:0:2,' ',tMonth[i]-tYear:0:2);

end.

Здесь нужно считать одинаковые буквы, которых всего может быть 26 (от A до Z), причем строчные и заглавные буквы считаются вместе. Поэтому создаем массив счетчиков из 26 элементов:

var count: array[1..26] of integer;

Для удобства можно сразу коды букв A и a и записать в целые переменные

cA := Ord('A'); { заглавные }

cAm := Ord('a'); { строчные }

В цикле, прочитав очередной символ, находим его код с помощью функции Ord,

k := Ord(c);

Если это заглавная буква, то номер символа в алфавите вычисляется как k-cA+1, а для строчных k-cAm+1, соответствующий счетчик (элемент массива) нужно увеличить на 1:

if ('A' <= c) and (c <= 'Z') then

count[k-cA+1] := count[k-cA+1] + 1;

if ('a' <= c) and (c <= 'z') then

count[k-cAm+1] := count[k-cAm+1] + 1;

Когда все данные (до первой точки) введены, остается найти номер максимального элемента (переменная iMax), а затем вывести на экран соответствующий символ и количество повторений. Вот полная программа:

var count:array[1..26] of integer;

i, k, cA, cAm, iMax:integer;

c: char;

begin

cA := Ord('A');

cAm := Ord('a');

for i:=1 to 26 do count[i] := 0;

repeat

read(c);

k := Ord(c);

if ('A' <= c) and (c <= 'Z') then

count[k-cA+1] := count[k-cA+1] + 1;

if ('a' <= c) and (c <= 'z') then

count[k-cAm+1] := count[k-cAm+1] + 1;

until c = '.';

iMax := 1;

for i:=2 to 26 do

if count[i] > count[iMax] then iMax := i;

writeln(char(cA+iMax-1), ' ', count[iMax]);

end.

Возможно, несколько лучшее решение получится, если использовать массив счетчиков с символьными индексами (это можно сделать в Паскале, но не во всех языках программирования):

var count:array['A'..'Z']of integer;

После чтения символа удобно сразу привести его к верхнему регистру с помощью функции ^ UpCase (преобразовать строчные буквы в заглавные):

c := UpCase(c);

или (если в вашей версии Паскаля ее нет) вручную

if c in ['a'..'z'] then

c := Char(Ord(c) - Ord('a') + Ord('A'));

Если символ – латинская буква, то увеличиваем соответствующий счётчик:

if c in ['A'..'Z'] then Inc(count[c]);

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

iMax:='A';

for c:='B' to 'Z' do

if count[c] > count[iMax] then iMax:=c;

writeln(iMax,' ',count[iMax]);

Отметим, что такое красивое решение возможно только в тех языках программирования, где есть массивы с симврольными индексами. Вот полная программа:

var c, iMax:char;

count: array['A'..'Z'] of integer;

begin

for c:='A' to 'Z' do count[c]:=0;

repeat

read(c);

if c in ['a'..'z'] then

c := Char(Ord(c) - Ord('a') + Ord('A'));

if c in ['A'..'Z'] then Inc(count[c]);

until c = '.';

iMax:='A';

for c:='B' to 'Z' do

if count[c] > count[iMax] then iMax := c;

writeln(iMax,' ',count[iMax]);

end.

Все аналогично предыдущей задаче с двумя изменениями: заглавных букв нет и нужно вывести количество для всех букв. Код программы:

var count:array[1..26] of integer;

i, k, cA:integer;

c: char;

begin

cA := Ord('a');

for i:=1 to 26 do count[i] := 0;

repeat

read(c);

k := Ord(c);

if ('a' <= c) and (c <= 'z') then

count[k-cA+1] := count[k-cA+1] + 1;

until c = '.';

for i:=1 to 26 do

if count[i] > 0 then

writeln(char(cA+i-1), count[i]);

end.

Возможен и другой вариант (идею предложил Р. Басангов, МОУ «СОШ 3» г. Элиста), в котором используется массив с символьными индексами:

count: array ['a'..'z'] of integer;

Вот полное решение:

var count: array ['a'..'z'] of integer;

c: char;

begin

for c:='a' to 'z' do count[c]:=0;

repeat

read (c);

if ('a' <= c) and (c <= 'z') then

count[c] := count[c] + 1;

until c = '.';

for c:='a' to 'z' do

if count[c]>0 then

writeln(c, count[c]);

end.

Заметим, что в этой задаче мы должны хранить в памяти все фамилии и считать, сколько раз они встретились. При этом имена нас не интересуют, поэтому можно выделить такой массив записей

var Info: array[1..100] of record

name: string; { фамилия }

count: integer; { счетчик }

end;

Второе поле (счётчик count) показывает, какая это запись по счёту с той же самой фамилией. Например, если счётчик равен 5, раньше эта фамилия встречалась уже 4 раза.

В этой задаче легко читать информацию целыми строками, а затем «вырезать» фамилию с помощью стандартных функций (фамилия окажется в строке s):

readln(s);

p := Pos(' ', s);

s := Copy(s,1,p-1);

Теперь проверяем, сколько таких фамилй уже есть в списке. Нужно в цикле просмотреть i-1 первых элементов массива Info (где i – номер обрабатываемой строки), если фамилия в очередной записи совпала с только что введенной, счетчик (переменная c) увеличивается на 1:

c := 1;

for k:=1 to i-1 do

if s = Info[k].name then

c := c + 1;

Затем записываем фамилию ученика и значение счётчика в очередную запись:

Info[i].name := s;

Info[i].count := c;

После обработки всех строк остается вывести на экран результат (список логинов). Если счётчик равен 1, фамилия встратилась в первый раз, и логин совпадает с фамилией. Если счётчик больше 1, его значение дописывается в конец фамилии (получаются логины вида «Иванов2», «Иванов3» и т.п.):

for i:=1 to N do begin

write(Info[i].name);

if Info[i].count > 1 then

write(Info[i].count);

writeln;

end;

Вот полный код программы:

var Info: array[1..100] of record

name: string;

count: integer;

end;

i, k, p, N, c: integer;

s: string;

exist: boolean;

begin

readln(N);

for i:=1 to N do begin

readln(s);

p := Pos(' ', s);

s := Copy(s,1,p-1);

c := 1;

for k:=1 to i-1 do

if s = Info[k].name then

c := c + 1;

Info[i].name := s;

Info[i].count := c;

end;

for i:=1 to N do begin

write(Info[i].name);

if Info[i].count > 1 then write(Info[i].count);

writeln;

end;

end.

Это упрощенный вариант второй задачи, подробно разобранной в основной части. Отличия: нужно найти максимум вместо минимума, и только один, а не три.

const LIM = 250;

var Info: array[1..LIM] of record

name: string;

sum: integer;

end;

i, k, N, mark, max: integer;

c: char;

begin

readln(N);

{ ввод исходных данных }

for i:=1 to N do begin

Info[i].name := '';

for k:=1 to 2 do

repeat

read(c);

Info[i].name := Info[i].name + c;

until c = ' ';

Info[i].sum := 0;

for k:=1 to 3 do begin

read(mark);

Info[i].sum := Info[i].sum + mark;

end;

readln;

end;

{ поиск максимума}

max := Info[1].sum;

for i:=2 to N do

if Info[i].sum > max then

max := Info[i].sum;

{ вывод результата }

for i:=1 to N do

if Info[i].sum = max then

writeln(Info[i].name);

end.

Возможен другой вариант решения (А.С. Абрамов, лицей при РГСУ, г. Воронеж), основанный на следующей идее: в массив записываются фамилии только тех участников, которые имеют суммарный балл, равный максимальному на данный момент; если максимум меняется, возвращаемся к 1-му элементу массива и следующую «цепочку» максимумов записываем поверх предыдущей. Обработка данных выполняется сразу при вводе, отдельный поиск максимума не требуется.

Целая переменная count будет обозначать количество найденных участников с максимальным баллом. В переменной max будем хранить максимальный (на данный момент) результат, а в переменной ball накапливать сумму баллов очередного участника. Тогда алгоритм обработки выглядит так (переменная s содержит фамилию и имя):

if ball > max then begin { новый максимум }

count := 1;

max := ball;

names[1] := s;

end

else

if ball = max then begin { еще один участник в списке }

count := count + 1;

names[count] := s;

end;

Вот полная программа:

const LIM = 250;

var names: array[1..LIM] of string;

i, k, N, ball, mark, max, count: integer;

s: string;

c: char;

begin

readln(N); { ввод количества участников }

max := 0; count:=0;

{ ввод данных в цикле }

for i:=1 to N do begin

s := '';

for k:=1 to 2 do { читаем фамилию и имя }

repeat

read(c);

s := s + c;

until c = ' ';

{ считываем и суммируем баллы }

ball := 0;

for k:=1 to 3 do begin

read(mark);

ball := ball + mark;

end;

readln;

{ ищем участников с максимальлным баллом }

if ball > max then begin

count := 1;

max := ball;

names[1] := s;

end

else

if ball = max then begin

count := count + 1;

names[count] := s;

end;

end;

{ вывод результата }

for i:=1 to count do

writeln(names[i]);

end.

Это вариант второй задачи, подробно разобранной в основной части. Отличия: нужно найти максимум вместо минимума, сумма складывается из четырех оценок.

const LIM = 100;

var Info: array[1..LIM] of record

name: string;

sum: integer;

end;

i, k, N, mark, max1, max2, max3: integer;

c: char;

begin

readln(N);

{ ввод исходных данных }

for i:=1 to N do begin

Info[i].name := '';

for k:=1 to 2 do

repeat

read(c);

Info[i].name := Info[i].name + c;

until c = ' ';

Info[i].sum := 0;

for k:=1 to 4 do begin

read(mark);

Info[i].sum := Info[i].sum + mark;

end;

readln;

end;

{ поиск трех максимальных }

max1 := 0; max2 := 0; max3 := 0;

for i:=1 to N do begin

if Info[i].sum > max1 then begin

max3 := max2; max2 := max1;

max1 := Info[i].sum;

end

else if Info[i].sum > max2 then begin

max3 := max2;

max2 := Info[i].sum;

end

else if Info[i].sum > max3 then

max3 := Info[i].sum;

end;

{ вывод результата }

for i:=1 to N do

if Info[i].sum >= max3 then

writeln(Info[i].name);

end.

Особенность этой задачи в том, что фамилии на выходе нужно отсортировать. «Школьные» сортировки имеют сложность ; это вообще говоря, не лучший вариант, но без сортировки здесь не обойтись. Применять «быстрые» сортировки (например, QuickSort) не следует, даже если вы их знаете – эксперты могут не понять.
Читаем очередную строку посимвольно до второго пробела, накапливаем строку в переменной s – там окажется фамилия вместе с именем:

s := '';

for k:=1 to 2 do

repeat

read(c);

s := s + c;

until c = ' ';

Теперь читаем два числа,

readln(mark1, mark2);

Учитывая, что до конца строки больше нет данных, используем оператор readln, а не read. Если хотя бы одна из оценок меньше 30, увеличиваем счетчик «неудачников» (переменная count) и записываем фамилию и имя (из переменной s) в элемент массива name с номером count:

if (mark1 < 30) or (mark2 < 30) then begin

count := count + 1;

name[count] := s;

end;

После чтения всех данных массив фамилий «неудачников» нужно отсортировать, здесь мы используем простейший метод – классический «пузырек». Не забываем, что нужно сортировать не все N строк в массиве name, а только count (столько, сколько нашли «неудачников»):

for i:=1 to count-1 do

for k:=count-1 downto i do

if name[k] > name[k+1] then begin

s := name[k]; name[k] := name[k+1];

name[k+1] := s;

end;

Вот полная программа:

const LIM = 500;

var name: array[1..LIM] of string;

i, k, count, mark1, mark2, N: integer;

c: char;

s: string;

begin

readln(N);

{ ввод исходных данных }

count := 0;

for i:=1 to N do begin

s := '';

for k:=1 to 2 do

repeat

read(c);

s := s + c;

until c = ' ';

readln(mark1, mark2);

if (mark1 < 30) or (mark2 < 30) then begin

count := count + 1;

name[count] := s;

end;

end;

{ сортировка }

for i:=1 to count-1 do

for k:=count-1 downto i do

if name[k] > name[k+1] then begin

s := name[k]; name[k] := name[k+1];

name[k+1] := s;

end;

{ вывод результата }

for i:=1 to count do

writeln(name[i]);

end.

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

var podr: array[1..100] of integer;

Количество найденных разных подразделений будем хранить в целой переменной count (это счетчик, в начале в него нужно записать 0).

Нас не интересуют фамилии и имена сотрудников, а также их полные телефоны. Поэтому при чтении строки пропускаем все символы до второго знака «–» включительно:

for k:=1 to 2 do

repeat

read(c);

until c = '-';

затем читаем номер подразделения в целую переменную p и проверяем, нет ли его в массиве podr (если есть – логическая переменная exist устанавливается в True):

for k:= 1 to count do

if podr[k] = p then begin

exist := True;

break;

end;

С помощью оператора break досрочно выходим из цикла, если прочитанный номер уже есть в массиве. Если номер не нашли, увеличиваем счетчик и сохраняем этот номер в очередном элементе массива:

if not exist then begin

count := count + 1;

podr[count] := p;

end;

После этого остается разделить общее число сотрудников N на количество подразделений. Вот полная программа:

var podr: array[1..100] of integer;

i, k, p, count, N: integer;

c: char;

exist: boolean;

av: real;

begin

readln(N);

{ ввод исходных данных }

count := 0;

for i:=1 to N do begin

for k:=1 to 2 do

repeat read(c); until c = '-';

readln(p);

exist := False;

for k:= 1 to count do

if podr[k] = p then begin

exist := True;

break;

end;

if not exist then begin

count := count + 1;

podr[count] := p;

end;

end;

{ вывод результата }

av := N / count;

writeln(av:0:2);

end.

Еще одно, более красивое решение этой задачи, предложила Л.Б. Кулагина (ФМЛ № 239, г. Санкт-Петербург). Идея заключается в том, чтобы создать массив логических значений (по количеству возможных подразделений), сначала в каждый его элемент записать false и при чтении номера подразделения в соответствующий элемент записывать true (нашли этот номер). В конце программы для определения количества подразделений останется подсчитать, сколько элементов массива имеют значение true.

var podr: array[0..99] of boolean;

i, k, p, count, N: integer;

c: char;

av: real;

begin

readln(N);

{ ввод исходных данных }

for i:=0 to 99 do

podr[i] := False; { еще ничего не нашли }

1 2 3 4 5 6 7 8 9

	Ответы на задачи A1-A13		Ответы на задачи A1-A13
	Документы 1. /ответы 9/архитектура компьютера.doc 2. /ответы...		Предлагаю решить олимпиадные задачи! Правильные ответы укажите на странице нашего форума!
	Ответы на задачи Первоначально тетради лежали в таком порядке: коричневая, красная, желтая, серая, синяя		Ответы на задачи С3 Задача полностью аналогична первой задаче, разобранной в тексте. Рекуррентная формула, определяющая заполнение массива
	Ответы на задачи С3 Задача полностью аналогична первой задаче, разобранной в тексте. Рекуррентная формула, определяющая заполнение массива		Документы 1. /Ответы/1 Книга песен Петрарки.txt 2. /Ответы/10.txt
	Ответы на задачи команды «Многогранник» Один крокодил весит 3 гориллы Тетради лежали на столе в следующем порядке: красная, коричневая, синяя, серая, жёлтая		Ответы на задачи С1 Хотя в задании сказано «Приведите пример таких чисел a, b, X,…», значение X ни на что не влияет (см далее), в ответе можно указать...
	Ответы на задачи С1 Хотя в задании сказано «Приведите пример таких чисел a, b, X,…», значение X ни на что не влияет (см далее), в ответе можно указать...

Ответы на задачи С4

Ответы на задачи С4:

Похожие: