Ruby实现的矩阵连乘算法

2024-10-04 13:15:06

动态规划解决矩阵连乘问题，随机产生矩阵序列，输出形如((A1(A2A3))(A4A5))的结果。

代码：

#encoding: utf-8
=begin
author: xu jin, 4100213
date: Oct 28, 2012
MatrixChain
to find an optimum order by using MatrixChain algorithm
example output:
The given array is:[30, 35, 15, 5, 10, 20, 25]
The optimum order is:((A1(A2A3))((A4A5)A6))
The total number of multiplications is: 15125

The random array is：[5, 8, 8, 2, 5, 9]
The optimum order is:((A1(A2A3))(A4A5))
The total number of multiplications is: 388
=end

INFINTIY = 1 / 0.0
p = [30, 35, 15, 5, 10, 20, 25]
m, s = Array.new(p.size){Array.new(p.size)}, Array.new(p.size){Array.new(p.size)}

def matrix_chain_order(p, m, s)
   n = p.size - 1
   (1..n).each{|i| m[i][i] = 0}
   for r in (2..n) do
     for i in (1..n - r + 1) do
       j = r + i - 1
       m[i][j] = INFINTIY
       for k in (i...j) do
         q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
         m[i][j], s[i][j] = q, k if(q < m[i][j])
       end
     end
   end
end 

def print_optimal_parens(s, i, j)
   if(i == j) then
    print "A" + i.to_s
   else
    print "("
    print_optimal_parens(s, i, s[i][j])
    print_optimal_parens(s, s[i][j] + 1, j)
    print ")"
   end
end

def process(p, m, s)
   matrix_chain_order(p, m, s)
   print "The optimum order is:"
   print_optimal_parens(s, 1, p.size - 1)
   printf("\nThe total number of multiplications is: %d\n\n", m[1][p.size - 1])
end

puts "The given array is:" + p.to_s
process(p, m, s)

#produce a random array
p = Array.new
x = rand(10)
(0..x).each{|index| p[index] = rand(10) + 1}
puts "The random array is：" + p.to_s
m, s = Array.new(p.size){Array.new(p.size)}, Array.new(p.size){Array.new(p.size)}
process(p, m, s)

Ruby实现的最优二叉查找树算法

算法导论上的伪码改写而成,加上导论的课后练习第一题的解的构造函数. 复制代码代码如下: #encoding: utf-8 =begin author: xu jin date: Nov 11, 2012 Optimal Binary Search Tree to find by using EditDistance algorithm refer to <<introduction to algorithms>> example output: "k2 is the r
Ruby实现的图片滤镜算法代码

原图一.灰度算法彩色照片每一个像素的颜色值由红.绿.蓝三种值混合而成,红绿蓝的取值分别由很多种,于是像素的颜色值也可以有很多种颜色值,这就是彩色图片的原理,而灰度照片则只有256种颜色,一般的处理方法是将图片颜色值的RGB三个通道值设为一样,这样图片的显示效果就会是灰色. 灰度处理一般有三种算法: 最大值法:即新的颜色值R＝G＝B＝Max(R,G,B),这种方法处理后的图片看起来亮度值偏高. 平均值法:即新的颜色值R＝G＝B＝(R+G+B)/3,这样处理的图片十分柔和加权平均值法:即新的颜
ruby实现的插入排序和冒泡排序算法

1.插入排序复制代码代码如下: seq = [3,4,9,0,2,5,9,7,1] 1.upto(seq.length-1) do |i| if seq[i] < seq[i-1] tmp = seq[i] j = i-1 while(j>=0 && tmp<seq[j]) do seq[j+1] = seq[j] j=j-1 end seq[j+1]=tmp endend seq.each {|num| puts
Ruby实现二分搜索(二分查找)算法的简单示例

在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search).对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法.搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束:如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较.如果在某一步骤数组为空,则代表找不到.这种搜索算法每一次比较都使搜索范围缩小一半
Ruby实现的3种快速排序算法

刚学Ruby,正巧算法老师鼓励用不熟悉的语言来写算法,我就用Ruby吧~~ 话说Ruby可真是超厉害,好多凭直觉的方法都可以用.....无限膜拜中.... 期间我遇到了invalid multibyte char (US-ASCII)的错误,解决办法是在开头加一个#encoding:utf-8 这个错误在stackoverflow上有人问到过,某人给出的回答是 Write # encoding: utf-8 on top of that file. That changes the defaul
Ruby实现的合并排序算法

算法课的作业,利用分治法,合并排序. #encoding: utf-8 #author: xu jin, 4100213 #date: Oct 27, 2012 #MergeSort #to sort an array by using MergeSort algorithm #example output: #The original array is:[4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70] #The sorted array i
Ruby实现的各种排序算法

时间复杂度:Θ(n^2) Bubble sort 复制代码代码如下: def bubble_sort(a) (a.size-2).downto(0) do |i| (0..i).each do |j| a[j], a[j+1] = a[j+1], a[j] if a[j] > a[j+1] end end return a end Selection sort 复制代码代码如下: def selection_sort(a) b =
Ruby实现的矩阵连乘算法

动态规划解决矩阵连乘问题,随机产生矩阵序列,输出形如((A1(A2A3))(A4A5))的结果. 代码: #encoding: utf-8 =begin author: xu jin, 4100213 date: Oct 28, 2012 MatrixChain to find an optimum order by using MatrixChain algorithm example output: The given array is:[30, 35, 15, 5, 10, 20, 25]
C++实现矩阵原地转置算法

本文实例描述了C++实现矩阵原地转置算法,是一个非常经典的算法,相信对于学习C++算法的朋友有很大的帮助.具体如下: 一.问题描述微软面试题:将一个MxN的矩阵存储在一个一维数组中,编程实现矩阵的转置. 要求:空间复杂度为O(1) 二.思路分析下面以一个4x2的矩阵A={1,2,3,4,5,6,7,8}进行分析,转置过程如下图: 图中右下角的红色数字表示在一维数组中的下标.矩阵的转置其实就是数组中元素的移动,具体的移动过程如下图: 我们发现,这些移动的元素的下标是一个个环,下标1的元素移动到
Python实现螺旋矩阵的填充算法示例

本文实例讲述了Python实现螺旋矩阵的填充算法.分享给大家供大家参考,具体如下: afanty的分析: 关于矩阵(二维数组)填充问题自己动手推推,分析下两个下表的移动规律就很容易咯. 对于螺旋矩阵,不管它是什么鬼,反正就是依次向右.向下.向右.向上移动. 向右移动:横坐标不变,纵坐标加1 向下移动:纵坐标不变,横坐标加1 向右移动:横坐标不变,纵坐标减1 向上移动:纵坐标不变,横坐标减1 代码实现: #coding=utf-8 import numpy ''''' Author: afanty
基于随机梯度下降的矩阵分解推荐算法（python）

SVD是矩阵分解常用的方法,其原理为:矩阵M可以写成矩阵A.B与C相乘得到,而B可以与A或者C合并,就变成了两个元素M1与M2的矩阵相乘可以得到M. 矩阵分解推荐的思想就是基于此,将每个user和item的内在feature构成的矩阵分别表示为M1与M2,则内在feature的乘积得到M:因此我们可以利用已有数据(user对item的打分)通过随机梯度下降的方法计算出现有user和item最可能的feature对应到的M1与M2(相当于得到每个user和每个item的内在属性),这样就可以得到通
C语言杨氏矩阵查找算法实例讲解

目录一.杨氏矩阵介绍二.查找算法 1.查找思路 2.步骤 3.代码三.杨氏矩阵例题代码特别注意四.总结本文以C语言实现,介绍杨氏矩阵中通用的查找算法. 一.杨氏矩阵介绍杨氏矩阵种,每一行的数都从左到右递增,每一列的数都从上到下递增.如下图是一个简单的杨氏矩阵: 有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在. 要求:时间复杂度小于O(N) 二.查找算法 1.查找思路杨氏矩阵是很有特点的,它有规律递增的特点决定了针对
Python光学仿真学习衍射算法初步理解

对衍射最经典的解释是Huygens-Fresnel原理,Huygens认为波阵面上每一点都会成为新的波源,这些子波源的相互干涉就形成了衍射.这显然是一种离散的观点,仿佛是专门为程序员准备的一样. 假设一束光打在一个方形孔上,这个方形孔被细分成 n×n个网格,那么每个网格都相当于是一个小孔,而这些小孔的互相干涉,即为衍射.随着网格不断被细分,最终可以逼近真实的衍射情形.那么,假设矩孔处为等相位面,其网格坐标为 (i,j),到衍射屏距离为 d d d,那么对于衍射屏上任意一点P(x,y),其光强为
Python验证码识别处理实例

一.准备工作与代码实例 (1)安装PIL:下载后是一个exe,直接双击安装,它会自动安装到C:\Python27\Lib\site-packages中去, (2)pytesser:下载解压后直接放C:\Python27\Lib\site-packages(根据你安装的Python路径而不同),同时,新建一个pytheeer.pth,内容就写pytesser,注意这里的内容一定要和pytesser这个文件夹同名,意思就是pytesser文件夹,pytesser.pth,及内容都要一样! (3)Te

Ruby实现的矩阵连乘算法

相关推荐

随机推荐