Haftanın sorusu

[Erdem]

Programlamaya yeni başlayan arkadaşlar için fikir jimnastiği olması açısından böyle bir soru hazırladım. Bilmiyorum duruma göre belki devamını hazırlayabilirim. Bazı haber gruplarında bu tür sorular yayınlanıyor ve konunun ilginç ayrıntılarının ortaya çıkmasında faydalı oluyor.

Sorunun çözümünü C, C++ veya D ile yazabilirsiniz.

Soru şu: Fibonacci dizisinin ilk 10 tanesini yazan bir program yazın.

Ek bilgiler: Fibonacci dizisi sayıları 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 şeklinde devam eden bir sayı dizisi. Her sayı kendinden önce gelen iki sayının toplamı olmuş oluyor.



Örneğin bu kenar uzunlukları fibonacci sayıları olan karelerden oluşan bir döşeme.



Doğada bile bu fibonacci sayı dizilimine rastlamak mümkünmüş. Örneğin ayçiçeğine benzer papatyagiller familyasından bu çiçekte olduğu gibi.

[travego0403]

Gerçekten güzel düşünce, soruya cevap vermek istiyorum ama yeni başlayan arkadaşların cevaplaması daha uygun diye cevap vermiyorum.
Soruların inşallah devamı gelir.

[utdmr]

C++ ile yazmış olayım dedim, ve her eleman için diziyi baştan hesaplayarak bulan bir program yazdım, saçma olduğunu biliyorum . Hem de rekürsif fonksiyon gibi zaten yavaş bir işlem ile .

İşte kod:

Kod Seç Genişlet

#include <iostream>

using namespace std;

int fib(int a){
if(a<=1)
    return a;
else
    return fib(a-1)+fib(a-2);
}

int main()
{
for(int i=0;i<10;i++)
    cout<<fib(i)<<" ";
return 0;
}


[mami96]

Dediğiniz şey şu şekil mi olacak?

Kod Seç Genişlet


#include <stdio.h>

long fibonacci(long);

int main(){

    long sonuc, sayi;

    printf("Bir tam sayi girelim: ");
    scanf("%ld", &sayi);
    sonuc = fibonacci(sayi);
    printf("Fibonacci(%ld) = %ld\n", sayi,sonuc);
    return 0;

}


/* Yinelemeli olarak tanimlanmis bir fibonacci fonksiyonu */
long fibonacci(long n)
    {

        if (n == 0|| n == 1)
            return n;
        else
            return fibonacci(n-1)+fibonacci(n-2);

    }



Yoksa bu tarz  bir şey mi?

Kod Seç Genişlet


#include <stdio.h>

int main()
{
    int i=1, ilkdegerim=0, ikincidegerim=1,
    degerim, sayi;
    printf("Bir Sayi Giriniz: ");
    scanf("%d",&degerim);
    printf("%d\n%d\n",ilkdegerim,ikincidegerim);


    while(i<9)
    {
        sayi=ilkdegerim+ikincidegerim;
        printf("%d\n",sayi);
        ilkdegerim=ikincidegerim;
        ikincidegerim=sayi;

        i++;
    }

    return 0;
}



Buda D dili ile yapilabilir

Kod Seç Genişlet



module fibonacci;

import std.stdio;

ulong iterative(ulong x)
{
    ulong prev1 = 1L;
    ulong prev2 = 1L;
    ulong result = x <= 2 ? 1L : 0L;
   
    for ( ulong i = 3; i <= x; ++i )
    {
        result = prev1 + prev2;
        prev1 = prev2;
        prev2 = result;
    }
    return result;

}

int main()
{
for (uint i = 1; i < 10; i++)
{
writef("%s, ", iterative(i));
}
writefln("%s", "...");

return 0;
}
}


[travego0403]

@ mami96 ben optimum kod olarak 2.yazdığın programı tercih ederim, büyük sayılara çıkıldığı zaman yinelemeli foksiyon yavaşlayacaktır.

[mami96]

Buyuk sayilari denedim calismaz hale gelebiliyor. Asiri yavasliyor.

Ben ne turde istendigini bilemedigimde hazirladim 2 kodu.

3. Kod ise bana ait degil sanirim. D ile ilgilenmeye basladigimdan beri kosede duruyor. Benim degildir. Ama guzel ve calisan bir kod

[Erdem]

Evet değişik çözümler üretilebilir 

D programındaki 1L aslında 1 demek 0L ise 0 demek.

Bir de her zaman önek olan ++ işleci daha hızlıdır. ++i gibi..

Arkadaşların da bahsettiği gibi normal yöntemlerle Fibonacci'yi hesaplamaya çalıştığımızda bunları saklaması da gerekeceği için yer bulamaz ve yavaş olurdu. D'nin bu konuya getirdiği çözüm tembellik Yani işini gerektiği zaman ve parça parça yapan veri yapıları. Bu da program hızı ve bellek kullanımı açısından çok faydalı.

Şimdilik bu kadar kısaca yazıyorum daha ayrıntılı olarak yarın yazmaya çalışacağım.

[Erdem]

Kod Seç Genişlet

    int[] dizi = [ 10, 11, 12 ];

    for (int i = 0; i != dizi.length; ++i) {
        write(' ', dizi[i]);
    }

    assert(dizi.length == 3);    // ← uzunluğu değişmez

Konuyu daha iyi anlamak için şu örneklere bakalım. Örneğin dizi elemanlarını yazan şu basit koda bakalım. Bu kod basitçe baştaki elemanı yazdırıyor. Yalnız dikkat ederseniz teker teker dizinin elemanlarını dolaşarak yazdırıyor. Burada assert satırı dizinin uzunluğunun 3 olduğundan eminim anlamına geliyor.

Kod Seç Genişlet

//           (front)
//           baştaki      dizi
//          ---------------------------------
//          | 10 | 11 | 12 |  |  |  |  |  | |   <--
//          ---------------------------------
//            | pop() çıkart
//            V

    for ( ; dizi.length; dizi = dizi[1..$]) {
        write(' ', dizi[0]);     // ← hep ilk elemana erişilir
    }

Bir de bu konuya farklı bir yaklaşımla bakalım. Burada şöyle diyoruz dizinin uzunluğu 0 olana kadar bu döngüyü devam ettir. dizi = dizi[1..$] satırı da döngü her işletildiğinde dizinin baştaki elemanının çıkartılmasını sağlıyor.

Bu döngü işletildiğinde dizinin elemanlarının durumu aşağıdaki gibi oluyor. Burada elemanlar arasında dolaşmak yerine her zaman dizi[0] yani ilk elemanı yazdırıyoruz.

       [ 10, 11, 12 ]
        [ 11, 12 ]
             [12 ]
               [ ]

Kod Seç Genişlet


import std.stdio;

struct FibonacciSerisi
{
    int baştaki = 0;
    int sonraki = 1;

    static immutable bool empty = false;  // ← sonsuz aralık

    @property int front() const
    {
        return baştaki;
    }

    void popFront()
    {
        int ikiSonraki = baştaki + sonraki;
        baştaki = sonraki;
        sonraki = ikiSonraki;
    }
}

void yazdır(T)(T aralık)
{
    for ( ; !aralık.empty; aralık.popFront()) {
        write(' ', aralık.front);
    }

    writeln();
}

void main()
{
    yazdır(FibonacciSerisi());   
}

Şimdi D'nin Fibonacci çözümüne bakalım. Gördüğünüz gibi Fibonacci serisini yazdıran basit bir yapı.

Kod Seç Genişlet

//         
//                            ikiSonraki 
//          baştaki   sonraki   |
//             |         |      .
//             v         v      V
//          -----------------------
//          |   0   |   1   |     |     
//          ----------------------
//   popFront |  baştakiniÇıkart
//            V

