Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » Rätselecke » Zahlenreihe Periode finden

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 < [ 2 ]
000
23.01.2009, 10:04 Uhr
mike
Pinguinhüpfer
(Operator)


Hi

Hab es selbst mal gebraucht und in einem anderen (Ruby-)Forum war es auch ein Rätsel:
Man hat eine Zahlensequenz (natürliche Zahlen): 0 1 2 3 4 5 6 4 5 6 4 5 6 ...
Und muss die kleinste sich wiederholende Sequenz suchen: hier eben 4 5 6

Hier meine Lösung - die Lösung ist gewachsen also evntl. etwas nicht C++lerisch


C++:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <sstream>

#include <stdlib.h>
#include <time.h>

using namespace std;

bool subSort(vector<unsigned> const &a, vector<unsigned> const &b)
{    
    /* Thats bad - first is bigger than second array */
    if(a.size() > b.size())
    {        
        pair<vector<unsigned>::const_iterator, vector<unsigned>::const_iterator > elem;
        elem = mismatch(b.begin(), b.end(), a.begin());
    
        /* Completly included */    
        if(elem.first == b.end())
            return false;
        
        if(*elem.first < *elem.second)
            return false;
        else
            return true;        
    }        
    
    pair<vector<unsigned>::const_iterator, vector<unsigned>::const_iterator > elem;
    elem = mismatch(a.begin(), a.end(), b.begin());
    
    /* Completly included */        
    if(elem.first == a.end())
        return true;
        
    if(*elem.first < *elem.second)
        return true;
    else
        return false;
}

int main()
{
    ostringstream debugOutput;    
    vector<unsigned> src;
        
    srand ( time(NULL) );
    
    /* ein paar "falsche" Zahlen */    
    for(unsigned i=0; i < 10; i++)
    {
        src.push_back( rand() % 10 );                
    }
    
    for(unsigned i=0; i < 50; i++)
    {
        src.push_back(7);
        src.push_back(2);
        src.push_back(3);        
        src.push_back(4);
    }
    
    /* ein paar "falsche" Zahlen */
    for(unsigned i=0; i < 10; i++)
    {
        src.push_back( rand() % 10 );                
    }
    
    copy(src.begin(), src.end(), ostream_iterator<unsigned>( debugOutput, " " ));
    cout << debugOutput.str() << endl;
    
    cout << "start build" << endl;
    
    /* Build suffix tree */
    vector<vector<unsigned> > vec;
    vec.resize(src.size());

    vector<unsigned>::iterator srcit = src.begin();    
    
    for(size_t index = 0; index < src.size(); index++, srcit++)
    {        
        vec[index].resize(distance(srcit, src.end()));
        copy(srcit, src.end(), vec.at(index).begin());        
    }
    
    cout << "end build" << endl;
    
    /* Sort the tree */
    cout << "start sort" << endl;        
    sort(vec.begin(), vec.end(), subSort);    
    cout << "end sort" << endl;    
    
    cout << "start search"<<endl;
    /* Go through the array and find best sequence */
    vector<vector<unsigned> >::iterator it;

    vector<unsigned> lastcommon;
    vector<unsigned> currcommon;
    vector<unsigned> prevdiff;
    vector<unsigned> currdiff;
    unsigned counter = 0, maxcounter = 0;
    size_t bestdist;
    vector<unsigned> bestdiff;
    
    
    for(it = vec.begin(); it != vec.end(); it++)
    {
        if(it + 1 == vec.end())
            break;        
        
        pair<vector<unsigned>::const_iterator, vector<unsigned>::const_iterator > elem;
        size_t dist;        
        
        lastcommon = currcommon;
        
        if(it->size() > (it+1)->size())
        {
            elem = mismatch((it + 1)->begin(), (it + 1)->end(), it->begin());            
            dist = distance(static_cast<vector<unsigned>::const_iterator>((it + 1)->begin()), elem.first);
            currcommon.resize(dist);
            copy(static_cast<vector<unsigned>::const_iterator>((it + 1)->begin()), elem.first, currcommon.begin());
        }
        else
        {
            elem = mismatch(it->begin(), it->end(), (it + 1)->begin());            
            dist = distance(static_cast<vector<unsigned>::const_iterator>(it->begin()), elem.first);                    
            currcommon.resize(dist);
            copy(static_cast<vector<unsigned>::const_iterator>(it->begin()), elem.first, currcommon.begin());        
        }            
        
        if(dist > bestdist)
        {
            bestdist = dist;                        
        }        
        
        /*******************************************************************************************/
                
        prevdiff = currdiff;
        
        if(currcommon.size() != 0 && lastcommon.size() != 0)
        {
            pair<vector<unsigned>::const_iterator, vector<unsigned>::const_iterator > elem;            
            size_t dist;
            
            if(currcommon.size() > lastcommon.size())
            {
                elem = mismatch(lastcommon.begin(), lastcommon.end(), currcommon.begin());
                
                if(elem.first == lastcommon.end())
                {
                    dist = distance(elem.second, static_cast<vector<unsigned>::const_iterator>(currcommon.end()));
                    currdiff.resize( dist );
                    copy(elem.second, static_cast<vector<unsigned>::const_iterator>(currcommon.end()), currdiff.begin());
                }
            }
            else
            {
                elem = mismatch(currcommon.begin(), currcommon.end(), lastcommon.begin());
                
                if(elem.first == currcommon.end())
                {
                    dist = distance(elem.second, static_cast<vector<unsigned>::const_iterator>(lastcommon.end()));
                    currdiff.resize( dist );
                    copy(elem.second, static_cast<vector<unsigned>::const_iterator>(lastcommon.end()), currdiff.begin());
                }            
            }            
        }
        else
        {                
            counter = 0;
        }
        
        if(prevdiff.size() == currdiff.size())
        {
            if(equal(prevdiff.begin(), prevdiff.end(), currdiff.begin()))
            {
                counter++;
            }
            
        }
        else
        {        
            counter = 0;
        }
        
        if(counter > maxcounter)
        {
            maxcounter = counter;
            bestdiff = currdiff;
        }        
    }
    
    cout << "end search"<<endl;
    
    debugOutput.str("");
    copy(bestdiff.begin(), bestdiff.end(), ostream_iterator<unsigned>( debugOutput, " " ));
    cout << debugOutput.str() << endl;
}



