算法 标签

协同过滤Item-based算法实现电影推荐系统

  |   0 评论   |   1,165 浏览

摘要: 采用离线式计算推荐给每位用户的电影,采用 Item-based 算法并做了适当修改,
主要分两部分:

  1. 计算电影的相似度:利用调整的余弦相似度计算方法;
  2. 相似度加权求和:使用用户已打分的电影的分数进行加权求和,权值为用户未打分的各电影与打分的各电影的相似度,然后对所有相似度的和求平均。

系统详细设计

离线计算推荐电影模块

系统所用算法

本系统采用协同过滤(Collaborative Filtering)推荐算法。协同过滤推荐算法分为预测过程和推荐过程,其包括 Item-based 算法和 User-based 算法,但经查阅相关资料发现 User-based 算法存在两个问题:

  1. 数据的稀疏性:一个大型的电影推荐系统会有大量的电影信息,用户已打分的电影可能只占总量的很少一部分,不同用户之间电影打分的重叠性较低,导致算法无法找到一个兴趣用户;
  2. 算法的扩展性:最近邻算法的计算量会随着用户和电影信息数量的增加而增加,不适合信息量大的情况。所以本系统采用了 Item-based 协同过滤算法,并对其做了适当修改。

计算过程

数据库内部排序算法之两阶段多路归并排序算法实现

  |   0 评论   |   469 浏览

摘要: 两阶段归并排序算法是数据库查询的一个基础技术,在数据库应用中,常常采用“两阶段多路归并排序算法”来解决对海量数据的排序问题(这里的海量数据是指数据大小远远超过了数据库可用的主存的大小,无法将所有数据一次性的载入主存进行排序)。

前言

基于斯坦福大学的《数据库系统实现》,实现两阶段多路归并排序算法,通过 merge-sort 算法的实现,理解外存算法所基于的 I/O 模型与内存算法基于的 RAM 模型的区别;理解不同的磁盘访问优化方法是如何提高数据访问性能的。

首先生成一个具有 10,000,000 个记录的文本文件,其中每个记录由 100 个字节组成。实验只考虑记录的一个属性 A,假定 A 为整数类型。记录在 block 上封装时,采用 non-spanned 方式,即块上小于一个记录的空间不使用。Block 的大小可在自己的操作系统上查看,xp 一般为 4096 bytes。在内存分配 50M 字节的空间用于外部 merge-sort。要求设计和实现程序完成下列功能:

  1. 生成文本文件,其中属性 A 的值随机产生。
  2. 对文本文件中的记录,按照属性 A 进行排序,其中在第二阶段的排序中每个子列表使用一

用Dijkstra算法求解无向图的最短路径

  |   0 评论   |   649 浏览

Dijkstra 算法是典型的算法。Dijkstra 算法是很有代表性的算法。Dijkstra 一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用 OPEN, CLOSE 表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。      

微软编程比赛里面的一道难度系数 5% 的编程题目如下:

image
image

Dijkstra 算法是用来求解图中顶点到另外其他顶点的最短路径的,根据题目,我们可以把每两个岛屿往来所花的最少金币当成图中的边权值,由此可以用 Dijkstra 算法来解决这个问题。

image

ACM刷题之-内存分配(POJ-1193 )

  |   0 评论   |   356 浏览

摘要: 内存是计算机重要的资源之一,程序运行的过程中必须对内存进行分配。 经典的内存分配过程是这样进行的: 1. 内存以内存单元为基本单位,每个内存单元用一个固定的整数作为标识,称为地址。地址从 0 开始连续排列,地址相邻的内存单元被认为是逻辑上连续的。我们把从地址 i 开始的 s 个连续的内存单元称为首地址为 i 长度为 s 的地址片。 2. 运行过程中有若干进程需要占用内存,对于每个进程有一个申请时刻 T,需要内存单元数 M 及运行时间 P。在运行时间 P 内(即 T 时刻开始,T+P 时刻结束),这 M 个被占用的内存单元不能再被其他进程使用。 3、假设在 T 时刻有一个进程申请 M 个单元,且运行时间为 P,则: 1. 若 T 时刻...

算法分析:

  1. 维护一个进程的链表,每个节点存有进程开始时间 t,进程运行时间 p, 在内存中的首地址 s,占用内存大小 m,和下一节点指针。

  2. 维护一个队列,表示还没有空间运行的进程。

  3. 维护一个释放内存的最早时间 nexttime,每读入一个新进程的时候,若进程开始时间不小于 nexttime,表示有进程在这之前已结束(可能不止一个),将其从链表删除,并循环检测队首

世界名画陈列馆问题(回溯法)

  |   0 评论   |   333 浏览

算法问题描述:

世界名画陈列馆问题。世界名画陈列馆由 m× n 个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右 4 个陈列室。试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。

算法问题形式化表示

本问题的 m*n 的陈列室的解可表示如下图所示。其中 1 代表在该陈列室设置警卫机器人哨位,0 表示未在该陈列室设置警卫机器人哨位。

问题描述

最为极端的情况是所有元素的值为 1。那什么情况下是最优解呢?就是设置警卫机器人哨位数最少即为最优。因为每个矩阵中的值都可以为 1 或 0,有 m*n 个元素,有 种可能满足约束条件的矩阵,要从 种可能中遍历找到满足约束条件的 1 的个数最小的矩阵。由此可见这是一个 NP 问题。这里的约束条件就是当某一个元素为 1 时,相邻的 4 个方向上的

