Fibonacci tallrekken

Hei, lenge siden jeg har sett noen programmering affære her inne.

Så jeg fikk lyst til å leke meg litt med fibonaccitall og vil dere skal være med.

Hoved regelen er å produsere fibonacci tallrekken.

Regler:

Du får selv velge språk
Du må være kreativ
Størrelse har ingenting å si, det er resultatet som teller.
Du må poste kode og output.
Du har lov til å poste så mange ganger du føler for det(Såklart i forskjellige språk, eller bedre løsninger)

Mitt bidrag blir en "Rekursiv" versjon av Fibonacci.

KODE:

Kode

#include "iomanip"
#include "iostream"
#include "conio.h"

using namespace std;

void fibonacci(int nummer1, int nummer2, int lengde)
{
	unsigned long sum;

	for(int n=0; n < lengde-1 ;n++)
	{
		if(n==0)
		cout << setw(5) << nummer1 << setw(5) << nummer2 << setw(5);
		else
		{
			sum=nummer1+nummer2;
			cout << sum << setw(5);
			nummer1=nummer2;
			nummer2=sum;
		}
	}
}

int main()
{
       fibonacci (  0 ,  1 , 10 ) ; cout << endl;
       fibonacci (  1 ,  1 , 10 ) ; cout << endl;
       fibonacci ( 10 , 11 , 10 ) ; cout << endl;
       fibonacci ( 15 , 16 , 10 ) ; cout << endl;

       _getche();
       return 0;
}

OUTPUT:

Kode

    0    1    1    2    3    5    8   13   21   34
    1    1    2    3    5    8   13   21   34   55
   10   11   21   32   53   85  138  223  361  584
   15   16   31   47   78  125  203  328  531  859

Mvh
CodeBarbarian

Sist endret av CodeBarbarian; 21. juli 2011 kl. 10:09.

Provo

5.579 14.200

Språk: C.

Kode

#include <stdio.h>
#include <math.h>

int main(){
	int i;
	for(i = 0; i < 50; i++)
		printf("%.0f  ", round((pow((1+sqrt(5))/2, i)-pow((1-sqrt(5))/2, i))/sqrt(5)));
	printf("\n");
}

Output:

Kode

0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181  6765  10946  17711  28657  46368  75025  121393  196418  317811  514229  832040  1346269  2178309  3524578  5702887  9227465  14930352  24157817  39088169  63245986  102334155  165580141  267914296  433494437  701408733  1134903170  1836311903  2971215073  4807526976  7778742049

liasis

Logotytme

4.062 3.209

På engelsk, eller Python om du vil:

Kode

a,b = 0,1
for i in range(1,50):
        print a
        a,b = b, a+b

Lanjelin

1d8+5+4d6

1.397 535

PHP, printer de 30 første.

Kode

<?for(;$j<5e5;)echo$i+=$j,"\n",$j+=$j?$i:1,"\n";

Kode

Sist endret av Lanjelin; 21. juli 2011 kl. 11:20.

Dyret

1.917 1.754

Sitat av Lanjelin

PHP, printer de 30 første.

Kode

<?for(;$j<5e5;)echo$i+=$j,"\n",$j+=$j?$i:1,"\n";

Vis hele sitatet...

Har en lignende en på 42 bytes liggende på PHPgolf. Du kan erstatte \n med et faktisk linjeskift og spare én byte :P

Liker løsningen i MS Excel. Skriv 1 i felt A1 og A2, så

Kode

SUM(A1:A2)

i felt A3. Kopier nedover og se at 12 tegn er nok ^_^ (helt til ting begynner å bli feil like etter felt A70).

Grix

NaN

2.045 1.055

Enda en kjedelig c++ variant:

Kode

#include <iostream>
#include <stdlib.h>
using namespace std;

int main()
{
double i = 1;
double iprev = 0;
int temp = 0;
while (temp < 30)
	{
	i = (i + iprev);
	cout << i << endl;
	iprev = (i - iprev); 
	temp++;
	}
system("PAUSE");
return 0;
}

Provo

5.579 14.200

Jeg glemte jo å fortelle hvorfor jeg gjorde det på den måten.. Fordelen er altså at man ikke trenger å telle fra null for å få et spesielt tall i rekken. Man kan for eksempel ta fra tall nr 42 til 47:

Kode

#include <stdio.h>
#include <math.h>

int main(){
	int i;
	for(i = 41; i < 47; i++)
		printf("%.0f  ", round((pow((1+sqrt(5))/2, i)-pow((1-sqrt(5))/2, i))/sqrt(5)));
	printf("\n");
}

Output:

Kode

165580141  267914296  433494437  701408733  1134903170  1836311903

Lanjelin

1d8+5+4d6

1.397 535

Da slenger jeg det ut i Batch også, printer de 30 første.

Kode

@echo off&cls
set /A vi=0
set /A vj=0
set /A ant = 0
:start
set /A vi = %vi% + %vj%
echo %vi%
set /A ant = %ant% + 1
if %vj% == 0 set /A vj = 1
set /A vj = %vj% + %vi%
echo %vj%
set /A ant = %ant% + 1
if %ant% LEQ 29 goto start
pause

CodeBarbarian

Sikkerhet/Utvikling

Trådstarter

242 82

Sitat av Lanjelin

Da slenger jeg det ut i Batch også, printer de 30 første.

Kode

@echo off&cls
set /A vi=0
set /A vj=0
set /A ant = 0
:start
set /A vi = %vi% + %vj%
echo %vi%
set /A ant = %ant% + 1
if %vj% == 0 set /A vj = 1
set /A vj = %vj% + %vi%
echo %vj%
set /A ant = %ant% + 1
if %ant% LEQ 29 goto start
pause

Vis hele sitatet...

Den likte jeg svært godt! Utrolig kreativt språk også! :P

Har løst denne i Java vha. rekursivitet

Kode

public class main
{
	public static void main(String args[])
	{
		for(int i = 0; i <=30; i++)
		{
			System.out.println(fibonacci(i)); 
		}
	}

	public static int fibonacci(int j)
	{
		if(j <= 2) return 1; 
		else  return fibonacci(j - 1) + fibonacci(j - 2);
	}
}

Output:

Kode

Dyret

1.917 1.754

Sitat av Opous

Har løst denne i Java vha. rekursivitet

Vis hele sitatet...

Selv om denne løsningen er fullgod for lave tall er dette selve kremeksempelet på hvorfor man bør ta i bruk memoisering.

Innen du har kommet til tall nummer 21 i rekka så har funksjonen din blitt kalt over 20.000 ganger. Siden fib(10) kaller fib(9) og fib(8), og fib(9) kaller fib(8) enda en gang, i tillegg til fib(7) så ser du at det baller ekstremt fort på seg.

Hvis du utvider funksjonen til noe sånt som:

Kode

private Hashtable oppslagstabell = new Hashtable();

	public static int fibonacci(int j)
	{
		if(oppslagstabell.containsKey(j)) return oppslagstabell.get(j));
		if(j <= 2) return 1;
		else oppslagstabell.put(j, return fibonacci(j - 1) + fibonacci(j - 2);
		return oppslagstabell.get(j);
	}

Her mellomlagrer du resultatene dine, slik at du ikke lenger trenger å gjøre så vanvittig mange kalkulasjoner om igjen for høyere tall. Ikke at løsningen din var særlig dårlig, men å vite om dette kan gjøre at ytelsen til dine fremtidige programmer blir utrolig mye høyere!

ivioynar

6.678 6.411

Tar litt tid, men pyttsann. Noen som gjetter, og eventuelt ikke er Provo?

Kode

from random import uniform
N = 10000000

def hit(x,y):
    if (x*x + y*y) < 1:
        return 1
    else:
        return 0

m = 0
for i in range(N):
    m += hit(uniform(0,1),uniform(0,1))

a = 4*float(m)/(5*N)
n = 2*(1-a**2/2 + a**4/24 - a**7/5040)

for i in range(50):
    print "%s: %d" %(i,(n**i - (1-n)**i)/2.2360679774997898)

edit: er forresten python - og hvis man ser asymptotisk på det, burde kjøretiden være ganske bra!
edit2: fjernet biblioteksavhengighet

Sist endret av ivioynar; 21. juli 2011 kl. 20:52.

ymgve

699 190

En annen Python-variant:

Kode

def matmult(a, b):
    return (a[0] * b[0] + a[1] * b[2], a[0] * b[1] + a[1] * b[3], a[2] * b[0] + a[3] * b[2], a[2] * b[1] + a[3] * b[3])
    
def fib(n):
    a = (1,0,0,1)
    x = (1,1,1,0)
    while n > 0:
        if n & 1 == 1:
            a = matmult(a, x)
            
        n >>= 1    
        x = matmult(x, x)

    return a[0]
    
for i in xrange(100):
    print fib(i)
    
print fib(1000)
print fib(10000)
print fib(100000)

ivioynar

6.678 6.411

Hehe, matrisemultiplikasjon ja... Jeg vurderte å bruke matriserepresentasjon og så finne en sær egenverdialgoritme for å regne ut relevante ting, men det ble litt mye slit.

Sitat av Dyret

Kode

private Hashtable oppslagstabell = new Hashtable();

	public static int fibonacci(int j)
	{
		if(oppslagstabell.containsKey(j)) return oppslagstabell.get(j));
		if(j <= 2) return 1;
		else oppslagstabell.put(j, return fibonacci(j - 1) + fibonacci(j - 2);
		return oppslagstabell.get(j);
	}

Vis hele sitatet...

Takk for nyttig informasjon!

Byttet ut variablen "i" i for-løkka fra 30 til 100, det endet med at eclipse hang seg og jeg måtte restarte maskinen.

Sist endret av Opous; 21. juli 2011 kl. 21:34.

z0p

uʍop ǝpısdn

3.814 906

Kode

//    \   \
//    \\_ \\_    fibonacci Tallrekken
//    ('_\('_\
//    / \_/\__       Javascript
//   / _/-'/`"
//  {\  )\  )_
//   `"""`"""`

Kode:

Kode

function fib( n, f ) {
    f = f ? f : [0,1];
    for( var i=0; i<n; i++ ) { 
        f.push( f[0] + f[1] );
        f.shift();
    }
    return f[0];
}

Eksempel bruk:

Kode

var l = 9;
var b = document.body; 
b.innerHTML = "";

b.innerHTML += "<br>";
for( i=0; i<=l; i++ ) b.innerHTML += fib(i)+" ";

b.innerHTML += "<br>";
for( i=0; i<=l; i++ ) b.innerHTML += fib(i,[1,1])+" ";

b.innerHTML += "<br>";
for( i=0; i<=l; i++ ) b.innerHTML += fib(i,[10,11])+" ";

b.innerHTML += "<br>";
for( i=0; i<=l; i++ ) b.innerHTML += fib(i,[15,16])+" ";

Utdata:

Kode

0 1 1 2 3 5 8 13 21 34
1 1 2 3 5 8 13 21 34 55
10 11 21 32 53 85 138 223 361 584
15 16 31 47 78 125 203 328 531 859

djxfade

FL Studio Guru

2.216 828

Nå vil jeg se noen skrive dette i brainfuck!

snippsat

1.393 716

Takk for nyttig informasjon! Byttet ut variablen "i" i for-løkka fra 30 til 100, det endet med at eclipse hang seg og jeg måtte restarte maskinen.

Vis hele sitatet...

Ja 100 vil knekke enhver pc og vil aldrig bli ferdig i din levetid.
Fikk lyst til og skrive den om til python og gjøre en profile av koden.

Kode

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

Her tar jeg med litt av profile resultatet.
2692542 function calls (6 primitive calls) in 2.280 CPU seconds
Vi ser at på 30 er vi allerede opp i 2692542 funksjon kall.

Øker til 40
331160286 function calls (6 primitive calls) in 284.336 CPU seconds
Her sliter pcen vi fyller opp "memory cache".

@Dyret er inne på memoisering for og gjøre det mere effektivitet.
Vil vise LRU(Least Recently Used) denne algoritmen er nå med i python og kan brukes som decorator.
Denne virker kun på python 3.2 og lru_cache er skrevet av raymond hettinger

