Posts Tagged ‘c++’

PostHeaderIcon Liczby Armstronga

Liczbą Armstronga (inaczej narcystyczną) nazywamy n-cyfrową liczbę naturalną, która jest sumą swoich cyfr podniesionych do potęgi n. Udowodniono, że takich liczb jest 88, przy czym najwyższa z nich ma 39 cyfr. Oczywiście algorytm do obliczania tak dużych liczb nie może operować na powszechnie znanych typach danych – przykładowo liczba typu int w języku C może być maksymalnie równa w przybliżeniu 4 miliardy. Aby poradzić sobie z tym problemem musimy stworzyć własny typ danych i zdefiniować dla niego podstawowe operacje (dla naszych celów przydadzą się jedynie operacje dodawania i mnożenia).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#define MAX_DIGTS 40
#define MAX_DIGTS2 (MAX_DIGTS+1)*(MAX_DIGTS+1)


uint_fast32_t powtabl[10*MAX_DIGTS2];
uint_fast32_t tmp[MAX_DIGTS];
uint_fast32_t maxnumber[MAX_DIGTS];
uint_fast32_t liczba[MAX_DIGTS];
uint_fast32_t digt;
uint_fast32_t ifrom[10], ilosc[10];
uint_fast32_t minnumber[11*MAX_DIGTS];
uint_fast32_t tmpx;
uint_fast32_t digtscnt[10];
uint_fast32_t flag = 1;
uint_fast32_t iend;
uint_fast32_t found = 0;
uint_fast32_t w;


// aa < bb
inline
//static
void addl(uint_fast32_t* c, const uint_fast32_t* a, const uint_fast32_t* b)
{
    uint_fast32_t i;

    for (i = 1; i <= *a; i++)
        c[i] = a[i] + b[i];

    for (i = *a+1; i <= *b; i++)
        c[i] = b[i];

    for (i = 1; i < *a; i++)
        if (c[i] > 9)
        {
            c[i] += -10;
            ++c[i+1];
        }

    for (i = *a; i < *b; i++)
    {
        if (c[i] > 9)
        {
            c[i] += -10;
            ++c[i+1];
        }
        else
        {
            *c = *b;
            return;
        }
    }

    if (c[*b] > 9)
    {
        c[*b] += -10;
        *c = *b+1;
        c[*c] = 1;
        return;
    }
    *c = *b;
}

inline
//static
void muli(uint_fast32_t *c, const uint_fast32_t *b, const uint_fast32_t a)
{
    uint_fast32_t i, tmpc;

    for (i = 1; i <= *b; i++)
        c[i] = b[i] * a;

    i = 0;
    while (++i < *b)
        if (c[i] > 9)
        {
            tmpc = 0.1*c[i];
            c[i+1] += tmpc;
            c[i] += -(tmpc << 3);
            c[i] += -(tmpc << 1);
        }

    if (c[i] > 9)
    {
        c[i+1] = 0.1*c[i];
        c[i] += -(c[i+1] << 3);
        c[i] += -(c[i+1] << 1);
        if (c[++i] > 9)
        {
            c[i+1] = 0.1*c[i];
            c[i] += -(c[i+1] << 3);
            c[i] += -(c[i+1] << 1);    // dwa zera z przodu
        }
    }

    *c = i;
}


//inline
static
uint_fast32_t *powll(uint_fast32_t a, uint_fast32_t b)
{
    uint_fast32_t tmp[MAX_DIGTS], i, *xx;

    if (powtabl[a*MAX_DIGTS2+b*(MAX_DIGTS)] == 0)
    {
        xx = powll(a,b-1);
        for (i = 0; i < MAX_DIGTS; i++)
            *(tmp+i) = *(xx+i);
           
        while (tmp[*tmp] == 0 && *tmp >= 2)
            (*tmp)--;
           
        muli(tmp, tmp, a);
       
        for (i = 0; i < MAX_DIGTS; i++)
            powtabl[a*MAX_DIGTS2+b*(MAX_DIGTS+1)+i] = tmp[i];
           
        while (powtabl[a*MAX_DIGTS2+b*(MAX_DIGTS+1)+powtabl[a*MAX_DIGTS2+b*(MAX_DIGTS+1)]] == 0 &&
                powtabl[a*MAX_DIGTS2+b*(MAX_DIGTS+1)] >= 2)
            powtabl[a*MAX_DIGTS2+b*(MAX_DIGTS+1)]--;
    }
    return powtabl+a*MAX_DIGTS2+b*(MAX_DIGTS+1);
}


