World-code - главная.

Меню сайта
Главная
Компиляторы

Если хотите почитайте
IT Happens

________________________________ Перестановки

Процедура для генерации всех перестановок из N элементов в лексиграфическом
(слварном порядке):

void gen(int n)
{
	vector <int> a;
	for (int i=0;i<n;i++)
		a.pushback(i);
	do
	{
		for (int i=0;i<n;i++)
			printf("%d",a[i]);
		puts("");
	} while (next_permutation(a.begin(),a.end()));
}

Функция для нахождения номера заданной перестановки в лексиграйическом порядке

int a[20],n;
bool used[20];

long long num()
{
	vector <long long> fact;
	fact.push_back(1);
	for (int i=0;i<=n;i++)
		fact.push_back(fact[i-1]*i);
	long long res=0;
	for (int i=0;i<n;i++)
	{
		int t=0;
		used[a[i]]=true;
		for (int j=a[i];j>=1;j--)
			if (!used[j]) t++;
		res+=t*fact[n-i-1];
	}
	return res+1;
}

Процедура для генерации перестановки по её номеру в лексиграйическом порядке

long long n,k;
int a[20];
bool used[20];

void gen()
{
	--k;
	vector <long long> fact;
	fact.push_back(1);
	for (int i=1;i<=n;i++)
		fact.push_back(fact[i-1]*i);
	for (int i=0;i<n;i++)
	{
		long long cur=0;
		int num=-1;
		for (int j=0;j<n;j++)
			if (!used[j])
				if (cur+fact[n-i-1]>k)
				{
					num=j;
					break;
				} 
				else
					cur+=fact[n-i-1];
		a[i]=num;
		used[num]=true;
		k-=cur;
	}
	for (int i=0;i<n;i++)
		cout << a[i]+1 << " ";
}

_____________________________________ Графы

Алгоритм Дейкстры

#include <iostream>
#include <set>
#include <vector>
using namespace std;
 
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
 
const int MAX = 1001;
const int MAXINT = 1000000000;
 
int n;
vvii G(MAX);
vi D(MAX, MAXINT);
 
void Dijkstra(int s)
{
    set<ii> Q;
    D[s] = 0;
    Q.insert(ii(0,s));
 
    while(!Q.empty())
    {
        ii top = *Q.begin();
        Q.erase(Q.begin());
        int v = top.second;
        int d = top.first;
 
        for (vii::const_iterator it = G[v].begin(); it != G[v].end(); it++)
        {
            int v2 = it->first;
            int cost = it->second;
            if (D[v2] > D[v] + cost)
            {
                if (D[v2] != 1000000000)
                {
                    Q.erase(Q.find(ii(D[v2], v2)));
                }
                D[v2] = D[v] + cost;
                Q.insert(ii(D[v2], v2));
            }
        }
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
 
    int m, s, t = 0;
    scanf("%d %d %d %d", &n, &m, &s, &t);
 
    for (int i = 0; i < m; i++)
    {
        int a, b, w = 0;
        scanf("%d %d %d", &a, &b, &w);
        G[a - 1].push_back(ii(b - 1, w));
        G[b - 1].push_back(ii(a - 1, w));
    }
 
    Dijkstra(s - 1);
 
    printf("%d\n", D[t - 1]);
 
    return 0;
}

Алгоритм Форда-Беллмана

for ( int i=0;i<n;i++)
	for (int j=0;j<k;j++)
		if (d[e[j].to]>d[e[j].from]>d[e[j].from]+e[j].l)
		{
			d[e[j].to]=d[e[j].from]+e[j].l;
			p[e[j].to]=e[j].from;
		}

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

for (int t=0;t<n;t++)
	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++)
			d[i][j]=min(d[i][j],d[i][t]+d[t][j]);

Алгоритм поиска в глубину (DFS)

#include <iostream>
#include <stdio.h>
#include <fstream>
#include <vector>
using namespace std;


int t,n,v1,v2;
bool used[110],a[110][110];
vector <int> k;


int dfs(int v)
{
    used[v]=true;
    k.push_back(v);
    if (v==v2)return 1;
    int u;
    for (u=1;u<=n;u++)
        if (!used[u] && a[v][u])
            if (dfs(u)==1)
                return 1;
    return 0;
}

int main()
{
    fstream in("input.txt",ios_base::in);
    fstream out("output.txt",ios_base::out);
    in >> n >> v1 >> v2;
    for (int i=1;i<=n;i++)
    {
        used[i]=false;
        for (int j=1;j<=n;j++)
        {
            in >> a[i][j];
        }
    }
    if (dfs(v1)==0)
       out << -1;
    else
    {
        out << k.size()-1 << "\n";
        for (int i=0;i<=k.size()-1;i++)
            out << k[i] << " ";
    }
    return 0;
}

Процедура для генерации всех перестановок из N элементов в лексиграфическом (слварном порядке):

Функция для нахождения номера заданной перестановки в лексиграйическом порядке

Процедура для генерации перестановки по её номеру в лексиграйическом порядке

Алгоритм Дейкстры

Алгоритм Форда-Беллмана

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

Алгоритм поиска в глубину (DFS)

Процедура для генерации всех перестановок из N элементов в лексиграфическом
(слварном порядке):