Шпора по программированию

  • 11 сент. 2011 г.
  • 1074 Слова
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 cherezdopolnit. 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.
2. Возвести в натуральную степень К число А обычным способом и ускоренным (порядка С 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 k0 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 Ai 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;
vara11,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;
beginfpr:=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
elseb:=b-a;
if a=0 then c:=b else c:=a;
writeln('NOD: ',c);
end.

6 Найти целые х И у такие, что Ах+Ву=НОД(А,В).

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