Zeichen rekursiv verdoppeln und "zählen"

Schlangenmensch

Ich habe keine Ahnung woher du solche Sachen hast (wenn du die Sachen dir nicht ausgedacht hast, wären Quellen nett).

Ist mit einer statischen Variable wahrscheinlich nicht ganz, wie gedacht und ich habe mir nicht viel Mühe gegeben alles zu testen, aber auf den ersten Blick scheint es zu funktionieren,.

std::string verdoppeln(const std::string& s, char c)
{
  static int count = 0;
  std::string res{};
  if(s.length() > 0)
  {
    if(s.length() == 1)
    {
      if (s[0] == c)
      {
        ++count;
        res = res + c + c + std::to_string(count);
      }
      else
      {
        res = res + s + std::to_string(count);
      }
      count = 0;
    }
    else if (s.front() != c)
    {
      res = res + s.front() + verdoppeln(s.substr(1, s.length()), c);
    }
    else
    {
      ++count;
      res = res + c + c + verdoppeln(s.substr(1, s.length()), c);
    }
  }
  return res;
}

P.S: Das man ab einer gewissen Rekursionstiefe in einen Overflow läuft, ist normal.

Danke für die Antwort.

In C(++) ist static erlaubt, in Java nicht...

In diesem Fall brauche ich aber einmal so viele rekursive Calls...

Ich habe herausgefunden, dass die Berechnung:

@NoIDE sagte in Zeichen rekursiv verdoppeln und "zählen":

(int) Math.ceil(Math.log10(lenDiff - Math.log(lenDiff + 1) + 1));

falsch ist.

Ich müsste floor(x*2+log_10(x)+1) für x lösen, was eine Herausforderung darstellt, siehe hier: https://www.wolframalpha.com/input?i=solve+floor(x*2%2Blog_10(x)%2B1)+for+x

Mein Mathe-Skills sind nicht so gut, um das umzusetzen. Hättest du eine Idee?

Vereinfacht gesagt, kann ich dann über die String-Längendifferenz bestimmen, wie oft verdoppelt wurde.

Schlangenmensch

Um ehrlich zu sein, verstehe ich nicht, was du wie berechnen willst, wie du auf den Term kommst und nach was du das auflösen möchtest.

@Schlangenmensch sagte in Zeichen rekursiv verdoppeln und "zählen":

Ich habe keine Ahnung woher du solche Sachen hast (wenn du die Sachen dir nicht ausgedacht hast, wären Quellen nett)

Die Frage wurde in dem anderen Forum von thomas_tom gestellt, aber ich habe sie leicht abgewandelt.

@Schlangenmensch sagte in Zeichen rekursiv verdoppeln und "zählen":

Um ehrlich zu sein, verstehe ich nicht, was du wie berechnen willst, wie du auf den Term kommst und nach was du das auflösen möchtest.

Verstehe ich im Moment auch nicht mehr, werde morgen nochmal schauen.

So, ich habe eine "allgemeine"/"generalisierte" Lösung gefunden.

import java.util.HashMap;

public class Doubly {
    public static String doubly(final String s, final char c) {
        if (s.length() > 0) {
            if (s.charAt(0) == c) {
                HashMap<Integer, Integer> map = new HashMap<>();
                map.put(2, 1);
                for (int j = 1; j <= 4; j++) {
                    int n0 = (int) Math.pow(10, j - 1);
                    int n1 = (int) Math.pow(10, j);
                    int i = n0;
                    for (; i < n0 + j; i++) {
                        int x = ((int) (i * 2 + Math.log10(i)) + 3 - j) / 2;
                        if (!map.containsKey(x)) {
                            map.put(x, j - 1);
                        }
                    }
                    for (; i < n1; i++) {
                        int x = ((int) (i * 2 + Math.log10(i)) + 3 - j) / 2;
                        if (!map.containsKey(x)) {
                            map.put(x, j);
                        }
                    }
                }
                //System.out.println("map = " + map);

                int len1 = s.length();
                String s1 = "" + c + c + doubly(s.substring(1), c);
                int len2 = s1.length();
                int lenDiff = len2 - len1;
                if (lenDiff > 0) {
                    int x = map.get(lenDiff);
                    //System.out.println(lenDiff + " " + x);
                    int n = Integer.parseInt(s1.substring(s1.length() - x));
                    return s1.substring(0, s1.length() - x) + (n + 1);
                }
                return s1;
            }
            return "" + s.charAt(0) + doubly(s.substring(1), c);
        }
        return "0";
    }

