Преимущество целых чисел? Точность вычислений (Пример: trunc и round)

1.

Ответим на вопросы:
1. Преимущество целых чисел?
Точность вычислений (Пример: trunc и round)
2. Целые типы данных?
byte, shorting, word, integer, longint, int64
3. Длинное число - ?
Число не помещается в переменную стандартных типов
4. Способы работы с длинными числами?
Используя массив, символьные переменные
5. Эффективность алгоритма?
Найти алгоритм, у которого временная и пространственная
сложность меньше
*Как можно это сделать?

2.

Пример программы №1
Сумма первых n чисел
В чем разность программ?
var n,i,s:integer;
begin
readln(n);
for i:=1 to N do
s:=s+i;
writeln(s);
end.
var n,i,s:int64;
begin
readln(n);
for i:=1 to N do
s:=s+i;
writeln(s);
end.
var n:int64;s:real;
begin
readln(n);
s:=n*(1+n)/2;
writeln(s:0:0);
end.
Как работают программы при N=10^5, 10^9, 10^18?
Определить временную сложность для N=5?

3.

Пример программы №2
Сумма цифр n-значного числа
В чем разность программ?
program pr1;
var n,a,s:int64;
begin
writeln('Введите число');
readln(n);
while n>0 do begin
a:=n mod 10;
s:=s+a;
n:=n div 10;
end;
writeln(s);
end.
program pr1;
var s:string; i,n,m,sum,e:integer;
begin
Writeln ('Введите 10-е число (количество цифр до
255) (найдем сумму цифр)');
readln(s);
n:=length(s);
for i:=1 to n do begin
val(s[i],m,e);
sum:=sum+m;
end;
writeln(sum);
readln;
end.
Как работают программы при N=10^5, 10^9, 10^18, 10^200?
*Определить временную сложность для N=10?

4.

• В прошлом году мы изучили базовые
констукции
• В прошлом году мы изучили структурные
типы: массив и файл
В этом году мы продолжили изучать
программирование

5.

Множества
автор презентации: учитель
информатики МБОУ СОШ №9
г.Нерчинска Курилов И.А.

6.

Цели урока:
Понятие структурного типа
множество
Научиться: Научиться решать простые
задачи с использованием
множеств
Узнать :
Домашнее задание: Задание
№4 стр.71

7.

Структурные типы. Множество.
Массивы
Файлы
Множества
Структуры (записи)
Множество – это некоторый набор элементов.
В Pascal:
Множество – это структурный тип (наряду с массивами,
файлами и структурами).
*Множество в Python - "контейнер", содержащий не повторяющиеся элементы в
случайном порядке.

8.

Примеры описаний типа множество:
var n1,m1,r:set of 1..100;
var s:set of '0'..'z'
Использование множеств:
if s[i] in ['0'.. '9'] then count:= count + 1;
if s[i] in ['a'..'z', '0'..'9', '.', '-', '_'] then …
Вывод множеств:
for k:=1 to n do
if k in n7 then write(k:4);
for c:='0' to '9' do
if c in digits then writeln(c);

9.

Операции с множествами
Пусть A:= [1,2,3,4]; B:= [2,3]; C:= [2,3]
Равенство/неравенство:
if A = B then write('A = B'); { нет }
if A <> B then write('A <> B'); { да }
Включение одного в другое:
if A >= B then write('A >= B'); да
if A > B then write('A > B'); { да }
Пустое множество:
digits:= [];
Непустое множество:
digits:= [1, 3, 5, 7];
Пересечение множеств:
digits:= [1, 3, 5, 7] * [2, 3, 4]; 3
Объединение множеств:
digits:= [1, 3, 5, 7] + [2, 3, 4]; 1, 2, 3, 4, 5,7
Вычитание множеств:
digits:= [1, 3, 5, 7] - [2, 3, 4]; 1, 5, 7
Операции с множеством
fs:= [fsBold, fsItalic]; { присвоить значение}
fs:= fs + [fsUnderline]; { добавить элементы }
fs:= fs - [fsItalic]; { исключить элементы }

10.

Примеры программ №1
Примеры задач:
Задача. Определить количество знаков препинания в символьной
строке.
1 способ)
count:= 0;
for i:=1 to Length(s) do
if (s[i]='.') or (s[i]=',') or (s[i]=';') or (s[i]=':') or (s[i]='!') or (s[i]='?')
then count:= count + 1;
2 способ с помощью множества)
if s[i] in ['.', ',', ';', ':', '!', '?'] then count:= count + 1; (in –
принадлежность множеству)
В чем отличие?
Эффективность решения задачи 2-м способом.

11.

Примеры программ №2
Задача. Вывести все различные цифры, присутствующие в
символьной строке s.
var s: string; i: integer; c: char;
digits: set of '0'..'9';
begin
readln(s);
digits:=[]; { пустое множество }
for i:=1 to Length(s) do
if s[i] in ['0'..'9'] then digits:= digits + [s[i]];
for c:='0' to '9' do
if c in digits then writeln(c)
end.
В чем особенность данной программы?
Упрощения при работе с повторяющимися символами

12.

Практическая работа на компьютере
Задания по методическим указаниям работы
Часть 1:
1.Составить программу вывода на экран множества чисел, делящихся на 7 без остатка.
2. Проверить входит ли подмножества M в множество N, найти пересечение множеств и определить
числа, составляющие пересечение данных множеств (1<=M,N<=100)
Например:
N [1,2,3,4,5,6,7]
M [3,5,7,9,11]
Множество не входит
Пересечение – 3,5,7
Часть 2:
3.Подсчитать сколько маленьких латинских букв встречается в данной символьной строке.
Например:
Мама and МАША I love you! ***2017***
10
4.Подсчитать число маленьких латинских букв в данной символьной строке и вывести их на экран в
алфавитном порядке.
Например:
Мама and МАША I love you! ***2017***
A,d,e,l,n,o,u,v,y
9