[Python-de] [Python vs. C] 3n+1-Problem

[daniel.poelzleithner]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Jens Kubieziel wrote:
| Hallo,
|
| ich habe mir kürzlich diverse Programmieraufgaben der Universidad da
| Valladolid (http://acm.uva.es) angeschaut und u.a auch
| http://acm.uva.es/p/v1/100.html.
|
| Hierbei wird das 3n+1-Problem (teile eine Zahl solange durch zwei, wenn
| sie gerade ist oder, falls nicht, multipliziere mit drei und addiere
| eins, bis man eins erreicht.) vorausgesetzt. Wenn z.B. 3 eingegeben
| wird, entsteht die Folge: 3 10 5 16 8 4 2 1. Aufgabe ist nun, in einem
| einzugebenden Intervall die Anzahl aller Folgenglieder (im obigen Bsp.
| 8) zu errechnen und auszugeben.
|
| Dies habe ich zunächst mit folgendem Brute-Force-Ansatz probiert:
|
| #v+
| i = int(raw_input("Please enter the lower boundary: "))
| j = int(raw_input("Please enter the upper boundary: "))
|
| total_rounds = []
|
| print i,j,
| for number in range(i,j+1):

xrange benutzt einen generator und verbraucht weniger speicher. Ich
würde aber eine while schlaufe benutzten, die währe aquivalent zu deiner
for schleife in c

|   total_rounds.append(rounds)
|   total_rounds.sort()

wo sind diese beiden zeilen in deinem c programm ?
Beide funktionen sind sehr sehr speicher und rechenzeit intensiv.


| print total_rounds[len(total_rounds)-1]
du erzeugst das riesige array nur um den letzten wert zu bekommen, da
hätte es auch ein print rounds getan.


#!/usr/bin/python -OO

i = int(raw_input("Please enter the lower boundary: "))
j = int(raw_input("Please enter the upper boundary: "))

print i,j,
rounds = 1
maxr = 0
maxi = 0

while i < j:
	n = i
	rounds = 0
	while n > 1:
		if n % 2 == 0:
			n = n/2
		else:
			n = 3*n+1
		rounds += 1
	if rounds > maxr:
		maxr = rounds
		maxi = i
	#print i," runs:", rounds
	i += 1
print "max bei %i mit %i runden" %(maxi, maxr)


Das kommt dem c programm näher.
Noch angemerkt:
Das C Programm benutzt register Variablen, ist also direkt im cpu L2
(oder wars L1 ?) Speicher, das ist natürlich nicht zu vergleichen.

[poelzi at cruor]> tmp/  ./n3+1.py
Please enter the lower boundary: 1
Please enter the upper boundary: 1000000
1 1000000 max bei 837799 mit 524 runden

Hat etwa 3 minuten gedauert :)

Gruß
~ Daniel


- --
nihil me cirumdat

.. . .. ... . . .. . ... . .. . ... . . .
pgp key @ http://files.poelzi.org/pgp.txt
ED80 E53D 5269 4BB1 1E73 3A53 CBF9 A421 0A7B 003D
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
Comment: Using GnuPG with Debian - http://enigmail.mozdev.org

iD8DBQFAKRety/mkIQp7AD0RAgksAJ9zNsHrgEbUrOvzK2RRE6JUxjU3JACfe4Qz
G4IQCfwB1imjuJ2gBEKzleE=
=j/Nu
-----END PGP SIGNATURE-----