Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Шпоры по программированию - файл 1.doc


Шпоры по программированию
скачать (423 kb.)

Доступные файлы (1):

1.doc423kb.29.11.2011 03:22скачать

Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
1 Поменять местами значения переменных А и В используя и не используя дополнительную переменную.

Задача решается в 2 приема.

Она настолько простая, что я не знаю, что здесь описывать.
program num1;

var a1,b1,a2,b2,c:integer;

begin

write('Vvedite A i B: ');

readln(a1,b1);
a2:=a1;

b2:=b1;

c:=a2;

a2:=b2;

b2:=c;

writeln('Obmen cherez dopolnit. peremennuyu: a=',a2,' b=',b2);
a2:=a1;

b2:=b1;

a2:=a2+b2;

b2:=a2-b2;

a2:=a2-b2;

writeln('Obmen bez dopolnit. peremennoy: a=',a2,' b=',b2);

end.

  1. Возвести в натуральную степень К число А обычным способом и ускоренным (порядка С logK).

Задача также решается в 2 этапа:

Обычным способом:

В цикле производится последовательное умножение переменной K раз.

Ускоренным способом:

Это единственная задача, математическое обоснование которой я не понял (списана из тетради).

Внимание: ускоренный метод пригоден лишь для натуральных чисел!
program num2;

var a,b,c,k,i: integer;

begin

write('Vvedite A i K: ');

readln(a,k);

c:=1;

for i:=1 to k do c:=c*a;

writeln('Obichnim sposobom: A^K=',c);
b:=1;

c:=a;

while k<>0 do

if k mod 2=0 then

begin

k:=k div 2;

c:=c*c;

end

else

begin

b:=b*c;

k:=k-1;

end;

writeln('Uskorennim sposobom: A^K=',c);

end.
3 Даны натуральные А и В. Вычислить частное Р и остаток Т при делении А на В используя и не используя операции div и mod.
Задача настольно простая, что не знаю что пояснять.

1. Вводим A, B.

2. Присваиваем остатку и частному начальные значения.

3. В цикле уменьшаем остаток до тех пор, пока он не станет меньше делимого B, одновре-менно с этим увеличиваем счетчик частного.

4. Выводим частное и остаток.
program num3a;

var a,b,p,t: integer;

begin

write('Vvedite A i B: ');

readln(a,b);

t:=a;

p:=0;

while t>=b do

begin

t:=t-b;

p:=p+1;

end;

writeln('P=',p,' T=',t);

end.

4 Вычислить п-й член последовательности Фибоначчи обычным способом и ускоренным (порядка С logn).

program fibona4i;

var n,k:longint;

procedure f1_usk;

var a11,a12,a22,a21,d11,d12,d21,d22,c11,c12,c21,c22:longint;

begin

a11:=1;

a12:=1;

a21:=1;

a22:=0;

c11:=a11;

c12:=a12;

c21:=a21;

c22:=a22;

while n>2 do begin

dec(n);

d11:=a11*c11+a12*c21;

d12:=a11*c12+a12*c22;

d21:=a21*c11+a22*c21;

d22:=a21*c12+a22*c22;

c11:=d11; c12:=d12; c21:=d21; c22:=d22;

end;

writeln(d11);

end;

procedure f2;

var i,c,fpr,fsl:longint;

begin

fpr:=1;

fsl:=1;

for i:=1 to n-2 do begin

c:=fsl;

fsl:=fpr+fsl;

fpr:=c;

end;

writeln(fsl);

end;

(*Osn proga*)

begin

writeln('Usk sposob=1',' ','Ob sposob=2');

read(k);

writeln('Nomer 4isla');

read(n);

case k of

1: f1_usk;

2: f2;

end;

end.
5 Вычислить НОД(А.В) с помощью алгоритма Евклида.
1. Вводятся числа А и В.

2. В цикле выполняется алгоритм Эвклида: Если с=НОД(А,В), то с=НОД(меньшего числа и разности этих чисел).

3. Цикл повторяется до тех пор, пока НОД не будет равен одному из этих чисел.

4. Определяем какое число сравнялось с НОД.

5. Выводим его.
program NOD;

var a,b,c:integer;

begin

write('Vvedite chisla A i B: ');

readln(a,b);

while (a>0)and(b>0) do

if a>b then a:=a-b

else b:=b-a;

if a=0 then c:=b else c:=a;

writeln('NOD: ',c);

end.


6 Найти целые х И у такие, что Ах+Ву=НОД(А,В).
Важное замечание: уравнению Ax+By=НОД(A,B) удовлетворяет бесконечное количество пар це-лых чисел x,y требуется найти одну из них.

Алгоритм аналогичен алгоритму задачи №5 за исключением того, в данной задаче вычисления проводятся не только над самими числами, но и над коэффициентами в них (m-n=pa+qb-ra-sb=a(p-r)+b(q-s), аналогично для n-m=a(r-p)+b(s-q)).

После завершения цикла одно из чисел m или n = НОД.

Мы определяем, какое число = НОД, и выводим его коэффициенты.
program NOD2;

var a,b,m,n,x,y,p,q,r,s:integer;

begin

write('Vvedite chisla A i B: ');

readln(a,b);

m:=a; n:=b; p:=1; q:=0; r:=0; s:=1;

{m=p*a+q*b, n=r*a+s*b}

while (m>0)and(n>0) do

if m>=n then

begin

m:=m-n;

p:=p-r;

q:=q-s;

end

else

begin

n:=n-m;

r:=r-p;

s:=s-q;

end;

if m=0 then

begin x:=r; y:=s; end

else begin x:=p; y:=q; end;

writeln('x=',x,' y=',y);

end.


  1. . Вывести квадраты К натуральных чисел обычным способом и, используя только знаки + и -.


1. Вводим число К

2. В цикле вычисляем и выводим квадраты до К обычным способом

3. В цикле вычисляем и выводим квадраты К путем использования вычисленного на преды-дущем витке цикла квадрата К-1.
program num7;

var k,i,sq:integer;

begin

write('Vvedite K: ');

readln(k);

writeln('Obichnim sposobom:');

for i:=1 to k do write((i*i):5);

writeln;
writeln('Ispolzuya yolko +- :');

{b^2=(a+1)^2=a^2+2a+1=a^2+2b-1}

sq:=0;

for i:=1 to k do

begin

sq:=sq+i+i-1;

write(sq:5);

end;

writeln;

end.

8, Разложить на простые множители натуральное К.
1. Вводим К

2. Задаем минимальный простой множитель L

3. В цикле проверяем Делится ли K на L без остатка. Если да, то выводим L и вычисляем следующее значение K, если нет, увеличиваем L на 1.

4. Цикл продолжается до тех пор пока L и K не сравняются.
program num8;

var k,l: integer;

begin

write('Vvedite K: ');

readln(k);

l:=2;

while k<>1 do

if k mod l=0 then

begin

k:=k div l;

write(l:4);

end

else l:=l+1;

writeln;

end.
9. Написать данное натуральное К цифрами в обратном порядке.
9

1. Вводим K

2. В цикле вычисляем и выводим последнюю цифру числа K (остаток от деления на 10) и от-брасываем ее от числа K (целочисленное деление на 10).

3. Вывод производится без перехода на следующую строку, следовательно цифры записыва-ются подряд.
program num9;

var k: longint;

begin

write('Vvedite K: ');

readln(k);

while k<>0 do

begin

write(k mod 10);

k:=k div 10;

end;

writeln;

end.

  1. Вычислить количество целых решений неравенства х2у2<п.


Внимание! В условии принципиальная ошибка x2+y2<n – неравенство, а не уравнение. Задача ре-шалась для неравенства, если требуется уравнение, то знак “<” меняется на «=».

1. Вводится N.

2. Вычисляем максимальные значения для X и Y: p.

3. В двойном вложенном цикле производим перебор всех допустимых X и Y.

4. Если текущие значения X,Y удовлетворяют неравенству, то увеличиваем счетчик K.

5. Выводим K
program num10;

var x,y,n,k,p:integer;

begin

write('Vvedite N: ');

readln(n);

p:=trunc(sqrt(n));

k:=0;

for x:=-p to p do

for y:=-p to p do

if x*x+y*y<n then

begin

writeln('x=',x,' y=',y);

k:=k+1;

end;

writeln('Kolichestvo=',k);

end.



  1. Написать К десятичных знаков числа 1/п, используя лишь натуральные числа.


1. Вводим N,K

2. Устанавливаем первоначальное значение остатка.

3. В цикле вычисляем и выводим результат целочисленного деления остатка на n (искомая цифра результата) и вычисляем следующий остаток, который умножаем на 10 (можно ум-ножать непосредственно при выводе, но мне почему-то захотелось здесь).

4. Вывод производится без перехода на следующую строчку подряд.
program num11;

var ost,i,k,n: integer;

begin

write('Vvedite N i K: ');

readln(n,k);

ost:=10;

write('1/n = 0.');

for i:=1 to k do

begin

write(ost div n);

ost:=(ost mod n)*10;

end;

writeln;

end.


  1. Посчитать количество нулей в массиве х[1..п].


1. Вводим размер массива N

2. В цикле вводим данные в массив

3. В цикле проверяем каждую ячейку на ноль, если да то увеличиваем счетчик K.

4. Выводим K
program num12;

var x: array[1..100] of real;

i,k,n: integer;

begin

write('Vvedite N: ');

readln(n);

writeln('Vvedite elementi massiva:');

for i:=1 to n do read(x[i]);

writeln;
k:=0;

for i:=1 to n do

if x[i]=0 then k:=k+1;

writeln('Kolichestvo nuley: ',k);

end.

  1. Найти наибольшее значение в массиве х[1..п].


1. Вводим размер массива

2. В цикле вводим данные в массив

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

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

5. Выводим значение максимального элемента (MAX) и его номер в массива (IMAX).
program num13;

var x: array[1..100] of real;

max: real;

i,n,imax: integer;

begin

write('Vvedite N: ');

readln(n);

writeln('Vvedite elementi massiva:');

for i:=1 to n do read(x[i]);

writeln;
max:=x[1];

imax:=1;

for i:=1 to n do

if x[i]>max then

begin

max:=x[i];

imax:=i;

end;

writeln('Max Element #',imax,': max=',max:0:2);

end.

  1. Посчитать количество различных элементов в упорядоченном по неубыванию массиве х[1..п].


1. Вводим размер массива N

2. В цикле вводим данные в массив

3. Устанавливаем первоначальные значения счетчиков I, K

4. Во внешнем цикле инкрементируем значения счетчиков.

5. Во внутреннем цикле осуществляем пропуск всех кроме одного идущих подряд одинако-вых элементов в упорядоченном массиве.

6. Выводим K
program num14;

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

i,n,k:integer;

begin

write('Vvedite N: ');

readln(n);

writeln('Vvedite elementi massiva:');

for i:=1 to n do read(x[i]);

writeln;
k:=0;

i:=1;

while i<=n do

begin

while (x[i]=x[i+1])and(i<n) do i:=i+1;

i:=i+1;

k:=k+1;

end;

writeln('Kolichestvo razlichnih elementov: ',k);

end.

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

1. Вводим размер массива N

2. В цикле вводим данные в массив

3. Выполняем цикл перестановки симметричных ячеек массива, двигаясь от концов к середи-не.

4. Выводим новый массив
program num15;

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

i,n,t:integer;

begin

write('Vvedite N: ');

readln(n);

writeln('Vvedite elementi massiva:');

for i:=1 to n do read(x[i]);

writeln;
for i:=1 to (n div 2) do

begin

t:=x[i];

x[i]:=x[n-i+1];

x[n-i+1]:=t;

end;

for i:=1 to n do write(x[i],' ');

writeln;

end.


  1. Вычислить выражение а[п]*хп+...+а[1]*х+а[0]. Схема Горнера.

1. Вводим степень многочлена N

2. Вводим коэффициенты многочлена (начиная с младших степеней)

3. Вводим X

4. Присваиваем начальное значение Y, согласно схеме Горнера.

5. В цикле вычисляем Y по схеме Горнера.

6. Выводим Y
program num16;

var a: array[0..100] of real;

i,n: integer;

x,y: real;

begin

write('Vvedite N: ');

readln(n);

writeln('Vvedite elementi massiva:');

for i:=0 to n do read(a[i]);

writeln;

writeln('Vvedite X: ');

readln(x);
y:=a[n];

for i:=0 to n-1 do y:=y*x+a[n-i-1];
writeln('Y=',y:0:3);

end.


16

Схема Горнера - прием для нахождения неполного частного и остатка при делении многочлена Pn(x) на двучлен (x-c).
Всякий многочлен единственным способом представим в виде

Pn(x)=(x-c)Qn-1(x)+R, где Qn-1(x)=b0 •xn-1+...+bn-2•x+bn-1 - неполное частное, а R - остаток.
Коэффициенты многочлена Qn-1 и R вычисляются по рекуррентным формулам

b0=a0, b1=a1+c•b0, ..., bn-1=an-1+c•bn-2, R=an+c •bn-1.
А теперь все то же самое, но для нашего случая:

Pn(x)=a[n]*xn + … + a[1]*x + a[0] = ((…(((a[n]*x + a[n-1])*x + a[n-2])*x +a[n-3])…)*x + a[1])*x +a[0]

Т.е. мы берем предыдущий вычисленный коэффициент Y, умножаем на X и + следующий коэф-фициент, после этого все повторяем в цикле.


  1. Вычислить произведение двух многочленов с коэффициентами а[0..п] и b[0..kj.

1. Ввод степеней многочленов N, K

2. Ввод коэффициентов многочленов A, B (начиная с младших степеней)

3. В двойном вложенном цикле произведение всех коэффициентов многочленов A, B. Сте-пень результирующего многочлена C = N+K. Во время выполнения перемножения сумма i+j несколько раз становится одной и той же. Это соответствует подобным слагаемым. Мы учитываем это, прибавляя предыдущее значение данного коэффициента.

4. Выводим коэффициенты итогового многочлена.
program num17;

var a,b,c: array[0..100] of real;

i,j,n,k:integer;

begin

write('Vvedite N: ');

readln(n);

writeln('Vvedite koeffitsienti mnogochlena A:');

for i:=0 to n do read(a[i]);

writeln;

write('Vvedite K: ');

readln(k);

writeln('Vvedite koeffitsienti mnogochlena B:');

for i:=0 to k do read(b[i]);

writeln;
for i:=0 to n do

for j:=0 to k do

c[i+j]:=c[i+j]+a[i]*b[j];
writeln('Itogoviy mnogochlen:');

for i:=0 to k+n do

write(c[i]:0:3,' ');

writeln;

end.

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

1. Вводим размеры массивов: K, N

2. Вводим данные в массивы A, B

3. В двойном вложенном цикле сравниваем элементы массива B с элементами массива A.

4. Если найден одинаковый элемент, то инкрементируем значение счетчика kol, значению начала для поиска внутреннего массива задаем следующее за текущим, и вызываем преры-вание работы внутреннего цикла.

5. Выводим kol.

Замечание: Возможно, программа написана не совсем оптимальным и эстетически красивым способом, но полностью рабочим.
program num18;

var x,y: array[1..100] of integer;

i,j,n,k,t,kol:integer;

begin

write('Vvedite K: ');

readln(k);

writeln('Vvedite elementi massiva X:');

for i:=1 to k do read(x[i]);

writeln;

write('Vvedite N: ');

readln(n);

writeln('Vvedite elementi massiva Y:');

for i:=1 to n do read(y[i]);

writeln;
kol:=0;

t:=1;

for i:=1 to k do

begin

for j:=t to n do

if x[i]=y[j] then

begin

kol:=kol+1;

t:=j+1;

break;

end;

end;

writeln('Kolichestvo obschih chlenov: ',kol);
end.


  1. Даны два возрастающих массива х[1..к] и у[1..п]. Вывести массив z[l..m] их общих элементов ускоренным способом.

Решение идентично решению задачи №18. Только при инкременте счетчика общих членов теку-щий элемент заносится в массив общих членов Z. И в конце он выводится.
program num19;

var x,y,z: array[1..100] of integer;

i,j,n,k,m,t,kol:integer;

begin

write('Vvedite K: ');

readln(k);

writeln('Vvedite elementi massiva X:');

for i:=1 to k do read(x[i]);

writeln;

write('Vvedite N: ');

readln(n);

writeln('Vvedite elementi massiva Y:');

for i:=1 to n do read(y[i]);

writeln;
kol:=0;

t:=1;

for i:=1 to k do

begin

for j:=t to n do

if x[i]=y[j] then

begin

kol:=kol+1;

z[kol]:=x[i];

t:=j+1;

break;

end;

end;
writeln('Obsche chleni:');

for i:=1 to kol do write(z[i],' ');

writeln;

end.

  1. В массиве х[1 ..к] встречаются все числа от 0 до к ровно по одному разу, кроме одного. Найдите это число.


program num20;

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

i,k,q:integer;

a: set of byte;

begin

write('Vvedite K: ');

readln(k);

writeln('Vvedite elementi massiva:');

for i:=1 to k do read(x[i]);

writeln;
for i:=1 to k do a:=a+[x[i]];

for i:=0 to k do

if not (i in a) then q:=i;
writeln('Chislo: ',q);

end.
20

Данную задачу удобно решать с помощью теории множеств.

1. Вводим размер массива K

2. Заполняем массив X данными

3. В цикле добавляем все элементы массива в множество A.

4. Выполняем в цикле проверку на принадлежность множеству. Если не принадлежит, то те-кущее число и есть искомое.

5. Выводим искомое число Q

  1. Напечатать все перестановки массива х[1..к].

1. Открываем файл для записи (количество перестановок K!)

2. Вводим размер массива

3. Заполняем массив X данными в цикле

4. Заполняем первоначальными данными массив индексов IND и множества индексов S (мас-сив индексов содержит в себе номера ячеек массива с данными, множество индексов все множество индексов (набор чисел от 1 до K))

5. Производим в цикле перебор всех возможных комбинаций индексов (представляем себе, что массив IND является K-разрядным числом в K-ричной системе исчисления и просто инкрементируем его рекурсивной процедурой Next) и проверку каждой комбинации на: является ли она перестановкой.

6. Закрываем файл.
program num21;

var s,s2: set of byte;

x: array[1..255] of integer;

ind: array[1..255] of byte;

ok: boolean;

i,k: integer;

fout: text;
procedure next(i:integer);

begin

if i<=k then

if ind[i]<k then ind[i]:=ind[i]+1

else

begin

ind[i]:=1;

next(i+1);

end

else ok:=true;

end;
procedure pr;

begin

s2:=[];

for i:=1 to k do s2:=s2+[ind[i]];

if s=s2 then

begin

for i:=1 to k do write(fout,x[ind[i]]:5);

writeln(fout);

end;

end;
begin

assign(fout,'21out.txt');

rewrite(fout);

write('Vvedite K: ');

readln(k);

writeln('Vvedite elementi massiva:');

for i:=1 to k do read(x[i]);
for i:=1 to k do

begin

ind[i]:=1;

s:=s+[i];

end;
ok:=false;

while not ok do

begin

next(1);

pr;

end;

close(fout);

end.

Процедура увеличения индексов в массиве индексов NEXT(i):

1. Если еще не все разряды массива обработаны, то:

2. Если текущий разряд меньше максимального K, т.е. его можно увеличить, то увеличиваем его

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

1. Формируем из всех разрядов массива индексов множество его индексов.

2. Сравниваем его с исходным множеством индексов.

3. Если они идентичны, то в цикле выводим массив исходных элементов, в порядке, задавае-мом массивом индексов.

Вывод в файл:

-3 -2 -1

-2 -3 -1

-3 -1 -2

-1 -3 -2

-2 -1 -3

-1 -2 -3


  1. Напечатать все возрастающие последовательности длины К из чисел от 1 до М.

Т.к. требуются именно возрастающие последовательности, то очевидно, что K > M.

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

2. Ввод с клавиатуры K, N.

3. Далее в цикле прибавляем к последовательности единицу и проверяем ее на возрастание.

4. Закрываем файл.
program num22;

var mas: array[1..256] of integer;

i,k,m:integer;

ok:boolean;

fo:text;
procedure next(i: integer);

begin

if i<=k then

if mas[i]<m then mas[i]:=mas[i]+1

else

begin

mas[i]:=1;

next(i+1);

end

else ok:=true;

end;
procedure up;

var i: integer;

ok2: boolean;

begin

ok2:=true;

for i:=1 to k-1 do

if mas[i]>=mas[i+1] then ok2:=false;

if ok2 then

begin

for i:=1 to k do write(fo,mas[i]:4);

writeln(fo);

end;

end;
begin

assign(fo,'22out.txt');

rewrite(fo);

write('Vvedite K i M: ');

readln(k,m);
ok:=false;

repeat

next(1);

up;

until ok;

close(fo);
end.

Процедура прибавления к разряду NEXT(разряд):

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

2. Если значение разряда меньше максимального, то он просто увеличивается на единицу.

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

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

2. Если это верно для всех разрядов в цикле производим вывод в файл полученной последо-вательности.
Вывод в файл:

1 2

1 3

2 3

1 4

2 4

3 4

1 5

2 5

3 5

4 5

  1. Напечатать все разбиение натурального К на натуральные слагаемые.

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

2. Открываем файл для записи

3. Вводим число K

4. Производим первоначальную установку слагаемых для самого простого случая, когда все слагаемые =1, т.е. количество слагаемых N=K

5. Далее в цикле пока число слагаемых больше единицы выполняем кучу разных ненужных действий. Что за ….ню я несу?

6. Выводим в цикле все слагаемые

7. Находим какое-то там слагаемое, начиная справа, которое выглядит как второе справа или меньше его, подряд самое левое. Воо загнул! Кто нить понял?

8. Увеличиваем его.

9. Находим в цикле сумму оставшихся справа.

10. В цикле создаем новый хвост из единичек, на 1 меньше чем был.

11. Хочу спать!

12. Вычисляем новое количество слагаемых

13. Опаньки! Цикл закончился!

14. Выводим последнее слагаемое – само число

15. Все! Спокойной всем ночи…
program num23;

var i,j,k,n,l,sum: integer;

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

fo: text;
Begin

assign(fo,'23out.txt');

rewrite(fo);

write('Vvedite K: ');

readln(k);

for j:=1 to k do x[j]:=1;

n:=k;

while n<>1 do

begin

for l:=1 to n do

write(fo,x[l],' ');

writeln(fo);
i:=n-1;

while (i<>1)and(x[i-1]<=x[i]) do

i:=i-1;

x[i]:=x[i]+1;

sum:=0;

for j:=i+1 to n do

sum:=sum+x[j];

for j:=1 to sum-1 do

x[i+j]:=1;

n:=i+sum-1;

end;

writeln(fo,k);

close(fo);

End.

Вывод в файл:

1 1 1 1 1

2 1 1 1

2 2 1

3 1 1

3 2

4 1

5



  1. Перечислить все последовательности длины К из чисел 1..М, каждая следующая последовательность отличается от предыдущей только одной цифрой. Коды Грея.

1. Открываем файл для записи

2. Вводим K, M

3. В циклах заполняем массивы X и D первоначальными данными

4. Далее в цикле выполняем опять много действий, пока все элементы последовательности не обработаем (подробнее смотри блок-схему).
program num24;

var i,j,k,m: integer;

x,d: array[1..100] of integer;

ok: boolean;

fo: text;
Begin

assign(fo,'24out.txt');

rewrite(fo);

write('Vvedite K i M: ');

readln(k,m);
for i:=1 to k do x[i]:=1;

for i:=1 to k do d[i]:=1;

ok:=true;

while ok do

begin

for j:=1 to k do write(fo,x[j],' ');

writeln(fo);
i:=k;

while (i>1)and(((d[i]=1)and(x[i]=m))

or((d[i]=-1)and(x[i]=1)))

do i:=i-1;

if ((d[i]=1)and(x[i]=m))or((d[i]=-1)and(x[i]=1))

then ok:=false

else

begin

ok:=true;

x[i]:=x[i]+d[i];

for j:=i+1 to k do

d[j]:=-d[j];

end;

end;

close(fo);

End.
Вывод в файл:

1

2

3

4

  1. Вычислить Сkn


1. Вводим значения K, N

2. Находим C как отношения произведений чисел от k+1 до n, и от 1 до (n-k). Для этого ис-пользуем соответствующую функцию (см. блок-схему)

3. Выводим С.

Замечание: для этой задачи я пользовался типом данных с плавающей запятой. В связи с этим связаны ограничения на величины N, K, а также возможно округление (замечено не было).
program num25;

var n,k,i:integer;

p,c:real;
function f(a,b: integer):real;

begin

p:=1;

for i:=a to b do

p:=p*i;

f:=p;

end;
begin

write('Vvedite K i N: ');

readln(k,n);

c:=f(k+1,n)/f(1,n-k);

writeln(c:0:0);

end.

  1. Описать алгоритм расстановки ферзей на шахматной доске, так чтобы они не были

под боем.
program num26;

var i,j,k: integer;

ok: boolean;

f: array[1..8,1..2] of integer;
procedure fer(n,x,y:integer);

var i,j: integer;

function bok(x,y:integer):boolean;

var i:integer;

begin

bok:=true;

for i:=1 to n-1 do

if (f[i,1]=x)or(f[i,2]=y)

or(abs(f[i,1]-x)=abs(f[i,2]-y))

then bok:=false;

end;

begin

if not ok then

for i:=y to 8 do

begin

if i<>y then x:=1;

for j:=x to 8 do

begin

if (bok(j,i))and(not ok) then

begin

if n=8 then

begin

ok:=true;

f[n,1]:=j;

f[n,2]:=i;

end

else

begin

f[n,1]:=j;

f[n,2]:=i;

fer(n+1,j,i);

end;

end;

end;

end;

end;



  1. Привести алгоритм сортировки элементов массива х[1..к] по возрастанию.


program num27;

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

i,k,t: integer;

ok: boolean;

begin

write('Vvedite K: ');

readln(k);

writeln('Vvedite elementi massiva:');

for i:=1 to k do read(x[i]);

writeln;
ok:=false;

while not ok do

begin

ok:=true;

for i:=1 to k-1 do

if x[i]>x[i+1] then

begin

t:=x[i];

x[i]:=x[i+1];

x[i+1]:=t;

ok:=false;

end;

end;
for i:=1 to k do write(x[i],' ');

writeln;

end.

27

В данной задаче я реализовал «Пузырьковый» метод сортировки массива. Этот метод на мой взгляд наиболее прост для понимания. Сложность алгоритма составляет O(N2) – что достаточно много. Однако этот алгоритм показывает исключительное быстродействие в случае почти отсор-тированных массивов (например, при добавлении новых элементов к отсортированному массиву).

1. Вводим размер массива

2. В цикле вводим данные в массив

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

4. Выводим массив.

  1. Алгоритм проверки правильности расстановки скобок в строке s.


program num28a;

var st: array[1..256] of char;

i,posst: integer;

c: char;

s: string;

ok: boolean;

procedure push(c:char);

begin

st[posst]:=c;

posst:=posst+1;

end;
function pop:boolean;

begin

if posst>1 then

begin

posst:=posst-1;

c:=st[posst];

pop:=true;

end

else pop:=false;

end;
function StEmpty:boolean;

begin

if posst=1 then StEmpty:=true else StEmpty:=false;

end;
begin

write('Vvedite stroku: ');

readln(s);

posst:=1;

ok:=true;

for i:=1 to length(s) do

begin

if (s[i]='(')or(s[i]='[') then push(s[i]);

if (s[i]=')')and((not pop)or(c<>'(')) then ok:=false;

if (s[i]=']')and((not pop)or(c<>'[')) then ok:=false;

end;

if ok and StEmpty then writeln('Verno!')

else writeln('Neverno!');

end.
28а

Не понравилась мне эта задача

1. Вводим строку

2. Исследуем в цикле каждый символ строки

3. Если находим любую открывающую скобку, сохраняем ее в стек

4. Если находим закрывающую скобку, то пытаемся извлечь символ из стека. Если это удает-ся и это оказывается соответствующей открывающей скобкой, то все нормально, если нет, то произошла ошибка расстановки скобок.

5. Выводим результат: если стек пуст и ошибок не было, то Верно.

29

1. Вводим ограничивающее число N

2. Формируем список простых чисел в интервале 2..N. Для этого, каждое число из интервала проверяем на делимость на любое число до него. Кроме того, согласно условию в список не вносим простые числа 2, 3, 5.

3. Проверяем каждое число на делимость без остатка (раскладываемость) любые простые числа из сформированного списка. Если текущее число не делится на числа из списка, зна-чит, оно может делиться только на 2, 3, 5.

4. Выводим найденные числа.
program num29;

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

i,j,k,n: integer;

ok: boolean;
procedure pr;

begin

k:=0;

for i:=2 to n do

begin

ok:=true;

for j:=2 to i-1 do

if (i mod j)=0 then ok:=false;

if ok and (i<>2)and(i<>3)and(i<>5) then

begin

k:=k+1;

p[k]:=i;

end;

end;

end;
function del(l:integer):boolean;

var i: integer;

begin

del:=false;

for i:=1 to k do

if (l mod p[i]=0) then del:=true;

end;
begin

write('Vvedite chislo: ');

readln(n);

pr;

for i:=2 to n do

if not del(i) then write(i,' ');

writeln;

end.


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



Определение 1. Область D принадлежащая пространству E2, будет называться выпуклой, если для любой пары точек q1 и q2 из D отрезок q1q2 целиком принадлежит D.

Определение 2. Выпуклой оболочкой множества точек S, принадлежащих пространству E2, называется граница наименьшей выпуклой области в E2, которая охватывает S.



Исходное множество S из N точек разбивается на два подмножества, каждое из которых будет содержать одну из двух ломаных, которые при соединении образуют выпуклую оболочку. Разбиение производится рекурсивно.


  1. Открываем для чтения файл.

  2. Считываем количество точек

  3. Считываем в цикле координаты всех точек

  4. Определяем базовые точки imin, imax. Под базовыми я понимаю самую левую и самую правую точку. Они точно являются вершинами выпуклой оболочки.

  5. Также здесь же определяем минимальные координаты X, Y для точек.

  6. Найденные минимальные координаты используем для сдвига координат точек. Это необходимо, т.к. алгоритм является рабочим, только если начало координат не лежит не на одной прямой образованной точками (невозможно определить знак отклонения точки от прямой)




  1. Базовые точки помечаем как вершины, тем самым исключая их из области поиска.

  2. Запускаем процедуру поиска вершин выпуклой оболочки NEXT по обе стороны от прямой образованной базовыми точками.




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

  2. Выделение начинается с первого ребра. Происходит в цикле соседнего ребра по общей вершине. Далее поиск соседнего для соседнего ребра. И т.д. пока все ребра не будут обработаны и соответственно все вершины найдены.

  3. Добавляем также повторно первую вершину для замыкания оболочки.

  4. Выводим отсортированный по направлению построения массив с вершинами оболочки CONV.


Процедура выделения вершин выпуклой оболочки по нужную сторону от прямой NEXT(t1,t2,zn)

  1. Определяем наиболее удаленную точку от прямой с заданной стороны.

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

  3. Если точка t3 определена, то очевидно, что она является вершиной.

  4. Помечаем ее как вершину.

  5. Очевидно, что точки лежащие внутри треугольника образованного точками на которых построена прямая и наидальней точкой, не являются вершинами выпуклой оболочки. Соответствующе помечаем их (mas[i].c = -1).

  6. Запускаем рекурсивно данную процедуру для выделения вершин с внешней стороны треугольника относительно новых прямых образованных наидальней точкой t3 и точками на которых была построена предыдущая прямая t1, t2.


Функция определения точки наиболее удаленной от прямой DAL(t1,t2,zn)

  1. Изначальное максимальное расстояние принимаем = -1

  2. В цикле определяем отклонение для всех не помеченных точек. Если направление отклонение противоположно (так проще) заданному, и расстояние больше максимального, то максимальное обновляется, одновременно запоминается текущая вершина.

  3. Если найденное максимальное значение = -1, то делаем вывод, что точек с заданной стороны не найдено, если нет, то возвращаем номер наиболее удаленной точки.


Функция определения принадлежности точки треугольнику TR(t1,t2,t3,tn)

См. блок-схему
Функция определения отклонения точки от прямой OTKL(t1,t2,tn)

Отклонение по модулю = расстоянию от прямой до точки. Отклонение отрицательно если точка и начало координат лежат по разные стороны от прямой, положительно – если по одну.

Математику см. на блок-схеме. Подробнее в разделе курса математики «аналитическая геометрия»

program num30;

type t=record

x,y,c: integer;

end;

var mas,mas1: array[1..100] of t;

cnv: array[1..100,1..2] of integer;

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

kol,kolc,i,j,k,tmp,imax,imin,xmin,xmax,ymin:integer;

fi: text;
function otkl(t1,t2,tn:integer):real;

var a,b,c,zn:integer;

ot:real;

begin

a:=mas[t2].y-mas[t1].y;

b:=mas[t1].x-mas[t2].x;

c:=mas[t1].y*mas[t2].x-mas[t1].x*mas[t2].y;

zn:=-(c div abs(c));

ot:=(mas[tn].x*zn*a+mas[tn].y*zn*b-c)/sqrt(a*a+b*b);

otkl:=ot;

end;
function tr(t1,t2,t3,tn:integer):boolean;

{tochka na granitse ne prenadlezhit treugolniku}

begin

if (otkl(t1,t2,t3)*otkl(t1,t2,tn)>0)and

(otkl(t1,t3,t2)*otkl(t1,t3,tn)>0)and

(otkl(t3,t2,t1)*otkl(t3,t2,tn)>0)

then tr:=true else tr:=false;

end;
function dal(t1,t2:integer;zn:real):integer;

{zn - otkl dlya tochki s drugoy storoni pryamoi}

{tochka na pryamoi mozhet bit' naidena}

var i,imax:integer;

max: real;

begin

max:=-1;

for i:=1 to kol do

if (mas[i].c=0)and(otkl(t1,t2,i)*zn<=0)and(abs(otkl(t1,t2,i))>max)

then begin

max:=abs(otkl(t1,t2,i));

imax:=i;

end;

if max>=0 then dal:=imax else dal:=0;

end;
procedure next(t1,t2:integer;zn:real);

var i,t3:integer;

begin

t3:=dal(t1,t2,zn);

if t3<>0 then

begin

mas[t3].c:=1;

for i:=1 to kol do

if tr(t1,t2,t3,i) then mas[i].c:=-1;

next(t1,t3,otkl(t1,t3,t2));

next(t3,t2,otkl(t3,t2,t1));

end

else

begin

kolc:=kolc+1;

cnv[kolc,1]:=t1;

cnv[kolc,2]:=t2;

end;

end;


begin

assign(fi,'30in.txt');

reset(fi);

readln(fi,kol);

for i:=1 to kol do readln(fi,mas1[i].x,mas1[i].y);

close(fi);
kolc:=0;
xmin:=mas1[1].x;

xmax:=mas1[1].x;

ymin:=mas1[1].y;

imin:=1;

imax:=1;

for i:=1 to kol do

begin

if mas1[i].x<xmin then

begin

xmin:=mas1[i].x;

imin:=i;

end;

if mas1[i].x>xmax then

begin

xmax:=mas1[i].x;

imax:=i;

end;

if mas1[i].y<ymin then ymin:=mas1[i].y;

end;

mas:=mas1;

if xmin<=0 then

for i:=1 to kol do mas[i].x:=mas[i].x+abs(xmin)+1;

if ymin<=0 then

for i:=1 to kol do mas[i].y:=mas[i].y+abs(ymin)+1000;

mas[imin].c:=1;

mas[imax].c:=1;

next(imin,imax,-1);

next(imin,imax,1);

conv[1]:=cnv[1,1];

k:=1;

i:=1;

while i<kolc do

for j:=1 to kolc do

if ((cnv[k,2]=cnv[j,1])or(cnv[k,2]=cnv[j,2]))and(k<>j)

then

begin

if (cnv[k,2]=cnv[j,2]) then

begin

tmp:=cnv[j,2];

cnv[j,2]:=cnv[j,1];

cnv[j,1]:=tmp;

end;

i:=i+1;

conv[i]:=cnv[k,2];

k:=j;

end;

conv[kolc+1]:=conv[1];

for i:=1 to kolc+1 do write(conv[i],' ');

writeln;

end.


  1. Вычисление выражения К! с помощью рекурсии.


31

1. Вводим К

2. Выводим результат рекурсивного вычисления К!
Функция вычисления факториала FACT(K)

1. Если К=0 или К=1, то К!=1

2. Иначе рекурсивно K!=K*(K-1)! Происходит рекурсивный вызов функции с меньшим К до тех пор пока К не будет равно 1 или 0.
program num31;

var k:integer;

function fact(k:integer):real;

begin

if (k=1)or(k=0) then fact:=1

else fact:=k*fact(k-1);

end;
begin

write('Vvedite k: ');

readln(k);

writeln('K!=',fact(k):0);
end.


  1. Алгоритм подсчета вершин в дереве. Рекурсия.


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

Представление нумерацией связей

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

Метка в конце массива FirstLink указывает на точку, расположенную сразу за последним элементом массива ToNode. Это позволяет легко определить, какие ветви выходят из каждого узла. Ветви, начинающиеся в узле i, указаны под номе­рами от FirstLink[i] до FirstLink [i + l]-l.

На рис. показано дерево и его представление нумерацией связей. Связи от узла 3 (обозначенного как D) - это ветви от FirstLink [ 3 ] до FirstLink[4] -1. Значение FirstLink [3] =9, a FirstLink [4] =11, поэтому эти ветви обозна­чены как 9 и 10. Записи массива ToNode для них составляют ToNode [ 9 ] =10 и ToNode [10] =11, следовательно, для узла 3 дочерними являются узлы 10 и И, обозначенные как К и L. Это означает, что узел D соединен с К и L.



Последовательное обращение ко всем узлам называется обходом дерева.

Обход дерева производится в прямом порядке:

  1. Обращение к узлу

  2. Рекурсивный прямой обход каждого поддерева узла



  1. Вводим в циклах массивы FirstLink (номера первых связей), Label (метки вершин), ToNode (номера вершин к которым ведут связи).

  2. Запускаем рекурсивную обработку вершин, начиная с вершины №0

  3. Инкрементируем количество вершин.

  4. Далее для каждой связи исходящей из данной вершины (определяется из FirstLink) вызывается рекурсивно процедура обработки вершины, к которой ведет каждая соответствующая связь (извлекается из ToNode).

  5. Выводим количество вершин KOL.



program num32;

var FirstLink,ToNode: array[0..100] of integer;

Lable: array[0..100] of Char;

i,k,kol: integer;

fi: text;
procedure Preorder(node:integer);

var link: integer;

begin

kol:=kol+1;

for link:=FirstLink[node] to FirstLink[node+1]-1 do

Preorder(ToNode[link]);

end;
begin

assign(fi,'32in.txt');

reset(fi);

k:=0;

while not seekeoln(fi) do

begin

read(fi,FirstLink[k]);

k:=k+1;

end;

readln(fi);

for i:=0 to k-2 do read(fi,Lable[i]);

readln(fi);

readln(fi);

k:=0;

while not seekeoln(fi) do

begin

read(fi,ToNode[k]);

k:=k+1;

end;

close(fi);
Preorder(0);

writeln('Kolichestvo vershin: ',kol);
end.


Скачать файл (423 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru