String-Index rückwirkend bestimmen

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8489
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: String-Index rückwirkend bestimmen

Beitrag von Xin » Fr Nov 07, 2014 8:37 pm

DaveX hat geschrieben:
Xin hat geschrieben:Darf ich fragen, warum Du den Index im Dezimalsystem verwendest? Vielleicht bietet sich zum Beispiel das 26er-Zahlensystem verwendest und als Ziffern könntest Du dann die Buchstaben verwenden? Daraus würde sich eine vergleichsweise einfache Abbildung ergeben...
Könntest du mir ein kleines Beispiel zeigen, wie du das genau meinst? Habe es nicht ganz verstanden. Klingt aber Interessant. Mir fiel eben keine Alternative ein, wie ich das sonst machen sollte als den Index im Dezimalsystem anzuzeigen bzw. auszugeben.
Was Du machst ist einen Text "ab" zu nehmen, 1(a)*26+2(b) zu nehmen. Nehmen wir das hexadezimale Zahlensystem, da hast Du die Ziffern 0123456789ABCDEF: 16 Ziffern. Du hast 26 Zeichen, das 26er Zahlensystem bietet sich an. Nimmt man nun noch die Ziffern 'abcdefghijklmnopqrstuvwxyz' als Ziffern, dann ist a == 1 und b==2, also a*26^1 + b*26^0. Im 26er Zahlensystem sähe die Zahl dann so aus: "ab". Dein Index ist also identisch mit dem String.

Das ganze ist nicht komplett als Gag gemeint, auch wenn man es so auffassen kann. Für mich stellt sich die Frage, warum Du Text in Dezimalzahlen ausdrücken möchtest, schließlich hast Du mit dem Text ja bereits eine eindeutige Zuordnung.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

Re: String-Index rückwirkend bestimmen

Beitrag von DaveX » Sa Nov 08, 2014 11:18 am

Hallo Xin :),

also mit Beispiel-String: "test" meinst du das in etwa so: 20(t)*26^3 + 5(t)*26^2 + 19(s)*26^1 + 20(t)*26^0 ?
Ich denke mal schon, denn mit dieser Berechnung komme ich ebenfalls auf den richtigen Index: 355414. :) Dankeschön. ;)
Aber wie kann ich beispielsweise folgenden String: "yyyyyyyyyyyyyyz" was den Index 17052375651866279936 hat so anzeigen bzw. ausgeben,
ohne auf das Dezimalsystem zugreifen zu müssen. Z.B. als String. Wäre das irgendwie möglich?

Ich habe folgendes Programm geschrieben:

Code: Alles auswählen

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

#define  NLiterals  26
#define  UI64MAXVAL 18446744073709551615U

uint64_t pow_u64( uint64_t, uint64_t );
uint64_t StrIndex( const char *, size_t, size_t );

int main( void )
{
    char *NStrs[] = { "z",
                      "yz",
                      "yyz",
                      "yyyz",
                      "yyyyz",
                      "yyyyyz",
                      "yyyyyyz",
                      "yyyyyyyz",
                      "yyyyyyyyz",
                      "yyyyyyyyyz",
                      "yyyyyyyyyyz",
                      "yyyyyyyyyyyz",
                      "yyyyyyyyyyyyz",
                      "yyyyyyyyyyyyyz",
                      "yyyyyyyyyyyyyyz" };

    for( char *StrPtr, **PtrPtr = NStrs; StrPtr = *PtrPtr++; )
        printf( "%s: %ju\n", StrPtr, StrIndex( StrPtr, strlen( StrPtr ), NLiterals ) );

    printf( "UINT64_T-MAXVAL: %ju\n", UI64MAXVAL );

    return( EXIT_SUCCESS );
}

/* uint64_t--Version of pow() */
uint64_t pow_u64( uint64_t base, uint64_t pow )
{
    if( pow ==  0 )
        return 1;

    if( pow < 0 )
        return 0;

    uint64_t result = 1;

    for( uint64_t i = 0; i < pow; i++ )
        result *= base;

    return result;
}

uint64_t StrIndex( const char *SPtr, size_t SLen, size_t NLit )
{
    uint64_t Index = 0;

    if( SLen > 0 )
    {
        size_t i;
        size_t l = SLen-1;

        if( SLen > 2 )
            for( i = 0; i < l; ++i )
                Index += pow_u64( NLit, SLen-i-1 ) * ( SPtr[i]-'a' );

        Index += 1 + SPtr[l]-'a';

        for( i = 0; i < l; ++i )
            Index += pow_u64( NLit, i+1 );
    }

    return Index;
}
Die Ausgabe ist folgende:

Code: Alles auswählen

z: 26
yz: 52
yyz: 17576
yyyz: 456976
yyyyz: 11881376
yyyyyz: 308915776
yyyyyyz: 8031810176
yyyyyyyz: 208827064576
yyyyyyyyz: 5429503678976
yyyyyyyyyz: 141167095653376
yyyyyyyyyyz: 3670344486987776
yyyyyyyyyyyz: 95428956661682176
yyyyyyyyyyyyz: 2481152873203736576
yyyyyyyyyyyyyz: 9169742482168496128
yyyyyyyyyyyyyyz: 17052375651866279936
UINT64_T-MAXVAL: 18446744073709551615
Also wie man sieht bewegt man sich bei "yyyyyyyyyyyyyyz" schon hart an der Grenze von unsigned long long. Hier rede ich von nur 26, also "a-z".
Aber mein kleines BruteForce-Experiment soll ja auch noch weitere Optionen enthalten. Nämlich [0-9], [0-9|a-z], [0-9|A-Z], [a-z|A-Z] usw. Dementsprechend steigt auch die Anzahl der Zeichen. Also bei [0-9|a-z] wären es anstatt 26 schon 36. Daher meine Frage. :)

DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

Re: String-Index rückwirkend bestimmen

Beitrag von DaveX » Sa Nov 08, 2014 3:38 pm

Ich wollte obigen Beitrag korrigieren. Geht aber leider nicht mehr. Deswegen leider ein weiterer Post von mir.
Habe eben festgestellt, dass bereits bei String "yyyyyyyyyyyyyz" die "unsigned long long"-Grenze überschritten ist.

Code: Alles auswählen

uint64_t max. Wert = 18,446,744,073,709,551,615
"yyyyyyyyyyyyyz"    = 64,509,974,703,298,890,976 <-- deutlich höher als max. Wert von uint64_t
Daher stimmen die beiden letzten Ergebnisse meines Programms im letzten Post nicht.

Code: Alles auswählen

.
.
yyyyyyyyyyyyz: 2481152873203736576 <-- richtig
yyyyyyyyyyyyyz: 9169742482168496128 <-- falsch (Grenze von uint64_t überschritten)
yyyyyyyyyyyyyyz: 17052375651866279936 <-- falsch (Grenze uint64_t überschritten)
UINT64_T-MAXVAL: 18446744073709551615
Letztes richtiges Ergebnis ist:

Code: Alles auswählen

yyyyyyyyyyyyz: 2481152873203736576
Von daher, sorry. :)

Antworten