Публикации Санек

#4 Уравнение прямой

Отправлено от Санек в 21 декабря 2011 - 18:02 in Геометрия

Чтобы прочитать(по ссылкам ниже) и понять эту тему повторите (желательно ВЫУЧИТЕ) что такое синус 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.

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

#52 Точка в круге

Отправлено от Санек в 23 декабря 2011 - 14:29 in Геометрия

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

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

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.

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

Отправлено от Санек в 19 ноября 2012 - 18:27 in Графы

Дан граф, состоящий из 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],' ');

#60 Типы данных char и string

Отправлено от Санек в 25 декабря 2011 - 18:56 in Строки

Типы данных char и string

char - символьный тип

string - строковый тип

Символьный тип

Значением переменных символьного типа char является один символ. Каждому символу соответствует код символа - целое число в диапазоне от 0 до 255. Значит, символьный тип является порядковым. В таких языках программирования как C, Java тип char относят к целым типам, что разумно, т.к. в памяти компьютера нет символов - есть только их числовые коды. Значит, все действия по обработке символов сводятся к действиям над целыми числами, расположенными строго по порядку.

Над данными символьного типа определены операции отношения: =, <>, <, >, <=, >=.

Для данных символьного типа определены стандартные функции:

chr(x) - возвращает значение символа его коду;
ord(ch) - возвращает код заданного символа ch;
pred(ch) - возвращает предыдущий символ;
succ(ch) - возвращает следующий символ;
upcase(ch) - преобразует строчную букву в заглавную.

Например

ord('A') = 65
chr(128) = 'Б'
pred('Б') = 'А'
succ('Г') = 'Д'
upcase('n') = 'N'

Строковый тип

Строка - это последовательность символов. Максимальное количество символов в строке может изменяться от 1 до 255. Переменную строкового типа можно определить через описание в разделе описания типов var или непосредственно в разделе объявления переменных.

var идентификатор: string;

Строка в Паскале трактуется как массив символов. Для строки из n символов в памяти компьютера отводится n+1 байт; n байт - для хранения символов строки, а один доп. байт - для значения текущей длины строки. Этот доп. байт имеет номер 0, соответственно первый символ строки имеет номер 1, второй - номер 2 и т.д.

К любому символу строки можно обратиться как к элементу массива. Но в отличии от массива, строка считывается и выводится просто

readln(s);
writeln(s);

где s - строка

Задача

Дана строка s. Вывести её в перевернутом виде и вывести все слова этой строки по отдельности

Решение

var s:string;
	i:longint;
begin
readln(s);
for i:=length(s) downto 1 do
  write(s[i]);
writeln;
for i:=1 to length(s) do
  if (s[i]=' ') and (s[i+1]<>' ') then writeln
   else write(s[i]);
end.

Думаю здесь всё предельно ясно.

#27 Сумма элементов одномерного массива

Отправлено от Санек в 22 декабря 2011 - 10:24 in Одномерные массивы

Вводится число n. Далее следует n чисел. Найти сумму всех чисел.

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

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

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

s - сумма всех чисел

Ввод

10

1 10 2 3 1 3 5 8 4 2

Вывод

39

Решение

var a:array [1..1000] of longint;
	n,i,s:longint;
begin
readln(n);  //ввод n - числа элементов в массиве
for i:=1 to n do //ввод чисел массива
  read(a[i]);
for i:=1 to n do //подсчет суммы всех элементов
  s:=s+a[i];
writeln(s); //вывод суммы
end.

#26 Сумма элементов двумерного массива

Отправлено от Санек в 22 декабря 2011 - 10:15 in Двумерные массивы

Дана матрица 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.

#37 Сочетание

Отправлено от Санек в 22 декабря 2011 - 12:40 in Комбинаторика

Сочетание из 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.

#23 Сортировка пузырьком

Отправлено от Санек в 22 декабря 2011 - 09:14 in Сортировка

