Перейти к содержимому


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

37 публикаций создано Санек (учитываются публикации только с 29-марта 23)



#273 Компоненты сильной связности

Отправлено от Санек в 20 ноября 2012 - 17:49 in Графы

Компонентой сильной связности (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 перед поиском к.с.с.



#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],' ');



#266 Двоичная куча

Отправлено от Санек в 16 ноября 2012 - 16:16 in Структуры данных

"Всплытие" и "затапливание" элементов кучи на паскале.

Допустим у нас n элементов и m запрос на изменение этих элементов. Запросы содержат два числа: pos и value, т.е. надо увеличить a[pos] на value. Но т.к. мы изменяем значение элемента, то вероятнее всего мы можем нарушить основное свойство кучи, т.е у нас может поток должен быть больше предка. Поэтому мы подымаем измененный элемент по кучи вверх, пока его предок не будет больше его или пока мы не доставим измененный элемент в вершину кучи.

Есть два способа сделать всплытие: через цикл while и рекурсией. Рассмотрим оба

 
procedure shift_up(pos:longint);
begin
  while (pos<>1) and (a[pos div 2] < a[pos]) do //пока не дошли до предка и потомок больше предка
    begin
      x:=a[pos div 2]; //меняем их местами
      a[pos div 2]:=a[pos];
      a[pos]:=x;
      pos:=pos div 2; //теперь мы в предке вершины pos
    end;
end;


 
procedure shift_up(pos:longint);
var x:longint;
begin
  if pos=1 then exit; //если мы в самом вверху, то вылетаем
  if a[pos div 2] < a[pos] //если потомок больше предка
    then //то меняем их местами
      begin 
        x:=a[pos div 2];
        a[pos div 2]:=a[pos];
        a[pos]:=x;
        shift_up(pos div 2); //подымаем предка наверх
      end;
end;


Рассмотрим затапливание элемента

У нас есть то же самое, что я описал выше, только теперь надо уменьшить a[pos] на value. Тогда опять нарушится условие кучи, т.к. предок получится меньше одного или двух своих потомков. Поэтому нам надо опускать наш a[pos] до тех пор, пока мы не придем в последний элемент или наш предок не станет больше потомка.

Опять же два способа: рекурсия и цикл while

 
procedure shift_down(pos:longint);
var pos2,x:longint;
begin
  while (2*pos<=n) do //пока мы не пришли в последний элемент
    begin
      pos2:=pos; 
      if (a[2*pos]>a[pos2]) //если левый потомок больше предка
        then pos2:=2*pos; //номеру предка присваем номер потомка
      if (2*pos+1<=n) and (a[2*pos+1]>a[pos2]) //если правый потомок есть и он больше предка
        then pos2:=2*pos+1; //номеру предка присваем номер потомка
      if (pos=pos2) then break; //если предок это потомок тогда вылетаем
      x:=a[pos]; //меняем местами предка и потомка
      a[pos]:=a[pos2];
      a[pos2]:=x;
      pos:=pos2; //номеру потомка присваем номер предка
    end;
end;


 
procedure shift_down(pos:longint);
var pos2:longint;
begin
  pos2:=pos; 
  if pos*2>n  then exit; //если пришли в последний элемент то вылетаем
  if a[pos*2]>a[pos2] //если левый потомок больше предка
    then pos2:=pos*2; //номеру предка присваем номер потомка
  if (pos*2+1<=n) and (a[pos*2+1]>a[pos2]) //если правый потомок есть и он больше предка 
    then pos2:=pos*2+1; //номеру предка присваем номер потомка
  if pos=pos2 then exit; //если предок это потомок тогда вылетаем
  x:=a[pos]; //меняем местами предка и потомка
  a[pos]:=a[pos2];
  a[pos2]:=x;
  shift_down(pos2);//топим потомка
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.




#264 Очередь

Отправлено от Санек в 14 ноября 2012 - 17:29 in Структуры данных

Просмотр сообщенияAndrew (14 ноября 2012 - 15:42) писал:

Киньте эту тему в структуры данных. Очередь используется не только для графов


Сделано



#261 Дерево отрезков

Отправлено от Санек в 14 ноября 2012 - 12:45 in Структуры данных

Дерево отрезков — это структура данных, которая позволяет эффективно (т.е. скорость алгоритма (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) целых числах A1, ..., AN. Структура должна поддерживать следующие операции.



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

2) MODIFY(pos,value) Значение Apos увеличивается на 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;



#243 Командный чемпионат г. Минска 2012 г., отборочный этап

Отправлено от Санек в 24 сентября 2012 - 12:15 in Флудилка

Результаты наших команд в отборочном туре командного чемпионата г.Минска 23.09.2012:

2 место: Витебск #11_1 ( Петрашко Татьяна, Лапенков Александр, Марчукевич Евгений ) 8 решенных задач, время 237 минут(ы)

7 место: Витебск #1 ( Медяников Илья, Яковлев Илья, Кускова Барбара ) 8 решенных задач, время 433 минут(ы)

10 место: Три области ( Петрушенко Ирина, Шах Егор, Русак Максим) 8 решенных задач, время 526 минут(ы)

11 место: Витебск #2 ( Пискевич Януш, Краснов Александр, Кодосов Никита ) 8 решенных задач, время 749 минут(ы)

19 место: Витебск #3 (Бородавко Евгений, Петуховский Артур, Ульянов Петр) 7 решенных задач, время 854 минут(ы)

27 место: Витебск #4 (Довгаль Алексей, Краснобаев Андрей ) 5 решенных задач, время 592 минут(ы)

28 место: Витебск #5 (Вычев Андрей, Родик Алексей ) 4 решенные задачи, время 273 минут(ы)

Кому интересно самим посмотреть результаты, прикрепляю рейтинг

Прикрепленные файлы




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

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

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



#86 Книга жалоб и предложений

Отправлено от Санек в 16 января 2012 - 06:33 in Флудилка

Просмотр сообщенияLVP (15 января 2012 - 16:55) писал:

всех кто не представятся настоящими именами, предлагаю удалить из форума


Я человек 20 удалил, но они опять зарегались.



#85 Книга жалоб и предложений

Отправлено от Санек в 16 января 2012 - 06:32 in Флудилка

Просмотр сообщенияЯ. Илья (15 января 2012 - 12:14) писал:

Предлагаю запретить незарегистрированным пользователям писать сообщения, а то появятся такие темы, как delete(в расписании)


Они были зарегистрированы, потом удалены за спам



#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.



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



#54 Мячик на лестнице

Отправлено от Санек в 23 декабря 2011 - 19:18 in Динамическое программирование

На вершине лесенки, состоящей из 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.



#53 Максимальная подпоследовательность

Отправлено от Санек в 23 декабря 2011 - 19:10 in Динамическое программирование

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

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

В первой строке вводится 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.



#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.



#51 НОД и НОК

Отправлено от Санек в 23 декабря 2011 - 14:14 in Рекурсия

Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей.

Пример: для чисел 70 и 105 наибольший общий делитель равен 35.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.

Наиме́ньшее о́бщее кра́тное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n.

Пример: НОК(16, 20) = 80.

var a,b :longint;
function NOD(x,y:longint):longint; //Функция поиска НОДа двух чисел
  begin
   if x<>0 then NOD:=NOD(y mod x,x)
	else NOD:=y;
  end;
function NOK(x,y:longint):longint; //Функция поиска НОКа двух чисел
  begin
   NOK:=( x div NOD(x,y) ) * y;
  end;
begin
  readln(a, b );
  writeln( 'НОД этих чисел = ', NOD(a,b ) );
  writeln( 'НОК этих чисел = ', NOK(a,b ) );
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.



#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.



#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.



#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.



#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.



#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.



#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.



#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.