Нахождение наибольшей общей подпоследовательности (Longest Common Subsequence)

# -*- coding: utf-8 -*-
"""
    Нахождение наибольшей общей подпоследовательности (Longest Common Subsequence)
    Реализации алгоритма LCS
    https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
"""
s = []
a = 'nematode knowledge'
b = 'empty bottle'
m = len(a)
n = len(b)
l = [[0 for j in xrange(n+1)]for i in xrange(m+1)]
"""
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
"""
for i in reversed(xrange(m)):
    for j in reversed(xrange(n)):
        if a[i] == b[j]:
            l[i][j] = 1 + l[i+1][j+1]
        else:
            l[i][j] = max(l[i+1][j], l[i][j+1])
"""
[[7, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 1, 0],
 [7, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 1, 0],
 [6, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 1, 0],
 [5, 5, 5, 5, 4, 4, 3, 3, 3, 3, 2, 1, 0],
 [5, 5, 5, 5, 4, 4, 3, 3, 3, 3, 2, 1, 0],
 [5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 0],
 [5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 0],
 [5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 0],
 [4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 0],
 [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 0],
 [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 0],
 [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 0],
 [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0],
 [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0],
 [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
"""
i = 0
j = 0
while i < m and j < n:
    if a[i] == b[j]:
        s.append(a[i])
        i += 1
        j += 1
    elif l[i+1][j] >= l[i][j+1]:
        i += 1
    else:
        j += 1
 
"""
    Наибольшая общая подпоследовательность
    l[0][0] = 7
 
    Последовательность
    s = ['e', 'm', 't', ' ', 'o', 'l', 'e']
"""

Кривая Коха (HTML5 Canvas)

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

Обновите браузер

    var canvas = document.getElementById("myCanvas");
    var ctx = canvas.getContext("2d");

    var imgData = ctx.createImageData(canvas.width, canvas.width);

    function index(y, x, c) {
        var w = canvas.width;
        return (y * w + x) * 4 + (c || 0);
    }

    function draw(w, h, sx, sy) {
        var i;
        var j;
        var t;
        var mx = 0;
        var my = 0;
        var r = 500;

        var x;
        var y;

        for (i = 0; i < 50000; i++) {
            t = mx;
            if (Math.random() <= 1/2) {
                mx = 1/2 * mx + 1/(2*Math.sqrt(3)) * my;
                my = 1/(2*Math.sqrt(3)) * t - 1/2 * my;
            } else {
                mx = 1/2 * mx -1/(2*Math.sqrt(3)) * my + 1/2;
                my = -1/(2*Math.sqrt(3)) * t - 1/2 * my + 1/(2*Math.sqrt(3));
            }

            x = sx + Math.round(r * mx);
            y = sy - Math.round(r * my);

            imgData.data[index(y, x, 0 )] = 255;
            imgData.data[index(y, x, 3 )] = 255;
        }


        ctx.putImageData(imgData, x, y);
    }

    draw(canvas.width, canvas.width, 0, 150);

Связные списки в С++. Базовые операции.

Интерфейс обработки списков.

---

Для распределения памяти под узлы списка и ее освобождения объявляются собственные функции. Функция construct применена для удобства реализации.

// list.h

typedef int Item;
struct node
{
  Item item;
  node * next;
};
typedef node *link;
typedef link *Node;

void construct(int);
link newNode(int);
void deleteNode(Node);
void insert(link, link);
link remove(link);
Node next(Node);
Item item(Node);

Реализация интерфейса обработки списков

---

Эта программа создает свободный список, который инициализируется в соответствии с максимальным количеством узлов, используемых программой. Все узлы взаимосвязаны. Когда клиентская программа удаляет узел, он привязывается к свободному списку.

#include <iostream>
#include <stdlib.h>
#include "list.h"

using namespace std;

link freelist;

void construct(int N)
{
  freelist = new node[N+1];
  for (int i = 0; i < N; i++)
  {
    freelist[i].next = &freelist[i+1];
  }
  freelist[N].next = 0;
}

link newNode(int i)
{
  link x = remove(freelist);
  x->item = i;
  x->next = x;
  return x;
}

void deleteNode(link x)
{
  insert(freelist, x);
}

void insert(link x, link t)
{
  t->next = x->next;
  x->next = t;
}

link remove(link x)
{
  link t = x->next;
  x->next = t->next;
  return t;
}

link next(link x)
{
  return x->next;
}

Item item(link x)
{
  return x->item;
}

void print_list(link x)
{
  link head = x, t = x;
  cout << "---list---" << endl;
  do
  {
    cout << t->item << endl;
    t = t->next;
  } while(t != head);
  cout << "---end-list---" << endl;
}

link reverse(link x)
{
  link t, y = x, r = 0;
  while (y != 0)
  {
    t = y->next;
    y->next = r;
    r = y;
    y = t;
  }

  return r;
}

int main(int argc, char *argv[])
{
  int N = 10;
  link x, t;

  construct(N);
  x = newNode(1);

  for (int i = 2; i <= N; i++ )
  {
    t = newNode(i);
    insert(x, t);
  }

  print_list(x);

  print_list(reverse(x));

  return 0;
}

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

Связные списки в С++

Связные списки являются примитивными конструкциями в некоторых языка программирования, но не в С++. Указатели для ссылок и структуры для узлов описывается следующим образом:

struct node
{
  Item item;
  node *next;
};
typedef node *link;

Связный список - это набор элементов, причем каждый из них является частью узла (node), который также содержит ссылку (link) на узел.

Узлы определяются ссылками на узлы, поэтому связные списки иногда называют самоссылочными (self-referent) структурами. Более того, хотя узел обычно ссылается на другой узел, возможна ссылка на самого себя, поэтому связные списки могут представлять собой циклические (cyclic) структуры.

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

• Это пустая (null) ссылка, не указывающая на какой-либо узел.
• Ссылка указывает на фиктивный узел (dummy node), который не содержит элементов.
• Ссылка указывает на первый узел, что делает список циклическим.

В качестве примера рассмотрим следующую программу решение задачи Иосифа (Флавия):

---

Для представления людей, расставленных в круг, построим циклический связный список, где каждый элемент (человек) содержит ссылку на соседний элемент против хода часовой стрелки. Целое число i представляет  i-того человека в круге. После создания циклического списка из одного узла вставляются узлы 2 до N. В результате образуется окружность с узлами от 1 до N. При этом переменная x указывает на N. Затем пропускаем M-1 узлов, начиная с 1-го, и устанавливаем значение ссылки (M-1)-го узла таким образом, чтобы пропустить М-ый узел. Продолжаем эту операцию, пока не останется один узел.

// Задача Иосифа (Циклические списки)


#include 
#include 

using namespace std;

struct node
{
  int item;
  node *next;

  node(int x, node *t)
  {
    item = x;
    next = t;
  }
};

typedef node *link;

int main(int argc, char *argv[])
{
  int i;
  int N = atoi(argv[1]);
  int M = atoi(argv[2]);

  link t = new node(1, 0);
  t->next = t;

  link x = t;

  for (i = 2; i <= N; i++)
  {
    x = (x->next = new node(i, t));
  }

  while(x != x->next)
  {
    for (i = 1; i < M; i++)
    {
      x = x->next;
    }

    x->next = x->next->next;
  }

  return 0;
}