int main()
{
    int_fast32_t i, ito[10], it[10];
    uint_fast32_t n, j;

    memset(powtabl, 0, 10*MAX_DIGTS2*sizeof(uint_fast32_t));

    for (i = 9; i >= 0; i--)
    {
        //liczymy pierwsza i zerowa potege
        powtabl[i*MAX_DIGTS2] = 1;
        powtabl[i*MAX_DIGTS2+1] = 1;
        powtabl[i*MAX_DIGTS2+MAX_DIGTS+1] = 1;
        powtabl[i*MAX_DIGTS2+MAX_DIGTS+2] = i;
        ito[i] = 0;
    }
   
    //liczymy pozostale potegi (1 do 39)
    for (i = 1; i < 10; i++)
        powll(i,MAX_DIGTS-1);

    minnumber[10*(MAX_DIGTS+1)] = 1;
    minnumber[10*(MAX_DIGTS+2)] = 0;

    for (n = 1; n <= MAX_DIGTS; n++)
    {
        digt = 9;
        ifrom[9] = it[9] = n;

        while (digt < 10)
            if (it[digt] >= ito[digt])
            {
                if (digt == 1)
                {
                    liczba[0] = liczba[1] = 1;

                    muli(liczba, liczba, *(it+1));
                    if (*liczba >= *(minnumber+2*(MAX_DIGTS+1)))
                        addl(tmp, minnumber+2*(MAX_DIGTS+1), liczba);
                    else
                        addl(tmp, liczba, minnumber+2*(MAX_DIGTS+1));
                    memcpy(liczba, tmp, (n+1)*sizeof(uint_fast32_t));
                    while (liczba[*liczba] == 0 && *liczba > 1)
                    {
                        (*liczba)--;
                    }

                    if (*liczba == n)
                    {
                        //memset(ilosc, 0, 10*sizeof(int_fast32_t));
                        for (i = 9; i >= 0; i--)
                            *(ilosc+i) = 0;
                        for (i = *liczba; i > 0; i--)
                            ilosc[liczba[i]]++;
                        if (((ilosc[1] - it[1]) | (ilosc[2] - it[2]) | (ilosc[3] - it[3]) | (ilosc[4] - it[4]) | (ilosc[5] - it[5]) | (ilosc[6] - it[6]) | (ilosc[7] - it[7]) | (ilosc[8] - it[8]) | (ilosc[9] - it[9])) == 0)
                        {
                            printf("%d/89: ", ++found);
                            for (i = *liczba; i > 0; i--) printf("%d", liczba[i]);
                            printf(" (%d)\n", n);
                        }
                    }
                    it[digt]--;
                    continue;
                }

                else if (digt != 9)
                {
                    muli(tmp, powtabl+digt*MAX_DIGTS2+n*(MAX_DIGTS+1), it[digt]);
                    if (*(minnumber+(MAX_DIGTS+1)*(digt+1)) >= *tmp)
                        addl(minnumber+(MAX_DIGTS+1)*digt, tmp, minnumber+(MAX_DIGTS+1)*(digt+1));
                    else addl(minnumber+(MAX_DIGTS+1)*digt, minnumber+(MAX_DIGTS+1)*(digt+1), tmp);
                }

                else muli(minnumber+(MAX_DIGTS+1)*9, powtabl+9*MAX_DIGTS2+n*(MAX_DIGTS+1), it[9]);

                ifrom[digt-1] = ifrom[digt]-it[digt];
                muli(maxnumber, powtabl+(digt-1)*MAX_DIGTS2+n*(MAX_DIGTS+1), ifrom[digt-1]);

                tmpx = (MAX_DIGTS+1)*digt;
                if (*maxnumber < *(minnumber+tmpx))
                    addl(maxnumber, maxnumber, minnumber+tmpx);
                else
                    addl(maxnumber, minnumber+tmpx, maxnumber);

                // ilosc najbardziej znaczacych, wspolnych cyfr
                if (*maxnumber < n)
                {
                    --it[++digt];
                }
                else if (minnumber[tmpx] > n)
                    --it[digt];
                else
                {
                    j = n;
                    while (minnumber[tmpx+j] == maxnumber[j] && j > 0)
                    {
                        --j;
                    }
                    iend = minnumber[tmpx];

                    for (i = 9; i >= 0; i--)
                        digtscnt[i] = 0;

                    for (i = n-j; i > 0; i--)
                        ++digtscnt[minnumber[tmpx+i+iend-n+j]];
                       
                    for (i = 9; i >= digt; i--)
                        flag = flag & (digtscnt[i] <= it[i]);

                    for (i = digt-1; i > 0; i--)
                        ito[i] = digtscnt[i];

                    if (flag != 1)
                    {
                        --it[digt];
                        flag = 1;
                    }
                    else
                    {
                        --digt;
                        it[digt] = ifrom[digt];
                    }
                }
            }
            else
            {
                --it[++digt];
            }
    }

    return 0;
}

