Практикум по программированию на алгоритмических языках сборник заданий



Скачать 330.24 Kb.
Дата21.10.2016
Размер330.24 Kb.
ТипПрактикум

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

«Челябинский государственный университет»

Математический факультет

М.Н. Алексеев
ПРАКТИКУМ ПО ПРОГРАММИРОВАНИЮ

НА АЛГОРИТМИЧЕСКИХ ЯЗЫКАХ
Сборник заданий

Челябинск 2014

ББК
Алексеев, М.Н. Практикум по программированию на алгоритмических языках. Сборник заданий: учеб. пособие / М.Н. Алексеев / ФГБОУВПО «ЧелГУ». – Челябинск: Челяб. гос. ун-т, 2012. - с.
ISBN

Учебное пособие содержит методические указания и задания для практических занятий по курсам «Языки программирования» и «Практикум на ЭВМ» и предназначено для начинающих изучать программирование студентов физико-математических и технических факультетов высших учебных заведений.


Печатается по решению редакционно-издательского совета

Челябинского государственного университета.
Рецензенты:

______________Без объявл. ББК

ISBN ФГБОУВПО «ЧелГУ», 2014

СОДЕРЖАНИЕ


  1. Введение

  2. Практические работы

    1. Присваивание и ввод-вывод

    2. Условные операторы

    3. Циклы

    4. Строки

    5. Одномерные массивы

    6. Двумерные массивы (матрицы)

    7. Процедуры и функции

    8. Записи

    9. Множества

    10. Файлы

  3. Контрольные работы и учебные олимпиады

  4. Зачётные работы

    1. Зачётные работы по языкам программирования

    2. Зачётные работы по информатике

    3. Комплексные (семестровые) работы

  5. Семестровые задания

  6. Литература

0. ВВЕДЕНИЕ
В учебного пособии собраны материалы для организации и проведения циклов практических занятий, а также контрольных работ и зачётных мероприятий, проводимых в рамках изучения курсов «Языки программирования» и «Практикум на ЭВМ» для студентов 1-го курса математического факультета, обучающихся на направлениях подготовки 010300.62 – Фундаментальная информатика и информационные технологии и 010400.62 – Прикладная математика и информатика.

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

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

Автор благодарен за любезно предоставленные материалы для сборника уважаемым коллегам – Ф.З. Абдуллину и А.С. Волчек из Миасского филиала ЧелГУ, а также А.К. Демидову и Т.Ю. Лымарь из Южно-Уральского госуниверситета.



  1. ПРАКТИЧЕСКИЕ РАБОТЫ


Практическая работа №1

Присваивание и ввод-вывод


  1. Задание № 1

    1. С клавиатуры задаются вещественные числа и . Вычислить:





Указания:



  • Изучите справку по стандартным функциям: Abs, Cos, Sin, Ln, Exp,Sqr, Sqrt.

  • Для возведения аргумента в произвольную степень , не равную 0.5 (т.е извлечение квадратного корня), используйте формулу:



  • например для вычисления в программе необходимо написать z=exp(1/8*ln(x))

  • Для извлечения квадратного корня всегда используйте стандартную функцию Sqrt.

  • Для возведения аргумента в целую степень можно использовать операцию многократного умножения или воспользоваться предложенной выше формулой.

  • Для выражения десятичного логарифма через натуральный использовать формулу:



  • Программа должна выдавать сообщения о необходимости ввода величин и .

  • Программа должна выводить на экран исходные данные и результаты расчетов с поясняющими надписями.

    1. Протестировать программу для значений:

  • ,

  • ,

  • ,

результаты вычислений должны совпадать с приведенными в таблице:

Входные данные

Результаты вычислений











2

3

2.05897

-0.000633

0.38873

3

4

3.02852

-0.000329

0.42352

45

45

120193.55395

0.023909

3.67627




    1. Сохраните отлаженную программу в файле в вашей рабочей папке.




  1. Задание № 2.

    1. С клавиатуры задаются значения двух чисел – длины катетов прямоугольного треугольника. Вычислить периметр и площадь треугольника.

    2. Протестировать программу для значений:

  • 3 и 4,

  • 5 и 8

Результаты работы должны совпадать с приведенными в таблице:

Длины катетов

Периметр

Площадь

3

4

12.00000

6.000

5

8

22.43398

20.000




    1. Сохраните отлаженную программу в файле в вашей рабочей папке.




  1. Задание № 3

    1. С клавиатуры задается четырехзначное число. Вычислить произведение его цифр.

Указания:

  • Изучите справку по стандартным функциям и целочисленного деления и получения остатка от деления.

  • Для отрицательных чисел произведение тоже должно быть положительным.

    1. Протестировать программу для значений:

  • 4321

  • -5611

