Алгоритмы для студентов

2010-11-28T11:14:30Z

Psihopat:

Здесь будет ряд алгоритмов из курса лекций "Основы программирования"

=== Вывод массива ===
<source lang="Delphi">procedure Print<T>(a: array of T; delim: string := ' ');
begin
foreach x: T in a do
write(x, delim);
end;

// С переходом на следующую строку
procedure Println<T>(a: array of T; delim: string := ' ');
begin
Print(a, delim);
writeln;
end;</source>

=== Заполнение массива случайными числами ===
<source lang="Delphi">procedure CreateRandomArray(var a: array of integer;
n: integer);
begin
SetLength(a,n);
for var i:=0 to n-1 do
a[i] := random(100);
end;</source>

=== Инвертирование массива ===
<source lang="Delphi">procedure Invert<T>(a: array of T);
begin
var n := a.Length;
for var i:=0 to n div 2 - 1 do
Swap(a[i],a[n-i-1]);
end; </source>

=== Поиск элемента по заданному значению ===
<source lang="Delphi">// С помощью for
function Find<T>(a: array of T; x: T): integer;
begin
Result := -1;
for var i := 0 to a.Length - 1 do
if a[i] = x then
begin
Result := i;
break;
end;
end;

// С помощью while
function FindWhile<T>(a: array of T; x: T): integer;
begin
var n := a.Length;
var i := 0;
while (i<n) and (a[i]<>x) do
i += 1;
if i=n then
Result := -1
else Result := i;
end;

// Поиск с барьером
function FindWithBarrier<T>(a: array of T; n: integer;
x: T): integer;
begin
Assert((0 < n) and (n < a.Length));
a[n] := x;
var i := 0;
while a[i]<>x do
i += 1;
if i=n then
Result := -1
else Result := i;
end;</source>

=== Минимальный элемент и его индекс ===
<source lang="Delphi">procedure MinElem(a: array of integer;
var min: integer; var minind: integer);
begin
min := a[0];
minind := 0;
for var i:=1 to a.Length-1 do
if a[i]<min then
begin
min := a[i];
minind := i;
end;
end;</source>

=== Сдвиг влево ===
<source lang="Delphi">procedure ShiftLeft<T>(a: array of T);
begin
for var i:=0 to a.Length-2 do
a[i] := a[i+1];
a[a.Length-1] := default(T);
end;</source>

=== Сдвиг вправо ===
<source lang="pascal">
procedure ShiftRight<T>(a: array of T);
begin
for var i := a.Length-1 downto 1 do
a[i] := a[i-1];
a[0] := default(T);
end;
</source>

[http://pascalabc.net/WDE/?shared=PacVlad/ShiftRight.pas Ссылка на алгоритм в среде WDE]

=== Циклический сдвиг вправо ===
<source lang="pascal">
procedure CycleShiftRight<T>(a: array of T);
begin
var v := a[a.Length-1];
for var i := a.Length downto 1 do
a[i] := a[i-1];
a[0] := v;
end;
</source>

[http://pascalabc.net/WDE/?shared=PacVlad/CycleShiftRight.pas Ссылка на алгоритм в среде WDE]

=== Удаление k-того ===
<source lang="pascal">
procedure Delete<T>(a: array of T; var n: integer; k: integer);
begin
Assert((0<=k) and (k<n) and (n<=a.Length));
for var i := k to n-2 do
a[i] := a[i+1];
a[n-1] := default(T);
n -= 1;
end;
</source>

[http://pascalabc.net/WDE/?shared=PacVlad/Delete.pas Ссылка на алгоритм в среде WDE]

=== Вставка на k-тое место ===
<source lang="pascal">
procedure Insert<T>(a: array of T; var n: integer; var k: integer; value: T);
begin
Assert((0<=k) and (k<=n) and (n<a.Length));
for var i := n-1 downto k+1 do
a[i+1] := a[i];
a[k] := value;
n += 1;
end;
</source>

[http://pascalabc.net/WDE/?shared=PacVlad/Insert.pas Ссылка на алгоритм в среде WDE]

=== Слияние двух упорядоченных в один упорядоченный ===
<source lang="pascal">
// a,b упорядочены по возрастанию
function Merge(a,b: array of integer; n,m: integer): array of integer;
begin
Assert((0 < n) and (n < a.Length));
Assert((0 < m) and (m < b.Length));
a[n] := integer.MaxValue;
b[m] := integer.MaxValue;
SetLength(Result,m+n);
var ia := 0;
var ib := 0;
for var ir := 0 to n+m-1 do
if a[ia]<b[ib] then
begin
Result[ir] := a[ia];
ia += 1;
end
else
begin
Result[ir] := b[ib];
ib += 1;
end;
end;
</source>

=== Поиск в упорядоченном массиве ===
<source lang="pascal">
function BinarySearch(a: array of integer; x: integer): integer;
begin
var k: integer;
var i := 0;
var j := a.Length-1;
repeat
k := (i+j) div 2;
if x>a[k] then
i := k+1
else
j := k - 1;
until (a[k]=x) or (i>j);
if a[k]=x then
Result := k
else
Result := -1;
end;
</source>

Алгоритмы для студентов

2010-11-27T21:11:42Z

Psihopat:

Здесь будет ряд алгоритмов из курса лекций "Основы программирования"

=== Вывод массива ===
<source lang="Delphi">procedure Print<T>(a: array of T; delim: string := ' ');
begin
foreach x: T in a do
write(x, delim);
end;

// С переходом на следующую строку
procedure Println<T>(a: array of T; delim: string := ' ');
begin
Print(a, delim);
writeln;
end;</source>

=== Заполнение массива случайными числами ===
<source lang="Delphi">procedure CreateRandomArray(var a: array of integer;
n: integer);
begin
SetLength(a,n);
for var i:=0 to n-1 do
a[i] := random(100);
end;</source>

=== Инвертирование массива ===
<source lang="Delphi">procedure Invert<T>(a: array of T);
begin
var n := a.Length;
for var i:=0 to n div 2 - 1 do
Swap(a[i],a[n-i-1]);
end; </source>

=== Поиск элемента по заданному значению ===
<source lang="Delphi">// С помощью for
function Find<T>(a: array of T; x: T): integer;
begin
Result := -1;
for var i := 0 to a.Length - 1 do
if a[i] = x then
begin
Result := i;
break;
end;
end;

// С помощью while
function FindWhile<T>(a: array of T; x: T): integer;
begin
var n := a.Length;
var i := 0;
while (i<n) and (a[i]<>x) do
i += 1;
if i=n then
Result := -1
else Result := i;
end;

// Поиск с барьером
function FindWithBarrier<T>(a: array of T; n: integer;
x: T): integer;
begin
Assert((0 < n) and (n < a.Length));
a[n] := x;
var i := 0;
while a[i]<>x do
i += 1;
if i=n then
Result := -1
else Result := i;
end;</source>

=== Минимальный элемент и его индекс ===
<source lang="Delphi">procedure MinElem(a: array of integer;
var min: integer; var minind: integer);
begin
min := a[0];
minind := 0;
for var i:=1 to a.Length-1 do
if a[i]<min then
begin
min := a[i];
minind := i;
end;
end;</source>

=== Сдвиг влево ===
<source lang="Delphi">procedure ShiftLeft<T>(a: array of T);
begin
for var i:=0 to a.Length-2 do
a[i] := a[i+1];
a[a.Length-1] := default(T);
end;</source>

'''№7. Сдвиг вправо'''
<source lang="pascal">
procedure ShiftRight<T>(a: array of T);
begin
for var i := a.Length-1 downto 1 do
a[i] := a[i-1];
a[0] := default(T);
end;
</source>

'''№8. Циклический сдвиг вправо'''
<source lang="pascal">
procedure CycleShiftRight<T>(a: array of T);
begin
var v := a[a.Length-1];
for var i := a.Length downto 1 do
a[i] := a[i-1];
a[0] := v;
end;
</source>

'''№9. Удаление k-того'''
<source lang="pascal">
procedure Delete<T>(a: array of T; var n: integer; k: integer);
begin
Assert((0<=k) and (k<n) and (n<=a.Length));
for var i := k to n-2 do
a[i] := a[i+1];
a[n-1] := default(T);
n -= 1;
end;
</source>

'''№10. Вставка на k-тое место'''
<source lang="pascal">
procedure Insert<T>(a: array of T; var n: integer; var k: integer; value: T);
begin
Assert((0<=k) and (k<=n) and (n<a.Length));
for var i := n-1 downto k+1 do
a[i+1] := a[i];
a[k] := value;
n += 1;
end;
</source>

'''№11. Слияние двух упорядоченных в один упорядоченный'''
<source lang="pascal">
// a,b упорядочены по возрастанию
function Merge(a,b: array of integer; n,m: integer): array of integer;
begin
Assert((0 < n) and (n < a.Length));
Assert((0 < m) and (m < b.Length));
a[n] := integer.MaxValue;
b[m] := integer.MaxValue;
SetLength(Result,m+n);
var ia := 0;
var ib := 0;
for var ir := 0 to n+m-1 do
if a[ia]<b[ib] then
begin
Result[ir] := a[ia];
ia += 1;
end
else
begin
Result[ir] := b[ib];
ib += 1;
end;
end;
</source>

'''№12. Поиск в упорядоченном массиве'''
<source lang="pascal">
function BinarySearch(a: array of integer; x: integer): integer;
begin
var k: integer;
var i := 0;
var j := a.Length-1;
repeat
k := (i+j) div 2;
if x>a[k] then
i := k+1
else
j := k - 1;
until (a[k]=x) or (i>j);
if a[k]=x then
Result := k
else
Result := -1;
end;
</source>

Вики проекта PascalABC.NET - Вклад [ru]

Алгоритмы для студентов

Алгоритмы для студентов