Kod zapisujemy pod nazwą big-number.c i kompilujemy pod Linuksem poleceniem:

gcc -Wall -O2 -ffast-math -funroll-loops -fomit-frame-pointer big-number.c -o numb

Możemy oczywiście stworzyć plik Makefile, aby zaoszczędzić sobie wpisywania lub pamiętania wszystkich flag przy następnych kompilacjach. Ma on postać:

numb: big-number.c
gcc -Wall -O2 -ffast-math -funroll-loops -fomit-frame-pointer big-number.c -o numb

PostHeaderIcon 2. Całkowanie Verleta

Sercem symulacji jest system cząsteczek. Zazwyczaj w implementacji systemu cząstek każda cząstka ma dwie główne zmienne: x – pozycja i v – jej prędkość. Następnie w ‚czasokrokowej’ pętli, nowa pozycja x’ i prędkość v’ są obliczane według:

 \textbf{x}' = \textbf{x} + \textbf{v} \cdot \Delta t
 \textbf{v}' = \textbf{v} + \textbf{a} \cdot \Delta t

gdzie dt jest krokiem czasu, a – przyspieszeniem obliczanym z wykorzystaniem prawa Newtona  \textbf{F} = m \cdot \textbf{a} (gdzie F to wypadkowa sił działających na cząstki). Jest to prosta integracja Eulera.

W naszym przypadku jednak wybieramy schemat w mniejszym stopniu oparty na prędkości: zamiast przechowywać pozycję i prędkość każdej cząstki, będziemy przechowywać jej aktualną pozycję x oraz wcześniejszą \textbf{x}^*. Utrzymując stały czasowy krok, pętla aktualizacyjna wygląda wtedy następująco:

 \textbf{x}' = 2\textbf{x} - \textbf{x}^* + \textbf{a} \cdot \Delta t^2
 \textbf{x}^* = \textbf{x}

Nazywamy to całkowaniem Verleta (patrz [((bibcite Verlet))]); jest ono intensywnie wykorzystywane podczas symulowania dynamiki molekularnej. Metoda jest dość stabilna, gdyż prędkość jest domyślnie podana, a co za tym idzie trudniej jest prędkości i pozycji być niezsynchronizowanymi. (Na marginesie warto zauważyć, że podobne podejście wykorzystuje znany efekt tworzenia fal w wodzie). Metoda działa z uwagi na fakt, że  2x - x^* = x + (x - x^*) oraz  x - x^* są przybliżeniem aktualnej prędkości (tak naprawdę jest to droga przebyta od ostatniego kroku). Metoda ta nie zawsze jest wyjątkowo dokładna (energia może np. opuścić system), ale za to szybka i stabilna. Zmieniając aktualizację reguły np. na taką:

 \textbf{x}' = 1,99\textbf{x} - 0,99\textbf{x}^* + \textbf{a} \cdot \Delta t^2

możemy wprowadzić niewielką ilość oporu do systemu.

Pod koniec każdego etapu aktualna pozycja x każdej cząstki zostaje przechowana w odpowiedniej zmiennej \textbf{x}^*. Zauważ, że gdy manipulujemy wieloma cząstkami, przydatną optymalizacją może być po prostu zamiana tablicy wskaźników.

Wynikowy kod będzie wyglądać mniej więcej tak (klasa Vector3 powinna zawierać odpowiednie funkcje i przeciążenia operatorów manipulacji wektorów):

// przykładowy kod symulacji fizyki
class ParticleSystem
{
Vector3   m_x[NUM_PARTICLES];            // aktualne pozycje
Vector3   m_oldx[NUM_PARTICLES];        // poprzednie pozycje
Vector3   m_a[NUM_PARTICLES];            // obliczone siły
Vector3   m_vGravity;                           // grawitacja
float   m_fTimeStep;

public:
void   TimeStep();

private:
void   Verlet();
void   SatisfyConstraints();
void   AccumulateForces();

// konstruktory, inicjalizacje itp. pominięte
};

// krok całkowania Verleta
void ParticleSystem::Verlet()
{
for (int i = 0; i < NUM_PARTICLES; i++)
{
Vector3& x = m_x[i];
Vector3 temp = x;
Vector3& oldx = m_oldx[i];
Vector3& a = m_a[i];
x += x - oldx + a*fTimeStep*fTimeStep;
oldx = temp;
}
}