Результаты работы программы должны совпадать с приведенными в таблице:

Число

Произведение цифр

4321

24

-5611

30

Сохраните отлаженную программу в файле в вашей рабочей папке.
Практическая работа №2

Условные операторы
Задания для разбора:


  1. Записать указанное действие в виде одного условного оператора:




  1. Вычислить:




  1. Даны действительные числа x, y (x<>y). Меньшее из них заменить их полусуммой, а большее – их удвоенным произведением.




  1. Даны действительные числа x, y. Если x и y отрицательны, то их значения заменить

модулем; если отрицательно только одно из них, то оба значения увеличить на 0,5; если оба значения неотрицательны и ни одно из них не принадлежит отрезку [0,5; 2,0], то оба значения уменьшить в 10 раз; в остальных случаях x и y оставить без изменения. Вывеси сообщение о результатах проверки.
Оператор выбора Case

Использование оператора выбора при разработке меню:

Var


a, b, c: integer;

begin


Write(‘Введите значение числа a’); readln(a);

Write(‘Введите значение числа b’); readln(b);

Write(‘Введите номер действия, которое хотите произвести с этими числами’);

Writeln(‘1 – получить сумму чисел’);

Writeln(‘2 – получить разность чисел’);

Writeln(‘3 – получить произведение чисел’);

readln(c);

case c of

1: writeln(‘a+b=’, a+b);

2: writeln(‘a-b=’, a-b);

3: writeln(‘a*b=’, a*b);



End;

End.


Задания для самостоятельного выполнения:


  1. Даны три действительных числа. Возвести в квадрат те из них, значения которых неотрицательны, и в 4-ую степень – отрицательные.




  1. Даны действительные числа x и y, не равные друг другу. Меньшее из этих двух чисел заменить половиной их суммы, а большее – их удвоенным произведением.




  1. Написать программу – модель анализа пожарного датчика в помещении, которая выводит сообщение «Пожарная ситуация», если температура в комнате превысила 60°С.




  1. Даны три числа а, b, с. Определить какое из них равно d. Если ни одно из них не равно d, то найти .



Задачи для закрепления:


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




  1. Вычислить площадь треугольника со сторонами a, b, c по формуле Герона, проверив условие корректности исходных данных (длины всех сторон положительны и сумма любых двух сторон больше третьей).




  1. Вычислить корни квадратного уравнения . Предусмотреть все возможные варианты решения уравнения:

( А) любой из коэффициентов a, b, c может быть равен 0

Б) дискриминант может быть больше, меньше или равен 0)




  1. Даны числа a1, b1, c1, a2, b2, c2. Напечатать координаты точки пересечения прямых, описываемых уравнениями и , либо сообщить, что эти прямые совпадают, не пересекаются, либо вовсе отсутствуют.


Практическая работа №3

Операторы цикла

  1. Оператор цикла for

Получить сумму чисел от 1 до N.

Var


n, i, summa: integer;

begin


write(‘введите значение N’);

readln(n);

summa:=0;

for i:=1 to n do

summa:=summa+i;

writeln(‘Сумма чисел в диапазоне от 1 до’, n, ‘равна’, summa);

end.



  1. Оператор цикла Repeat

Вычислить сумму четных чисел в диапазоне от 1 до 10 включительно.

Var


I, sum: integer;

Begin


I:=0;

Sum:=0;


Repeat

Sum:=sum+I;

I:=i+2

Until (i>10);

Writeln(‘Сумма четных чисел равна’,sum);

End.


  1. Оператор цикла While

Вычислить сумму нечетных чисел в диапазоне от 1 до 10 включительно.

Var


I, sum: integer;

Begin


I:=0;

Sum:=0;


While (i<11) do

begin

Sum:=sum+I;

I:=i+2;

End;

Writeln(‘Сумма нечетных чисел равна’,sum);

End.

Задачи для самостоятельного выполнения:


  1. Вычислить n! с помощью всех трех операторов цикла (for, repeat, while).

  2. Получить таблицу температур по Цельсию от 0 до 20 градусов и их эквивалента по шкале Фаренгейта, используя для перевода формулу: tf=3/5*tc+32.

  3. Вычислить значения функции y=4*x3-2*x2+5 для значений X, изменяющихся от -3 до 1 с шагом 0,1.

  4. Дано натуральное число N, определяющее возраст человека в годах, n≤100. Дать для этого числа наименование «год», «года» или «лет» в зависимости от введенного значения.


Задачи для закрепления:

  1. Рассчитать траекторию движения снаряда по формулам

