kostenloser Webspace werbefrei: lima-city

Terminiert diese Schleife?

lima-city → Forum → Programmiersprachen → C/C++ und D

1. Autor dieses Themas

   c****s

   1:07, 2.6.2009

   Das Problem ist wohl eher mathematischer Natur, aber kann mir jemand zeigen ob folgende Schleife für beliebige Werte für a terminiert?
   
   

   unsigned int a = 7; // 7 nur als Beispiel
   
   for (; a - 1; a = (a % 2) ? (a * 3 + 1) : (a / 2) )
       printf ("%i\r\n", a);

   
   
   Erzeugt zum Beispiel für 7 die Folge:
   7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2
   
   
   Beitrag zuletzt geändert: 2.6.2009 1:14:46 von census

2. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

3. kochmarkus

   Co-Admin

   kochmarkus hat kostenlosen Webspace.

   2:38, 2.6.2009

   ttobsen schrieb:
   Hi
   
   Ich verstehe diese Zeile nicht ganz.
   
   (a % 2) ? (a * 3 + 1) : (a / 2)
   
   Soll dass bedeuten:
   
   Falls a nicht durch 2 teilbar ist dann mache a * 3 + 1 sonst a / 2 ?
   

   
   Stimmt.
   
   

   
   Ich seh hier auch irgendwie keine Abbruchbedingung. ich denke mal das soll a-1 sein. Also abbrechen wenn a-1 erfüllt ist?
   

   
   Abgebrochen wird, wenn a == 1, dann wird a-1 gerechnet was 0 ergibt und somit die for-Schleife abgebrochen.
   
   

   
   Edit: Gibt es irgendwelche Einschränkungen für a? Z.B. nur natürliche Zahlen? So dürften sie ja rein theoretisch auch negativ sein (oder sogar reell).
   

   
   Die Deklaration der Variable a lautet unsigned int. Also nur ganze positive Zahlen und 0.
   
   Und um auch was zum eigentlichen Thema zu sagen, dass ist auch meiner Meinung nach eher ein mathematisches Problem. Man könnte aber auch eine zweite for Schleife um die vorhandene machen, welche für a alle Zahlen von 2 bis (UINT_MAX-1)/3 testet. Bei 1 wird die for Schleife überhaupt erst gar nicht ausgeführt und bei größeren Zahlen als (UINT_MAX-1)/3 bekommst du einen Überlauf der Variable. Das Programm kannst du dann mal über Nacht laufen lassen und wenn es sich irgendwann beendet, dann weißt du, dass alle Zahlen zulässig sind.
   
   UINT_MAX ist übrigens in der <limits.h> definiert.
   
   €dit: 0 ist übrigens auch nicht zulässig als Startwert, wegen a-1 in der for Schleife.
   
   €dit2: ein kleines Testprogramm:
   

   #include <stdio.h>
   #include <limits.h>
   
   int main(void)
   {
     unsigned int a,curr,max;
     
     max=(UINT_MAX-1)/3;
   
     for(curr=2;curr<=max;++curr)
     {
       a=curr;
       if(!(a%1000))
         printf("a=%u\t%f percent done\n",a,(float)a/max*100);
       for(; a-1; a=(a%2)?(a*3+1):(a/2));
     }
     printf("DONE!\n");
   }

   
   
   Beitrag zuletzt geändert: 2.6.2009 15:15:12 von kochmarkus

4. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?