ACM刷题之-POJ-1002(487-3279)

  |   0 评论   |   286 浏览

Description

Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call the University of Waterloo by dialing the memorable TUT-GLOP. Sometimes only part of the number is used to spell a word. When you get back to your hotel tonight you can order a pizza from Gino's by dialing 310-GINO. Another way to make a telephone number memorable is to group the digits in a memorable way. Yo

ACM刷题之-POJ-1011(Sticks)

  |   0 评论   |   259 浏览

Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line con

ACM刷题之-POJ-1014(Dividing)

  |   0 评论   |   258 浏览

Description

Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbl

ACM刷题之-POJ-1061(青蛙的约会)

  |   0 评论   |   302 浏览

Description

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙 A 和青蛙 B,并且规定纬度线上东经 0 度处为原点,由东往西为正方向,单位长度 1 米,这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 x,青蛙 B 的出发点坐标是 y。青蛙 A 一次能跳 m 米,青蛙 B 一次能跳 n 米,两只青蛙跳一次所花费的时间相同。纬度线总长 L 米。现在要你求出它们跳了几次以后才会碰面。

Input

输入只包括一行 5 个整数 x,y,m,n,L,其中 x≠ y < 2000000000,0 < m、n < 2000000000,0 < L < 21

ACM刷题之-POJ-1396(Simple Arithmetics)

  |   0 评论   |   235 浏览

Description

One part of the new WAP portal is also a calculator computing expressions with very long numbers. To make the output look better, the result is formated the same way as is it usually used with manual calculations.

Your task is to write the core part of this calculator. Given two numbers and the requested operation, you are to compute the result and print it in the form specified below. With addition and subtraction, the numbers are written below each other. Multiplication

ACM刷题之-POJ-2192(Zipper)

  |   0 评论   |   238 浏览

Description

Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order.
For example, consider forming "tcraete" from "cat" and "tree":
String A: cat
String B: tree
String C: tcraete
As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee

Kmeans算法解析及基于MapReduce的并行化实现

  |   0 评论   |   596 浏览

Kmeans 算法,最为经典的基于划分的聚类方法

Kmeans 算法:

k-means 算法接受参数 k ;然后将事先输入的 n 个数据对象划分为 k 个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。

K-means 算法是最为经典的基于划分的聚类方法,是十大经典数据挖掘算法之一。K-means 算法的基本思想是:以空间中 k 个点为中心进行聚类,对最靠近他们的对象归类。通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果。

假设要把样本集分为 c 个类别,算法描述如下:

(1)适当选择 c 个类的初始中心;

(2)在第 k 次迭代中,对任意一个样本,求其到 c 个中心的距离,将该样本归到距离最短的中心所在的类;

(3)利用均值等方法更新该类的中心值;

(4)对于所有的 c 个聚类中心,如果利用(2)(3)的迭代法更新后,值保持不变,则迭代结束,否则继续迭代。

该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。

ACM刷题之-2015微软编程之美资格赛

  |   0 评论   |   307 浏览

题目一:2 月 29

时间限制:2000ms

单点时限:1000ms

内存限制:256MB

描述

给定两个日期,计算这两个日期之间有多少个 2 月 29 日(包括起始日期)。
只有闰年有 2 月 29 日,满足以下一个条件的年份为闰年:

  1. 年份能被 4 整除但不能被 100 整除
  2. 年份能被 400 整除

输入

第一行为一个整数 T,表示数据组数。

之后每组数据包含两行。每一行格式为"month day, year",表示一个日期。month 为{"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November" , "December"}中的一个字符串。day 与 year 为两个数字。

数据保证给定的日期合法且第一个日期早于或等于第二个日期。

输出

对于每组数据输出一行,形如"Case #X: Y"。X 为数据组数,从 1 开始,Y 为答案。

数据范围

ACM刷题之-POJ-3749(破译密码)

  |   0 评论   |   243 浏览

Description

据说最早的密码来自于罗马的凯撒大帝。消息加密的办法是:对消息原文中的每个字母,分别用该字母之后的第 5 个字母替换(例如:消息原文中的每个字母 A 都分别替换成字母 F)。而你要获得消息原文,也就是要将这个过程反过来。
密码字母:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z M
原文字母:V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

注意:只有字母会发生替换,其他非字母的字符不变,并且消息原文的所有字母都是大写的。

Input

最多不超过 100 个数据集组成,每个数据集之间不会有空行,每个数据集由 3 部分组成:
起始行:START
密码消息:由 1 到 200 个字符组成一行,表示凯撒发出的一条消息.
结束行:END
在最后一个数据集之后,是另一行:ENDOFINPUT

Output

每个数据集对应一行,是凯撒的原始消息。

Sample Input

START NS BFW, JA

ACM刷题之-POJ-1191(棋盘分割)

  |   0 评论   |   322 浏览

Description

将一个 8 * 8 的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有 n 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)
image
原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 n 块矩形棋盘,并使各矩形棋盘总分的均方差最小。
均方差,其中平均值,xi 为第 i 块矩形棋盘的总分。
请编程对给出的棋盘及 n,求出 O'的最小值。

Input

第 1 行为一个整数 n(1 < n < 15)。
第 2 行至第 9 行每行为 8 个小于 100 的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

Output

仅一个数,为 O'(四舍五入精确到小数点后三位)。

Sample Input

3 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1