popFront baştaki elemanı çıkart demek. Şimdi bu işleve bakalım. Çıkartmadan önce bir sonraki elemanın ilk iki elemanın toplamı olduğunu biliyorduk. Bu yüzden ikiSonraki'yi kolayca buluyoruz. Bütün elemanlar bir yana kayacak. O yüzden baştaki = sonraki ve sonraki = ikiSonraki yapıyoruz. Yazdırma işleminde ikinci örnekte olduğu gibi hep baştaki elemanı yazdırıyoruz.

empty aralığın boş olup olmadığını belirtiyor. empty işlevini her zaman false yaparak
bu aralığı sonsuz yapıyoruz. Dikkat ederseniz aralık boşaldığı için döngümüz sonlanıyordu. Aralığımızı sonsuz yaptığımız için int.max'a kadar (yani tamsayı değerlerin maksimum değerine kadar) doğru olarak Fibonacci sayılarını üretir.

Aslında bunu

Kod Seç Genişlet

    writeln(FibonacciSerisi());

şeklinde de kullanabilirsiniz. writeln de aynı şekilde çalışır

Bu yüzden FibonacciSerisi tembel bir aralık olmuş oluyor. İşini gerektiği kadar ve parça parça gerçekleştirir. Bu da program hızı ve bellek kullanımı açısından çok yararlıdır.

Konuyla ilgili daha fazla bilgiyi buradan okuyabilirsiniz:

http://ddili.org/ders/d/araliklar.html

[mami96]

Bakın şöyle birşey buldum (:

http://www.scriptol.com/programming/fibonacci.php

[sem]

Bolca soru arayanlar için bende bu bağlantıyı vereyim;

http://www.csystem.org/calisma-sorulari

[travego0403]

Bir başka algoritma sorusu da benden gelsin. Özellikle istatistik derslerinde kullandığımız bir soru için sizlerden çözümler alalım.

0-100 arasında 10000 tane değerimiz var. Bunların frekans dağılımlarını yani kaçı 0-10, kaçı 10-20 . . . 90-100 arasındadır. Bunu sayıp ekrana basan bir program  yazabilirsiniz. Bakalım kaç farklı çözüm gelecek?( Şu an 3 çözüm biliyorum.) Değerler için rastgele sayı seçtirip işlem yapabilirsiniz.

[utdmr]

@travego0403, Python ile yaptım, umarım hile sayılmaz :

Kod Seç Genişlet

>>> from collections import Counter
>>> import random
>>> random.seed()
>>> numbers=[random.randint(1,99) for i in range(10000)]
>>> Counter([number/10 for number in numbers])
Counter({6: 1038, 4: 1036, 1: 1031, 8: 1014, 3: 1013, 2: 1010, 7: 1006, 5: 991, 9: 958, 0: 903})
Sayının ilk basamağına göre kaç tane olduğun söylüyor .

[Erdem]

Benim aklıma şöyle bir çözüm geldi:

Kod Seç Genişlet

import std.stdio;
import std.random;

void main()
{
    uint[uint] değerler;

    foreach (i; 0 .. 10_000) {
        auto sayı = uniform(1, 100);
        uint aralık = sayı / 10 * 10;
        ++değerler[aralık];
   }

   foreach (aralık, kaçtane; değerler) {
       writefln("%3d%s%3d%s%4d", aralık, "-", aralık + 10, " : ", kaçtane);
   }
}


[travego0403]

@utdmr  Python bilmiyorum ama anladığım kadarıyla aynı şeyi düşünmüşüz.
@Erdem Sayıyı 10'a bölüp integer kısmını almak benimde bildiğim ve en iyisi olduğunu düşündüğüm çözüm.

Bildiğim yöntemeri yazayım kısaca:
1.Yöntem: Sizinde söylediğiniz gibi sayıyı 10'a bölersek bir tam sayı ve ve küsüratı olacaktır.Eğer integer kısmını alıp incelersek aynı aralıkta olan sayıların aynı tam sayıya sahip olduğu görülür.(İlk basamaktaki sayı) Bizde bir dizi açıp bunu kutular gibi düşünebiliriz. Kutuların başlangıçta içleri boş. Yukarıdaki işlemden sonra elde ettiğimiz tam sayıyı ilgili kutuya atarız.Bütün sayılar bittikten sonra kutuların içlerinde sayılar bize kaç değerin o aralıkta ( kutuda ) olduğunu verecektir.Kodlar:

Kod Seç Genişlet

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define MAX 10000
using namespace std;
int main(int argc, char **argv){
    srand(time(NULL));
    int degerler[MAX];
    for(int i=0;i<MAX;++i){ //Rastgele degerler sec
        degerler[i]=rand()%100;
        cout<<degerler[i]<<"  ";
    }
    cout<<"\n************************************************************\n";
    int frekans[10];
    for(int i=0;i<10;++i){
        frekans[i]=0; // Dizinin icini bosalt
    }
    for(int i=0;i<MAX;++i){
        int k;
        k=degerler[i]/10;
        frekans[k]++;
    }
    for(int i=0;i<10;++i){
        cout<<(i*10)<<" ile "<<(i*10+10)<<" arasında "<<frekans[i]<<" deger var.\n";
    }
    return 0;
}

2.Yöntem İç içe iki döngü ile ilk degerden başlayarak kaç tanesi  ilk aralığa düştüğünü buluruz.Dıştaki döngü 2.tura geçtiği zamanda ikinci aralığa düşen değerlerin sayısını buluruz.Bu şekilde lerler.Evet tahmin ettiğiniz gibi gereksiz yere degerleri 10 defa kontrol ediyor.Kodlar:

Kod Seç Genişlet

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define MAX 10000
using namespace std;
int main(int argc, char **argv){
    srand(time(NULL));
    int degerler[MAX];
    for(int i=0;i<MAX;++i){ //Rastgele degerler sec
        degerler[i]=rand()%100;
        cout<<degerler[i]<<"  ";
    }
    cout<<"\n************************************************************\n";
    for(int i=0;i<100;i+=10){
        int sayac=0;
        for(int k=0;k<MAX;++k){
            if(degerler[k]>=i && degerler[k]<i+10){
                ++sayac;
            }
        }
        cout<<i<<" ile "<<(i+10)<<" arasinda "<<sayac<<endl;
    }
    return 0;
}

3.Yöntem: Programlamaya ilk başladığımız zamanlarda aklımıza gelen ilk yöntem. Bir döngü açmak ve içine if (şart), if(şart) diye doldurmak. Kodları vermeye gerek duymuyorum.


İstatistik Bilgi: Rastgele seçilen sayılar(10000 için) görüldüğü gibi her aralığa eşit sayıda gidiyor.(1000 civarı) Ufak dalgalanmalar oluyor ama istatistikte deney sayısını arttırırsanız dalgalanmalar azalcaktır.Hatta deney sayısı sonsuza giderse her aralığa sayılar teorik olarak hesapladığımız şekilde gelecektir. 

Düzenleme : Kodların girintilemesi düzeltildi.

[Erdem]

Bunu C++ ile yazarken bir eşleme tablosu gerçekleştirmesi olan std::map kullanabilirdik.

Kod Seç Genişlet

#include <iostream>
#include <map>
#include <cstdlib>

using std::map;

int rastgeleSayi(int n)
{
    const unsigned aralik = ((unsigned)(RAND_MAX)+1) / n;
    int r;
    do r = rand() / aralik;
    while (r >= n);
    return r;
}


int main()
{
    typedef map<int, int> Sayilar;
    Sayilar sayilar;

    srand(time(NULL));

    for (int i = 0; i < 10000; ++i) {
        const int sayi = rastgeleSayi(100);
        const unsigned int aralik = sayi / 10 * 10;
        ++sayilar[aralik];
    }

    Sayilar::iterator konum;
    for (konum = sayilar.begin(); konum != sayilar.end(); ++ konum)
        std::cout << konum->first << "\t" << konum->second << '\n';
}

[sem]

Çok güzel kodlar paylaşmısınız, elinize sağlık...

[kaansef]

Bizim hocamız bu fibonacci sorusunu ev ödevi olarak vermişti.Defterden aynen yazıyorum.(Ben yapmadım,Hocanın yaptırdığı bu.)Fakat sadece algoritma olarak yazılmış.Birileri bir programlama diliyle kodlarsa iyi olur.

Kod Seç Genişlet


Başla
ysay=1,ysay2=1,esay=0,sayac=0;
Yaz;"ysay2";
ysay=esay+ysay1;
esay=ysay1;
ysay1=ysay2;
sayac=sayac+1 //veya sayac++;
eğer sayac=15 değilse 3.adıma git.
Yaz;"ysay2";
Bitir


[Erdem]

Kod Seç Genişlet


Başla
ysay=1,ysay2=1,esay=0,sayac=0;
ysay=esay+ysay1;


Burada ysay1 diye bir değişken göremiyorum. Ayrıca hocana söyle algoritma içinde de olsa sihirli sabitler kullanmak vazgeçsin

[mami96]

@kaansef

Hocan ilginçmiş

Pseudocode

bilginizi sifirlatacak (:

İlginç bir sahte kod yapisi (:

*****************************

Beyin fırtınasına bendende bir soru gelsin. Algoritmasini anlatacagim siz kod ornekleriyle senlendirin bakalim

Oyuncu iki zarı aynı anda atacak. İki zarında altı yüzü var. Bu yüzlerde 1,2,3,4,5 ve 6 adet nokta oldugunu varsayalım. Zarlar durduktan sonra her iki zarında üste gelen yüzleri toplanır. Eğer toplam ilk atışta 7 ya da 11 ise oyuncu kazanır. eğer toplam ilk atışta 2,3 ya da 12 gelirse bu barbur olur ve oyuncu kaybeder. Eğer ilk atışta toplam 4,5,6,8,9,10 ise bu toplam oyuncunun, sayısı haline gelir. Kazanmak için oyuncu sayısını bulana kadar zarları atmaya devam eder. Zarları atmaya devam ederken kendi sayısı yerine 7 atarsa kaybeder.

Evet bunu koda dokecek kisiler aranmakta (:

[travego0403]

Burada anlamadığım bir kaç yer var.

Mesela ilk zarları attık toplamı 5 geldi. İkinci atışımızda 2 veya 6 atmamız mı lazım kazanmak için?

7 atma meselesi: 5 atmıştık diyelim ilk zarlarda, ikinci zarlarda toplam 7 gelirsemi kaybeder(ilk zar önemsiz mi yani), yoksa 5+2 toplamında mı kaybeder buda ilk madddeyi etkiler.

[mami96]

7'ye ulasmaniz onemli şöyle açıklayayım

ilk atışta 7 ya da 11 atarsanız kazanırsınız

ama

5 + 6 atarsanız sonuç 11'ye gelirse kazanirsiniz.

sonucu direkt etkileyenler

7 ve 11 kazanır

2,3,12

toplamlarında ise kaydebilir.

yani 6+6 gelirse kaybedersiniz

7+4 gelirse kazanirsiniz.

5+5 gelirse oyuna devam edilir ya 11 ya da 12'ye ulasilmaya calisilir.

[travego0403]

Yanlış anlamadıysam şöyle bir şey öyleyse Biraz acele oldu ama idare eder.

Kod Seç Genişlet

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
int zarlariAt(){
    int zar1,zar2;
    zar1=rand()%6+1;
    zar2=rand()%6+1;
    //cout<<"1.Zar = "<<zar1<<"    2.Zar = "<<zar2<<endl;
    return zar1+zar2;   
}

int main(int argc, char** argv) {
    srand(time(NULL));
    int oyuncuSayisi=0;
    int zarToplam;
   
    while(1){
        zarToplam=zarlariAt();
        cout<<"Gelen Zarların Toplamı = "<<zarToplam<<endl;
        if(oyuncuSayisi!=0 && zarToplam==7){     
            //2. ve sonraki atışlarda 7 gelmesini kontrol et
            cout<<"1. zardan sonra 7 attınız kaybettiniz"<<endl;
            break;
        }
        oyuncuSayisi+=zarToplam;
        cout<<"Oyuncu Sayisi = "<<oyuncuSayisi<<endl;
        if(oyuncuSayisi>=13){
            cout<<"Oyuncu Sayisi 12'den büyük!!!\nKaybettiniz :("<<endl;
            break;
        }
        if(oyuncuSayisi==7||oyuncuSayisi==11){
            cout<<"Kazandınız"<<endl;
            break;
        }
        else if(oyuncuSayisi==2||oyuncuSayisi==3||oyuncuSayisi==12){
            cout<<"Barbur oldu.Kaybettiniz.... :("<<endl;
            break;
        }       
    }
    return 0;
}


[mami96]

Kod Seç Genişlet


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int zarAtma(void);

int main()
{
int oyunDurumu, toplam, oyuncuPuani;

srand(time(NULL));
toplam = zarAtma(); /* zarın ilk atılışı */

switch(toplam) {
case 7: case 11: /* ilk atışta kazanma */
oyunDurumu = 1;
break;
case 2: case 3: case 12: /* ilk atışta kaybetme */
oyunDurumu = 2;
break;
default: /* hatırlatma noktası */
oyunDurumu = 0;
oyuncuPuani = toplam;
printf("Oyuncunun kazanacağı zar: %d\n", oyuncuPuani);
break;
}

while (oyunDurumu == 0) { /* zar atmaya devam et */
toplam = zarAtma();

if(toplam == oyuncuPuani) /* kazanılacak zarı atma */
oyunDurumu = 1;
else
if(toplam == 7) /* 7 atma ile kaybetme */
oyunDurumu = 2;
}

if (oyunDurumu == 1)
printf("Oyuncu kazanır\n");
else
printf("Oyuncu kaybeder\n");

return 0;
}

int zarAtma(void)
{
int zar1, zar2, toplamZar;

zar1 = 1 +(rand() %6);
zar2 = 1 +(rand() %6);
toplamZar = zar1 + zar2;
printf("Oyuncu %d + %d = %d attı\n", zar1, zar2, toplamZar);
return toplamZar;
}



Çıktı olarak

Kod Seç Genişlet


ali@ali:~/Masaüstü$ g++ barbur.cpp -o barbur
ali@ali:~/Masaüstü$ ./barbur
Oyuncu 3 + 1 = 4 attı
Oyuncunun kazanacağı zar: 4
Oyuncu 5 + 5 = 10 attı
Oyuncu 2 + 3 = 5 attı
Oyuncu 1 + 2 = 3 attı
Oyuncu 6 + 4 = 10 attı
Oyuncu 6 + 4 = 10 attı
Oyuncu 4 + 2 = 6 attı
Oyuncu 4 + 3 = 7 attı
Oyuncu kaybeder
ali@ali:~/Masaüstü$


[ozdemir08]

Ben de ileri seviyedeki arkadaşlar için fibonaccinin bi değişik versiyonunu sormak istiyorum (erdem de dahil) acaba fibonacciyi O(log n) de çözebilecek arkadaş var mı

[sem]

"@ mami96 ben optimum kod olarak 2.yazdığın programı tercih ederim, büyük sayılara çıkıldığı zaman yinelemeli foksiyon yavaşlayacaktır."

@travego0403; bir programda farklı yerlerde lazım olabilme ihtimali ya da  yazmışken her programda aynı fonksiyonu kullanılabilmek adına ben olsam fonksiyonu seçerdim...

Yavaşlık konusunda ise, parametre değişkenine kopyalamayı diyorsunuz sanırım? Programın akışı değişecek ve yeni veriler fonksiyon parametresi olarak kopyalanacak... Göstericiler ile ya da  C++ için göstericilere ek olarak referanslar ile kopyalama yerine adres aktarımı sayesinde verimlilik arttırılabilir.

Benim düşüncem de budur =)

EK: Fonksiyon kendini çağıran, özyinemeli (recursive) bir fonksiyonmuş... İşler değişiyor tabii bu durumda =)