vaikka mitä osaan jo, en vieläkään osaa tehdä ohjelmaa, joka tulostaa fibonaccin lukuja.. ainoa esimerkki, jonka olen nähnyt, on ollut rekursiivinen metodi, mutta kai sen voi normaalistikin tehdä? haluaisin todella oppia tekemään tuon.. :D
Edit: 200. viesti!
Normaalisti? No kai sen voi jotain funktiota kutsumalla tehä jos looppaa sitä funktiota.
Tein tuon pikaisesti laskimelle ja tässä tulos pseudona:
int a = 0;
int b = 1;
int c;
while(1) {
c = a + b;
a = b;
b = c;
print(a);
}ok, pitääpä katsoa ...
Edit: hei, toihan toimii, kiitos!
Edit2: ei tullut edes mieleen käyttää 3 muuttujaa, kun yritin vaan pistää 2 loopin sisään ja breakata aina sisemmästä ulos ja plussata yhteen ;D
PS: eihän tuo mitään pseudoa ole :D toimi muuten suoraan, paitsi että piti vaihtaa ehto...
Eipä tuon rekursiivisen toteutuksen tajuaminenkaan hirveän vaikeaa ole.
Limbolla vaikka:
fibonacci(a, b : int)
{
sys->print("%-3d\n", a + b);
if (a+b < MAX)
{
fibonacci(b, a+b);
}
}Saa tuon kahdellakin muuttujalla tehtyä silmukan avulla, kun hieman pohdiskelee ensiksi. Tässä kaksi ratkaisua, kumpikin tulostavat 10 ensimmäistä Fibonaccin lukua.
public class Fibs {
public static void main(String args[]){
int a = 0;
int b = 1;
for (int i = 0; i < 10; i++){
if ( a < b ){
System.out.println(a);
a = a + b;
} else {
System.out.println(b);
b = a + b;
}
}
// Toinen tapa
a = 0;
b = 1;
for (int i = 0; i < 10; i++){
System.out.println(a);
a = a + b;
b = a + (0 & (a = b)); // Vaihtaa muuttujien arvot keskenään.
}
}
}Jos tuo muuttujien vaihto ihmetyttää, niin siitä keskusteltiin jokunen aika sitten täällä putkassa, sillä sen tuohon laitoin. Kyseinen keskustelu: https://www.ohjelmointiputka.net/keskustelu/
Oma toteutukseni (huano), tein joskus koulussa ATK:n tunnilla (tais mennä 5-10min).
public class fibonacc {
public static void main(String[] args) {
long count = 60;
long first = 1;
long second = 1;
long sum;
String numbers;
numbers = first+", "+second+", ";
for(int i=0;i<count;i++){
sum = first + second;
numbers += sum;
first = second;
second = sum;
if(i<count-1){
numbers += ", ";
}
}
System.out.println(numbers);
}
}jalski kirjoitti:
Eipä tuon rekursiivisen toteutuksen tajuaminenkaan hirveän vaikeaa ole.
Rekursiivisella Fibonaccin lukujen toteutuksella tarkoitetaan yleensä jotain tämän tapaista:
int fib(int n) {
return n == 0 ? 0 :
n == 1 ? 1 :
fib(n - 1) + fib(n - 2); }Tai jollain toisella kielellä:
fib 0 = 0 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2)
Eli melko suoraa käännöstä matemaattisesta määritelmästä.
Tärkeä optimointitekniikka on memoization, eli paluuarvojen tallentaminen johonkin tietorakenteeseen; esim.:
#define N 42
int fib_result[N];
int fib_is_cached[N] = {0};
int fib(int n) {
if (n < N && fib_is_cached[n]) {
return fib_result[n]; }
int fib_n = n == 0 ? 0
: n == 1 ? 1
: fib(n - 1) + fib(n - 2);
if (n < N) {
fib_result[n] = fib_n;
fib_is_cached[n] = 1; }
return fib_n; }Edit: fib(0) = 0
Päärynämies kirjoitti:
Saa tuon kahdellakin muuttujalla tehtyä silmukan avulla, kun hieman pohdiskelee ensiksi. Tässä kaksi ratkaisua, kumpikin tulostavat 10 ensimmäistä Fibonaccin lukua.
public class Fibs { public static void main(String args[]){ int a = 0; int b = 1; for (int i = 0; i < 10; i++){ if ( a < b ){ System.out.println(a); a = a + b; } else { System.out.println(b); b = a + b; } } // Toinen tapa a = 0; b = 1; for (int i = 0; i < 10; i++){ System.out.println(a); a = a + b; b = a + (0 & (a = b)); // Vaihtaa muuttujien arvot keskenään. } } }
Kahden kokonaisluvun käyttämiseen ilman apumuuttujaa on myös kolmas, mahdollisesti intuitiivisempi tapa. Ks.
for (int c = 0, i = 1, j = 1; c < 10; ++c) {
j = i-j;
i += j;
System.out.println(j);
}Kolmannen muuttujan välttely on usein turhaa. Paitsi että koodista tulee näin usein vaikeaselkoisempaa (ks. yllä + lainaus), on myös lopputulos käännettynä hitaampi (tässä tapauksessa merkitystä tuskin on).
Tommittaja missa(a|si) tässä hyvän tilaisuuden kehittää ns. "ohjelmoijan" logiikkaansa - samoin tosin myös monissa aiemmissakin viestiketjuissaan.
funktio kirjoitti:
-- fib 0 = 1 --
Indeksoinnistahan tämä riippuu, mutta "nollantena" Fibonaccin lukuna taidetaan yleiseisimmin pitää nollaa.
eq kirjoitti:
Indeksoinnistahan tämä riippuu, mutta "nollantena" Fibonaccin lukuna taidetaan yleiseisimmin pitää nollaa.
Joo, olet oikeassa. Onnistuin jopa linkittämään Wikipediaan, jossa lukusarja alkaa nollalla, mutta jostain syystä kirjoitin sitten kuitenkin ykkösen.
eq kirjoitti:
Kahden kokonaisluvun käyttämiseen ilman apumuuttujaa on myös kolmas, mahdollisesti intuitiivisempi tapa. Ks.
for (int c = 0, i = 1, j = 1; c < 10; ++c) { j = i-j; i += j; System.out.println(j); }
Joo noinhan sen tosiaan saa menemään ehkä nätimmin, nuo omat ratkaisut olivat vaan nopeita pohdintoja noiden alkioiden yhteenlaskun pohjalta.
eq kirjoitti:
Kolmannen muuttujan välttely on usein turhaa. Paitsi että koodista tulee näin usein vaikeaselkoisempaa (ks. yllä + lainaus), on myös lopputulos käännettynä hitaampi (tässä tapauksessa merkitystä tuskin on).
Mietin, että kirjoittaako tuosta viestiini vai en, jätin sitten pois. Nuo olivat vain esimerkkejä siitä, että sen voi kahdella muuttujalla tehdä (Tommittaja kun sitä sanoi miettineensä jollakin tapaa), ei tapoja miten tuo lukujonon laskeminen tulisi tehdä. Kyllähän nuo kahden muuttujan tavat ovat epäselvempiä, kuin tuo petrinm:n esittämä tapa, jossa käytetään kolmatta muuttujaa.
Ja voihan Fibonaccin lukujonon termejä laskea myös suoraan, ilman mitään silmukoita tai rekursiota, analyyttisen muodon avulla, http://fi.wikipedia.org/wiki/Fibonaccin_lukujono#Analyyttinen_muoto. Tietokone tosin tuossa tapauksessa joutuu laskemaan likiarvoilla.
Minusta kaikkein intuitiivisin tapa hoitaa silmukka kahdella muuttujalla on tulostaa kaksi lukua joka kierroksella:
int l1 = 0, l2 = 1;
while (l1 < 10000) {
print(l1);
l1 += l2;
print(l2);
l2 += l1;
}Tämä tapa on helppo toteuttaa myös Brainfuckilla. ;)
Kahden muuttujan toteutus on vieläkin helpompi esimerkiksi Pythonilla:
l1, l2 = 0, 1 while l1 < 10000: print(l1) l1, l2 = l2, l1 + l2
Itsellenikin ekana taisi tulla mieleen tuo ratkaisu, jossa tulostetaan kaksi termiä kerralla, mutta ajattelin, että kokeilee nyt tehdä sellaisen, joka tulostaa vain yhden termin silmukan jokaiselle kierroksella. Tuollahan se helposti menee.
Hieman aihetta sivuten funktionaalisen ohjelmoinnin puolelta löytyy kivoja tapoja määritellä lista, joka sisältää periaatteessa kaikki Fibonaccin lukujonon termit. Sen voi tehdä vaikkapa näin:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
En tuon toimintaperiaatetta ala enempää nyt selittämään, rekursiivinen se on. Tuosta on kuitenkin sitten helppo noukkia vaikkapa ensimmäiset 100 alkiota ja tulostaa ne. Koodia taitaisi tulla lisää 2 riviä. On se funktionaalinen ohjelmointi kivaa.
Tämä nyt vain esimerkkinä toisenlaisesta lähestymistavasta ohjelmointiin, jota ei putkassa paljoa tule vastaan.
Kahden muuttujan käyttökin on hieman tuhlaavaista, koska saman voi tehdä yhdellä muuttujalla:
int fibo = 256;
while (1) {
printf("%i\n", (fibo&0xFF));
if ((fibo&0xFF) > 200) break;
fibo |= ((fibo&0xFF)+((fibo>>8)&0xFF))<<16;
fibo = (fibo>>8)&0xFFFF;
}ok... tuo esimerkki on jo hieman siansaksaa minulle, ja varmaan monelle muullekkin.. :D
Metabolix, tein tuon oikeastaan juuri noin, mutta tulostin vain toisen luvun, ja vastauksesta tulikin, kuten varmaan arvaat, hieman suuri... :D
Edit: tuskin tuosta edellisestä osaan edes käyttää puoliakaan noista operaattoreista.. esim: |=... mitä tuonkin pitäisi tehdä?
Tuossa Antin esimerkissä pelaillaan tuon fibo-muuttujan tavuilla. Nuo &,|,>>,<< (ja, tai, siirrot oikealle ja vasemmalle) ovat bittitason operaattoreita. Ei tuo esimerkki kovin monimutkainen ole, se vain näyttää siltä.
Lue vaikka http://en.wikipedia.org/wiki/Bitwise_operation, niin selviää miten nuo operaattorit toimivat.
Antin esimerkki on harhaanjohtava, koska siinä käytetään muuttujan yksittäisiä bittejä niin, että samaan muuttujaan saadaan tallennettua kaksi (pienempää) arvoa. Yhtä hyvin voisi paperilla laskea yhdellä luvulla: 101, 102, 203, 305, 508, 813, 1321 jne. Antti kyllä tuhlailee nyt bittioperaatioita aivan syyttä suotta, nimittäin tiivistäminen käy oikein helposti:
int fibo = 1;
while ((fibo >> 16) >= 0) {
printf("%d\n", fibo >> 16);
fibo = (fibo >> 16) + ((fibo + (fibo >> 16)) << 16);
}Aihe on jo aika vanha, joten et voi enää vastata siihen.