22
algoritma yarışması - mstryoda
merhaba puvolar algoritma yarışması ile yeni bir konuda buluşuyoruz.

bu konuda çok hoş olacağını düşündüğüm bir algoritma ve optimizasyon sorusu soracağım, sonrasında ise çözümünü anlatacağım.

sorumuz "fibonacci" üzerine.

öncelikle fibonacci serisi nedir onu bir göstereyim :

0 1 1 2 3 5 8 13 21 34 55 89 144 . . . . . . .

diye devam eden bir seri.

serinin hesaplanması ise şöyle. başlangıç sayılarımız = 0 1

bu sayılardan başlayarak kendisinden bir önceki sayı ile toplayarak devam ediyoruz.

0 1

0 + 1 = 1
0 1 1

1 + 1 = 2
0 1 1 2

1 + 2 = 3
0 1 1 2 3

şeklinde devam ediyor.

sanırım burası anlaşıldı.

soru şu şekilde : "fibonacci(x) denildiğinde en kısa adım sayısı ve en az bellek kullanımı ile bu sayıyı hesaplayan algoritmayı herhangi bir dil ile yazın"


not :

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(10) = 55

not 2 :

programlama dillerinin hazır fibonacci kütüphanesi ile yapmak yasaktır. soruda istenen şey algoritmayı sizin implement etmenizdir.

soru gayet açık. bu akşam 00:00 da çözümü açıklayacağım.

katılan arkadaşlara başarılar.

dipnot : bu tarz algoritma soruları programlama yeteneğinizin ve algoritma kabiliyetinizin artmasını sağlar, bana ne faydası olacak diye soran kişilere istinaden bunu belirtiyorum.

dikkat : puvolar size fibonacci yi kodlamanızı söylemiyorum, fibonacci kodunuzu optimize ederek kodlamanızı soruyorum, buna dikkat edin, bazı arkadaşlar direk fibonacci kodunu atıyor buraya.
  • 0
    xlamber 2 ay önce ~ 2 ay önce
    
    <?php
    function fibonacci($deger) { return round(pow((sqrt(5)+1)/2, $deger) / sqrt(5)); }
    ?>
    
    0
    mryoda 2 ay önce
    fibonaccinin matematiksel formülü olduğu için bu şekilde verilen cevapta geçerli.

    fakat burada asıl amaçlanan şey dinamik programlamayı aşılayabilmek.

    matematiksel ifadesi olmayan bir "x" sorusu olduğunu düşünün bunun.

    ayrıca algoritmayı kendiniz implement edin demişim, çözüm için başkasının yazdığı teoriyi kullanmakta aslında bir nevi sorunun kurallarını ihlal ediyor

    onun dışında eline sağlık, ama eğer bir algoritma implement edersen daha hoş olur.
  • 0
    ibrahimipek 2 ay önce ~ 2 ay önce
    hojam php kodunu veriyorum:
    
    <?php 
    echo "Fibonacci Dizisi:<br><br>";
    $a=0;$b=1;$c=1;$d=0;$e=0;
    echo $a."<br>".$b."<br>".$c;
    do{
    $d=$c;
    $e=$b;
    $c=$e+$d;
    $b=$d;
    $a=$e;
    echo "<br>".$c;
    }
    while ($c<=200);
    ?>
    
    0
    mryoda 2 ay önce
    dostum soru optimizasyon içerdiği için bu geçerli bir cevap değil maalesef.

    hard coded fibonacci olmuş bu, hemde baya baya hard coded.. burada asıl optimizasyona geçmeden bu kodun kendisi de optimize edilmeli (:
  • 0
    g7aa3 2 ay önce ~ 2 ay önce
    
    class Program
        { 
            static void Main(string[] args)
            {
                int x = Convert.ToInt32(Console.ReadLine());
                Console.WriteLine(fibonacci(x));
                Console.ReadLine();
            }
            static int fibonacci(int x)
            {
                int result = 0;
                if(x==1)
                {
                    return 1;
                }
                else if(x==0)
                {
                    return 0;
                }
                else
                {
                    result += fibonacci(x - 1) + fibonacci(x - 2);
                }
                return result;
            }
        }
    
    0
    mryoda 2 ay önce
    dostum aynı şekilde sana da cevabın üsttekiyle aynı : "soru optimizasyon içerdiği için maalesef bu da geçerli bir cevap değil"
  • 0
    www 2 ay önce
    ödül yok mu?
    2
    mryoda 2 ay önce
    hurma vereceğim
  • 0
    unnecessary 2 ay önce ~ 2 ay önce
    
    def fib(x):
         if(x==0): return 0
         if(x==1):return 1
         return fib(x-1) + fib(x-2)
    OR
    def fib(n):
        a,b = 0,1
        for i in range(n):
            a,b = a+b,a
        return a
    
    0
    mryoda 2 ay önce
    recursive metodu optimize ederseniz tam doğru olur
  • 0
    jakado 2 ay önce ~ 2 ay önce
    void __cdecl fibonacci(int AA){
    	__int64 * FO  	= new __int64[AA + 1];
    	FO[0]  		= 0;
    	FO[1]  		= 1;
    	for (int i = 2; i <= AA; i++) {
    		FO[i] 	= FO[i - 2] + FO[i - 1];
    	}
    	ShowMessage(FO[AA]);
    	delete []FO;
    }
    
  • 0
    efdali 2 ay önce
    import java.util.Scanner;
    public class fibonacci{
    public static int fib(int sayi){
    if(sayi==0){return 0;}
    if(sayi==1) return 1;
    return fib(sayi-1)+fib(sayi-2);
    
    
    }
    public static void main(String [] args){
    
    Scanner scan=new Scanner(System.in);
    int sayi;
    System.out.println("Sayıyı Giriniz:");
    sayi=scan.nextInt();
    for(int i=0;i<=sayi;i++){
    System.out.println("fibonacci("+i+")="+fib(i));
    }
    }
    }
    0
    mryoda 2 ay önce
    recursive metodu optimize ederseniz tam doğru olur
  • 0
    romica 2 ay önce
    süreyi yarın akşam yapsak? :)
    0
    mryoda 2 ay önce
    benim için farketmez puvo
  • 0
    organik58 2 ay önce ~ 2 ay önce
    function GetFib(x)
    {
      var a=0;
      var b=1;
      var c=0;
    for (i = 0; i < x-1; i++) { 
    c=a+b;
      a=b;
      b=c;
     
    }
      console.log(c);
    }
    0
    romica 2 ay önce
    0
    organik58 2 ay önce
    düzenledim. cevabı beklicez artık
  • 1
    organik58 2 ay önce ~ 2 ay önce
    olmuşmu acemiyim biraz kusra bakmayın javascript
    0
    mryoda 2 ay önce
    dostum eline sağlık, sen direk fibonacci hesaplamasını yaptırmışsın

    birçok arkadaşta onu yaptırmış

    aslında bu soruda istenen şey dynamic programming - memoization kullanarak bir çözüm üretmek.

    yani düz bir döngüyle değilde recursive bir metodu optimize ederek çözüme ulaşmak.
  • 1
    bturker 2 ay önce
    
        static HashMap<Long, Long> fibonacciMap = new HashMap<>(); 
        /*
         * Recursive ile olusan dallanmalarda ayni sonuca goturen islemleri bir kez
         * hesaplayip daha sonra ki tekrarlarda key value ile islem yapmadan sonuca
         * ulasiyoruz. 'Memoization' ile asagida goruldugu gibi fibonacci(4) icin fibonacci(2) icin tekrardan islem yapilmadi.
         *                           fibonacci(4) = 3    map.put(4,3)
         * 				 /              \
         *               fibonacci(3)		fibonacci(2) = map.get(2);
         *               map.put(3,2);       
         * 	  	     /                  \
         *    fibonacci(2) = 2      fibonacci(1) = 1
         *      map.put(2,1);         basecase
         *       /         \            
         * fibonacci(1) = 1 fibonacci(0) = 0
         *  basecase     basecase 
        */
        
    
        public static void main(String[] args) {
    	System.out.println(fibonacci(111));
        }
    
        public static long fibonacci(long num) {
    	if (num == 1 || num == 0) { // base case - recursion'i sonlandirmamizi saglayan cikis
    	    return num;
    	}
    	if (fibonacciMap.get(num) != null) {  // key'lerimizi fibonacci() methodumuza yolladigimiz ardisil sayilar ile yapiyoruz. aramamizida bu sekilde
    	    return fibonacciMap.get(num);
    	} else {
    	    long fibonacciValue = fibonacci(num - 1) + fibonacci(num - 2);
    	    fibonacciMap.put(num, fibonacciValue);
    	    return fibonacciValue;
    	}
        }
    
    0
    mryoda 2 ay önce
    doğru ve geçerli olan cevap budur. istediğimiz şey dynamic programming ve memoization ile çözümüydü.

    arkadaş attı eline sağlık.
  • 0
    wtapostar 2 ay önce
    	function fib_puv($a, $v = 0, $l = 0){
    		
    		if($a == 0){
    			return $v;
    		}
    		
    		return fibo_puvo($a-1, $v+$l , $v);
    	}
    
    # Örnek; 10. değer için çıktıyı verir.  başlangıç için  0 ve 1 değeri  sabittir, değiştirmeyiniz, sadece kaçıncı #fibbonaci sayısını bulmak istiyorsanız 10 yerine onu yazınız. Çıktı => 55 
     
    echo fib_puv(10, 0, 1);
    
    
    
  • 0
    wtapostar 2 ay önce
    ilk attıgım yorumu düzenleyerek atıyorum, yazdıgınız kurala uygun düzenledim.

    
    
    <?php
    
    	function fib_puv($a, $v = 0, $l = 1){
    		
    		if($a == 0){
    			return $v;
    		}
    		
    		return fib_puv($a-1, $v+$l , $v);
    	}
    
    	# 10. cu fibonacci sayısını verir.
    
    	echo fib_puv(10);
    
    ?>
    
    
  • 0
    pys60 2 ay önce
    def fibr(n):
    if n==1 or n==2:
    return 1
    return fibr(n-1)+fibr(n-2)
    print fibr(5)
  • 0
    keremozden 2 ay önce
    php ile yazdım buyrun kabul mu bilmiyorum ama sonuç veriyor...
    $_aryFIBONACCI = array(0,1);
    $_iFIBONACCI = 20;
    $_iPREV_NUMMER = 0;
    for($i = 1; $i < $_iFIBONACCI; $i++){
    $_iCOUNT = count($_aryFIBONACCI);
    $_aryFIBONACCI[] = $_aryFIBONACCI[$_iCOUNT-1] + $_aryFIBONACCI[$_iCOUNT-2];
    }
    var_dump($_aryFIBONACCI);
  • 0
    onlyastranger 2 ay önce ~ 1 ay önce
    c# kodunu aşağıda paylaşıyorum. biraz geç oldu ama işlerimden yetişemedim :)
    yorumlarınızı beklerim
    
          class Program
        {
            static void Main(string[] args)
            {
                B:
                //Kural Xn+1 = Xn + Xn-1. n ideksi ifade etmektedir. X0=0, X1=1;
                //n>=2 olmalı. çünkü 0 ve 1 indeksli sayılar dizinin başlatılması için zaten var!!!
                int x0 = 0, x1 = 1; 
                int Index = Convert.ToInt32(Console.ReadLine());
                Console.WriteLine(FindFibonacci(x1, x0, Index));
                Console.WriteLine("----------------Bir sonraki--------------");
                goto B;
            }
    
            static long FindFibonacci(long CurrentNumber, long PreviousNumber, int Index)
            {
                long NewCurrentNumber = CurrentNumber + PreviousNumber;
                if (Index > 2)
                {
                    Index--;
                    return FindFibonacci(NewCurrentNumber, CurrentNumber, Index);
                }
                else if (Index == 0) return 0;
                return NewCurrentNumber;
            }
        }
    


  • programlama

    Donanıma ne yapması gerektiğini söyleyen sanat! Bilgi paylaşımı amacıyla kurulmuş bu bölümde yeni bilgiler edinebilir, kendinizi geliştirebilir ya da bilgilerinizi paylaşarak katkıda bulunabilirsiniz.

    124 takipçi

  • abone ol

  • moderatörler

    ssl

    mryoda
    erkansivas35
  • bölüm kuralları

    sizden uymanızı rica edeceğimiz bazı basit kurallar var. 

    • bilgisayar teknolojileri ile ilgisi olmayan içerikleri bu bölümde oluşturmayın. yorumlar için de aynı geçerlilik mevcuttur.
    • yazılım bir sanattır ve siyasetin, küfür ve hakaretin sanatla ilgisi yoktur. lütfen yorumlarınıza ve içeriklerinize özen bu konuda özen gösterin.
    • puiv içerisinde başka bir üyenin yazısını bütün olarak kesinlikle kopyalamayın. kullanmak istediğiniz kısımı alıntı işareti içerisine alıp, orjinal başlığına link verin.
    • etik ya da legal olmayan her türlü yazılımsal ürün ya da içerik paylaşımı yasaktır. hack, crack vb.


    içerik standartları

    • anlatacağımız şeyi çok iyi bilmemize gerek yok, herkes her şeyi bilemez. siz başlatın, elbet konuya hakim bir yazarımız vardır.
    • içeriğimizde kod varsa, kodumuza yorum ekleyip öğrenmek isteyen arkadaşlara destek olalım!
    • puiv standartları gereği paylaştığınız kodların tüm harfleri lowercase olacaktır. bir başkası kopyalayıp çalıştırmaya çalıştığında hata almayacağına emin olalım. yorum kullanarak belirtelim.
    • resim ya da anket paylaşımları haricinde içeriğimizin çoğunu anlatımların oluşturması gerektiğini unutmayalım.

    bölüm kuralları hakkında bilgi edinmek ve fikir belirtmek için tıklayınız.

popi yükleniyor...

popi yükleniyor...

pupu yükleniyor...

pupu yükleniyor...

tepe yükleniyor...

tepe yükleniyor...

g20 yükleniyor...

g20 yükleniyor...