Diferente pentru coduri-gray intre reviziile #18 si #26

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Coduri Gray
(Categoria _Matematica_, autor _Cosmin Negruseri_)
== include(page="template/implica-te/scrie-articole" user_id="alecman") ==
 
(Categoria _Matematica_, Autor _Cosmin Negruseri_)
(toc){width: 20em}*{text-align:center} *Cuprins*
* 'Introducere':coduri-gray#introducere
* 'Problema 3: Matrix':coduri-gray#matrix
* 'Problema 4: Divizori':coduri-gray#divizori
* 'Problema 5: Sortnet':coduri-gray#sortnet
* 'Bibliografie':coduri-gray#biblio
h2(#introducere). Introducere
In continuare vom nota acest cod cu $G{~n~}$. Putem da astfel o noua metoda de constructie. Fie $G'{~n-1~}$ sirul $G{~n-1~}$ inversat, atunci obtinem $G{~n~}$ daca punem cate un bit $0$ in fata fiecarui numar din $G{~n-1~}$, urmat de numerele din $G'{~n-1~}$, carora le adaugam cate un $1$ ca bit semnificativ ( pe scurt $G{~n~} = 0G{~n-1~},1G'{~n-1~} (1)$). Se poate observa ca acest cod este circular, diferenta intre ultimul si primul numar fiind de exact un bit. De asemenea, orice cod de ordin $n$ il contine pe cel de $n-1$ ca prefix, deci am putea nota prin $G{~∞~}$ sirul numerelor naturale in care orice doua numere consecutive difera in reprezentarea binara prin exact un bit si pentru care sirul primelor $2^n^$ elemente coincide cu $G{~n~}$ (∀ $n$ ∈ _**N**_).
Fie $g(x)$ al $x$-lea numar din $G{~∞~}$ si $g-1(y)$ pozitia la care apare numarul $y$ in sirul $G{~∞~}$. Se pune problema calcularii eficiente a celor doua functii. Se poate demonstra prin inductie ca daca avem un numar $x$ cu reprezentarea binara $(...a{~2~}a{~1~}a{~0~}){~2~}$ si codul lui Gray $(...b{~2~}b{~1~}b{~0~}){~2~}$, atunci avem $b{~i~} = a{~i~} ^∧^ a{~i+1~}$ (2). De exemplu, pentru numarul $6$ cu reprezentarea binara $110$, atunci $g(110) = 101$. De aici se deduce ca $g(i) = x ^∧^ (x / 2)$. Din (2) obtinem ca $b{~i~} ^∧^ b{~i+1~} ^∧^ b{~i+2~} ^∧^ ... = (a{~i~} ^∧^ a{~i+1~}) ^∧^ (a{~i+1~} ^∧^ a{~i+2~}) ^∧^ (a{~i+2~} ^∧^ a{~i+3~}) ^∧^ ... = a{~i~}$. Suma este finita deoarece va exista un $b{~i~}$ egal cu $0$ si un $a{~i~}$ egal cu $0$ (daca $i$ este indeajuns de mare). Rezulta astfel ca $g-1(y) = y ^∧^ y/2 ^∧^ y/4 ^∧^ ...$
Fie $g(x)$ al $x$-lea numar din $G{~∞~}$ si $g-1(y)$ pozitia la care apare numarul $y$ in sirul $G{~∞~}$. Se pune problema calcularii eficiente a celor doua functii. Se poate demonstra prin inductie ca daca avem un numar $x$ cu reprezentarea binara $(...a{~2~}a{~1~}a{~0~}){~2~}$ si codul lui Gray $(...b{~2~}b{~1~}b{~0~}){~2~}$, atunci avem $b{~i~} = a{~i~} ^∧^ a{~i+1~}$ (2). De exemplu, pentru numarul $6$ cu reprezentarea binara $110$, atunci $g(110) = 101$. De aici se deduce ca $g(x) = x ^∧^ (x / 2)$. Din (2) obtinem ca $b{~i~} ^∧^ b{~i+1~} ^∧^ b{~i+2~} ^∧^ ... = (a{~i~} ^∧^ a{~i+1~}) ^∧^ (a{~i+1~} ^∧^ a{~i+2~}) ^∧^ (a{~i+2~} ^∧^ a{~i+3~}) ^∧^ ... = a{~i~}$. Suma este finita deoarece va exista un $b{~i~}$ egal cu $0$ si un $a{~i~}$ egal cu $0$ (daca $i$ este indeajuns de mare). Rezulta astfel ca $g-1(y) = y ^∧^ y/2 ^∧^ y/4 ^∧^ ...$
Din cele de mai sus obtinem urmatoarele metode:
Pentru a fi siguri ca aprindem becul trebuie in cel mai rau caz sa trecem prin toate configuratiile apasat/ne-apasat ale intrerupatoarelor. Pentru a schimba starea curenta trebuie sa apasam cel putin un buton, deci in cazul cel mai defavorabil va trebui sa facem cel putin $2^n^ - 1$ apasari. Codul Gray ne da o posibilitate de a trece prin toate configuratiile trecand de la una la alta prin o apasare de buton, rezolvandu-ne problema.
h2(#matrix). Problema 3: _Matrix_ ( acm.sgu.ru - 249)
h2(#matrix). Problema 3: '_Matrix_':http://acm.sgu.ru/problem.php?contest=0&problem=249 (SGU)
Trebuie sa aranjati numerele de la $0$ la $2^(n + m)^ - 1$ intr-o matrice cu $2^n^$ randuri si $2^m^$ coloane. De asemenea, numerele care sunt situate in celule adiacente pe verticala sau orizontala trebuie sa difere prin exact un bit in reprezentarea lor binara. Matricea este ciclica, adica pentru fiecare rand celula cea mai din stanga se considera invecinata cu cea mai din dreapta, de asemenea pentru fiecare coloana celula cea mai de sus se considera invecinata cu celula cea mai de jos. La intrare se dau numerele $n$ si $m$ ( $0 < n, m; n + m <= 20$ ). Trebuie sa afisati o asemenea matrice. De exemplu daca $n = 1$ si $m = 1$ o matrice ar fi
( $0$ $2$ )
|_. 101 | 10100 | 10101 | 10111 | 10111 |
|_. 100 | 10000 | 10001 | 10011 | 10010 |
Este evident ca orice doua numere adiacente in matrice sunt diferite in reprezentarea binara prin exact un bit. In concurs limita de timp era foarte stransa si trebuia folosita functia prezentata anterior. Deci pe linia $i$, coloana $j$ a matricei scriem numarul <code>(binToGray(i) << M) | binToGray(j)</code>.
Este evident ca orice doua numere adiacente in matrice sunt diferite in reprezentarea binara prin exact un bit. In concurs limita de timp era foarte stransa si trebuia folosita functia prezentata anterior. Deci pe linia $i$, coloana $j$ a matricei scriem numarul (binToGray(i) << M) | binToGray(j).
h2(#divizori). Problema 4: _Divizori_
h2(#divizori). Problema 4: '_Divizori_':problema/divizori
Vom considera un numar natural $N$. In sirul $A$ vom aseza toti divizorii lui $N (2 <= N <= 2.000.000.000)$. Se cere sa se permute elementele sirului $A$ astfel incat pentru oricare doua elemente consecutive $A[i]$ si $A[i+1]$ sa avem fie $A[i] = A[i+1] * p$, fie $A[i+1] = A[i] * p$ ( $p$ numar prim oarecare). Valoarea $p$ poate diferi de la o pereche de elemente la alta. De exemplu, pentru $N = 12$ o posibila solutie ar fi $1, 2, 3, 4, 12, 6, 3$.
Complexitatea finala a solutiei este $O(T)$ unde $T$ reprezinta numarul de divizori ai lui $N$.
h2(#sortnet). Problema 5: _Sortnet_ (Mihai Patrascu, lot 2002)
h2(#sortnet). Problema 5: '_Sortnet_':problema/sortnet (Lot 2002)
O retea completa de sortare este o retea de sortare cu $N$ fire de adancime $D$ ce are $D * (N/2)$ comparatori. Amintim principiul $0-1$ care spune ca o retea de sortare sorteaza orice $N$ numere daca aceasta sorteaza orice secventa de $N$ numere $0-1$. Problema noastra cere sa se determine cate astfel de secvente de $0-1$ nu sunt sortate corect.
== code(cpp) |
#include <stdio.h>
#define MAX_N 20
#define MAX_M 33
#define MAX_C 59049
#define FIN "sortnet.in"
#define FOUT "sortnet.out"
#define GRAY(x) ((x) ^ ((x) >> 1))
#define BIT(a, b) (((a) & (1 << (b))) > 0)
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define SORTED(x) (((x) & ((x)+1)) == 0)
#define FOR(i, a, b) for (i = (a); i < (b); i++)
int N, M, G[ 33 ][ 20 ], V[ 33 ], V2[ 33 ], Res;
int N, M, G[MAX_M][MAX_N], V[MAX_M], V2[MAX_M], Res;
inline int GRAY(int x)
{
    return x ^ ( x >> 1 );
}
 
inline int BIT(int a, int b)
{
    return (a & (1 << b)) > 0;
}
 
inline int MIN(int a, int b)
{
    return (a < b) ? a : b;
}
 
inline int MAX(int a, int b)
{
    return (a > b) ? a : b;
}
 
inline int SORTED(int x)
{
    return (x & (x+1)) == 0;
}
int works(int n, int a)
{
    int i, b, t;
    V2[0] = n;
    FOR (i, 0, M)
    for (i = 0; i < M; i++)
    {
        b = G[i][a];
        if ((BIT(V[i], MAX(a, b)) && !BIT(V[i], MIN(a, b))) ||
{
    int i, j, k, a, b, bit;
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    freopen("sortnet.in", "r", stdin);
    freopen("sortnet.out", "w", stdout);
    scanf("%d %d\n", &N, &M);
    FOR (i, 0, M) FOR (j, 0, N/2)
    {
        scanf("<%d,%d> ", &a, &b);
        a--; b--;
        G[i][a] = b; G[i][b] = a;
    }
    for (i = 0; i < M; i++)
        for (j = 0; j < N/2; j++)
        {
            scanf("<%d,%d> ", &a, &b);
            a--; b--;
            G[i][a] = b; G[i][b] = a;
        }
    Res = 1;
    FOR (i, 1, (1<<N))
    for (i = 1; i < (1 << N); i++)
    {
        k = GRAY(i) ^ GRAY(i-1);
        for (bit = 0; (1<<bit) < k; bit++);
}
==
h2. Bibliografie
h2(#biblio). Bibliografie
* [1] D.E.Knuth TAOC Prefascicle 2A
* [2] W.H. Press et. all. Numerical Recipies in C, Cambridge University Press
* [3] 'http://en.wikipedia.org/wiki/Gray_code':http://en.wikipedia.org/wiki/Gray_code
# D.E.Knuth TAOC Prefascicle 2A
# W.H. Press et. all. Numerical Recipies in C, Cambridge University Press
# 'Gray code, wikipedia':http://en.wikipedia.org/wiki/Gray_code

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3686