Schleifen durchläufe bestimmen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:15 Fr 23.04.2010 | | Autor: | cheerio |
| Aufgabe | Es sind alle Zuweisungen (in der Art: x=y) in abhängigkeit von n zu geben.
i=1
j=0
while(i<=n)
{
i=i+1
j=i
while(j<=n)
{
j=j*i
}
} |
Meine Frage bezieht sich auf die innere Schleife.
Ich habe für den Rest: 2+2*n+?
wobei sich das ? auf die Anzahl der Schleifendurchläufe der inneren Schleife bezieht.
Hier ein kleiner Auszug der schleifendurchläufe von "while(j<=n)" in bezug auf n:
n=0 -> 0
n=1 -> 0
n=2 -> 1
n=3 -> 2
n=4 -> 4
n=5 -> 5
n=6 -> 6
n=7 -> 7
n=8 -> 9
n=9 -> 11
n=10 -> 12
n=11 -> 13
n=12 -> 14
n=13 -> 15
n=14 -> 16
n=15 -> 17
n=16 -> 20
n=17 -> 21
n=18 -> 22
n=19 -> 23
n=20 -> 24
n=21 -> 25
n=22 -> 26
n=23 -> 27
n=24 -> 28
n=25 -> 30
n=26 -> 31
n=27 -> 33
n=28 -> 34
n=29 -> 35
n=30 -> 36
n=31 -> 37
n=32 -> 39
n=33 -> 40
n=34 -> 41
n=35 -> 42
n=36 -> 44
n=37 -> 45
n=38 -> 46
n=39 -> 47
n=40 -> 48
n=41 -> 49
n=42 -> 50
n=43 -> 51
n=44 -> 52
n=45 -> 53
n=46 -> 54
n=47 -> 55
n=48 -> 56
n=49 -> 58
n=50 -> 59
n=51 -> 60
n=52 -> 61
n=53 -> 62
n=54 -> 63
n=55 -> 64
n=56 -> 65
n=57 -> 66
n=58 -> 67
n=59 -> 68
n=60 -> 69
n=61 -> 70
n=62 -> 71
n=63 -> 72
n=64 -> 76
n=65 -> 77
n=66 -> 78
n=67 -> 79
n=68 -> 80
n=69 -> 81
n=70 -> 82
n=71 -> 83
n=72 -> 84
n=73 -> 85
n=74 -> 86
n=75 -> 87
n=76 -> 88
n=77 -> 89
n=78 -> 90
n=79 -> 91
n=80 -> 92
n=81 -> 95
n=82 -> 96
n=83 -> 97
n=84 -> 98
n=85 -> 99
n=86 -> 100
n=87 -> 101
n=88 -> 102
n=89 -> 103
n=90 -> 104
n=91 -> 105
n=92 -> 106
n=93 -> 107
n=94 -> 108
n=95 -> 109
n=96 -> 110
n=97 -> 111
n=98 -> 112
n=99 -> 113
n=100 -> 115
Welche möglichkeit habe ich dieses nicht lineare verhalten abhängig von 'n' darzustellen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo cheerio,
> Es sind alle Zuweisungen (in der Art: x=y) in abhängigkeit
> von n zu geben.
>
> i=1
> j=0
> while(i<=n)
> {
> i=i+1
> j=i
> while(j<=n)
> {
> j=j*i
> }
> }
Die innere Schleife wird solange ausgeführt bis [mm]i^{\left\lfloor\log_i n\right\rfloor}=n[/mm]. D.h. die innere Schleife wird [mm]\left\lfloor\log_i n\right\rfloor\texttt{-mal}[/mm] ausgeführt.
Die äußere Schleife wird [mm]n-1\texttt{-mal}[/mm] ausgeführt mit [mm]i=2,\dotsc,n[/mm]: [mm]\textstyle\sum_{i=2}^n{\left\lfloor\log_i n\right\rfloor}[/mm]. Für [mm]i=n\![/mm] wird eigentlich nur der Schleifenkopf der inneren Schleife ausgeführt. Aber auch dieser Spezialfall wird in der obigen Summe berücksichtigt, denn [mm]\left\lfloor\log_n n\right\rfloor=1[/mm]; Und die äußere Schleife wird bei diesem Spezialfall trotzdem einmal ausgeführt.
Viele Grüße
Karl
|
|
|
|
