1er-Zählung in den Zahlen bis n

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Dagon
User
Beiträge: 6
Registriert: Donnerstag 9. Februar 2006, 22:03

Hi Leute,
wie es die Überschrift schon sagt versuche ich eine Funktion zu entwickeln, die die Häufigkeit der Ziffer 1 in den Zahlen von 1 bis n berechnet. Ich hatte mir den Ansatz überlegt erstmal alle Zahlen von 1-n in eine Liste zu schreiben:

Code: Alles auswählen

 liste = []
 x = 0
 while x < n:
     x = x+1
     liste.append(x)
Nur habe ich da zwar jetzt alle Zahlen drin, doch mir fehlt einfach die zündende Idee wie ich nun die 1en zählen kann. Natürlich könnte ich theoretisch einfach nach 1,10,11,12 etc. suchen lassen, aber das ist ja nicht Sinn der Sache. Wäre schön wenn mir da wer helfen könnte.
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Wenn du die Zahlen als Strings in speicherst, kannst du mit

Code: Alles auswählen

if "1" in einString
rausfinden, ob eine 1 enthalten ist.
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Mit anderen Worten:

Code: Alles auswählen

 if "1" in str(125): print "drin"
Dagon
User
Beiträge: 6
Registriert: Donnerstag 9. Februar 2006, 22:03

Ok jetzt hab ichs soweit:

Code: Alles auswählen

def eins(n):
 x=0
 a=0
 while x <= n:
     if "1" in str(x):
         a=a+1
     x=x+1
 print a
Aber jetzt besteht noch das Problem, dass bei einer 11 nur eine 1 gezählt wird und nicht beide. Da man n ja beliebeig wählen kann müsste auch 111 ls 3 1er 1111 als 4 1er etc. gezählt werden...
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Als One-Liner:

Code: Alles auswählen

sum(str(i).count("1") for i in range(1,n+1))
Und für die Häufigkeit dann logischerweise:

Code: Alles auswählen

sum(str(i).count("1") for i in range(1,n+1))/float(n)
Da das Ding Generator-Expressions benutzt geht es logischerweise nur unter Python 2.4...
--- Heiko.
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Das ganze geht noch ein Stückchen schneller (da der "einfache" Algorithmus den ich im letzten Post angegeben habe exponentiell skaliert aufgrund von str(x)) wenn man das Problem leicht abwandelt und sagt dass man die relative Häufigkeit einer (beliebigen) Ziffer in <=n-stelligen Zahlen berechnen will, dann kann man nämlich einfach:

r(z,n) = Summe(i=1,n,9^(n-i)*(n i)*i)/10^n

berechnen (wobei (n i) n über i bedeutet und r(z,n) die relative Häufigkeit der Ziffer ze{0-9} bei n>=1-stelligen Zahlen ist). Was man daraus sieht: alle Ziffern haben die selbe relative Häufigkeit, zumindest wenn man das Problem so wie oben leicht abwandelt.

Das ganze kann man mit Sicherheit noch weiter vereinfachen (der Term da oben sollte eine algebraische, also exakte Lösung haben die ohne Summe auskommt wenn mich nicht alles täuscht), aber da müßte ich nachgucken.

Die Implementierung des ganzen überlass ich mal Dir. ;-)
--- Heiko.
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Hier ein Beispielprogramm um das ganze auszurechnen:

Code: Alles auswählen

# -*- coding: iso-8859-15 -*-

import operator

def fak(n):
    if n in (0,1):
        return 1
    else:
        return reduce(operator.mul,range(1,n+1))

def comb(n,k):
    return fak(n)/(fak(k)*fak(n-k))

def r(n):
    return float(sum(9**(n-i)*comb(n,i)*i for i in range(1,n+1)))/10**n

for i in range(1,21):
    print ("Bei einer zufälligen Dezimalzahl mit <=%s Stellen"
           " im Schnitt %s mal die 1" % (i,r(i)))