// funkcja ta powinna obliczać siły dla każdej cząstki
void ParticleSystem::AccumulateForces()
{
// wszystkie cząstki podlegają grawitacji
for (int i = 0; i < NUM_PARTICLES; i++)
m_a[i] = m_vGravity;
}

// tu uwzględniamy ograniczenia
void ParticleSystem::SatisfyConstraints()
{
// ta funkcja jest na razie nieistotna
}

void ParticleSystem::TimeStep()
{
AccumulateForces();
Verlet();
SatisfyConstraints();
}

Powyższy kod został napisany dla przejrzystości, a nie szybkości działania. Jedną z optymalizacji byłoby użycie tablic typu float zamiast Vector3 dla reprezentacji stanów. Mogłoby to również ułatwić implementację na procesorach wektorowych.

Zaprezentowana metoda prawdopodobnie nie wygląda jeszcze bardzo przełomowo. Jednakże korzyści powinny być wyraźne, gdy zaczniemy używać ograniczeń i przełączymy się na ciała sztywne. Zauważymy wtedy, jak powyższa metoda prowadzi do zwiększenia stabilności i zmniejszenia ilości obliczeń w porównaniu do innych metod.

Spróbuj np. ustawić \textbf{a} = (0,0,1) i użyć jako warunku początkowego \textbf{x} = (0,0,0) i \textbf{x}^* = (0,0,0), a następnie wykonać ręcznie kilka powtórzeń, aby zobaczyć, co się dzieje.

PostHeaderIcon Teoria

Techniki dotyczące programowania gier.

PostHeaderIcon Witam na stronie

Kliknij w interesujący Cię temat.

PostHeaderIcon Valet Parking

ściągnij rozwiązanie : Valet Parking (7z)

1. Cel zadania

Parking (Valet Parking) to gra logiczna polegająca na wyprowadzeniu auta zaparkowanego na przepełnionym parkingu.

2. Reguły gry

Każde z aut może poruszać się tylko w przód i w tył. Przeszkodą uniemożliwiającą ruch są ściany oraz inne auta. Celem gry jest znalezienie takiej sekwencji przestawień poszczególnych aut, aby możliwe było wyprowadzenie z parkingu wskazanego auta poprzez wyjazd. Poza momentem wyprowadzania wyróżnionego auta, żadne z aut nie może także znaleźć się w polu stanowiącym wyjazd.

Plansza zawiera opis parkingu wraz z układem samochodów i wskazanym wyjazdem. Możliwe jest także rozmieszczenie aut, przy którym nie istnieje sekwencja ruchów umożliwiająca wyprowadzenie wyróżnionego auta.

Celem projektu jest napisanie programu, który:

  • wczyta opis planszy ze standardowego wejścia,
  • znajdzie sekwencję ruchów aut,
  • wypisze rozwiązanie na standardowe wyjście

3. Opis wejścia/wyjścia

Program wczytuje opis planszy ze standardowego wejścia. Znaczenie znaków jest następujące:

* * (gwiazdka) – ściana,
* ^ (daszek) – wyjazd z parkingu,
* . (kropka) lub   (spacja) – pusta przestrzeń,
* dowolny znak alfanumeryczny – część auta.

Każda plansza jest prostokątna. Ściany i wyjazd znajdują się wyłącznie na obrzeżach planszy (w skrajnych wierszach i kolumnach). Każda plansza ma dokładnie jeden wyjazd. Jedynymi przeszkodami wewnątrz parkingu są pozostałe auta. Każde z aut składa się z przynajmniej dwóch znaków alfanumerycznych ułożonych sąsiadująco w pionie lub poziomie.

Auto, które należy wyprowadzić, składa się z symboli w postaci liter A (wielkie A).

Wyjściem programu powinna być sekwencja par oznaczających przesuwane auto i kierunek jego ruchu, składających się ze znaku określającego auto i kierunek ruchu w postaci jednej z liter n, s, w, e. Wszystkie pary sekwencji wyjściowej muszą być oddzielone białymi znakami. Ostatni ruch sekwencji powinien doprowadzić do „pokrycia się” jednego z symboli wyprowadzanego auta z symbolem określającym wyjazd z parkingu. Jest to jedyna sytuacja, w której auto może znaleźć się w polu wyjazdu.

Jeśli nie istnieje sekwencja wyprowadzająca auto, program powinien wypisać pojedynczą linię linię o treści:

NO

4. Przykład

Przykładowa plansza gry:

*******
*AAAC ^
*   C *
*BB C *
*     *
*******

Rozwiązaniem jest, między innymi, następująca sekwencja:

Cs
Ae
Ae
Ae

Program podczas działania: