アルゴリズムと計算量


プログラム


  1. フィボナッチ数 (再帰)

    def fibr(k)
        if k==0 || k==1
            1
        else
    	fibr(k-1) + fibr(k-2)
        end
    end
    
  2. フィボナッチ数 (数え上げ)

    def fibl(k)
        f=1
        p1=1
        for i in 2..k
            p2 = p1      #fib(i-2)
            p1 = f       #fib(i-1)
            f  = p1 + p2 #fib(i)
        end
        f                #fib(k)
    end
    
  3. フィボナッチ数 (数え上げ,下6桁)

    def fibl6(k)
        f=1
        p1=1
        for i in 2..k
            p2 = p1
            p1 = f
            f  = (p1 + p2) % 1000000
        end
        f
    end
    
  4. 単純整列法

    def simplesort(a)
      for i in 0..(a.length()-1)
        k = min_index(a,i)
        v = a[i]
        a[i] = a[k]
        a[k] = v
      end
      a
    end
    
  5. 併合整列法

    def merge(a,b)
      c = Array.new(a.length()+b.length())
      ia=0	
      ib=0
      ic=0
      while ia < a.length() && ib < b.length()
        if a[ia] < b[ib]
          c[ic] = a[ia]
          ia = ia + 1
          ic = ic + 1
        else
          c[ic] = b[ib]
          ib = ib + 1
          ic = ic + 1
        end
      end
      # a,bのうちまだ残っている方を全てcに移す(省略)
      c
    end
    
    def mergesort(a)
      n = a.length()
      from = Array.new(n)
      for i in 0..(n-1)
        from[i] = [ (a[i]) ]
      end
      while n > 1
        to = Array.new((n+1)/2)
        for i in 0..(n/2-1)
          to[i] = merge(from[i*2], from[i*2+1])
        end
        if !is_even(n)
          to[(n+1)/2-1]=from[n-1]
        end
        from=to
        n=(n+1)/2
      end
      from[0]
    end
    
  6. クイックソート

    def quicksort(a)
      qsort(a, 0, a.length()-1)
    end
    
    def qsort(a, from, to)  
      if from < to
        pivot = (from + to) / 2
        med = a[pivot]
        l = from
        r = to  
        while l <= r do
          while a[l] < med
            l = l + 1
          end
          while a[r] > med
            r = r - 1
          end
          if l <= r
            tmp = a[l]
            a[l] = a[r]
            a[r] = tmp
            l = l + 1
            r = r - 1
          end
        end
        qsort(a, from, r)
        qsort(a, l, to)
      end
      a
    end
    

2016年11月13日作成
伊知地 宏
Copyright (C) Hiroshi Ichiji, 2016. All rights reserved.