Optimale Lösungen kommen sogar mit Störwerten innerhalb der Sequenz zurecht:
0 1 2 3 4 5 6 4 5 6 4 5 6 9 4 5 6 4 5 6 4 5 6

Wenn wer Zeit und Lust hat

lg
--

Dieser Post wurde am 29.01.2009 um 20:14 Uhr von FloSoft editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
23.01.2009, 15:21 Uhr
~kronos
Gast


Wie definierst du Periode in einer endlichen Folge? Wenn du sagst die kürzeste Sequenz, die sich ab einem Punkt bis Ende wiederholt, dann ist das die letzte Zahl. Mindestens eine Wiederholung? Mindestens zwei Zahlen?

Und was ist das Ziel des Rätsels?
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
23.01.2009, 22:56 Uhr
mike
Pinguinhüpfer
(Operator)


Damit meine ich dass du sowas suchst wie
1 2 3 7 8 9 7 8 9 7 8 9 7 8 9 ...
dann wäre es 1 2 3 {7 8 9}* weil sich 7 8 9 am öftesten wiederholt. Anwneund gibts viele - die Gen Typen haben so ähnliche Probleme - nur mit mehr Störwerten

Ziel: schönste Lösung, schnellster Code
--
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
23.01.2009, 23:18 Uhr
Guybrush Threepwood
Gefürchteter Pirat
(Operator)


Kann so eine Sequenz die selbe Ziffer mehrmals enthalten?
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
24.01.2009, 06:14 Uhr
0xdeadbeef
Gott
(Operator)


Wenn ich die 8en und 9en als Störwerte auffasse, ist die kleinste, sich wiederholende Sequenz in deinem Beispiel aber 7. Eine mathematisch etwas eindeutigere Definition wäre...wünschenswert.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
27.01.2009, 23:02 Uhr
mike
Pinguinhüpfer
(Operator)


Puh. Mathematische Defintion kann ich jetzt aus dem Stehgreif nicht liefern.
Wegen dem obigen Bsp:
1 2 3 7 8 9 7 8 9 7 8 9 7 8 9 ...
Angenommen (7 8 9) wiederholt sich 10000 Mal und ich habe an Stelle 567 und 1876 eine 4 drinnen - dann kann man das als "Messfehler" / Störwert nehmen und (7 8 9)* als Periode. Bin mir jetzt gar net sicher obs ne saubere Defintion gibt die wasserdicht ist - man arbeitet da meines Wissens viel mit Heuristiken (eindeutige Ergebnisse?)
Aber für die Rätselecke kann man das auch ohne Störwerte machen - damit man bessere Vergleiche hat - somit ist bei 1 2 3 7 8 9 7 8 9 7 8 9 7 8 9 ... (7 8 9)* eindeutig definiert als kleinste sich wiederholende Periode
--
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
30.01.2009, 00:08 Uhr
0xdeadbeef
Gott
(Operator)


Geh ich recht in der Annahme, dass bei z.B. 1232323456456456 das Ergebnis 456, nicht 23 wäre?
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
30.01.2009, 11:57 Uhr
ao

(Operator)


Gibt es das tatsächlich, periodische Zahlen mit einzelnen Störwerten? Wie entstehen die? Jedenfalls nicht so wie ungestörte periodische Zahlen durch Division.


Zitat von mike:
dann kann man das als "Messfehler" / Störwert nehmen


Messfehler? Bei einer exakten Rechnung? Also bitte!
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
30.01.2009, 12:40 Uhr
0xdeadbeef
Gott
(Operator)


Nimm an, ich will dir eine lange Zahlenfolge übers Netzwerk schicken, aber in Ermangelung eines Netzwerkkabels muss ich dazu eine Kette rostiger Kuchengabeln benutzen.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
01.02.2009, 16:23 Uhr
kronos
Quotenfisch
(Operator)


Als Definition schlag' ich mal die schließlichen Periode mit mindestens einer Wiederholung und mit möglichst großem kleinem N vor:


C++:
#include <string.h>
#include <stdio.h>

size_t period(const char*s)
{
    const char*p=s+1;
    size_t n=1;

    while((p=strchr(p,*s)))
    {
        n=p-s;
        while(!strncmp(s,p,n))
            p+=n;
    }
    return n;
}

int main()
{
    char*s="12123121234455.0"; // Invertierte!! String-Darstellung
    printf("%.*s\n",period(s),s);
    return 0;
}

--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>

Dieser Post wurde am 01.02.2009 um 18:11 Uhr von kronos editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 < [ 2 ]     [ Rätselecke ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: