Metode som multipliserer alle tallene fra 1 til n

[x-ray-cat]

Noen som vet hvordan man lager en metode som multipliserer alle tallene fra 1 til n?

[_Xorcist]

Du lager en løkke som løper fra 1 til n og multipliserer sammen alle tallene underveis.

[icebyte]

Du kan vel for eksempel lage en metode som vist her:

 

void multipliser(int x) {
int resultat=0;

for (int i=0; i<x; i++) {
resultat = x*i;
System.out.println(i + " * " + x + " = ", resultat);
}
}

Endret 1. oktober 2006 av icebyte

[pgdx]

Fakultet?

 

Noe ala dette?

 

int sum = 1;

int fakultet = 10;

for (int i = 1; i <= fakultet; i++) {

sum = sum * i;

}

Endret 1. oktober 2006 av drange

[Mr.Garibaldi]

static int fak(int x, int n){
if(n == 1){
   return x;
 }else{
   return fak(x*n ,n-1);
 }
}

public static void main(String[] args){
 System.out.println("Fak 8 = " + fak(1, 8));
}

 

Nå også i fungerende form...

Endret 7. oktober 2006 av Mr.Garibaldi

[pgdx]

Hvorfor tar fak() to parametre? Den trenger bare en!

 

8! er alltid 8x7x6x5x4x3x2x1

[_Xorcist]

Den trenger vel begge parameterne for å kunne fungere rekursivt såvidt jeg kan se.

[toddy23]

Halerekursjon er en uting og bør ikke brukes. Men bare på gøy lager jeg en, som dere ser bruker fakRek bare en parameter

Ikke rekursiv

public class Fak{

static int fak(int n){
 for(int i = n; i > 2; n*=--i);
 return n;
}

static int fakRek(int n){
 return n == 1 ? n : n * fakRek(n-1);
}

public static void main(String[] args){
 System.out.println("Fak 8 = " + fak(8) + " = " + fakRek(8));
}
}

 

edit: la til den rekursive løsningen

Endret 2. oktober 2006 av toddy23

[qualbeen]

 return n == 1 ? n : n * fakRek(n-1);

6985240[/snapback]

har ikke så mye med hva trådstarter spurte etter, men har ved flere anledninger sett folk bruke den kortformen med spørsmålstegn og kolon, som du har over her. Gidder noen forklare meg hvordan den virker?

 

Er det en kortform for if(betingelse) gjørNoe(); else gjørNoeAnnet();

eller der det helt feil?

[_Xorcist]

 return n == 1 ? n : n * fakRek(n-1);

6985240[/snapback]

har ikke så mye med hva trådstarter spurte etter, men har ved flere anledninger sett folk bruke den kortformen med spørsmålstegn og kolon, som du har over her. Gidder noen forklare meg hvordan den virker?

 

Er det en kortform for if(betingelse) gjørNoe(); else gjørNoeAnnet();

eller der det helt feil?

6986316[/snapback]

 

Ja,

 

betingelse ? true : false

[toddy23]

nesten riktig den fungerer som følger

 

variable = (boolsk uttrykk) ? (hvis true tilordne denne) : (hvis false tilordne denne)

 

bare tenkte jeg skulle lage 2 eksempler som regner ut fakultet som fungerer. Mr.garabaldis kode kompilerer ikke og er et dårlig eksempen på en rekursiv metode, men som sagt ikke finn på å bruke min rekursive metode heller, det beste ang ytelse er å skrive noe som ligner på den for løkken jeg laget.

 

Ps. trådstarter spurte jo etter en metode som multipliserer sammen tallene fra 1 til n. Begge metodene mine gjør det.

[_Xorcist]

nesten riktig den fungerer som følger

 

variable = (boolsk uttrykk) ? (hvis true tilordne denne) : (hvis false tilordne denne)

6986922[/snapback]

 

Dette blir litt OT, men man trenger ikke nødvendigvis å tilordne en variabel, kanskje man vil kalle to ulike metoder eller kaste en exception:

 

Object o = getObject();
o != null ? performOperation(o) : throw new IllegalArgumentException("o kan ikke være null");

Endret 3. oktober 2006 av _Xorcist

[toddy23]

stemmer du har rett, man trenger ikke bruke returverdien av en ? : man kan kalle slik du har vist

[Mr.Garibaldi]

bare tenkte jeg skulle lage 2 eksempler som regner ut fakultet som fungerer. Mr.garabaldis kode kompilerer ikke og er et dårlig eksempen på en rekursiv metode, men som sagt ikke finn på å bruke min rekursive metode heller, det beste ang ytelse er å skrive noe som ligner på den for løkken jeg laget.

 

Flaut, men sant. Var noen skrivefeil, samt glemte return på det rekursive kallet.

(Og static på metoden om du bare brukte den uten å instansiere klassen den ble lagt i) Sånn kan det gå når man koder rett i svar-vinduet samtidig som man er på vei i seng...

 

OT: Dog lurere jeg litt på hvorfor du sier man ikke skal bruke "halerekursjon", siden det bruker mindre minne enn annen type rekursjon. Har snarere fått beskjed om at det er bedre å bruke i mange tilfeller. F.eks her...

[toddy23]

Grunnen til at man ikke bør bruke halerekursjon er at de kan skrives om til løkker og løkker bruker mye mindre minne enn rekursjon. Hver gang en ny metode kalles via rekursjon må variablene dyttes på stakken. Det trengs ikke i en løkke.