При постоянных скоростях . Время t изменяется от 0 с шагом . Цикл закончить при y<=0.



  1. Найти наибольший общий делитель НОД двух натуральных чисел А и В. (Для решения задачи воспользоваться алгоритмом Евклида: уменьшить каждый раз большее из чисел на величину меньшего до тех пор, пока оба значения не станут равными).

  2. Определить сколько раз последовательность из N целых чисел меняет знак. (Произведение двух чисел с разными знаками – отрицательное число).

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

Даны натуральное число n, действительные положительные числа . Считая, что числа - это оценки, выставленные судьями одному из участников соревнований, определить, какая оценка пойдет в зачет этому спортсмену.

  1. Вычислить сумму квадратов целых чисел, попадающих в интервал (), x>1.

Практическая работа №4

Работа со строками
Задания для разбора:

  1. Удалить в начале строки все пробелы, если они имеются.

Program LeftDel;

Var


Str, str1: string[20];

Dlina: byte;

Begin

Read(str);



Dlina:=length(str);

While((dlina>0) and (str[1])=’ ‘) do

Delete(str,1,1);

Writeln(str);

End.


  1. Дана строка символов. Группа символов между пробелами считается словом. Подсчитать количество слов в строке.

Program pr3;

Uses crt;

Var

St: string[30];



I, k:byte;

Begin


Readln(st);

For i:=1 to length(st) do

If st[i]=’ ‘ then

k:=k+1;


Writeln(k+1);

End.



  1. Дано слово. Определить, является ли оно палиндромом.

Program pr3;

Uses crt;

Var

St: string[30];



I, k, n:byte;

Fl: Boolean;

Begin

Clrscr;


Readln(St);

Fl:=true;

N:=length(st);

For i:=1 to (n div 2) do

If st[i]<>st[n-i+1] then

Fl:=false;

If fl then

Writeln(‘Palindrom’)

Else

Writeln(‘Ne palindrom’)



End.
Задачи для самостоятельного выполнения:


  1. Удалить все пробелы в строке.

  2. Подсчитать количество слов, начинающихся на ‘B’.

  3. Преобразовать данную строку, заменяя всякое вхождение слова «eto» на слово «tot».

  4. Написать программу, определяющую частоту появления символов A, B, C и цифры 9 в тексте, состоящем из любого числа строк. Вычисление частоты повторяемости символа оформить в виде процедуры.

  5. Дана строка символов, среди которых есть одна открывающаяся и одна закрывающаяся скобка. Вывести на экран все символы, расположенные внутри этих скобок.

  6. Дана строка, заканчивающаяся точкой. Подсчитать, сколько слов в строке.


Практическая работа №5

Одномерные массивы
Задачи для разбора:


  1. Даны натуральное число n, действительные числа a, b (b>a>0). Получить последовательность действительных чисел y0, y1,…,yn: 

Var

a, b, I, h:integer;

x,y: array [1..50] of real;

begin


writeln(‘Введите значения а и в:’);

readln(a,b);

n:=50;

h:=(b-a)/n;



for i:=1 to n do

begin


x[i]:=a+ih;

y[i]:=sqrt(x[i]);

writeln(y[i]);

end;


end.


  1. Найти максимальное значение массива, состоящего из 100 элементов и значение индекса этого элемента.

Var

a: array [1..100] of integer;

max, I, i_max: integer;

begin


randomize;

for i:=1 to 100 do

a[i]:=random(300);

max:=a[1];

for i:=2 to 100 do

if max

begin

max:=a[i];



i_max:=I;

end;


writeln(‘максимальное значение массива =’, max);

end.



  1. Даны целые числа a1, a2,…,a50. Получить последовательность b1, b2,…,b50, отличающуюся от исходной тем, что все нечетные числа удвоены.

Var

a, b:array[1..50] of integer;

i:byte;

begin


randomize;

for i:=1 to 50 do

begin

a[i]:=random(100);



if odd(a[i]) then

b[i]:=a[i]*2

else b[i]:=a[i];

writeln(‘a[’,i,’]=’,a[i],’ b[‘,i,’]=’,b[i]);

end;

end.
Задачи для самостоятельного выполнения:


1. Заполнив массив из 100 элементов случайными целыми числами от -100 до 100, найти в этом массиве максимум и минимум, а также номера всех максимальных и минимальных элементов.

2. В массиве из задачи №1 найти номер(а) и значение элемента(ов), наиболее близкого(их) к среднему арифметическому значений всех элементов массива.

3. Используя массивы, составить программу вычисления первых шестидесяти чисел Фиббоначи. Числа Фиббоначи вычисляются по рекуррентной формуле:

Первые два числа Фиббоначи равны 1.

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


1