    public static void main(final String[] args) {
        String s = "0cac1c";
        for (int i = 2; i <= 1010; i++) {
            s += "a";
            String s2 = doubly(s, 'a');
            System.out.println("Expected: " + i + ", actual: " + s2.substring(s2.length() - (int) Math.log10(i) - 1));
            if (!String.valueOf(i).equals(s2.substring(s2.length() - (int) Math.log10(i) - 1))) {
                System.out.println("ERROR");
                return;
            }
        }
    }
}

Meine Frage wäre ... Wie man, anstatt eine HashMap zu verwenden, Zeile 7 bis 26 in eine geschlossene Formel umwandeln könnte...

Aber erst mal kann ich beruhigt schlafen.

Schlangenmensch

@NoIDE sagte in Zeichen rekursiv verdoppeln und "zählen":

durch Rekursion, nicht durch Schleifen

und, wie passt deine Lösung zu deinen eigenen Anforderungen? Wenn du Schleifen zulässt kannst du gleich am Schluss die Anzahl an chars c zählen und durch 2 teilen.
Davon abgesehen, sieht das: for (int j = 1; j <= 4; j++) nicht nach einer "allgemeinen"/"generalisierten" Lösung aus.

@Schlangenmensch sagte in Zeichen rekursiv verdoppeln und "zählen":

und, wie passt deine Lösung zu deinen eigenen Anforderungen?

Das "Verdoppeln" soll nicht durch Schleifen geschehen... Zudem ist die map quasi nur eine Hilfsvariable...

@Schlangenmensch sagte in Zeichen rekursiv verdoppeln und "zählen":

Davon abgesehen, sieht das: for (int j = 1; j <= 4; j++) nicht nach einer "allgemeinen"/"generalisierten" Lösung aus.

Für mehr als i=10 000 Rekursionstiefe, macht das aber keinen Sinn mehr.

Theoretisch könnte man für die 4 einen beliebig hohen Wert wählen.

Btw... Zeile 14 und Zeile 20 kann noch etwas vereinfacht werden:

int x = ((int) Math.log10(i) + i * 2 + 3 - j) / 2;

das ist mir gestern nicht mehr aufgefallen...

und dann steht da ja quasi: x=floor((floor(log_10(i))+i2+3-j)/2).

https://www.wolframalpha.com/input?i=solve+x%3Dfloor((floor(log_10(i))%2Bi2%2B3-j)%2F2)+for+i da kommt eine Stufenebene raus (Treppe)

Schlangenmensch

@NoIDE sagte in Zeichen rekursiv verdoppeln und "zählen":

Das "Verdoppeln" soll nicht durch Schleifen geschehen

Damit wird's halt einfach. Dann weiß ich auch nicht, was dein "Versuch" mit dem Beweis sollte.

Und, auch wenn für deinen Anwendungsfall hier die 4 ausreicht, ist, egal welche Zahl da steht, das nicht "allgemeingültig". Sowas führt dann am Ende zum Year 2038 Problem

@Schlangenmensch sagte in Zeichen rekursiv verdoppeln und "zählen":

Damit wird's halt einfach. Dann weiß ich auch nicht, was dein "Versuch" mit dem Beweis sollte.

a) ich weiß nicht genau, ob der Beweis "richtig" ist, und
b) ich weiß auch nicht mehr genau, was ich da beweisen wollte.

@Schlangenmensch sagte in Zeichen rekursiv verdoppeln und "zählen":

Und, auch wenn für deinen Anwendungsfall hier die 4 ausreicht, ist, egal welche Zahl da steht, das nicht "allgemeingültig".

Deshalb war ja eigentlich die Frage nach der Formel.

@admin und @Mod kann dieses Thema nicht gelöscht werden, bitte? Es stellt doch offenbar für viele ein Ärgernis dar.

Edit: Also, nicht nicht... Bitte löschen.