Контрольная работа № Cистемы счисления. Программирование с использованием множеств и строк

Контрольная работа № 2. Cистемы счисления. Программирование с использованием множеств и строк.

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

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

где – цифры, p – основание системы счисления. Количество цифр равно p. Для записи цифр в общем случае может быть использован любой набор p символов. Обычно для используют символы 0…9, для добавляют буквы латинского алфавита A, B, C, D, E, F которые в десятичной системе представляют числами 10, 11, 12, 13, 14, 15. Например

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

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

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

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

2.2 Тип множество

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

Для работы с множествами в Паскале введен тип переменных set of:

Type <имя типа>=set of <базовый тип>;

Var A,B,C: имя типа;

здесь <базовый тип> - любой порядковый тип кроме Word, Integer, Longint, т.е. (перечисляемый, интервальный, char, byte, boolean).

Множество-константа: [i₁, i₂, …, i_k], где i_k – элементы множества.

2.2.1 Операции над множествами

Над переменными типа множеств допустимы операции присваивания сложения, вычитания, умножения. Эти операции дополняют две процедуры

Include (S, i); – добавление в множество S элемента i, базового типа;

Exclude (S, i); – исключение из множества S элемента i, базового типа.

Эти операции выполняются значительно быстрее, чем их эквивалентные s:=s+[i]; s:=s-[i];

Операции проверки условия

Результат c=d будет true если множества одинаковы;

Результат c< > d будет true если множества не одинаковы;

Результат c>=d будет true если все элементы d принадлежат с;

Результат c<=d будет true если все элементы с принадлежат d;

Результат i in c будет true если элемент i принадлежит с.

2.2.2 Примеры работы с множествами

1. Ввод n элементов множества:

......

Var A:set of char;

s:char;

n:Word;

begin

A:=[ ]; // Очистка множества

for i:=1 to n do begin

read(s);

A:=A+[s];

end;

end.

2. Распечатать содержимое множества:

......

Var B:set of 1..100;

k:byte;

begin

for k:=1 to 100 do If k in B then Write(k);

......

end.

3. Сокращение проверок в операторе If:

Оператор If (k=5) or (k=1) or (k=8) then .... можно записать более изящно:

If k in [5,1,8] then ....

2.3. Типы данных для работы со строками и основные операции

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

Var

s1 : String[N] ; // Короткая строка, N  255

s2 : ShortString; // Короткая строка, N = 255

s3 : String; // Длинная строка, N  2 ГБайт

s4 : WideString; // Широкая строка

s5 : PChar; // Нуль-терминальная строка

Короткие строки занимают фиксированное количество байт. Строка типа String[N] может содержать nt (0≤nt≤255) символов. Под переменную типа String[N] отводится N+1 байт. В s1[0] содержится текущая длина строки. Строка ShortString эквивалентна String[255].

Длинная строка типа String. При работе с этим типом данных, в отличие от String[N] память выделяется по мере необходимости (динамически) и может занимать практически всю доступную программе память. Фактически переменные этого типа являются типизированными указателями.

Широкая строка типа WideString. Введена для обеспечения совместимости с компонентами, основанными на OLE-технологии. От типа String отличается только тем, что для представления каждого символа используется не один, а два байта.

Нуль-терминальная строка типа PChar. Представляет собой цепочку символов, ограниченную символом #0. Максимальная длина строки ограничена только доступной программе памятью. Нуль-терминальные строки широко используются при обращениях к API-функциям Windows (API – Application Program Interface – интерфейс прикладных программ).

К каждому элементу строки можно обращаться с помощью индекса, аналогично обращению к элементу массива символов: s[i]:=s[j].

Основные операции над переменными строкового типа: присвоение, сцепление (s:=s1+’ fg’+s2), сравнение (>, , =, <, ≤). Большей считатется та, строка у которой больше первый (второй, трений, …) символ.

2.4. Некоторые процедуры и функции обработки строк

Процедуры:

Delete(St:String; pz,n:integer); - удаляет из строки n символов начиная с позиции pz.

Insert(St,St1;string;pz:integer); - вставляет строку St внутрь строки St1 начиная с позиции pz.

Функции:

St:=Copy(St1,pz,n); - выделяет из строки St1 подстроку St из n символов начиная с позиции pz, при этом St1 сохраняется.

N:=Length(St); - определяет текущую длину строки.

pz:=pos(St,St1); - определяет номер позиции, начиная с которой внутри строки St1 расположена строка St, если внутри St1 нет St тогда pz=0.

Описание функций преобразования чисел в строки и наоборт помещено в Приложении 1.

2.5. Пример написания программы

Задание: написать программу подсчета количества неповторяющихся символов в каждом слове произвольной строки. Слова отделяются друг от друга одним или несколькими пробелами. Ввод строки заканчивать нажатием клавиши Enter.

Панель диалога будет иметь вид (рис. 2.1).

Рис. 2.1
Текст программы приведен в Листинге 2.1.
Листинг 2.1.

unit Unit2;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls,

Forms, Dialogs, StdCtrls;

Type

TForm1 = class(TForm)

Edit1: TEdit;

Label2: TLabel;

Edit2: TEdit;

Label1: TLabel;

procedure FormCreate(Sender: TObject);

procedure Edit1KeyPress(Sender: TObject; Var Key: Char);

private { Private declarations }

public { Public declarations }

end;

Var Form1: TForm1;

implementation

{$R *.dfm}

Function Krz(St:string):Word; // Подсчет кол-ва различныx символов

Var a : set of char;

m,i : Word;

begin

m:=0; a:=[];

for i:=1 to Length(St do

If not(St[i] in a) then begin

Include(a,St[i]); Inc(m);

end;

Result:=m;

end;

Function FWrd(st : string) : string;

Var n,i,nst: integer;

sl,srez : string;

begin

Result:=''; srez:=''; n:=Length(st);

If n=0 then exit;

st:=st+' '; n:=n+1; sl:='';

for i:=1 to n do

If st[i]<>' ' then sl:=sl+st[i]

else

If sl<>'' then begin

srez:=srez+' '+sl+'-'+IntTostr(Krz(sl)); sl:='';

end;

Result:=srez;

end; // Конец функции FWrd

procedure TForm1.FormCreate(Sender: TObject);

begin

Edit1.Clear; Edit2.Clear;

end;

procedure TForm1.Edit1KeyPress(Sender: TObject; Var Key: Char);

begin

If Key = #13 then Edit2.Text:=FWrd(Edit1.Text);

end;

end.

2.6. Выполнение индивидуального задания

Для ввода строк и работы с ними использовать компонент TEdit. Ввод строки заканчивать нажатием клавиши Enter. Алгоритм оформить в виде подпрограммы.

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

2. Дана строка, представляющая собой запись числа в четырнадцачиричной системе счисления. Преобразовать ее в строку, представляющую собой запись числа в десятеричной системе счисления.

3. Дана строка, представляющая собой запись числа в десятеричной системе счисления. Преобразовать ее в строку, представляющую собой запись числа в восьмеричной системе счисления.

4. Дана строка, представляющая собой запись числа в восьмиричной системе счисления. Преобразовать ее в строку, представляющую собой запись числа в двоичной системе счисления.

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

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

7. Дана строка, состоящая из групп нулей и единиц. Каждая группа отделяется от другой одним или несколькими пробелами. Подсчитать количество символов в самой длинной группе.

8. Дана строка, состоящая из групп нулей и единиц. Каждая группа отделяется от другой одним или несколькими пробелами. Найти и вывести на экран группы с четным количеством символов.

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

10. Дана строка символов, состоящая из произвольных десятичных чисел, разделенных пробелами. Вывести четные числа этой строки.

11. Дана строка, представляющая собой запись числа в двоичной системе счисления. Преобразовать ее в строку, представляющую собой запись числа в шестнадцатиричной системе счисления

12. Дана строка символов, состоящая из произвольного текста, слова разделены пробелами. Вывести на экран порядковый номер слова, накрывающего k-ю позицию (если на k-ю позицию попадает пробел, то номер предыдущего слова), и найти в нем количество посторяющихся символов.

13. Дана строка символов, состоящая из произвольного текста, слова разделены пробелами. Разбить исходную строку на две подстроки, причем первая длиной k-символов (если на k-ю позицию попадает слово, то его следует отнести ко второй строке, дополнив первую пробелами до k-позиций).

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

15. Дана строка символов, состоящая из произвольного текста, слова разделены пробелами. Вывести на экран порядковый номер слова минимальной длины и количество непосторяющихся символов этом слове.