Перебор всех перестановок n символов с использованием метода декомпозиции

Пример на странице 15

Перебор всех перестановок n символов  с использованием метода декомпозиции.

#include <stdio.h>

#include <string.h>

#include <conio.h>

void swp( char *s, int i, int j)        //перестановка символов

{

char t=s[i]; s[i]=s[j]; s[j]=t;

}

void permute (char *s, int n, int number)

{

//S-строка символов, number-длина строки

char temp; int i, j;

if (n>1)

{

permute(s, n-1, number);   //перестановка первых n-1 символов

for(i=n-1; i>=1; i--)

{

swp(s,n-1,i-1);         //меняем местами n-й и i-й символы

per-mute(s, n-1, number); //генерируем перестановку первых n-1

//символов

swp(s,n-1,i-1) ;        //снова меняем местами

}

}

else

{

for(j=0 ; j<number; j++ )

printf("%c", s[j]) ;

printf("\n") ;

}

}

main()

{

char data[]="123" ;

permute(data, strlen(data),strlen(data) ) ; getch();

}

Пример на странице 16

Вывод всех перестановок n символов в антилексикографическом порядке.

#include<stdio.h>

#include<conio.h>

int N;

int s[]={1,2,3};

void swp(int i,int j)

{

int t=s[i]; s[i]=s[j]; s[j]=t;

}

void reverse(int m)      //обращение массива S

{

int i;

for (i=0;i<m/2;i++) swp(i,m-1-i);

}

void antylex(int m)      //генерирует перестановки S[0],..., S[m-1]

//в антилексикографическом порядке, оставляя

//на месте S[m],..., S[N-1]

{

int i,j;

if (m==1)

{

printf("\n");

for (j=0; j<N; j++) printf(" %d",s[j]);

}

for (i=0; i<m;i++)

{

antylex(m-1);

if (i<m-1) swp (i, m-1);

reverse(m-1);

}

}

main()

{

clrscr();

N = sizeof(s)/sizeof(s[0]);

antylex(N);

getch();

}

Программа на странице 19

Вывод на экран кривой Гилберта заданного порядка.

#include <stdio.h>

#include <math.h>

#include <conio.h>

#include <graphics.h>

void A(int n,int h);

void B(int n,int h);

void C(int n,int h);

void D(int n,int h);

void A(int n, int h)

{

if(n>0)

{

D(n-1,h); linerel(-h,0);

A(n-1,h); linerel(0,h);

A(n-1,h); linerel(h,0);

B(n-1,h);

}

}

void B(int n, int h)

{

if(n>0)

{

C(n-1,h); linerel(0,-h);

B(n-1,h); linerel(h,0);

B(n-1,h); linerel(0,h);

A(n-1,h);

}

}

void C(int n, int h)

{

if(n>0)

{

B(n-1,h); linerel(h,0);

C(n-1,h); linerel(0,-h);

C(n-1,h); linerel(-h,0);

D(n-1,h);

}

}

void D(int n, int h)

{

if(n>0)

{

A(n-1,h); linerel(0,h);

D(n-1,h); linerel(-h,0);

D(n-1,h); linerel(0,-h);

C(n-1,h);

}

}

main()

{

int gdriver = VGA, gmode = VGAHI ;

int N = 5;

int h = 256/(1<<N);

initgraph(&gdriver,&gmode,"C:\\Temp\\bc31\\Bgi");

moveto(400-h,100+h);

A(N,h);

getch() ;

closegraph() ;

}

Программа на странице 22

Синтаксический анализ и вычисление методом рекурсивного спуска

#include <stdio.h>

#include <ctype.h>

#include <conio.h>

#include <string.h>

enum token_value  {NUMBER,ENTER,PLUS='+',MINUS='-',LP='(',RP=')'};

token_value cur_tok;

int number_value;

int no_of_errors = 0;

int error(char *s)

{

no_of_errors++;

printf("-error: %s\n",s); return 1;

}

int term();

token_value get_token()

{

char ch;

do

{

if ((ch=getchar())==EOF) return cur_tok=ENTER;

}  while (ch!='\n'&&isspace(ch));

switch (ch)

{

case ';': case '\n': return cur_tok = ENTER;

case '+': case '-': case '(': case ')': return cur_tok = ch;

case '0': case '1': case '2': case '3': case '4':

case '5': case '6': case '7': case '8': case '9':

ungetc(ch,stdin);

scanf("%d",&number_value);

return cur_tok = NUMBER;

}

}

int expr()

{

int result=term();

for(;;)

switch (cur_tok)

{

case '+': get_token(); result+=term(); break;

case '-': get_token(); result-=term(); break;

default: return result;

}

}

int term()

{

int e;

switch (cur_tok)

{

case NUMBER: get_token(); return number_value;

case '-': get_token(); return -term();

case '(': get_token(); e=expr(); if (cur_tok!=')')

return error("нет правой скобки");

get_token();

return e;

case ENTER: return 1;

default: return error ("это не терм");

}

}

main()

{

clrscr();

get_token();

printf("=%d ",expr());

getch() ;

}

Программа на странице 24

