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

Martin Möllenbeck Martin.Moellenbeck at t-online.de
Die Feb 10 18:32:27 CET 2004


Hallo,

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):
>  
>
hier sollte ein "xrange" verwendet werden, da nicht erst die gesamte 
liste der zahlen im
speicher zur verfügung gestellt wird, sondern nur die angeforderten.

>  rounds = 1
>  
>  while number>1:
>    if number % 2 == 0:
>      number = number/2
>      rounds = rounds+1
>    else:
>      number = 3*number+1
>      rounds = rounds+1
>  total_rounds.append(rounds)
>  total_rounds.sort()
>print total_rounds[len(total_rounds)-1]
>#v-
>
>Wenn hier nun spasseshalber alle Zahlen von 1 bis zur in der Aufgabe
>gegebenen Obergrenze von 1.000.000 berechnen lasse, dauert das auf
>meinem Rechner (AMD Athlon 1 GHz) etwas über 20 Stunden. Das Äquivalent
>in C hingegen:
>
>#v+
>#include <stdio.h>
>#include <stdlib.h>
>
>#define MAX 1000000
>
>int main(void)
>{
>   int i, max=0, imax;
>   
>   for (i=1; i <= MAX; ++i) {
>      register long long z=i;
>      register int cnt=1;
>      while (z != 1) {
>	 if (z % 2 == 0)
>	   z /= 2;
>	 else
>	   z = 3*z+1;
>	 
>	 ++cnt;
>      }
>      
>      if (cnt > max) {
>	 max = cnt;
>	 imax = i;
>      }
>   }
>   
>   printf("Max bei %d mit %d Schritten\n", imax, max);
>   
>   return EXIT_SUCCESS;
>}
>#v-
>
>benötigt für selbigen Durchlauf nur 2-3 Sekunden.
>
>Bis auf die fehlenden Eingaberoutinen im C-Programm sind beide Programme
>IMHO äquivalent (Meine ich zumindest). Wo könnte hier das Problem
>liegen, dass die Python-Variante derart langsamer ist?
>  
>
mfg
Martin