1

2

3

5

8

13

21

34

55

89

144

233

377

610

987

1597

2584

4. Заполнить массив N≤100 случайными числами от 0 до N и выделить в другой массив все числа, которые встречаются более одного раза.

Пример:

Исходные данные:



7

Результат:

4 1 2 1 6 2 5

1 2


Практическая работа №6

Двумерные массивы (матрицы)
Задачи для разбора:

  1. Обнулить все элементы квадратной матрицы, находящиеся выше главной диагонали и на главной диагонали.

Program m_2;

Uses crt;

Var


i, j, sum: integer;

a : array [1..5,1..5] of integer;

begin

randomize;



clrscr;

sum:=0;


for i:=1 to 5 do

for j:=1 to 5 do

begin

a[i,j]:=random[50];



if (j>=i) then

a[i,j]:=0;

end;

for i:=1 to 5 do



begin

for j:=1 to 5 do

Write(a[i,j]);

Writeln;


End;

end.



  1. Составить программу для вычисления суммы положительных элементов каждой строки матрицы А(6*8).

Program m_3;

Uses crt;

Var

i, j, sum: integer;



a : array [1..6,1..8] of integer;

SumP: array [1…6] of integer;

begin

randomize;



clrscr;

for i:=1 to 6 do

for j:=1 to 8 do

a[i,j]:=random(50)-30;

for i:=1 to 6 do

begin


sum:=0;

for j:=1 to 8 do

if a[i,j]>0 then

sum:=sum+a[i,j];

SumP[i]:=sum;

End;


For i:=1 to 6 do

Write(sump[i],’ ‘);

End.
Задачи для самостоятельного выполнения:


  1. Получить матрицу




  1. Составить программу, находящую максимальный элемент в квадратной матрице.




  1. Дана квадратная матрица А[N*N]. Записать на место отрицательных элементов нули, а на место положительных 1. Вывести на печать нижнюю треугольную матрицу в общепринятом виде. (i>=j)




  1. Для заданной квадратной матрицы сформировать одномерный массив из ее диагональных элементов. Суммировать элементы одномерного массива. Преобразовать исходную матрицу по следующему правилу: четные строки разделить на полученное значение, нечетные оставить без изменения.




  1. Дана матрица А(10*10). Вычислить наибольшие элементы каждой строки матрицы и переписать их в одномерный массив В.




  1. Дано натуральное число n, действительная матрица размеров n*9. Найти среднее арифметическое каждого из столбцов, имеющих четные номера.




  1. Дана матрица А(10*10). Переписать в одномерный массив Р – все положительные элементы, а в массив N – все отрицательные элементы. Подсчитать количество нулевых элементов.



Практическая работа №7

Процедуры и функции
Задачи для разбора:

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

Program DemoFunction;

Var z: integer;

k, s: real;



Function step(f: real; exp: integer): real;

Var c: integer;

t: real;

begin


if exp=0 then

step:=1


else

begin


t:=f;

for c:=2 to abs(exp) do

t:=t*f;

if exp<0 then



step:=1/t

else


step:=t;

end;


end;

Begin {основной блок программы}

Writeln(‘Введите число’);

Readln(z);

S:=step(z, 3); {Возводит число z в степень 3 }

Writeln(S);

S:=step(z, 4); {Возводит число z в степень 4 }

Writeln(S);

k:=1.4; {вводим вещественное число}

S:=step(k, 3);

Writeln(S);

end.



  1. Посчитать тангенс любого угла.

Program tangens;

Uses crt;

Var

x, y, t: real; {определяем функцию – тангенс, которая возвращает значение тангенса}



Function tan(c:real): real;

begin


tan:=sin(c)/cos(c);

end;


Begin

Clrscr;


Writeln(‘Введите значение X и Y’);

Readln(x, y);

t:=tan(x);

Writeln(‘tg(x)=’,t);

t:=tan(y);

Writeln(‘tg(y)=’,t);

End.
Задачи для самостоятельного выполнения:


  1. Даны действительные числа x1, y1, x2, y2,…,x10, y10. Найти периметр десятиугольника, вершины которого имеют соответственно координаты (x1,y1), (x2,y2), …, (x10,y10).

  2. Заданы длины трех сторон треугольника ABC. Рассчитать углы треугольника с использованием теоремы косинусов и оформить в виде функции. .

  3. Написать программу для нахождения суммы большего и меньшего из трех чисел.

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

  5. По заданным 20-элементным целым массивам x и y вычислить


Практическая работа №8

Множества
Задачи для разбора:

  1. Сформировать и вывести на экран множество из n символов латинского алфавита (n<20). Если вводимая буква уже есть в множестве, выдать соответствующее сообщение.

Const N=20;

Var


s: set of char;

b: Char;


i: integer;

Begin


S:=[];

For i:=1 to N do

begin

writeln (‘Введите букву’);



readln (b);

if b in s then

writeln (‘Буква ’,b,’ уже есть’)

else


s:=s+[b];

end;


writeln (‘Буквы, входящие во множество’);

for b:=’A’ to ‘Z’ do

if b in S then

write(b:2);



End.


  1. Дано натуральное число n. Напечатать в возрастающем порядке все цифры, которых нет в записи данного числа.

var

m: set of 0..9;

n,o,i: integer;

begin

write('введите число:');

readln(n);

m:=[0,1,2,3,4,5,6,7,8,9];

while n>0 do

begin

o:=n mod 10;

n:=n div 10;

if (o in m) then

m:=m-[o]

end;

writeln('цифры, которых нет в числе');

for i:=0 to 9 do

if i in m then

write(i,',');

readln;

end.
Задачи для самостоятельного выполнения:


  1. Дан текст на русском языке. Найти количество согласных букв в последнем слове.




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




  1. Дан текст на русском языке. Напечатать в алфавитном порядке все звонкие согласные буквы, которые входят хотя бы в одно слово.




  1. Дан текст на русском языке. Найти количество гласных букв



Практическая работа №9

Записи
Задания для самостоятельного выполнения:


  1. Из ведомости о четырех студентах с их оценками (порядковый номер, ФИО, пять оценок) определить количество отличников и средний балл каждого студента.




  1. О каждом студенте известна информация:

  • ФИО

  • Год рождения

  • Группа

  • Отметка по математике

  • Отметка по истории

  • Отметка по английскому языку

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


  1. Даны такие сведения о 20 владельцах авто: фамилия водителя, марка машины, и ее номер (целое число), пробег (целое число). Найти фамилию владельца, машина которого имеет максимальный пробег, и количество машин, номер которых заканчивается цифрой 9.




  1. Даны такие сведения о 10 персонах: фамилия, пол и дата рождения (дата типа запись). Определить возраст каждого, и вывести на экран фамилии тех, кто достиг пенсионного возраста (мужчины старше 60, женщины - 55).


Практическая работа №10

Файлы
Задания для разбора:


  1. Записать n целых чисел в файл. Просмотреть содержимое файла в Блокноте или в программе просмотра файл-менеджера FAR (F3, Hex). Повторить процедуру для действительных чисел. Сравнить результаты.

Var

F: file of integer; {F: file of real;}

a:integer; {a: real;}

I, n: integer;

Begin

Assign(f, ‘num.dat’);



Rewrite(f);

Read(n);


For i:=1 to n do

Begin


Write(‘a=’);

Read(a);


Write(f,a);

End;


Close(f);

End.


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

Var

F: text;


A, b, c: array[1..5,1..5] of real;

I, j, k: integer;

Begin

Assign(f, ‘abcd.txt’);



Rewrite(f);

Writeln(‘Введите матрицу А:’);

For i:=1 to 5 do

For j:=1 to 5 do

Read(a[I,j]);

Writeln(‘Введите матрицу В:’);

For i:=1 to 5 do

For j:=1 to 5 do

Read(b[I,j]);

Writeln(‘Матрица С=А+В:’);

Writeln(f, ‘Матрица С=А+В:’);

For i:=1 to 5 do

Begin

For j:=1 to 5 do



Begin

C[I,j]:=a[I,j]+b[I,j];

Write(f, c[I,j]:8:3,’ ‘);

End;


Writeln;

Writeln(f);

End;

Close(f);



End.
Задания для самостоятельного выполнения:


  1. Задан файл вещественных чисел abc.dat. Удалить из него максимальный и минимальный элемент. (Считать компоненты из файла в массив, в котором находим максимальный и минимальный элементы и их номера. Открываем файл для записи и вносим в него все элементы, за исключением макс. и мин. элемента).




  1. Записать в файл последовательного доступа N действительных чисел. Вычислить произведение компонентов файла и вывести на печать.




  1. Заполнить файл последовательного доступа F целыми числами, полученными с помощью генератора случайных чисел. Записать в файле G нечётные компоненты файла F, а в файл Н - чётные.




  1. Дан файл, содержащий текст. Провести частотный анализ текста, т.е. указать (в процентах) сколько раз встречается та или иная буква.


2. КОНТРОЛЬНЫЕ РАБОТЫ И УЧЕБНЫЕ ОЛИМПИАДЫ

Контрольная работа №1


Цель: Подготовка к контрольным работам с проверяющей системой.

Тема: Циклы и условные операторы.