Рассмотрим задачу нахождения вершин графа, допускающих пути в заданную вершину SÎV. Задача решается с помощью раскраски вершин графа

Шаг 1.  Предположить, что все вершины графа не раскрашены, установив c[v]=0 для всех vÎV. Массив c[|V|] состоит из «цветов» вершин графа. Если c[v]=1, то вершина раскрашена. Установить c[s]=1.

Шаг 2.  Вызывать рекурсивную подпрограмму раскраски вершин rec(s). Эта подпрограмма определяется с помощью внешнего массива a[u][v], состоящего из элементов матрицы смежности:

#include <stdio.h>

#include <conio.h>

// нахождение компоненты связности

int c[6];               // раскраска

int a[6][6]={ 0,1,0,0,0,1,     // матрица смежности

1,0,0,0,0,1,

0,0,0,1,1,0,

0,0,1,0,1,0,

0,0,0,1,0,0,

1,1,0,0,0,0 };

void rec(int s,int n)

{

int i;

for (i=0; i<n;i++)

if ( (a[s][i]||a[i][s]) && (c[i]==0) )

{ c[i]=1; rec(i,n); }

}

int main()

{

int i;

clrscr();

for (i=0; i<sizeof(c)/sizeof(c[0]);i++) c[i]=0;

c[0]=1; // начальная вершина

rec(0,sizeof(c)/sizeof(c[0]));

for (i=0; i<sizeof(c)/sizeof(c[0]);i++)

if(c[i])

printf("\n вершина %d принадлежит компоненте связности вершины 0", i);

getch();

}

Программа на странице 25

Поиск возможных путей из одной вершины графа в другие.

#include <stdio.h>

#include <conio.h>

//поиск путей из вершины s в вершины графа

int n;

int c[6];                  // номера предшествующих вершин

int a[6][6]={ 0,1,0,0,0,1, // матрица смежности

1,0,0,0,0,1,

0,0,0,1,1,0,

0,0,1,0,1,0,

0,0,0,1,0,0,

1,1,0,0,1,0 };

void rec(int p)

{

int i;

for (i=0; i<n;i++)

if ( (a[p][i]||a[i][p]) && (c[i]<0) )

{

c[i]=p; rec(i);

}

}

void path(int s,int v)

{

if(v==s) { printf(" %d ",s); return;}

if (c[v]>=0)

{

path(s,c[v]); printf(" %d ",v);

}

}

void main()

{

int i;

int s=4;

n=sizeof(c)/sizeof(c[0]);

clrscr();

for (i=0; i<n;i++) c[i]=-1;

c[s]=s;

rec(s);

for (i=0; i<n;i++)

{

printf("\n путь из %d в %d состоит из вершин", s,i);

path(s,i);

}

getch();

}

Программа на странице 29

Алгоритм Дейкстры поиска кратчайшего пути.

Пусть задан простой неориентированный граф G = (V, E), как конечное множество вершин V и множество E неупорядоченных пар {v_i, v_j} – ребер. Каждому ребру предписано действительное число a[i][j] > 0, которое называется длиной этого ребра. Требуется найти кратчайший путь между заданными вершинами s и q, то есть такую последовательность вершин u₁,u₂,…,u_n, что u₁=s, u_n=q, {u_i, u_i+1}ÎE для всех 1 £ i £ n-1, и сумма длин ребер {u_i, u_i+1} минимальна.

/* Алгоритм Дейкстры. Программу написал Качалов А.А. */

#include <iostream.h>

#include <conio.h>

#define VERTEXES 6 //Число вершин в графе

int v;

void main()

{

clrscr();

int infinity=1000;                     // Бесконечность

int p= VERTEXES;                       // Количество вершин в графе

int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3,  // Матрица смежности графа

1,0,5,0,0,1,

0,5,0,5,20,1,

0,0,5,0,3,2,

1,0,20,3,0,10,

3,1,1,2,10,0  };

// Будем искать путь из вершины s в вершину g

int s;                      // Номер исходной вершины

int g;                      // Номер конечной вершины

cout<<"Введите s: ";        // Номер может изменяться от 0 до p-1

cin>>s;

cout<<"Введите g: ";

cin>>g;

int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,

// x[i]=0 - еще не найден кратчайший путь в i-ю вершину,

// x[i]=1 - кратчайший путь в i-ю вершину уже найден

int t[VERTEXES];  //t[i] - длина кратчайшего пути от вершины s в i

int h[VERTEXES];  //h[i] - вершина, предшествующая i-й вершине

// на кратчайшем пути

// Инициализируем начальные значения массивов

int u;              // Счетчик вершин

for (u=0;u<p;u++)

{

t[u]=infinity; //Сначала все кратчайшие пути из s в i

//равны бесконечности

x[u]=0;        // и нет кратчайшего пути ни для одной вершины

}

h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует

t[s]=0; // Кратчайший путь из s в s равен 0

x[s]=1; // Для вершины s найден кратчайший путь

v=s;    // Делаем s текущей вершиной

while(1)

{

// Перебираем все вершины, смежные v, и ищем для них кратчайший путь

for(u=0;u<p;u++)

{

if(a[v][u]==0)continue; // Вершины u и v несмежные

if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не

//найден кратчайший