Informatika gyűjtemény

Egy szinttel feljebb fejvagyiras.cpp

2004050607080910

<<  1. óra - Ismétléses variáció  >>

<<  Fej vagy írás  >>

NézetNyomtat

fejvagyiras.cpp (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 3 KB
/* 
 * File:   fejvagyiras.cpp
 * Author: Kriván Bálint
 *
 * Created on 2008. szeptember 21., 18:33
 */

#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <math.h>

using namespace std;

typedef unsigned char byte;

class Problem {
    
private:
    int n;
    bool* data;
    string pattern;
    int patternFound;
    int* maxSeries;
    int currentCase;
    int* futamszamok;

public:

    Problem(int n) {
        this->n = n;
        data = new bool[n];

        initSubProblems();
    }

    char* caseToString() {
        char* c = new char[n];
        for (int i = 0; i < n; i++) {
            c[i] = data[i] ? 'F' : 'I';
        }
        return c;
    }

    bool isEqual(char c, bool b) {
        if ((b && (c == 'F')) || (!b && (c == 'I'))) return true;
        return false;
    }

    void useGeneratedCase() {
        // ha ki szeretnénk iratni a képernyőre az eseteket.
        /*char* c = caseToString();
        std::cout << c << endl;
        delete[] c;*/

        // Minta illesztés

        int pos = 0;
        bool cool = true;

        // amíg az illesztés "sikeres", addig illesztünk
        while ((pos + pattern.length()) <= n) {
            cool = true;
            for (int i = 0; i < pattern.length(); i++) {
                if (!isEqual(pattern[i], data[i + pos])) {
                    // véletlen nem egyezik a mintánk, akkor
                    pos++;
                    cool = false;
                    break;
                }
            }
            if (cool) {
                patternFound++;
                break;
            }
        }

        // fej-sorozatok átlagos hossza
        byte max = 0;
        byte v = 0;

        for (int i = 0; i < n; i++) {
            if (data[i]) { // fejecske
                v++;
                if (v > max) max = v;
            } else v = 0;
        }

        maxSeries[currentCase] = max;

        // futamszámok számolása
        bool prevState = data[0];
        int futamszam = 1;

        for (int i = 1; i < n; i++) {
            if (prevState != data[i]) {
                futamszam++;
                prevState = data[i];
            }
        }

        futamszamok[currentCase] = futamszam;

        currentCase++;
    }

    void generateCases(int i) {
        if (i == this->n) {
            useGeneratedCase();
        } else {
            this->data[i] = true;
            generateCases(i + 1);
            this->data[i] = false;
            generateCases(i + 1);
        }
    }

    void initSubProblems() {
        cout << "Minta: ";
        getline(cin, pattern);

        patternFound = 0;
        long db = (long) pow(2, n);
        maxSeries = new int[ db ];
        currentCase = 0;
        futamszamok = new int[ db ];
    }

    void solve() {
        generateCases(0);

        // minták
        cout << "Minta előfordulásainak száma: " << patternFound << endl;

        long db = currentCase;

        // fej-sorozatok átlag hossza
        long sum = 0;
        for (int i = 0; i < db; i++) {
            sum += maxSeries[i];
        }

        cout << "Fej-sorozatok átlagos hossza: " << ((double) sum / (double) db) << endl;

        // átlag futamszámok
        sum = 0;
        for (int i = 0; i < db; i++) {
            sum += futamszamok[i];
        }

        cout << "Futamszámok átlagos hossza: " << ((double) sum / (double) db) << endl;
    }

    ~Problem() {
        delete[] data;
        delete[] maxSeries;
        delete[] futamszamok;
    }

};

int main(int argc, char** argv) {

    // paraméterben adhatjuk meg, hogy mennyi legyen az "n".
    istringstream stream;
    string param = argv[1];
    stream.str(param);
    int n;
    stream >> n;

    Problem* p = new Problem(n);
    p->solve();
    delete p;

}
(Vissza)