Задание: Зарегистрироваться на сайте http://ipc.susu.ac.ru.

В разделе «Учебные задачи/ 6. Цикл+условный оператор» решить задачи с номерами: 46, 21, 24.



Замечание: Сдать задачу проверяющей системе на сайте, для зачёта показать результат сдачи преподавателю.

Контрольная работа №2


Тема: Циклы и условные операторы.

Задание 1: Зарегистрироваться на сайте http://ipc.susu.ac.ru.

В разделе «Учебные задачи/ 6. Цикл+условный оператор» решить задачи с номерами: 0+N, 25+N, где N – номер студента в регистрационной учётной записи, например, для учетной записи mt101_12 номер N=12.



Задание 2: В разделе «Учебные задачи/ 8. Вложенные циклы» решить задачу с номером: 0+N, где N – номер студента в учетной записи.

Замечание: Сдать задачу проверяющей системе на сайте, для зачёта показать результат сдачи преподавателю. Оценка за контрольную = 2+Z , где Z – количество сданных задач.

Контрольная работа №3


Тема: Обработка последовательностей символов.

Задание: Зарегистрироваться на сайте http://ipc.susu.ac.ru.

В разделе «Учебные задачи/ 7. Обработка последовательностей символов» решить задачи с номерами: 0+N, 11+N, 22+N, 33+N, 44+N, где N –номер студента в списке преподавателя.


Замечание: Сдать задачу проверяющей системе на сайте, для зачёта показать результат сдачи преподавателю.

УЧЕБНЫЕ ОЛИМПИАДЫ


Задание: Зарегистрироваться на сайте http://ipc.susu.ac.ru.

В разделе «Рабочее место участника» в строке «Соревнование, созданное Alexeev» нажать «Выбрать».

Для просмотра текстов задач перейти в раздел «Задачи»,

для сдачи программы проверяющей системе – «Послать решение»,

для просмотра результатов – «Результаты проверки» и «Результаты соревнования»

Примечание. Наборы олимпиадных задач выбираются из архива «Задачи» (в меню «Начало»).



№ олимпиады

№№ задач в архиве

1

1720, 1763

2

1708, 1505, 1519, 1499, 1437

3




4




5




6




7




8




3. ЗАЧЁТНЫЕ ЗАДАНИЯ
3.1. Зачётные задания по языкам программирования
3.1.1. По введенным координатам вершин треугольника вычислить величины его углов, периметр и площадь.

Указание: вывод результатов организовать таблицей следующего вида




Вершина

Координаты

на плоскости



Величина угла

(в градусах)



A

(0,0)

90

B

(0,1)

45

C

(1,0)

45




Периметр треугольника

3,414

Площадь треугольника

0,5

3.1.2. По введенным целым коэффициентам квадратного уравнения вычислить его корни.

Указание: рассмотреть 3 случая - существование двух различных корней, один корень, отсутствие действительных корней. Вывод результатов – в свободной форме.
3.1.3. а) Для введенного целого числа в диапазоне от 0 до 100 вывести заключение о возрасте вводившего с использованием правильной словоформы слова «год».

Пример1: Введите Ваш возраст:


17
Вам 17 лет

Пример2: Введите Ваш возраст:


21
Вам 21 год

Указание: ни в коем случае не перечислять все 100 возможных значений, унифицировать значения с помощью вычисления остатка.

б) Модифицировать выполненное задание до варианта с многократным повторением ввода и обработки данных.

Пример работы программы:


«Введите возраст:»
«17»
«Вам 17 лет»
«Продолжить работу? (Y/N)»
«Y»
«Введите возраст:»
«21»
«Вам 21 год»
«Продолжить работу? (Y/N)»
«N»
«Работа программы закончена.»

в) По введенному целому числу в диапазоне от 0 до 1000 вычислить и вывести его правильную запись в виде текста.

Пример1: Введите число:
17
семнадцать

Пример2: Введите число:


123
сто двадцать три
3.1.4. а) Без использования формулы суммы (то есть почленным суммированием) вычислить сумму К=100 элементов геометрической прогрессии ,
где . Определить минимально необходимое количество элементов К, при превышении которого результат перестаёт меняться - при использовании переменных типа real и double

б) сумму последовательности с элементами , вычислить с точностью до заданного с клавиатуры вещественного числа.

Пример1 работы программы:
«Введите точность вычисления суммы:»
«1»
«Сумма равна 1»

Пример2 работы программы:


«Введите точность вычисления суммы:»
«0.01»
«Сумма равна 3.948»

Указание: Для определения достижения точности использовать величину очередного элемента: если он меньше заданного числа, считать точность достигнутой.




      1. а) Реализовать преобразование целых чисел из системы с основанием 10 в системы с основаниями 2, 8, 16 и обратно.

б) Реализовать преобразование целых чисел из системы с основанием M в систему с основанием N, где 13.1.6. а) В массиве из 100 случайных целых чисел найти минимальный и максимальный элементы и количество вхождений этих элементов в массив.

Указание: Реализовать предварительную сортировку в парах соседних элементов так, чтобы каждый нечётный элемент не превышал по величине правого соседа, и поиск максимумов и минимумов вести по чётным и нечётным элементам соответственно.

б) Реализовать простые операции с матрицами: транспонирование, умножение на число, сложение и перемножение двух матриц. Значения матриц задавать случайным образом, выбор операции предоставлять пользователю.
3.1.7. Разработать программу, которая по заданным с клавиатуры координатам и радиусам двух окружностей определяет, как окружности расположены на плоскости относительно друг друга - совпадают, вложены, пересекаются или не пересекаются, и вычисляет расстояние между ближайшими точками окружностей. Окружность задавать как запись с тремя полями: координаты центра окружности (вещественного типа), радиус окружности (целого типа). В случае пересекающихся окружностей вычислить координаты точек пересечения.
3.1.8. а) В файле input.txt содержится некоторое количество строк «Hello!». Написать программу, подсчитывающую количество строк в input.txt, и выводящую результат в файл output.txt.

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

3.1.9. Написать программный модуль, включающий все ранее реализованные алгоритмы сортировок. Создать тестовую программу, использующую данный модуль.
3.1.10. Перевести результат выполнения задания №9 по информатике в объектно-ориентированный стиль.

Указание: Создать объекты с необходимыми полями, ранее реализованные операции сделать методами, добавить необходимые конструкторы и деструкторы.


3.1.11. Перевести результат выполнения задания №10 по информатике в объектно-ориентированный стиль.

Указание: Компоненты объекта «Структура данных» нужно разумно поделить на закрытые и открытые.


3.2. Зачётные задания по информатике

3.2.1. Системы счисления

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

Основание исходной системы

Основание целевой системы

Значение 1

Значение 2

Значение 3

10

2

12

123

12345

2

10

101b

1111011b

1010101010101b

10

8

12

123

12345

8

10

7o

12o

123o

10

16

12

123

12345

16

10

2h

21h

1000h

2

8

111b

101010b

1010010101101b

8

2

5o

12o

125o

2

16

1111b

10101010b

110011001101b

16

2

12h

123h

12345h

3.2.2. Программы для машины Тьюринга.

Задание 1: На ленте записано целое десятичное число. В начальном состоянии МТ обозревает левую цифру числа. Построить МТ, которая умножает заданное число на 10.

Задание 2: На ленте записано последовательность символов «+». Построить МТ, которая заменяет эту последовательность на последовательность цифр и заканчивает работу в исходной позиции считывающей головки, например:

++++++++++++++++ заменяет на 1234567890123456.

Задание 3: На ленте записано целое десятичное число. В начальном состоянии МТ обозревает левую цифру числа. Построить МТ, которая вычитает единицу из заданного числа, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было "100", то выходным должно быть "99", а не "099".

Задание 4*: На ленте записано целое десятичное число. В начальном состоянии МТ обозревает правую цифру числа. Построить МТ, которая умножает заданное число на выбранное однозначное число (2,3,4,5,6,7,8,9) – младшую цифру Вашего номера в списке группы.

Задание 5*: На ленте записаны два целых двоичных числа, разделенные одним пустым символом. В начальном состоянии МТ обозревает левую цифру первого из чисел. Построить МТ, которая складывает заданные числа. В результате работы на ленте должно остаться одно число – результат сложения.

Задание 6*: Дана последовательность символов "*". Требуется записать их количество числом десятеричной системы счисления.

* - задания 4-6 - небязательны для выполнения, за эти сданные задания начисляется 0,5 балла к экзаменационной оценке по предмету «Информатика».


3.2.3. Нормальные алгорифмы Маркова.

Задание 1: Что делает следующий алгорифм над алфавитом из четырех знаков {1,2,Н,Ч} с исходными данными, состоящими из одних единиц?



  1. 11  2

  2. 22  2

  3. 21  1

  4. 1  Н

  5. 2  Ч

Задание 2: Дана последовательность из пробелов. Написать нормальный алгорифм Маркова для удаления всех пробелов кроме одного.

Задание 3*: Написать алгорифм сложения двух двоичных чисел.

* - задание - необязательно для выполнения, за сданную работу начисляется 0,5 балла к экзаменационной оценке по предмету «Информатика».
3.2.4. Итерационные алгоритмы

Задание: Реализовать указанный преподавателем вариант алгоритма сортировки случайного набора данных.

Варианты:


  1. «пузырьковая» сортировка;

  2. сортировка простым выбором;

  3. сортировка простыми вставками.

3.2.5. Рекурсивные алгоритмы.

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

Варианты:



  1. вычисление числа Фибоначчи;

  2. нахождение НОД (наибольшего общего делителя) двух чисел;

  3. вычисление суммы цифр числа.

3.2.6. Рекурсивные алгоритмы сортировки.

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

Варианты:



  1. сортировка слиянием;

  2. быстрая сортировка;

  3. пирамидальная сортировка.

3.2.7. Внешние алгоритмы сортировки.

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

Варианты:



  1. прямое слияние;

  2. естественное слияние.

3.2.8. Динамические структуры данных. Списки.

Задание: Реализовать указанный преподавателем вариант списка и основные операции над ним - добавление, удаление, поиск и сортировка элементов, определить сложность основных операций.

Варианты:



  1. односвязный список;

  2. двусвязный список;

  3. кольцевой список.

3.2.9. Дисциплины обработки данных.

Задание: Реализовать указанный преподавателем вариант дисциплины и основные операции над структурой данных (добавление, удаление, просмотр элементов) для двух вариантов физической организации – статической и динамической. Конкретику физической организации определить самостоятельно.

Варианты:


  1. Стек.

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

б) Показать использование стека для преобразования скобочной формулы в обратную польскую запись.

в) Показать использование стека для вычисления значения формулы на основе обратной польской записи.


  1. Очередь. Смоделировать случайное поведение очереди, её рост и рассасывание.

  2. Дек. Смоделировать случайное поведение объектов в деке подобно очереди.

3.2.10. Динамические структуры данных. Деревья.

Задание: В файле «input.txt» содержится набор исходных данных – построчно записанные целые числа. Написать программу, реализующую построение бинарного дерева поиска и основные операции над ним – добавление и поиск элемента, слияние деревьев.

Задание*: Реализовать операцию удаления элемента из дерева поиска.


3.2.11. Динамические структуры данных. Графы.

Задание: В файле «input.txt» содержится набор исходных данных – построчно записанная информация о графе. Написать программу, реализующую построение внутреннего программного представления графа.






внешнее представление

внутреннее представление

Вариант 1

список ребер

матрица смежности

Вариант 2

список смежности

иерархический список

Задание*: Реализовать операцию поиска пути между двумя вершинами графа.

Задание**: Реализовать операцию поиска кратчайшего пути между двумя вершинами графа.

Указание: Вид графа (ориентированный или не ориентированный, взвешенный или нет) выбрать самостоятельно.


  1. СЕМЕСТРОВЫЕ ЗАДАНИЯ

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

Примерные темы семестровых заданий.



  1. Длинная арифметика.

Составить библиотеку (модуль) программ реализующих ввод-вывод и основные арифметические операции для длинных целых чисел с использованием символьных строк и/или целочисленных массивов.

  1. Анализ текста.

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

  1. Сжатие данных.

Составить программы для сжатия и разжатия текстов методами RLE, Хафмена, Лемпеля-Зива, арифметического метода и другими – по выбору.

  1. Сложные олимпиадные задачи.

Решить несколько задач студенческих олимпиад по программированию, предложенных преподавателем.

  1. Тема, предложенная студентом и согласованная с преподавателем.

ЛИТЕРАТУРА

  1. Павловская Т.А. Паскаль. Программирование на языке высокого уровня: Учебник для вузов. -СПб.: Питер, 2003.

  2. Пратт Т., Зелковиц М. Языки программирования. Разработка и реализация. -СПб.: Питер, 2002.

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

  4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. –М.: МЦНМО: БИНОМ. Лаборатория знаний, 2004.

  5. Шень А. Программирование: Теоремы и задачи. –М.: МЦНМО. 2004.

  6. Кнут Д.Э. Искусство программирования, т. 1. Основные алгоритмы, 3-е изд.  М.: Вильямс, 2000.

  7. Кнут Д.Э. Искусство программирования, т. 3. Сортировка и поиск, 2-е изд.  М.: Вильямс, 2000.

Ресурсы интернет:



  1. http://pascalabc.net/ - Система программирования PascalABC.NET

  2. http://ipc.susu.ac.ru/ - Сайт «Informatics, Programming, Contest»

  3. http://acmp.ru/ - Сайт «Школа прграммиста»

  4. http://www.intuit.ru/ - Интернет-университет информационных технологий.

  5. http://algolist.ru/ - Алгоритмы, методы, исходники


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©grazit.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал