Зная координаты трех вершин, надо найти площадь треугольника.

Входные данные

6 чисел - координаты вершин треугольника

Выходные данные

1 число - ответ на задачу

Решение

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

var x1,x2,x0,y1,y2,y0,s1,s2,s3,a,b,c,p,h:real;
begin
//1 Вариант. Косое произведение векторов
readln(x1,y1,x2,y2,x0,y0);
s1:=abs((x2-x1)*(y0-y1)-(y2-y1)*(x0-x1))/2;
writeln(s1:0:15);
//2 Вариант. По формуле Герона
a:=sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0));
  b:=sqrt((x2-x0)*(x2-x0)+(y2-y0)*(y2-y0));
   c:=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
p:=(a+b+c)/2;
s2:=sqrt(p*(p-a)*(p-B)/>*(p-c));
writeln(s2:0:15);
//3 Вариант. Произведение высоту на сторону, к которой она проведена
h:=abs((y2-y1)*x0+(x1-x2)*y0+(y1*x2-x1*y2))/sqrt(a*a+b*B)/>;
s3:=h*c/2;
writeln(s3:0:15 );
end.

Определить, лежит ли точка М в круге

Входные данные

5 чисел - mx,my - координаты точки М, xc,yc - координаты центра круга, r - радиус круга

Выходные данные

Вывести "точка М лежит в круге" если это так или "точка М лежит вне круга"


Решение

var xc,yc,mx,my,d,r:real;
begin
readln( mx,my,xc,yc,r ); //mx,my - координаты точки M, xc,yc,r - координаты круга и его радиус
d:=sqrt(sqr(xc-mx)+sqr(yc-my));
if d<=r then writeln ('точка M лежит в круге')
      	else writeln ('точка M лежит вне круга');
end.

Размещение из n элементов состоит из m элементов (позиций), причём один и тот же элемент может повторяться не более m раз.

Формула размещения с повторением

A=n в степени m


Словесно алгоритм можно описать так:

В n-ричной системе исчесления перебираем все числа от 001 до 000

var p:array [0..1000] of integer;
	b:array [0..1000] of char;
	i,j,m,n,s:longint;
   begin
  
	readln(n,m);
	for i:=0 to n-1 do read(b[i]);
  
	for i:=0 to m do p[i]:=0;
  
   while p[0]=0 do
	begin
    
	j:=m;
	while p[j]=n-1 do begin
           			p[j]:=0;
           			j:=j-1;
           			end;
	p[j]:=p[j]+1;
    
	for i:=1 to m do write(b[p[i]]);
	s:=s+1;
	writeln;
    
	end;
	writeln(s);
   end.

Сочетание из n элементов по m - это соединение, содержащее m элементов, взятых из nразличных элементов, отличающихся хотя бы одним элементом. Порядок элементов не учитывается.

Сочетания обозначаются буквой C.

Формула сочетания:

С из n по m

C=n! / m!*( n-m )!



Задача.

В магазине 5 разных по цвету гвоздик: К(красная),Ж(жёлтая),Р(розовая),Б(белая),Г(голубая). Из них надо выбрать все возможные варианты букетов и вывести их на экран.

Для начала попробуем сделать это на бумаге:

К Ж Р (1 перестановка )

К Ж Б (2 перестановка )

К Ж Г (3 перестановка )

К Р Б (4 перестановка )

К Р Г (5 перестановка )

К Б Г (6 перестановка )

Ж Р Б (7 перестановка )

Ж Р Г (8 перестановка )

Ж Б Г (9 перестановка )

Р Б Г (10 перестановка )

Как мы видим всего получилось 10 вариантов.

Теперь давайте проверим нашу формулу сочетания (которая указана выше).

C(из 5 по 3)
С = 5! / 3! ( 5 - 3 )! = 4*5 / 2 * 1 = 10

Ответ:10 вариантов.



Теперь давайте попробуем составить словесный алгоритм этой задачи.

Словесный алгоритм:

1. Читаем заданные n и m и забивает массив р от 0..m

(в этой задачи лучше пользоваться Рипитом)

2. Первым делом в Рипите выводим сочетание.

3. Ищем с конца элемент не достигшей своего максимума(этот элемент j).

4. Если нашли такой элемент, то увеличиваем его значение на единицу, а остальные элементы по порядку от j+1 делаем на единицу больше чем предыдущий(на паскале это выглядит так: p[i]:=p[i-1]+1).


Программный алгоритм

var p: array [0..1000] of byte;
	n,m,i,j,s:longint;
	b:array [1..1000] of char;
 
begin
   readln(n,m);
 
   for i:=1 to n do read(b[i]);
   for i:=0 to m do p[i]:=i;
 
  REPEAT
  
   for i:=1 to m do write(b[p[i]]);
	writeln;
   s:=s+1;
    
   j:=m;
	while (j>0) and(p[j]=j+n-m) do dec(j);
   if j>0 then begin
            	p[j]:=p[j]+1;
            	for i:=j+1 to m do p[i]:=p[i-1]+1;
       		end;
UNTIL j=0;
 
writeln(s);
 
end.

Размещение из n по m - это соединения, отличающиеся друг от друга составом элементов или их порядком, содержащие m элементов из n различных.

Размещение обозначается буквой A

Формула размещения

А= n! / ( n-m )!


Теперь устная задача

Задача

Найти сколько вариантов из 3-х букв a b c можно составить 2-х буквенных слов.

Попробуем на бумаге:

(1 перестановка ) a b (3 перестановка ) a c (5 перестановка ) b c

(2 перестановка ) b c (4 перестановка ) c a (6 перестановка ) c b

Получается 6 вариантов.

Теперь проверим нашу формулу

А=3!/(3-2)1=6/1=6

Значит формула правильная.

Ответ: 6 вариантов.



Алгоритм

Тут нам понадобится совместить алгоритм сочетания и алгоритм перестановки .

Способ первый

В алгоритме сочетания ( смотри ниже).

1. Пересохраняем массив p в q.

2. Делаем перестановку из m элементов на ходящихся в массиве q.

3.Теперь меняем элементы с помощью сочетания.

type mas= array [0..1000] of byte;
var p,q:mas;
	n,m,i,j,s,k,d:longint;
	b:array [1..1000] of char;
begin
   readln(n,m);
   for i:=1 to n do read(b[i]);
   s:=0;
   for i:=0 to m do p[i]:=i; //Часть 1
  REPEAT
 
//Часть 2
for i:=0 to m do q[i]:=p[i];
while q[0]=0 do
	Begin
  	while q[0]=0 do
	begin
	for i:=1 to m do write(b[q[i]]);
  	writeln;
  	inc(s);
	j:=m;
  	while q[j-1]>q[j] do dec(j);
    
	k:=m;
  	while q[j-1]>q[k] do dec(k);
	d:=q[j-1];
	q[j-1]:=q[k];
	q[k]:=d;
	for i:=j to (m+j-1)div 2 do
  	begin
   	d:=q[m+j-i];
   	q[m+j-i]:=q[i];
   	q[i]:=d;
  	end;
	end;
	end;
 
//Часть 3
 
  j:=m;
while (j>0) and(p[j]=j+n-m) do dec(j);
  if j>0 then begin
            	p[j]:=p[j]+1;
            	for i:=j+1 to m do p[i]:=p[i-1]+1;
   			end;
  
  
UNTIL j=0;
writeln(s);
end.

Способ второй

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

type mas= array [0..1000] of byte;
var p:mas;
	n,m,i,j,s:longint;
	b:array [1..1000] of char;
  procedure perestan(q:mas);
   var i,j,k,d:longint;
 
begin
   while q[0]=0 do
	begin
	for i:=1 to m do write(b[q[i]],' ');
  	writeln;
  	inc(s);
	j:=m;
  	while q[j-1]>q[j] do dec(j);
    
	k:=m;
  	while q[j-1]>q[k] do dec(k);
	d:=q[j-1];
	q[j-1]:=q[k];
	q[k]:=d;
	for i:=j to (m+j-1)div 2 do
  	begin
   	d:=q[m+j-i];
   	q[m+j-i]:=q[i];
   	q[i]:=d;
  	end;
	end;
end;
 
begin
   readln(n,m);
 
   for i:=1 to n do read(b[i]);
   for i:=0 to m do p[i]:=i;
 
  REPEAT
   perestan(p);
   j:=m;
	while (j>0) and(p[j]=j+n-m) do dec(j);
   if j>0 then begin
            	p[j]:=p[j]+1;
            	for i:=j+1 to m do p[i]:=p[i-1]+1;
       		end;
until j=0;
 
writeln(s);
 
end.

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

Входные данные

В первой строке вводится n (1<=n<=1000) - длина последовательности. Далее идет сама последовательность длиной n чисел (все числа по модуля не превосходят 10000).

Выходные данные

Одно число - ответ на задачу.

Решение

var a,f:array [1..10000]of longint;
	n,i,max,j:longint;
begin
readln(n); //читаем кол-во чисел
for i:=1 to n do
  read(a[i]); //считываем последовательность
for i:=1 to n do
  f[i]:=1; //забиваем массив ответов 1
for i:=1 to n do
  for j:=1 to i-1 do
   if (a[i]>a[j]) and (f[j]+1>f[i]) then f[i]:=f[j]+1; //ищем длину возрастающей последовательности на каждом шаге последовательности
for i:=1 to n do
  if f[i]>max then max:=f[i]; //находим максимальную подпоследовательность в массиве ответов
writeln(max);
end.

На вершине лесенки, состоящей из n ступенек, лежит мячик. Он начинает прыгать вниз, к основанию лесенки. Мячик может прыгнуть на след. ступеньку, на ступеньку через одну или через две. Т.е. если мячик лежит на 10 ступеньке, то он может прыгнуть на 9, 8 или 7 ступеньки. Определите число всевозможных маршрутов мячика.

Входные данные

Число n - кол.во ступенек (0<=n<=70)

Выходные данные

Одно число - ответ на задачу

Решение

var f:array [1..70] of int64; i,n:longint;
begin
readln(n); //считываем число ступенек
f[1]:=1; //если у нас 1 ступенька, то кол-во способов 1, т.к. есть один способ сигануть с вершины лесенки до основания, если всего одна ступенька (проверьте сами)
f[2]:=2; //если у нас 2 ступеньки, то кол-во способов 2, т.к. есть два способа сигануть с вершины лесенки до основания, если всего две ступеньки (проверьте сами)
f[3]:=4; //если у нас 3 ступеньки, то кол-во способов 4, т.к. есть четыре способа сигануть с вершины лесенки до основания, если всего три ступеньки (проверьте сами)
for i:=4 to n do
  f[i]:=f[i-2]+f[i-1]+f[i-3]; //А дальше динамика. В массив ответов заносим сумму вариантов "сигания" с i-1, i-2, i-3 ступенек.
writeln(f[n]); //ответ на задачу
end.

Компонентой сильной связности (strongly connected component) называется такое максимальное подмножество вершин графа, что если мы возьмем любое две вершины, то есть путь как из одной в другую, так и обратно.

Задача

Дан граф (n вершин и m ребер). Далее идут описания ребер, т.е. две вершины, из которой в какую есть путь (ребро). Найти все компоненты сильной связности (их количество).

Словесный алгоритм

• Сортируем вершины топологически.
  
• Инвертируем граф (т.е. меняем направления ребер, например если было ребро из 2 в 3 вершину, то делаем из 3 во 2)
  
• Пробегаемся по отсортированному массиву и если находим не помеченную вершину, то увеличиваем счетчик кол-во к.с.с. и пускаем dfs2 от этой вершины

Реализация


Топологическая сортировка

 
procedure dfs(v:longint);
var i:longint;
begin
  used[v]:=true;//помечаем вершину
  for i:=1 to n do //перебираем все вершины
    if not(used[i]) and (g[v,i]=1) then dfs(i); //если вершина не помеченна и есть путь из нашей вершину в нее, то запускаем глубину от этой вершины
  cnt:=cnt+1;//кол-во вершин тоположке
  dag[cnt]:=v; //кидаем нашу вершину в топологически отсортированный массив
end;

Меняем направление ребер

 
for i:=1 to n do
    for j:=1 to n do
      if (g[i,j]=1) then g1[j,i]:=1; //здесь думаю все понятно

Ищем кол-во к.с.с

 
scc:=0;
  for i:=cnt downto 1 do
    if not(used[dag[i]]) //если вершина не помеченна
      then
        begin
          scc:=scc+1; //на 1 увеличиваем кол-во к.с.с.
          dfs2(dag[i]); //пускаем dfs2 от нашей вершины
        end;
  writeln(scc);

Сам dfs2

 
procedure dfs2(v:longint);
var i:longint;
begin
  used[v]:=true; //помечаем вершину
  for i:=1 to n do//перебираем все вершины
    if not(used[i]) and (g1[v,i]=1) then dfs2(i);//если вершина не помеченна и есть путь из нашей вершину в нее, то запускаем глубину от этой вершины
end;

Не забудьте обнулить массив меток used перед поиском к.с.с.

Дан граф, состоящий из n вершин и m ребер. Далее даны описания ребер (откуда и куда). Требуется расположить вершины так, чтобы все ребра совпадали по направлениям.

Например дан граф из 6 вершин



Тогда мы можем расположить вершины в такое порядке: 5 2 7 1 3 6. Почему так? Потому что: 5 --> 2, 2 --> 7, 5 --> 1, 1 --> 3, 1 --> 6, 3 --> 6. Все стрелки --> получились одинаковыми, а значит мы отсортировали граф топологически.

Реализация поиском глубиной

Перебираем все вершины и смотрим, что если она не помеченная (used массив меток), тогда из нее пускаем глубину

for i:=1 to n do
  if not(used[i]) then dfs(i);

Рассмотрим dfs. Думаю, я не буду все расписывать, ведь всё указано в пунктах выше, разве что некоторые моменты

 
procedure dfs(v:longint);
var i:longint;
begin
  used[v]:=false; //помечаем вершину, типа мы здесь были
  for i:=1 to n do
    if (not(used[i])) and (g[v,i]=1) //если мы не были в этой вершине и есть путь из вершины v в нашу
      then
        begin
          parent[i]:=v; //предком для нашей вершины является вершина v, т.е. мы пришли из неё
          dfs(i); //глубиной идем от нашей вершины
        end;
  inc(cnt); //увеличиваем счетчик
  dag[cnt]:=v; //в массив тоположки кидаем нашу вершину v
end;

Ну и сам вывод массива вершин, топологически отсортированного

for i:=cnt downto 1 do
  write(dag[i],' ');

Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. Требуется найти все совершенные числа от n до m (1 <= n,m <=100000)


Ввод

Два числа n и m

Вывод

В каждой строке вывести совершенные числа на промежутке от n до m. Если таких нет, вывести Absent.

Пример
______
6 6

6
______
4 5

Absent
______

Решение

Циклом бежим от n до m и находим сумму делителей числа i. Если сумма равна i, тогда выводим число i.

var n,m,i:int64;
    f:boolean;
function pr(x:int64):boolean;
var d,s:int64;
begin
  s:=1;
  if(x=1)then begin pr:=false; exit; end;
  d:=2;
  while int64(d)*d<x do
    begin
      if(x mod d=0)then s:=s+d+(x div d);
      d:=d+1;
    end;
  if d*d=x then s:=s+d;
  pr:=(s=x); //if s=x then pr:=true else pr:=false;
end;
begin
  assign(input,'input.txt'); reset(input);
    assign(output,'output.txt'); rewrite(output);
  readln(n,m);
  f:=false;
  for i:=n to m do
    if(pr(i))then begin writeln(i); f:=true; end;
  if not(f) then writeln('Absent');
end.

Дерево отрезков — это структура данных, которая позволяет эффективно (т.е. скорость алгоритма (O(log n)) реализовать операции следующего вида:

• Нахождение суммы на отрезке [L;R]
  
• Нахождение минимума и максимума на отрезке [L;R]
  
• Изменение элементов (увеличение и уменьшение) на отрезке [L;R]

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



Важной особенностью деревьев отрезков является то, что они потребляют линейный объём памяти: стандартному дереву отрезков требуется порядка 4n элементов памяти для работы над массивом размера n.

Например в задаче n<=100000. Значит нам надо сделать массив [0..400000].

Структура дерева

Подсчитаем и запомним сумму элементов всего массива, т.е. отрезка a[0..n-1] Также посчитаем сумму на двух половинках этого массива: a[0..n/2] и a[n/2..n-1]. Каждую из этих двух половинок в свою очередь разобьем пополам, посчитаем и сохраним сумму на них, потом снова разобьем пополам, и так далее, пока текущий отрезок не достигнет длины 1. Иными словами, мы стартуем с отрезка [0..n-1] и каждый раз делим текущий отрезок надвое (если он ещё не стал отрезком единичной длины), вызывая затем эту же процедуру от обеих половинок; для каждого такого отрезка мы храним сумму чисел на нём.

Можно говорить, что эти отрезки, на которых мы считали сумму, образуют дерево: корень этого дерева — отрезок [0..n-1], а каждая вершина имеет ровно двух сыновей (кроме вершин-листьев, у которых отрезок имеет длину 1).

Задача


Реализуйте структуру данных, хранящую информацию об N (1 ≤ N ≤ 100000) целых числах A₁, ..., A_N. Структура должна поддерживать следующие операции.



1) INIT(N) Инициализация числом N. При этом каждому числу A_i присваивается значение 0.

2) MODIFY(pos,value) Значение A_pos увеличивается на value, если value ≥ 0, и уменьшается на |value|, если value < 0.

3) FINDSUM(l,r) Вывод в выходной файл суммы a[l]..a[r].



Input

Входной файл содержит не более 100000 операций. Каждая операция описывается в отдельной строке. Описание операции начинается с целого числа от 1 до 3 --- ее номера в списке выше. Далее следуют параметры операции в порядке их перечисления в скобках. Числа в каждой строке разделены пробелами.

Все операции корректны. Это значит, что:

• операция INIT является самой первой операцией во входном файле и больше нигде в нем не встречается;
  
• для операции MODIFY выполняются ограничения 1 ≤ pos ≤ N и -10000 ≤ value ≤ 10000;
  
• для операции FINDSUM выполняются ограничения 1 ≤ l ≤ r ≤ N.

Output




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

Ввод

1 5
2 4 3
2 2 2
3 2 3
2 5 -2
3 2 4
2 5 6
2 4 2
3 3 3
2 1 -8
2 5 -3
2 4 -7
2 5 -4
3 4 4
3 1 2

Вывод

2
5
0
2
6

Решение

Совершенно очевидно, что надо применять дерево отрезков для решения этой задачи. Каждый из запросов задается первым числом в строке входного файла. Т.е. если нам ввели 1, то надо выполнить запрос INIT, если ввели 2, то надо выполнить запрос MODIFY, если 3, то запрос FINDSUM. Итак рассмотрим каждый из запросов в отдельности.

Запрос INIT(N)

Здесь нам надо обнулить всё дерево, т.е. построить его. Для этого сделаем вот что:

Прочитаем число n. Далее подберем такой показатель степени (банально мы подбираем число), чтобы при возведении 2 в эту степень полученное число было больше нашего n. Это и будет размером нашего массива для хранения дерева сумм. Ну и обнуляем все a[i].

Запрос MODIFY(pos,value)

Этот запрос получает на вход индекс pos и значение value, и перестраивает дерево отрезков таким образом, чтобы оно соответствовало новому значению a[pos]=value .
Тогда понятно, что запрос обновления можно реализовать как рекурсивную функцию: ей передается текущая вершина дерева отрезков, и эта функция выполняет рекурсивный вызов от одного из двух своих сыновей (от того, который содержит позицию pos в своем отрезке), а после этого — пересчитывает значение суммы в текущей вершине точно таким же образом, как мы это делали при построении дерева отрезков (т.е. как сумма значений по обоим сыновьям текущей вершины).

Запрос FINDSUM(l,r)

Реализация

Построение

 
procedure init;
begin
  readln(n);
  pr:=1;
  while pr<n do
    pr:=pr*2;
end;
 

Обновление

 
procedure modify(p,v:longint);
begin
  a[p]:=a[p]+v;
  if p<>1 then modify(p div 2,v);
end;
 

Нахождение суммы

 
procedure findsum(v,l,r:longint);
begin
  if (lv>r) or (rv<l)
    then exit
      else
        if (l>=lv) and (rv>=r)
          then s:=s+a[v]
            else
              begin
                findsum(2*v,l,(l+r)div 2);
                findsum(2*v+1,(l+r)div 2+1,r);
              end;
end;

В основном коде делаем вот что

 
читаем b
      if b=1 then init;
      if b=2
        then
          begin
            readln(p,v);
            p:=pr+p-1;
            modify(p,v);
          end;
      if b=3
        then
          begin
            readln(lv,rv);
            lv:=pr+lv-1;
            rv:=pr+rv-1;
            findsum(1,pr,2*pr-1);
            writeln(s);
            s:=0;
          end;
    end;

Перестановки из n элементов с повторениями – это перестановки из n элементов, в каждую из которых входят n1 элементов 1-го типа, n2 элементов 2-го типа…, nm элементов m-го типа, где n1+n2+n +…+nm=n.

Pn(n1, n2, … nm) = n!/n1*n2*…*nm

Если m=3, b=’xyz’, kp=[2, 3, 2], ( в массиве kp записано сколько раз повторятся i-той букве как написано в примере) то перестановки с повторениями будут такими:

01122233 => xxyyyzz
01122323 => xxyyzyz
01122332 => xxyyzzy
01123223 => xxyzyyz
01123232 => xxyzyzy
…
03322211 => zzyyyxx

Словесный алгоритм тот же, что и в обычных перестановках.

var b:string; p,kp:array [0..255] of integer; n,i,j,d,k,l,s:longint;
  begin
   readln(B)/>;
	n:=length(B)/>;
	for i:=1 to n do read(kp[i]);
  
	p[0]:=0;
	for i:=1 to n do
	for j:=1 to kp[i] do
   	begin
    	l:=l+1;
    	p[l]:=i;
   	end;
  
   n:=l;
	while p[0]=0 do
	Begin
   	for i:=1 to n do write(b[p[i]]);
		writeln;
		s:=s+1;
      
   	j:=n;
    	while p[j-1]>=p[j] do j:=j-1;
      
   	k:=n;
    	while p[j-1]>=p[k] do k:=k-1;
      
   	d:=p[k];
   	p[k]:=p[j-1];
   	p[j-1]:=d;
      
   	for i:=j to (n+j-1)div 2 do
    	begin
    	d:=p[i];
    	p[i]:=p[n-i+j];
    	p[n-i+j]:=d;
    	end;
	end;
	writeln(s);
end.

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

Перестановка обозначается буквой P
Формула перестановки из n элементов
P=n!

Итак, допустим нам надо посчитать кол-во перестановок из 3 элементов (допустим n=3). Значит сначала введем эти элементы. Пусть это будут a b c.
Выполним перестановки на бумаге.
a b c (1 перестановка )
a c b (2 перестановка )
b a c (3 перестановка )
b c a (4 перестановка )
c a b (5 перестановка )
c b a (6 перестановка )

Словесный алгоритм будет выглядеть так:

Пока p (нулевое)=0 повторять:

1. Выводим перестановку b[p[i]] .

2. Ищем элемент слева меньший в паре начинаем с конца (это p[j-1]>p[j]) .

3. С конца ищем больший элемент, чем p[j-1]. (это будет p[k] элемент).

4. Меняем местами p[j-1] и p[k].

5. Элементы от p[j] до p[n] меняем в обратном порядке.

Программный алгоритм выглядит так :

var b:string; p:array [0..255] of integer; c,n,i,j,r,q,d,k:longint;
  begin
   readln(B)/>;
    n:=length(B)/>;
    
    for i:=0 to n do p[i]:=i;
    
    while p[0]=0 do
 	Begin

   	for i:=1 to n do write(b[p[i]]);
     	writeln;
      
   	j:=n;
        while p[j-1]>p[j] do j:=j-1;
      
   	k:=n;
        while p[j-1]>p[k] do k:=k-1;
      
   	d:=p[k];
   	p[k]:=p[j-1];
   	p[j-1]:=d;
      
   	for i:=j to (n+j-1)div 2 do
        begin
        d:=p[i];
        p[i]:=p[n-i+j];
        p[n-i+j]:=d;
        end;
    end;
end.

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

Последовательность простых чисел начинается так:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, …

Функция простого числа на паскале

function pr(x:longint):boolean;
var d:longint;
begin
if x mod 2 =0 then pr:=(x=2)
          	else
          	begin
  d:=3;
  while (d*d<=x)and(x mod d <>0) do
  d:=d+2;
  pr:=(d*d>x)and(x<>1);
end;
end;

Пример задачи с использованием простых чисел.

Задача

Вывести все простые числа от M до N включительно.

Ограничения: 2 <= M <= N <= 300 000.

Ввод: В первой строке находятся разделённые пробелом M и N.

Вывод: Вывести числа в порядке возрастания, по одному в строке. Если между M и N включительно нет простых - вывести "Absent".

Примеры

Ввод 1

2 5

Вывод 1

2

3

5

var n,m,i,f:LONGINT;
function pr(x:longint):boolean;
var d:longint;
begin
if x mod 2 =0 then pr:=(x=2)
          	else
          	begin
  d:=3;
  while (d*d<=x)and(x mod d <>0) do
  d:=d+2;
  pr:=(d*d>x)and(x<>1);
end;
end;
begin
f:=0;
readln(n,m);
for i:=n to m do
if pr(i) then begin writeln(i); f:=1; end;
if f=0 then writeln('Absent');
end.

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену.

Алгоритм

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:



Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).

Пусть переменная p изначально равна двум — первому простому числу.

Считая от p шагами по p, зачеркнуть в списке все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …)

Найти первое не зачеркнутое число, большее чем p, и присвоить значению переменной p это число.

Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n

Теперь все не зачеркнутые числа в списке — простые.

На практике, алгоритм можно несколько улучшить следующим образом. На шаге № 3, числа можно зачеркивать, начиная сразу с числа p2, потому что все составные числа меньше его уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.

Можно показать, что сложность алгоритма составляет O(nlog log n) операций в модели вычислений RAM, или O(n(log n)(log log n)) битовых операций, при условии вычисления и зачеркивания каждого кратного числа за время O(1), например при использования массивов с прямым доступом.



http://upload.wikime...ratosthenes.gif



Программный код

var b:array[2..100000] of boolean;
i,j,n:longint;
begin
readln(n);
for i:=2 to n do b[i]:= true;
i:=2;
while i*i<= n do begin
if b[i]= true then begin
       			j:=i*i;
       			while j<=n do begin
                     			b[j]:=false;
                     			j:=j+i;
                     			end;
       			end;
if i=2 then i:=3 else i:=i+2;
end;
for i:=2 to n do
if b[i] then write(i,' ');
end.

Алгоритм Флойда, применяется для

*поиска кратчайших расстояний расстояний между всеми парами вершин графа (одновременно можно построить и сами кратчайшие пути от каждой вершины до каждой)

*построения матрицы достижимости графа

*построения множества истоков и множества стоков (исток - вершина, в которую нет входящих дуг) (сток - вершина, из которой нет исходящих дуг)

Алгоритм Флойда

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Входные данные

В первой строке входного файла INPUT.TXT записано единственное число N (1 <= N <= 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы - всегда нули.

Выходные данные

В выходной файл OUTPUT.TXT выведите N строк по N чисел - матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно быть равно весу кратчайшего пути из вершины i в вершину j.

Пример

INPUT.TXT

4

0 5 9 100

100 0 2 8

100 100 0 7

4 100 100 0

OUTPUT.TXT

0 5 7 13

12 0 2 8

11 16 0 7

4 9 11 0

var g:array [1..100,1..100] of longint; n,j,i,k:longint;
function min(x,y:longint):longint;
begin
if x<y then min:=x
		else min:=y;
end;        
begin
//Считываем граф
readln(n);
for i:=1 to n do
  for j:=1 to n do read(g[i,j]);
//Вот это - алгоритм Флойда, т.е простейший для реализации способ нахождения кратчайших расстояний от каждой вершины к каждой
for k:=1 to n do
	for i:=1 to n do
        for j:=1 to n do
   		G[i,j]:=min(G[i,j],G[i,k]+G[k,j]);
//Вывод полученного графа
for i:=1 to n do
  begin  
    for j:=1 to n do
      write(g[i,j],' ');
    writeln;
   end;  
end.  

Поиск в ширину, применяется для решения произвольных задач на графах, требующих соответствующего порядка обхода ("в ширину") графа; раскрашивая пройденные вершины и/или дуги можно управлять порядком и способами обхода (например, однократное или многократное использование дуг и вершин)

Задача Кратчайший маршрут

В стране Б есть N городов, которые соединены M дорогами. По дорогам можно ездить в обоих направлениях. Между двумя городами могут существовать несколько дорог. Мальчик Вася живет в городе с номером 1, и он хочет поехать в город с номером N. Система дорог спроектирована так, что время проезда по каждой дороге одинаковое. Вася просит вас помочь найти кратчайший маршрут из города 1 в город N. Для этого вам необходимо выяснить, какое минимальное количество дорог необходимо проехать, чтобы попасть в желаемый город.
Формат ввода:
N M
X[1] Y[1]
X[2] Y[2]
…
X[M] Y[M]
N – количество городов в стране.
M – количество дорог в стране.
X[i] Y[i] – описание i-ой дороги между городами X и Y.
Ограничения:
2 <= N < = 1000
1 <= M < = 2000
Формат вывода:
Ответ на задачу - минимальное количество дорог, которые необходимо проехать, чтобы попасть в желаемый город.
Пример ввода:
4 4
1 2
2 3
2 4
3 4
Пример вывода:
2

var g:array[1..1000,1..1000] of longint; p,q:array [1..1000] of longint;  i,uk,un,n,m,a,b,v:longint;
begin
 readln(n,m);
 for i:=1 to m do
  begin
   readln(a,B)/>;
   g[a,b]:=g[a,b]+1;
   g[b,a]:=g[b,a]+1;     
  end;
 for i:=1 to n do
  begin
   p[i]:=-1;
   g[i,i]:=0;
  end;
 un:=1;
 uk:=2;
 p[1]:=0;
 q[1]:=1;
 while uk<>un do
  begin
   v:=q[un];
   un:=un+1;
   for i:=1 to n do
    if (g[v,i]>0)and(p[i]=-1) then begin
                                    q[uk]:=i;
                                    uk:=uk+1;
                                    p[i]:=p[v]+1;
                                   end;
  end;
 writeln(p[n]);
end.

Сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, сортировка Шелла и быстрая сортировка.

Пример работа алгоритма



Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Первый проход:

(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.

(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 5 > 4

(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как 5 > 2

(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.

Второй проход:

(1 4 2 5 8) (1 4 2 5 8)

(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как 4 > 2

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)



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

Третий проход:

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)



Теперь массив отсортирован и алгоритм может быть завершён.

Программный код

var a:array[1..10000] of integer;
	i,j,x,n:integer;
begin
  readln(n);   
  writeln('введите ',n,' элементов массива');
  for i:=1 to n do
   read( a[i] );
  for i:=1 to n-1 do
   for j:=1 to n-i do
	if a[j]>a[j+1] then begin
                     	x:=a[j];
                     	a[j]:=a[j+1];
                     	a[j+1]:=x;
                    	end;
writeln('после сортировки:');
for i:=1 to n do
  write( a[i],' ' );
end.

Сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, сортировка Шелла и быстрая сортировка.

Пример работа алгоритма



Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Первый проход:

(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.

(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 5 > 4

(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как 5 > 2

(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.

Второй проход:

(1 4 2 5 8) (1 4 2 5 8)

(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как 4 > 2

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)



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

Третий проход:

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)



Теперь массив отсортирован и алгоритм может быть завершён.

Программный код

var a:array[1..10000] of integer;
	i,j,x,n:integer;
begin
  readln(n);  
  writeln('введите ',n,' элементов массива');
  for i:=1 to n do
   read( a[i] );
  for i:=1 to n-1 do
   for j:=1 to n-i do
	if a[j]>a[j+1] then begin
                 		x:=a[j];
                 		a[j]:=a[j+1];
                 		a[j+1]:=x;
                    	end;
writeln('после сортировки:');
for i:=1 to n do
  write( a[i],' ' );
end.

Вводятся число n. Далее идут n чисел. Найти количество различных чисел.

Входные данные

Сначала вводится n - количество чисел (n<=1000). Далее идут n чисел.

Выходные данные

Число - ответ на задачу.

Решение

var a:array[1..1000] of integer;
    i,j,n:integer;
begin
readln(n); //ввод количества элементов
for i:=1 to n do  //ввод элементов массива
  read(a[i]);
i:=1; 
while (i<10) and (j<n+1) do //подсчет количества различных элементов
  begin
   j:=i+1;
   while (j<n+1) and (a[i]<>a[j]) do
    j:=j+1;
   i:=i+1;
  end;
if i<11 then writeln('В массиве ',i,' одинаковых элементов')
          else writeln('Все элементы массива различны');
end.

Дана матрица n*m . Найти сумму всех элементов этой матрицы.

Входные данные

n,m - размеры матрицы (n,m<=100). Далее в n столбцах и m строках следуют элементы матрицы a[i,j]

Выходные данные

Одно число - сумма всех элементов

Ввод

2 3

1 3 4
2 6 3

Вывод

19

Решение

var a:array[1..100,1..100] of longint;
	s,n,m,i,j:longint;   
begin
readln(n,m);
s:=0;
for i:=1 to n do
  for j:=1 to m do
   read(a[i,j]);
for i:=1 to n do
  for j:=1 to m do
	s:=s+a[i,j];
writeln(s);
end.

Задача Пересечение окружностей


Задан набор из N окружностей, которые описываются координатами своих центров. Все окружности имеют одинаковый радиус R. Необходимо найти две окружности, площадь пересечения которых максимальная. На рисунке красным цветом отображается область пересечения двух окружностей.



Формат ввода:

N R
X[1] Y[1]
X[2] Y[2]
…
X[N] Y[N]

N – Количество окружностей
R – Радиус окружностей
X[i] Y[i] – центр i-ой окружности

Ограничения:

2 <= N < = 100
0 <= X[i] Y[i] R <= 1000
Все числа целые.

Формат вывода:

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

Пример ввода:

3 1
0 0
1 0
1 1

Пример вывода:

1 2

Программный код.

var x,y:array[1..1000] of longint; n,i,r,n2,n1,j:longint; minp,p:real;
begin
readln(n,r);
for i:=1 to n do
  readln(x[i],y[i]);
minp:=sqrt( (x[1]-x[2])*(x[1]-x[2])+(y[1]-y[2])*(y[1]-y[2]) );
n1:=1;
n2:=2;
for i:=1 to n do
  for j:=1 to n do
   begin
	p:=sqrt( (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) );
	if (minp >p)and(i<>j) then begin
                            	minp:=p;
                            	n1:=i;
                            	n2:=j;
                           	end;
   end;
writeln(n1,' ',n2);
end.

Чтобы прочитать(по ссылкам ниже) и понять эту тему повторите (желательно ВЫУЧИТЕ) что такое синус sin, косинус cos, тангенс tg, а также основные свойства пропорции и вектора.


Тригонометрические_функции

Пропорция

Вектор



Итак рассмотрим несколько случаев

1.Общее уравнение прямой

ax+by+c=0, где а,b - это вектора, а c мы просто берем как переменную (пока не заворачивайтесь что это), x y координаты точки.

У каждой прямой есть перпендикулярный её вектор.

2.Уравнение прямой с угловым коэффициентом k.

y=kx+l

На графике (который вы скоро увидите ниже) будут представлены определения значений l,k

По числу k можно определить как прямая наклонена, если k>0 то начало прямой слева внизу ,а конец справа вверху, а если k<0, то наоборот.

Из формулы, которую я описал в пункте 1 можно вывести формулу y=kx+l

ax+by+c=0

a/b*x+y+c/b=0 // как вы поняли мы разделили все части уравнения на b

y=-a/b*x-c/b

y=( -a / b ) * x + ( -c / b )


Тогда мы получили наше уравнение y=kx+l, только в другом виде.

Значит переменные k и l можно выразить как

k=-a/b

l=-c/b



3.Уравнение прямой через 2 точки.

w1/w2=g1/g2

y2-y1/y-y1=x2-x1/x-x1

(y2-y1)(x-x1)=(y-y1)(x2-x1) //дальше попробуйте сами раскрыть скобки, сократить на подобные переменные и перенести всё в левую часть

x*(y2-y1)+y*(x1-x2)+y1*x2-x1*y2=0

Таким образом мы вывели формулы для нахождения переменных a,b,c

a=y2-y1

b=x1-x2

c=y1*x2-x1*y2

Теперь можно вывести ещё одну формулу для нахождения угла при пересечении прямой с осью Ox. Решим задачу.

Задача №1
Вводятся a,b,c. Найти угол наклона прямой к оси Ox.

Думаю вы знаете что число pi(дальше буду обозначать его так как в паскале) это 180 градусов. Т.е. 3,14 = 180 градусам. Тогда угол наклона прямой к оси Ox можно найти по формуле (угол наклона прямой к оси Ox обозначим u):

u=arctg(-a/ b *180(градусов)/pi

var a,b,u:real;
begin
readln(a,B)/>;
if b=0 then u:=90
          else u=arctg(-a/B)/>*180/pi;
writeln(u);
end.

Вот как-то так

Задана матрица A размера NxM. Вам необходимо отсортировать числа в каждой строке матрицы в порядке возрастания.

Формат ввода:

В первой строке находятся числа N и M. Далее следует описание самой матрицы - N строк по M чисел в каждой.

Ограничения:

1 <= N, M <= 100
-100 <= A[i,j] <= 100

Формат вывода:

Ответ на задачу - исходная матрица, каждая строка которой отсортирована по возрастанию.

Пример ввода:

3 4
1 2 3 4
4 3 2 1
4 1 3 2

Пример вывода:

1 2 3 4
1 2 3 4
1 2 3 4

Здесь применяется метод быстрой сортировки

var a:array [1..1000] of longint; n,m,i,j:longint;
procedure qsort(l,r:longint);
var i,j,x,p:longint;
begin
i:=l;
j:=r;
x:=a[(i+j)div 2];
repeat
  while a[i]<x do i:=i+1;
  while a[j]>x do j:=j-1;
  if i<=j then begin
            	p:=a[i];
            	a[i]:=a[j];
            	a[j]:=p;
            	i:=i+1;
            	j:=j-1;
   			end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
begin
readln(n,m);
for i:=1 to n do
  begin
   for j:=1 to m do
	read(a[j]);
	qsort(1,m);
   for j:=1 to m do
	write(a[j],' ');
   writeln;
end;
end.

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

Перестановка обозначается буквой P
Формула перестановки из n элементов
P=n!

Итак, допустим нам надо посчитать кол-во перестановок из 3 элементов (допустим n=3). Значит сначала введем эти элементы. Пусть это будут a b c.
Выполним перестановки на бумаге.
a b c (1 перестановка )
a c b (2 перестановка )
b a c (3 перестановка )
b c a (4 перестановка )
c a b (5 перестановка )
c b a (6 перестановка )

Словесный алгоритм будет выглядеть так:

Пока p (нулевое)=0 повторять:

1. Выводим перестановку b[p[i]] .

2. Ищем элемент слева меньший в паре начинаем с конца (это p[j-1]>p[j]) .

3. С конца ищем больший элемент, чем p[j-1]. (это будет p[k] элемент).

4. Меняем местами p[j-1] и p[k].

5. Элементы от p[j] до p[n] меняем в обратном порядке.

Программный алгоритм выглядит так :

var b:string; p:array [0..255] of integer; c,n,i,j,r,q,d,k:longint;
  begin
   readln(B)/>; 
    n:=length(B)/>;
    
    for i:=0 to n do p[i]:=i;
    
    while p[0]=0 do
     Begin
 
       for i:=1 to n do write(b[p[i]]);
         writeln;
       
       j:=n;
        while p[j-1]>p[j] do j:=j-1;
       
       k:=n;
        while p[j-1]>p[k] do k:=k-1;
       
       d:=p[k];
       p[k]:=p[j-1];
       p[j-1]:=d;
       
       for i:=j to (n+j-1)div 2 do 
        begin
        d:=p[i];
        p[i]:=p[n-i+j];
        p[n-i+j]:=d;
        end;
    end;
 end.