Динамические переменные и указатели

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

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

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

type <имя ссылочного типа> = ^<имя типа динамической величины> (значок ^ указывает на то, что величина является динамической). Например:

type p = ^ integer;

q = ^record

х: integer;

у: string [20] end;

В некоторых случаях возникает необходимость в качестве значения указателя принять «пустую» ссылку nil, которая не связывает с указателем никакого объекта и принадлежит любому ссылочному типу.

Для порождения динамического объекта, на который указывает ссылочная переменная i, служит стандартная процедура new(i). Имя ссылочной переменной с последующим символом ^ называют «переменной с указателем». Именно она синтаксически выполняет роль динамической переменной и может быть использована в любых конструкциях языка, где допустимо использование переменных того типа, что и тип динамической переменной.

Процедура dispose (i) уничтожает порожденные динамические объекты.

Примеры на программирование простых алгоритмов

Пример 1. Вывести на экран большее из двух данных чисел

Program Example_1;

Var x,y: Integer;

Begin

Writeln('введите 2 числа’);

Readln(x,у); {вводим два целых числа через пробел}

If x>y Then Writeln (х); {если (If)x больше у, то (Then) выводим х}

Else Writeln(у); {иначе (Else) выводим у}

Readln;

End.

Пример 2 Даны целые числа а, b, с. Если а<=b<=с, то все числа заменить их квадратами, если а>b>c, то каждое число заменить наибольшим из них, в противном случае сменить знак каждого числа.

Решение.

Условие задачи перепишем следующим образом:

а = а², b = b², с = с², если а <= b <= с,

а = с, b = с, если а > b > с,

а = -a, b = - b, с = -с, в остальных случаях.

Program Example_2;

Var a,b,c: Integer;

Begin

Writeln('Введите числа a,b,c');

Readln(a,b,c);

If (a<=b) And (b<=c) Then

Begin a:=sqr(a); b:=sqr(b); c:=sqr(c) End

Else If (a>b) And (b>c) Then

Begin a:=c; b:=c

End

Else Begin a:=-a; b:=-b; c:=-c End;

Writeln(a:3,b:3,c:3);

Readln; End.

Пример 3 Составить программу вычисления значения выражения у=((...(20²- 19²)²- 18²)²-... - 1²)².

Решение. В данном случае целесообразно организовать цикл с параметром, изменяющимся от 20 до 1, то есть шаг изменения параметра равен -1.

Обозначим: у - очередное значение квадрата числа; п - параметр цикла. Учитывая это, составим программу:

Program Example_4;

Var у, n: Integer;

Begin

y:=sqr(20);

For n:=19 Downto 1 Do у:=sqr(y-sqr(n)); Writeln('Значение выражения равно'); Writeln(у);

End.

П ример 4. Из чисел от 10 до 99 вывести те, сумма цифр которых равна n (0 <n< 18) Решение. Обозначим: k - это просматриваемое число, p- это первая цифр числа k, p2- это вторая цифра числа k, s -это сумма цифр данного числа k. Число kбудем выписывать только в том случае, когда сумма p1 и p2 будет равна.s.

Program Example_4;

Var k,n,pi,p2,s: Integer;

Begin

Writeln('введите целое число1);

Readln(n); {вводим целое число}

For k:=10 To 99 Do {для(For) k от 10 до(То) 99 делать(Do)}

Begin

pl:=k Div 10; {выделяем первую цифру}

p2:=k Mod 10; {выделяем вторую цифру}

s:=pl+p2; {находим сумму цифр}

If s=n Then Writeln(k); {если сумма равна п, то выводим К

End;

Readln;

End.

Пример 5. Дано число п. Каким образом можно построить «перевертыш» данного числа?

Решение. Обозначим: n - вводимое число, m — дубликат числа n, a - перевертыш числа n, i — переменная цикла для создания перевертыша.

Program Example_5;

Var n,m,a,i: Integer;

Begin

Writeln('введите целое число, не большее 9999');

Readln (n); {вводим целое число}

m:=n; a:=0;

{создание перевертыша}

For i:=l To 4 Do {так как число четырехзначное}

Begin

a:=a*10+m Mod 10; m:=m Div 10; End;

If a=n Then Writeln('ДА!') Else Writeln('НЕТ!!!'); {если перевертыш равен данному числу, то выводим «ДА», иначе — «НЕТ»}

Readln;

End.

Пример 6. Даны натуральные числа п, к (п, к<9999). Из чисел от п до к выбр те, запись которых содержит ровно три одинаковые цифры. Например, числа 0006, 0060, 6766, 5444, содержат ровно три одинаковые цифры.

Решение. Если данное число содержит ровно три одинаковых цифры, то только одна из цифр отличается от остальных, т. е. возможны четыре случая.

В первом случае отличается последняя цифра, во втором - третья, в третьем - вторая, а в четвертом - первая. Для каждого числа выполняется только одно условий.

Фрагмент решения

Begin {Example_6};

Writeln('Введите два числа, не больших 9999'); Readln(n, к); For i:=n To k Do Begin

m::=i; {выделение цифр: al — первая, а2 — вторая,аЗ — третья, а4 четвертая}

a4:=m Mod 10; m:=m Div 10;

аЗ:=m Mod 10; m:=m Div 10;

а.2:=m Mod 10; al:=m Div 10;

{проверка условий}

If ((al=a2) And (al=a3) And (al<>4)) Or

{первое условие}

((al=a2) And (al=a4) And (al<>a3)) Or {второе условие}

((al=a3) And (al=a4) And (al<>a2)) Or {третье условие}

((a2=a3) And (a2=a4) And (a2<>al)) {четвертое условие}

Then Writeln (i:5);

End;

Readln;

End.

Циклы с условиями

Пример 7. Цикл с предусловием. Дано натуральное число п. Подсчитайте количество цифр данного числа.

Решение. Подсчет количества цифр начнем с последней цифры числа. Увеличим счетчик цифр на единицу. Число уменьшим в 10 раз (тем самым мы избавляемся от последней цифры числа). Далее с получившимся числом проделаем ту же последовательность действий и т.д., пока число не станет равным нулю.

Program Example_8;

Var m, n: Longint;

k: Integer; {счетчик цифр}

Begin

Writeln('Введите целое число'); {вводим целое число n}

Readln(n);m:=n;

k:=0;

While m<>0 Do {пока число m<>0 делать (Do) }

Begin

Inc(k); {или k:=k+l;}

m:=m Div 10; {«уменьшаем» число на последнюю цифру}

End;

Writeln ('В числе', п, ' - ', к, ' цифр!'); {вывод количества цифр} Readln;

End.

Пример 8. Дана непустая последовательность натуральных чисел, за которой следует 0. Составить программу поиска в данной непустой последовательности порядкового номера наименьшего элемента.

Решение. Обозначим через х, i — очередной член последовательности и его номер; min, k - минимальный член последовательности и егономер. Считывание членов последовательности производится до тех пор, пока не будет введен 0, то есть пока х<>0. Начальное значение минимума определяется значением первого члена последовательности. Очередное вводимое число требуется сравнивать с текущим значением минимума, и если текущее значение min окажется больше очередного члена последовательности, то его надо изменить.

Program Example_9;

Var x, i, min, k: Integer;

Begin

Writeln('Введите первый член последовательности');

Read(x); k:=l;

min:=x; i:=2;

While x<>0 Do

Begin

If x<min Then Begin min:=x; k:=i End; Writeln('Введите ',i,' элемент последовательности¹); Read(x); Inc (i); End;

Writeln('Номер минимального элемента - ', k); End.

Пример 9. Цикл с постусловием. Составить программу планирования закупки товара в магазине на сумму, не превышающую заданной величины.

Решение. Обозначим через х, к соответственно цену и количество товара, через р - заданную предельную сумму, через s - общую стоимость покупки. Начальное значение общей стоимости покупки (s) равно нулю. Значение предельной суммы считывается с клавиатуры. Необходимо повторять запрос цены и количества выбранного товара, вычислять его стоимость, суммировать ее с общей стоимостью и выводить результат на экран до тех пор, пока она не превысит предельную сумму р. В этом случае на экран надо вывести сообщение о превышении.

Program Example_10;

Var x, k, p, s:Integer;

Begin

Writeln('Предельная сумма - '); Readln(p);

s:=0;

Repeat

Writeln('Введите цену товара и его количество'); Readln(x,к); s:=s+x*k;

Writeln('Стоимость покупки равна ',s); Until s>p;

Writeln ('Суммарная стоимость покупки превысила предельную сумму¹); End.

При описании циклов с постусловием необходимо принимать во внимание следующее:

• перед первым выполнением цикла условие его окончания (или продолжения)
должно быть определено;

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

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

Пример 10. Написать программу нахождения наибольшего общего делителя (НОД) двух неотрицательных чисел.

Решение. Для решения данной задачи воспользуемся алгоритмом Евклида. Пусть х и у одновременно не равные нулю целые неотрицательные числа и пусть х>у, тогда если у=0, то НОД(x,y) = x, а если y<>0, то для чисел х, у и г, где r - остаток от деления х на у выполняется равенство НОД(х,у) = HOД(y,r).

Program Example_l0;

Var x, у: Integer;

Begin

Writeln('Введите два числа');

Readln(x,у); {вводим два целых числа }

Repeat {выполнять}

If x>y Then x:=x Mod у Else y:=y Mod х;

Until (x=0) Or (y=0);

{до тех пор, пока одно из чисел не станет равно нулю} Writeln('НОД=', х+у); {вывод НОД — без условного оператора, так как одно из чисел обязательно равно нулю}

Readln;

End.

Пример 11. Даны натуральные числа х и у, не равные нулю одновременно. Найти d = НОД(х,у) и такие целые q и w, что d = qx + wy.

Решение. Добавим в алгоритм Евклида переменные р, q, r, s, m и п, такие, что т = pa + qb, п = r а + sb, где первоначально т = а = х, п = b = у.

Значения переменных р, q, r, s изменяются следующим образом:

• как только значение переменной т уменьшается на к∙п, значение р уменьшается на к∙r, a q уменьшается на k∙s;

• аналогично, как только значение п уменьшается на к∙т, значения переменных r и s уменьшаются соответственно на k∙p и на k∙q.

Учитывая все, что сказано выше, составим программу:

Program Example_11;

Var x,y: Integer; {исходные данные}

p,q,r,s,m,n: Integer; {введенные вспомогательные переменные}

к: Integer; {для изменения значений p,q,r,s}

d: Integer; {значение наибольшего общего делителя}

Begin

Read(x,у);

m:=x; n:=y; p:=l; q:=0; r:=0; s:=l;

Repeat

If m>n Then

Begin

k:=m Div n; m:=m Mod n;

p:=p-k*r; q:=q-k*s

End

Else

Begin k:=n Div m; n:=n Mod m; r:=r-k*p; s:=s-k*q

End;

Until (m=0) Or (n=0);

If m=0 Then Begin d:=n; q:=r; w:=s;

Else Begin d:=m; q:=p; w:=q;

End;

Writeln(d,'=',q,'*',x,’+’,w,’*’,y);

End.

 

X	Y		Результаты
48 mod 18= 12		x>y	НОД(48,18) =НОД(12,18)
	18 mod 12 = 6	x<y	НОД(12,18) = НОД(12,6)
12 mod 6 = 0		x>y	НОД(12,6) = НОД(0,6)
		x=0	НОД(0,6) =6

Пример 12. Вложенные циклы. Даны натуральные числа п и k. Составить программу вычисления выражения 1^к + 2^к +... + п^к.

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

Program Example_12;

Var n,k,y,i,s,m:Integer;

Begin

Writeln('Введите исходные данные n и к');

Readln(n,k);

s:=0;

For i:=1 To n Do

Begin

y:=i;

For m:=l To к Do y:=y*i; {нахождение степени к числа i}

s:=s+y; End;

Writeln('Ответ:’;s); End.

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

Пример 13. Модифицировать предыдущую программу так, чтобы она вычисляла сумму 1¹+ 2² +... + п".

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

Program Example_13;

Var n,y,i,s,m: Integer;

Begin

Writeln('Введите начальное значение п');

Readln(n);

s:=0;

For i:=l To n Do

Begin y:=l;

For m:=l To i Do y:=y*i;{нахождение степени к числа i} s:=s+y; End;

Writeln('Ответ: ',s);

End.

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

Пример 14. Старинная задача. Сколько можно купить быков, коров и телят, если плата за быка 10 руб., за корову — 5 руб., за теленка - полтинник (0,5руб.), если на 100 руб. надо купить 100 голов скота.

Решение. Обозначим b - число быков; к - число коров; t - число телят. После этого можно записать два уравнения: 10b + 5k + 0,5t= 100 и b + k + t = 100. Преобразуем их: 20b +10k + t = 200 и b + к + t = 100.

На 100 рублей можно купить:

• не более 10 быков, т. е. 0 < b < 10;

• не более 20 коров, т.е. 0 < k < 20;

• не более 200 телят, т.е. 0 < t < 200.

Program Example_15;

Var b, k, t: Integer;

Begin

For b:=0 To 10 Do

For k:=0 To 20 Do

For t:=0 To 200 Do

If (20*b+10*k+t=200) And (b+k+t=100) Then

Writeln('быков ', b, 'коров', k, 'телят',t);

End.

Пример 15. Сколько раз будет проверяться условие в данной программе?

Решение. Значение переменной b изменяется 11 раз (от 0 до 10), для каждого ее значения переменная k изменяется 21 раз, а для каждого значения переменной k:переменная t изменяется 201 раз. Таким образом, условие будет проверяться 11∙21∙201 раз. Но если известно число быков и коров, то число телят можно вычислить по формуле t = 100 - (b + к) и цикл по переменной t исключается.

Program Example_16;

Var b,k,t:Integer;

Begin

For b:=0 To 10 Do

For k:=0 To 20 Do

Begin

T:=100-(b+k);

If (20*b+10*k+t=200) Then

Writeln(‘быков ‘,b,’коров ’,k,’телят ’,t);

End;

End.