Fibonaccis talföljd

Detta är en tråd med det klassiska "läxa till imorgon" -motivet..

Uppgiften vi fått är att skriva ett program som fyller en vektor med 25 platser med Fibonaccis talföljd.

Fn = Fn-1 + Fn-2 då n>=3...

men jag förstår inte riktigt hur jag ska gå till väga.. Har testat söka på google men de lösningar jag hittat har för komplicerade medel att nå lösningen; läxan är bara till för att kontrollera att vi fattat det där med vektorer (som jag alltså inte är 100 på:))

Vart exakt kör du fast?

Lite seudo-kod:

public int fib(i){
	om i = 0 return 1
	om i = 1 return 1
	annars return fib(i-1) + fib(i-2)
}

public void fibArray() {
	initiera vektor
	loop i = 1 till 25
		lägg till  talet fib(i) till vektor
}

Gein skrev:

Vart exakt kör du fast?

Lite seudo-kod:

public int fib(i){
	om i = 0 return 1
	om i = 1 return 1
	annars return fib(i-1) + fib(i-2)
}

public void fibArray() {
	initiera vektor
	loop i = 1 till 25
		lägg till  talet fib(i) till vektor
}

Fast det där är ingen vidare bra lösning, eftersom det tar kvadratisk tid. Det är lätt att göra om det till att använda linjär tid, genom att utnyttja de tidigare uträknande Fibonacci-talen.

public int[] getFibonaccis(int numberOfFibonaccis) {
	int[] fibonaccis = int[numberOfFibonaccis];
	int i = 0;
	
	while(i < numberOfFibonaccis) {
		if (i == 0)
			fibonaccis[i] = 0;
		else if (i == 1)
			fibonaccis[i] = 1;
		else
			fibonaccis[i] = fibonaccis[i-1] + fibonaccis[i-2];
	}

	return fibonaccis;
}

Med risk att jag har använt fel syntax någonstans.

Gein skrev:

Vart exakt kör du fast?

Lite seudo-kod:

public int fib(i){
	om i = 0 return 1
	om i = 1 return 1
	annars return fib(i-1) + fib(i-2)
}

public void fibArray() {
	initiera vektor
	loop i = 1 till 25
		lägg till  talet fib(i) till vektor
}

Vi har i princip inte använt oss av något av det du säger, detta är så låg nivå som programmering a:)

Dectgaps ser bättre ut, men du verkar inte tagit med att det minsta värdet för n är 3?

shun skrev:

Dectgaps ser bättre ut, men du verkar inte tagit med att det minsta värdet för n är 3?

Släng in en if-sats som tar hand om det bara, så löser det sig.

public int[] getFibonaccis(int numberOfFibonaccis) {
	if(numberOfFibonaccis <= 0)
		return;

	int[] fibonaccis = int[numberOfFibonaccis];

Vill du göra det snyggare slänger du en Exception istället för att bara använda return, men om ni inte har läst något om det är det kanske bara överkurs.

Att jag skriver

if(numberOfFibonaccis <= 0)

istället för

if(numberOfFibonaccis <= 2)

beror på att Fibonacci-talen är definierade även för n=1 och n=2, och kommer att behandlas korrekt av metoden. Skillnanden mellan det första och det tjugonde Fibonacci-talet är att det första är definierat som ett basfall (F(1) = 0), medan det tjugonde är definierat rekursivt (F(20) = F(19) + F(18)).

Det blev mycket på en gång för trötta mig, men hur skulle koden se ut när man är klar med att ha "slängt in if-satsen"?

public int[] getFibonaccis(int numberOfFibonaccis) {
	if(numberOfFibonaccis <= 0)
		return;

	int[] fibonaccis = int[numberOfFibonaccis];
	int i = 0;
	
	while(i < numberOfFibonaccis) {
		if (i == 0)
			fibonaccis[i] = 0;
		else if (i == 1)
			fibonaccis[i] = 1;
		else
			fibonaccis[i] = fibonaccis[i-1] + fibonaccis[i-2];
	}

	return fibonaccis;
}

Jag var nog lite otydlig innan, men den ska fylla 25 platser i en vektor, och börja med n=3..

Men getFibonaccis, vad är det? Tror inte vi använt oss av det än:/

shun skrev:

Jag var nog lite otydlig innan, men den ska fylla 25 platser i en vektor, och börja med n=3..

Men getFibonaccis, vad är det? Tror inte vi använt oss av det än:/

edit- lägger till en bild. Förstår inte riktigt hur läraren tänkt, ska talföljdens början se ut som den han skrivit eller ska den börja med n=3? (eller båda? jisses)

Till att börja med:
Menar du en vektor eller en array? Jag gissar att du menar array, men det finns nämligen en inbyggd Java-klass som heter Vector.

shun skrev:

Men getFibonaccis, vad är det? Tror inte vi använt oss av det än:/

Det är en metod som jag skrev, som är tänkt att man sedan ska använda.

Om du vill fylla arrayn med 25 platser anropar du metoden med 25 som argument:

getFibonnacis(25);

shun skrev:

och börja med n=3..

Det enklaste vore nog att skapa en array med två platser mer än vad som behövs, och när man ska returnera arrayn tar man bort de två första platserna.

Eller så kan man förresten göra så här:

public int[] getFibonaccis(int numberOfFibonaccis) {
	if(numberOfFibonaccis <= 0)
		return;

	int[] fibonaccis = int[numberOfFibonaccis];
	int i = 0;
	
	while(i < numberOfFibonaccis) {
		if (i == 0)
			fibonaccis[i] = 1;
		else if (i == 1)
			fibonaccis[i] = 2;
		else
			fibonaccis[i] = fibonaccis[i-1] + fibonaccis[i-2];
	}

	return fibonaccis;
}

Vi förskjuter helt enkelt talföljden två steg, så stämmer det enligt dina instruktioner.
Kanske inte världens snyggaste sätt, men det är enkelt både ur programmeringssynpunkt och för datorn att beräkna.

shun skrev:

shun skrev:

Jag var nog lite otydlig innan, men den ska fylla 25 platser i en vektor, och börja med n=3..

Men getFibonaccis, vad är det? Tror inte vi använt oss av det än:/

edit- lägger till en bild. Förstår inte riktigt hur läraren tänkt, ska talföljdens början se ut som den han skrivit eller ska den börja med n=3? (eller båda? jisses)

Enligt de instruktionerna ska det vara som i den förra metoden jag skrev. Inte som i inlägget direkt före detta alltså.

Var är public class namnpåfil{.. i början? Mina kunskaper är något begränsade;)

shun skrev:

Var är public class namnpåfil{.. i början? Mina kunskaper är något begränsade;)

Det får du själv skriva dit.
Jag skrev bara hur du kan skriva en metod som räknar ut Fibonacci-tal.

public class fibfibfib{
	public static void main(String[] args){
		int fib[] = new int[25];

		fib[0] = 0;
		fib[1] = 1;
		
		System.out.println(fib[0]);
		System.out.println(fib[1]);
		
		for(int i=2; i<25; i++) {
			fib[i] = fib[i-1]+fib[i-2];
			System.out.println(fib[i]);
		}
	}
}