Gibt eine lustige Ausgabe:

Code: Alles auswählen

modelnine@phoenix ~ $ python test.py
Bei einer zufälligen Dezimalzahl mit <=1 Stellen im Schnitt 0.1 mal die 1
Bei einer zufälligen Dezimalzahl mit <=2 Stellen im Schnitt 0.2 mal die 1
Bei einer zufälligen Dezimalzahl mit <=3 Stellen im Schnitt 0.3 mal die 1
Bei einer zufälligen Dezimalzahl mit <=4 Stellen im Schnitt 0.4 mal die 1
Bei einer zufälligen Dezimalzahl mit <=5 Stellen im Schnitt 0.5 mal die 1
Bei einer zufälligen Dezimalzahl mit <=6 Stellen im Schnitt 0.6 mal die 1
Bei einer zufälligen Dezimalzahl mit <=7 Stellen im Schnitt 0.7 mal die 1
Bei einer zufälligen Dezimalzahl mit <=8 Stellen im Schnitt 0.8 mal die 1
Bei einer zufälligen Dezimalzahl mit <=9 Stellen im Schnitt 0.9 mal die 1
Bei einer zufälligen Dezimalzahl mit <=10 Stellen im Schnitt 1.0 mal die 1
Bei einer zufälligen Dezimalzahl mit <=11 Stellen im Schnitt 1.1 mal die 1
Bei einer zufälligen Dezimalzahl mit <=12 Stellen im Schnitt 1.2 mal die 1
Bei einer zufälligen Dezimalzahl mit <=13 Stellen im Schnitt 1.3 mal die 1
Bei einer zufälligen Dezimalzahl mit <=14 Stellen im Schnitt 1.4 mal die 1
Bei einer zufälligen Dezimalzahl mit <=15 Stellen im Schnitt 1.5 mal die 1
Bei einer zufälligen Dezimalzahl mit <=16 Stellen im Schnitt 1.6 mal die 1
Bei einer zufälligen Dezimalzahl mit <=17 Stellen im Schnitt 1.7 mal die 1
Bei einer zufälligen Dezimalzahl mit <=18 Stellen im Schnitt 1.8 mal die 1
Bei einer zufälligen Dezimalzahl mit <=19 Stellen im Schnitt 1.9 mal die 1
Bei einer zufälligen Dezimalzahl mit <=20 Stellen im Schnitt 2.0 mal die 1
modelnine@phoenix ~ $
Die Vereinfachung sollte ja klar sein (also n/10), wobei ich da ehrlich gesagt auf jeden Fall noch mal nachschauen muß warum das so ist; das kann ich nicht mit Bestimmtheit sagen.
--- Heiko.
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

modelnine hat geschrieben:Als One-Liner:

Code: Alles auswählen

sum(str(i).count("1") for i in range(1,n+1))
Warum nicht gleich:

Code: Alles auswählen

"".join(map(str,range(1,n+1))).count("1")
Wird natürlich für große n unpraktisch.
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Wird natürlich für große n unpraktisch.
Jo, besonders weil die Stringlänge O(n*logn) wächst, und Du immer noch den Geschwindigkeitsnachteil hast O(a^n). Deswegen schrieb ich ja dass es sinnvoller ist sich ein bissel mit Kombinatorik zu befassen, da geht's dann nämlich in konstanter Zeit. ;-)
--- Heiko.
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Wieso O(a^n)? O(n)...

Natürlich würde man das einfach mit Kombinatorik lösen, es ging hier aber ja um einen Einzeiler
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Die Konvertierung einer Zahl in Binärdarstellung in Demizaldarstellung (also str(i)) ist O(a^logn). Deswegen sagte ich ja dass der Algorithmus nicht linear skaliert (wie man zuerst vermuten könnte wenn man einfach nur die Schleife sieht).
--- Heiko.
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Stimmt. Nicht nachgedacht.
Antworten