Сортиро́вка пузырько́м (англ. 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.

#22 Сортировка пузырьком

Отправлено от Санек в 22 декабря 2011 - 09:13 in Сортировка и перебор

Сортиро́вка пузырько́м (англ. 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.

#24 Сортировка матрицы n*m

Отправлено от Санек в 22 декабря 2011 - 09:16 in Сортировка и перебор

Задана матрица 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.

#265 Совершенные числа

Отправлено от Санек в 15 ноября 2012 - 15:17 in Целочисленная арифметика

Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. Требуется найти все совершенные числа от 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.

#18 Решето Эратосфена

Отправлено от Санек в 22 декабря 2011 - 08:59 in Целочисленная арифметика

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа 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.

#38 Размещение с повторением

Отправлено от Санек в 22 декабря 2011 - 12:41 in Комбинаторика

Размещение из 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.

#95 Размещение в подпрограмме

Отправлено от Санек в 17 января 2012 - 18:53 in Комбинаторика

Если сам писал, то молодец конечно. Кстати что за сайт?

#36 Размещение

Отправлено от Санек в 22 декабря 2011 - 12:38 in Комбинаторика

Размещение из 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.

#13 Размещение

Отправлено от Санек в 22 декабря 2011 - 08:27 in Комбинаторика

Размещение из 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.

#30 Различные элементы

Отправлено от Санек в 22 декабря 2011 - 10:50 in Одномерные массивы

Вводятся число 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.

#21 Простое число

Отправлено от Санек в 22 декабря 2011 - 09:06 in Целочисленная арифметика

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

Последовательность простых чисел начинается так:
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.

#6 Поиск в ширину

Отправлено от Санек в 21 декабря 2011 - 18:11 in Графы

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

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

В стране Б есть 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.

#7 Поиск в глубину

Отправлено от Санек в 21 декабря 2011 - 18:18 in Графы

Поиск в глубину, применяется для

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

*построения множества истоков и стоков (как истоков на транспонированном графе)

*построения сильносвязных компонент (ССК) графа ССК - это множество вершин, каждая из которых достижима из всех вершин ССК

Пример задачи на поиск в глубину.

Грядки

Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:
из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.

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

В первой строке входного файла INPUT.TXT находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. (1 <= N, M <= 200)

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

В выходной файл OUTPUT.TXT выведите количество грядок на садовом участке.

Примеры

INPUT.TXT

5 10

##......#.

.#..#...#.

.###....#.

..##....#.

........#.

OUTPUT.TXT

3

Основной код

var g:array [1..200,1..200] of char; k,i,j,n,m:integer;
procedure dfs(x,y:longint);
begin
g[x,y]:='o';
if (y<m )and(g[x,y+1]='#') then dfs(x,y+1);
if (y>1 )and(g[x,y-1]='#') then dfs(x,y-1);
if (x<n )and(g[x+1,y]='#') then dfs(x+1,y);
if (x>1 )and(g[x-1,y]='#') then dfs(x-1,y);
end;
begin
readln(n,m);
k:=0;
for i:=1 to n do begin
   				for j:=1 to m do
   				read(g[i,j]);
  readln;
end;
for i:=1 to n do
  for j:=1 to m do begin
                	if (g[i,j]='#')
 					then begin
       					k:=k+1;
       					dfs(i,j);
                      	end;
                	end;
writeln(k);
end.

#43 Площадь треугольника по 3 вершинам

Отправлено от Санек в 22 декабря 2011 - 16:16 in Геометрия

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

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

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.

#35 Перестановка с повторением

Отправлено от Санек в 22 декабря 2011 - 12:37 in Комбинаторика

Перестановки из 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.

#34 Перестановка

Отправлено от Санек в 22 декабря 2011 - 12:35 in Комбинаторика

Перестановка из 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.

#5 Перестановка

Отправлено от Санек в 21 декабря 2011 - 18:08 in Комбинаторика

Перестановка из 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.

#25 Пересечение окружностей

Отправлено от Санек в 22 декабря 2011 - 09:33 in Геометрия

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

Задан набор из 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.