Nedenfor har jeg pastet en link til wikipedia som forklarer litt mer detaljert hvorfor.

 

Wp:Tail recursion

[steingrim]

Grunnen til at man ikke bør bruke halerekursjon er at de kan skrives om til løkker og løkker bruker mye mindre minne enn rekursjon.

En god kompilator burde klare å detektere halerekursjon og generere den samme koden. Dette er forholdsvis grunnleggende kompilator-optimalisering.

 

Det finnes språk som ikke har konstruksjoner for løkker, der standarden krever at halerekursjon skal optimaliseres. Scheme er et eksempel på et slikt språk.

[toddy23]

Grunnen til at man ikke bør bruke halerekursjon er at de kan skrives om til løkker og løkker bruker mye mindre minne enn rekursjon.

En god kompilator burde klare å detektere halerekursjon og generere den samme koden. Dette er forholdsvis grunnleggende kompilator-optimalisering.

 

Det finnes språk som ikke har konstruksjoner for løkker, der standarden krever at halerekursjon skal optimaliseres. Scheme er et eksempel på et slikt språk.

7011883[/snapback]

Send en mail til Sun da, java 5.0 optimerer ikke bort halerekursjon, bare test løsningsforslaget mitt ovenfor. Hos meg brukte maskinen over dobbelt så lang tid på å bruke halerekursjonen i forhold til den med løkken og det ved bare 19 rekursive kall. Jeg vil anta at forskjellen vil bli større jo flere kall som blir gjort. Hvis du vil motbevise påstanden min ovenfor om bruk av minne og kjøretid, kan du legge ut et eksempel som jeg kan kjøre.

 

Foresten heter slike språk som du refferer til Funksjonelle språk, og der er man tvunget til å benytte rekursjon for løkker. Har selv programmert ml som også er et funksjonellt språk. Føler foresten at hele diskusjonen har vandret ganske langt bort fra tråden.

[pgdx]

Prøvd å kompilere det med GCJ?

[toddy23]

Har nå prøvd å kompilere med gcj, jeg ser fortsatt at den rekursive bruker ca 2 ganger mer tid.

Med mindre jeg har gjort en blunder i koden, tror jeg dere må gi dere på denne. Testen nedenfor er kjørt på en 2.4 p4 med ubuntu

 

Java 5 sun

javac Fak.java

:~java Fak

1091 2495

:~$ java Fak

1093 2411

:~$ java Fak

1090 2416

:~$ javac -O Fak.java

:~$ java Fak

1092 2493

:~$ java Fak

1090 2409

:~$ java Fak

1089 2411

 

Gcj

:~$ gcj-4.1 --main=Fak Fak.java

:~$ ./a.out

3276 4606

:~$ ./a.out

3294 4597

:~$ ./a.out

3294 4591

:~$ gcj-4.1 --main=Fak -O2 -g0 Fak.java

:~$ ./a.out

883 2214

:~$ ./a.out

884 2213

:~$ ./a.out

885 2215

 

Fak.java

public class Fak{

       static int fak(int n){
               for(int i = n; i > 2; n*=--i);
               return n;
       }

       static int fakRek(int n){
               return n == 1 ? n : n * fakRek(n-1);
       }

       public static void main(String[] args){
               long result1 = 0, result2 = 0;
               long start;

               start = System.currentTimeMillis(); 
               for(int i = 0; i < 10000000;i++) fak(19);
               result1 += System.currentTimeMillis() - start;

               start = System.currentTimeMillis(); 
               for(int i = 0; i < 10000000;i++) fakRek(19);
               result2 += System.currentTimeMillis() - start;

               System.out.println(result1 + " " + result2);
       }
}

Endret 6. oktober 2006 av toddy23

[Mr.Garibaldi]

Har nå prøvd å kompilere med gcj, jeg ser fortsatt at den rekursive bruker ca 2 ganger mer tid.

Med mindre jeg har gjort en blunder i koden, tror jeg dere må gi dere på denne. Testen nedenfor er kjørt på en 2.4 p4 med ubuntu

 

7016438[/snapback]

 

Men nå bruker jo ikke koden din tail-recursion, men vanlig rekursjon.

Siste operasjon i koden din er gangeoperasjonen "n * fakRek(n-1)", ikke kallet "fakRek", noe som gjør at koden din ikke oppfyller kravene til tail-recursion.

 

Note that the tail call doesn't have to literally appear after all other statements in the source code; it is only important that its result be immediately returned

(Min utheving i halvfet)

When a function is called, the computer must "remember" the place it was called from, the return address, so that it can return to that location with the result once the call is complete. Typically, this information is saved on the stack, a simple list of return locations in order of the times that the call locations they describe were reached. Sometimes, the last thing that a function does after completing all other operations is to simply call a function, possibly itself, and return its result. But in this case, there is no need to remember the place we are calling from — instead, we can leave the stack alone, and the newly called function will return its result directly to the original caller.

(Min utheving i halvfet)

 

Because tail recursion is equivalent to

iteration, tail-recursive programs can be compiled as efficiently as

iterative programs.

 

[EDIT] Til Drange;

Den bruker 2 parametre for at den skal være tail-recursive, slik at den ikke skal bruke masse plass. Ellers får du problemet toddy23 snakker om

[/EDIT]

Endret 7. oktober 2006 av Mr.Garibaldi