Kode

from functools import lru_cache

@lru_cache()
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(100))

På millisekunder får vi resultatet 354224848179261915075
En profile av denne koden.
739 function calls (441 primitive calls) in 0.003 seconds
En klar forskjell og jeg synes at det er litt stillig at vi går fra noe som aldrig vil bli ferdig til 0.003sec.

Tar med en PHPgolf,gjort i python(first 30 numbers in the Fibonacci Sequence)
Denne er på 38 bytes.

Kode

x,y=0,1
while y<9e5:print x;x,y=y,x+y

Sist endret av snippsat; 22. juli 2011 kl. 16:00.

BlueWolf

123 12

Ja, for prøve jeg også, og legger ved et rask forslag til Fibonacci rekken i programmeringsspråket Ada.

Kode

with text_io; use text_io;
procedure fib is
	a : integer := 0;
	b : integer := 1;
begin
	for x in 0 .. 30
	loop
		a := a+b;
		b := a-b;
		text_io.put_line(integer'image (a));
	end loop;	
end fib;

Resultat:

Kode

Alfonzor

I like turtles

1.174 607

Kode:

Kode

var n:uint=0
var a:uint=0
var b:uint=1
var c:uint

while (n<100){
	
	trace (a)
	
	c=a
	a=b
	b=c+b
	
	n++
}

Output:

Kode

moret

#D4AF37

6.868 6.426

25. juli 2011

Har en svært kjedelig kode i java her. Prøvde å gjøre den så liten som mulig, men fortsatt lesbar så man kan forstå den. Sikkert ikke det kuleste bidraget, men det er da noe. Forresten er det fritt fram for å komme med forslag til forbedringer. Selv er jeg litt misfornøyd med hvordan det blir bestemt hvor langt opp den skal gå(tallet 154 er forresten der for ingen spesiell grunn, bare random tall på numpaden)

Kode

public class Fib{
	public static void main(String[] args){
		int j=1;
		for(int i = 0; i < 154; j = i + (i = j)){
			System.out.println(j);
		}
	}
}

Når jeg tenker meg om burde kanskje "0" vært med som første i rekken... Det tenkte jeg ikke på.

Edit:
Output

Kode

1
1
2
3
5
8
13
21
34
55
89
144
233
Trykk en tast for å fortsette...

Liten C++ variant. Skrevet rett i nettleseren da jeg ikke har innstallert noen C++ kompliatorer atm. Tror den ville gått igjennom og kjørt

Kode

class fibonacci{
   int main()
   {
     fib(10);
     return 0;
   }

   fib(int i)
   {
      return i <= 2 ? i : fib(i - 1) + fib(i - 2);
   }
};

Sist endret av Opous; 26. juli 2011 kl. 02:07.

Provo

5.579 14.200

Sitat av Opous

Liten C++ variant. Skrevet rett i nettleseren da jeg ikke har innstallert noen C++ kompliatorer atm. Tror den ville gått igjennom og kjørt

Kode

class fibonacci{
   int main()
   {
     fib(10);
     return 0;
   }

   fib(int i)
   {
      return i <= 2 ? i : fib(i - 1) + fib(i - 2);
   }
};

Vis hele sitatet...

Nei, det ville den ikke, av flere grunner.

For det første har du pakket det inn i en klasse, slik at du ikke har noen "global" main. For det andre har du ikke angitt return type på fib-funksjonen. Du vil også få feil på at fib-funksjonen er definert etter main, der den brukes, uten å ha en prototype over main. Videre ville du ikke fått output fordi du aldri skriver til skjerm. Du kunne heller ikke skrevet til skjerm, ettersom du ikke inkluderer <iostream>. Men med disse små endringene vil det kjøre:

Kode

#include <iostream>

int fib(int i)
{
  return i <= 2 ? i : fib(i - 1) + fib(i - 2);
}

int main()
{
 std::cout << fib(10);
 return 0;
}

Men løsningen din var elegant C++, om enn noe ressurskrevende hvis man skal skrive ut en hel serie.

Sitat av Provo

Nei, det ville den ikke, av flere grunner.

Kode

#include <iostream>

int fib(int i)
{
  return i <= 2 ? i : fib(i - 1) + fib(i - 2);
}

int main()
{
 std::cout << fib(10);
 return 0;
}

Men løsningen din var elegant C++, om enn noe ressurskrevende hvis man skal skrive ut en hel serie.

Vis hele sitatet...

Nesten litt flaut med tanke på at C++ er språket jeg har lært på høgskolen. Men java er det jeg har kodet i det siste året, forveksler muligens litt her og der..selvom mye er likt

Liker også å inkludere

Kode

using namespace std

slik at man slipper

Kode

std::

for hver bidige cout, cin etc.

Sist endret av Opous; 26. juli 2011 kl. 13:48.

lor3ntz

Brokkoli!

500 187

Her er en i C# den bruker det gylne snitt. Husker ikke hvor jeg leste det, men det skal i hvertfall stemme bedre og bedre jo større tallene blir. Den trenger dessverre litt drahjelp til å begynne med

Kode

public static void Main(string[] args)
    {
        int[] fibonacciTall = fib(15);       
        Console.ReadLine();
    }

    //Fibonacci etter det gylne snitt
    public static int[] fib(int length)
    {
        int[] fib = new int[length];
        Array.Copy(new int[] { 0, 1, 1 }, fib, 3);

        for (int i = 0; i < length; i++)
        {
            if(i > 2)
                fib[i] = (int)Math.Round(fib[i-1] * 1.61803399);
            Console.WriteLine(fib[i]);
        }

        return fib;
    }

Kode

Sist endret av lor3ntz; 26. juli 2011 kl. 14:38. Grunn: glemte output

▼ ... over en uke senere ... ▼

Restyle

exquisite

4.700 1.391

Da fikk jeg stresset maskinen litt også:

Kode:

Kode

public class Fibonacci {
    public static long fib(int n) {
        if (n <= 1) return n;
        else return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int num = 50;
        for (int i = 1; i <= num; i++)
            System.out.println(i + ": " + fib(i));
    }

}

Output (0 -> 50):

Kode

1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55
11: 89
12: 144
13: 233
14: 377
15: 610
16: 987
17: 1597
18: 2584
19: 4181
20: 6765
21: 10946
22: 17711
23: 28657
24: 46368
25: 75025
26: 121393
27: 196418
28: 317811
29: 514229
30: 832040
31: 1346269
32: 2178309
33: 3524578
34: 5702887
35: 9227465
36: 14930352
37: 24157817
38: 39088169
39: 63245986
40: 102334155
41: 165580141
42: 267914296
43: 433494437
44: 701408733
45: 1134903170
46: 1836311903
47: 2971215073
48: 4807526976
49: 7778742049
50: 12586269025

Sitat av Restyle

Da fikk jeg stresset maskinen litt også:

Kode:

Kode

public class Fibonacci {
    public static long fib(int n) {
        if (n <= 1) return n;
        else return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int num = 50;
        for (int i = 1; i <= num; i++)
            System.out.println(i + ": " + fib(i));
    }

}

Vis hele sitatet...

Kult å herme?

snippsat

1.393 716

En litt mere kreativ måte og løse dette på,for dem som ikke liker matte

Kode

import urllib,re

#How many fibonacci number 25 50 100 150 200.....
fib_num = 50
site = 'http://www.bigprimes.net/archive/fibonacci/%s'
for i in range(0,fib_num,25):
    url = urllib.urlopen(site % i).read()[0:6000]
    result = [match.group(1) for match in re.finditer(r'\/">(\d+)', url)]
    print result

Output

Kode

['0', '1', '1', '2', '3', '5', '8', '13', '21', '34', '55', '89', '144', '233', '377', '610', '987', '1597', '2584', '4181', '6765', '10946', '17711', '28657', '46368']
['75025', '121393', '196418', '317811', '514229', '832040', '1346269', '2178309', '3524578', '5702887', '9227465', '14930352', '24157817', '39088169', '63245986', '102334155', '165580141', '267914296', '433494437', '701408733', '1134903170', '1836311903', '2971215073', '4807526976', '7778742049']

Restyle

exquisite

4.700 1.391