【XP提问区活动】R考场活动结果 - Project1

=begin
下面是附加题，多少和算法有点关系，大家可以选择作答。
一共有三道题目，答题的时候可以任选一道作答。三个题目的难度不同，因此各自的满分
也不一样，请慎重选择。
注意，只允许选择一道题作答，如果多答，则按照题号最小的题目进行评判，不考虑其他
的题目。因此回答之前要注明所选题号。
=end
#=============================================================================
# 附加题1（猴王问题）：本小题满分50分
#-----------------------------------------------------------------------------
# 现在考虑 n 只猴子围成一圈，编号 ID 为1,2,3,...,n，顺序为逆时针。现在从ID为1的
# 猴子开始报数 1 ，按照逆时针顺序，下面的猴子报数2,3,4,...，现在指定一
# 个数 m，每当有猴子报出数 m 时，它就被淘汰，而它的下一个猴子（仍是按照逆时针
# 次序）继续从 1 开始报数，如此反复。当最后剩下一只猴子时，这只猴子就被选中当做
# 猴群的猴王。问题：请写出一个算法，在给定猴子数目 n 和指定的正整数 m 的条件下
# 求出最后剩下的猴子（猴王）的ID。
#=============================================================================
#=============================================================================
# 本题思路：考虑到猴子们围成一圈，因此可以设计成“循环链表”的模式。定义出猴子
# 类 Monkey，这个类的属性只有两个，一个是猴子的 ID，另一个是它的下一只猴子。
# 为了处理问题方便，还定义出“猴子队列”类 Monkey_Queue。制作队列完毕后，开始
# 循环，逐个剔出被淘汰的猴子。直到队列的长度为1即可。
#=============================================================================
module Ex1
N = 6
M = 1
class Monkey
attr_reader :id # 猴子 ID
attr_accessor :next_monkey # 下一只猴子
def initialize(id)
@id = id
@next_monkey = nil
end
end
class Monkey_Queue
attr_reader :size # 当前队列长度
attr_reader :data # 保存着所有猴子的信息，注意，是所有，而不是当前队列中的
attr_accessor :current # 当前被操作的猴子
def initialize(num)
@size = num
@data = Array.new(num){|i| Monkey.new(i+1)}
@data.each_with_index{|monkey, i| monkey.next_monkey = @data[(i+1) % @data.size]}
@current= @data[0]
end
#-------------------------------------------------------------------------
# 删除一个猴子
#-------------------------------------------------------------------------
def delete(monkey)
# 确保队列长度超过1
return if @size == 1
# 找到前驱结点
pre = @data.find{|member| member.next_monkey == monkey}
# 重新设置次序（下面那个设置为nil的必要）
@current= pre.next_monkey = monkey.next_monkey
monkey.next_monkey = nil
# 队列长度-1
@size -= 1
end
end
#---------------------------------------------------------------------------
# 主函数
#---------------------------------------------------------------------------
def self.solve
# 生成 N 个猴子的环列
queue = Monkey_Queue.new(N)
# 循环，直到剩下一只猴子为止
until queue.size == 1
# 找到下一只被淘汰的猴子
(M-1).times do
queue.current = queue.current.next_monkey
end
# 剔除
queue.delete(queue.current)
end
# 显示结果
p queue.current.id
end
end
#=============================================================================
# 附加题2（括号匹配问题）：本小题满分100分
#-----------------------------------------------------------------------------
# 这是一个很经典的问题，写脚本的同学都知道，括号'()'在脚本中起到了很关键的作用
# ，比如说改变运算顺序，包含方法参数等等。但是，有些书写错误的括号不能通过编译
# 会发生 Syntax Error，比如说(1 + 2)) + 3，它就多了一个右括号。现在的问题是，
# 给定一个字符串，能否确定其中所有不能匹配的括号的位置？
# 为了使得问题更加简单，我们假定字符串中出现的括号只有圆括号'()'一种，方括号
# 和花括号等其他类别的括号不作考虑。当然，除了括号以外，其它字符（比方说字母
# 、数字、空格）会出现在表达式中。请设计一个算法，为其中所有不能匹配的括号作
# 出特殊标记，如果一个左括号没有对应的右括号，则在相应位置输出'，如果一个右
# 括号没有对应的左括号，则在相应位置输出'?'。
# 例（两边的引号代表字符串，不算内容）：
# Input1: "())"
# Output1:" ?"
# Input2: "))(()((((xy))))"
# Output2:"??$ "
#=============================================================================
#=============================================================================
# 本题思路：考虑现实中我们从左到右的阅读顺序，这里的括号匹配也是同样的道理。
# 在这里我们只考虑括号的出现时机。从左到右阅读时，如果发现了一个左括号，那么
# 我们一定要找到与之对应的右括号。如果一开始就发现了个右括号，那么这个括号肯定
# 是有问题的。如果我们读到左括号，继续向右搜寻，读到了一个右括号，那么这两个
# 括号就会自然配对，从而消去这两个括号，不作考虑。如果仍然读到左括号，那么我们
# 就把手头已有的这个括号放弃，暂不考虑，而去为最近的一个左括号寻找右括号。
# 因此我们可以定义一个栈模型，从左到右依次处理每个字符，处理方式如下：
# 1.读到一个左括号，入栈。
# 2.读到一个右括号，观察栈顶部是不是左括号，如果是，则把左括号弹出栈。如果不是
# 则将此右括号入栈。
# 3.读到其他字符，跳过。
# 这样一来，处理完毕后，栈中剩下的所有字符就是无法进行配对的字符，全部弹出，然
# 后按照索引做标记即可（索引可能需要进行预处理）。
#=============================================================================
module Ex2
INPUT = "))(()((((xy))))"
class Char_With_Index
attr_accessor :char # 字符内容
attr_accessor :index # 索引
def initialize(char, index)
@char= char
@index = index
end
end
def self.solve
# 预处理，实际上就是为每个字符标上索引，以便于查找
input = Array.new(INPUT.size){|i| Char_With_Index.new(INPUT[i], i)}
# 初始化栈
stack = []
# 循环，直到所有字符都被处理到
until input.empty?
# 拿出一个字符
ch = input.shift
# 如果是左括号
if ch.char.chr == "("
# 入栈
stack.push(ch)
end
# 如果是右括号
if ch.char.chr == ")"
# 栈为空或者栈顶不是左括号
if stack.empty? || stack[-1].char.chr != "("
# 入栈
stack.push(ch)
else
# 栈顶元素（一定是左括号）出栈
stack.pop
end
end
end
# 输出结果
output = " " * INPUT.size
# 替换
stack.each do |ch|
ch.char.chr == "(" ? output[ch.index] = "$" : output[ch.index] = "?"
end
p output
end
end
#=============================================================================
# 附加题3（DNA序列比对问题）：本小题满分150分
#-----------------------------------------------------------------------------
# DNA序列分析现在的应用价值比较大，有了它就可以为生物的同源性提供有力的证据。
# 这里的DNA序列比对，特指给定两串基因X和Y，我们来比较它们的相似性。但是由于
# 时间久远，两段DNA可能不完全相同，因此我们要设计一个匹配方式，来将这两个DNA
# 进行配对。
# 其中，我们考虑下面两种配对方式
# 这里，设基因X：AGCCT
# 设基因Y：ACCG
#（1）字母——字母：即两个字母相互匹配
#（2）字母——空位：如果X和Y不等长，那么则要在短的那个基因处插入空格，插入的
# 空格位置可以任意，但是基因Y的相对次序不可以变。注，也可以在基因X的地方
# 插入空格，但是也不可以改变基因X的相对次序，若这样做，基因Y就必须插入更
# 多的空格。
# 例（下划线_代表空位）：
# 基因X：AGCCT
# 基因Y：A_CCG
# 另外一种可能的配对方式为：
# 基因X：AGCC_T
# 基因Y：A_CCG_
# 注：此时Y的最后一位要用空位补齐。
# 自然，对于一组基因X和Y，配对的方式多种多样，现在我们利用一个打分原则对所有
# 的配对方式进行评价，现在这个评价方式如下：
#（1）如果字母和字母进行配对，进行配对的两个字母相同，分数+1
# 进行配对的两个字母不同，分数-1
#（2）如果字母和空位进行配对，无论怎么匹配，分数均-1
# 例如，上面两个例子的配对方式：
# 基因X：AGCCT
# 基因Y：A_CCG
# 五个位置分数为+1,-1,+1,+1,-1，总分为1分
# 另一种匹配方式：
# 基因X：AGCC_T
# 基因Y：A_CCG_
# 六个位置分数为+1,-1,+1,+1,-1,-1,总分为0分
# 显然前一种配对方式要好于后一个。
# 那么，我们的问题自然是，在给定基因X和基因Y，并且在这个打分原则的条件下，
# 找出得分最高的匹配方式。
# 在这里，基因X：ATGCCTGA
# 基因Y：AGCTAA
#=============================================================================
#=============================================================================
# 本题思路：配对的方式多种多样，通过计算（利用斯特林公式）我们可以大概估计出
# 需要列出的配对方式大概是指数量级。因此穷举定然会十分麻烦。因此我们考虑动态
# 规划算法。在这里列出一个二维表格F（可以看作二维数组），其中F[i][j]就表示序
# 列 X 的前 i 个和序列 Y 的前 j 个进行匹配，所能达到的最高得分。因此假设序列
# X和Y的长度分别为m和n，那么F[m][n]就是我们要求的最高得分。
# 那么如何计算F[m][n]？这就要用到递推式子。
# 假设我们要求F[i][j]，那么我们应该怎么看呢？
# 我们看匹配的最后一位（注意，匹配结束后，X和Y可以看作是等长的，不足的位置已
# 经用空格替代了），它无非有三种情况：
# （1）序列X的最后一位真正的字母和序列Y添加的空格配对
# （2）序列X添加的空格和序列Y的左后一位真正的字母配对
# （3）序列X和序列Y的最后一位真正的字母配对
# 注意不存在空格和空格配对的情况，因为可以同时删去空格，这样做毫无意义。
# 我们很容易能找到下面的递推关系：
# 情况（1）：F[i][j] = F[i-1][j] - 1
# 情况（2）：F[i][j] = F[i][j-1] - 1
# 情况（3）：F[i][j] = F[i-1][j-1] + d(i,j)
# 其中，d(i,j) = 1 when X[i-1] = Y[j-1]
# d(i,j) = -1 when X[i-1] != Y[j-1]
# 注意，这里d(i,j)只与i和j有关，而与F无关，这点是非常重要的。
# 因此我们得到重要的递推公式如下：
# F[i][j] = [F[i-1][j] - 1,F[i][j-1] - 1, F[i-1][j-1] + d(i,j)].max
# 初始值的话很容易算，这里就不说了。
# 当然，要想知道具体匹配方式的话，还需要进行回溯，这是个细节问题，懂的人应该会
# 处理的。
#=============================================================================
module Ex3
X = "ATGCCTGA"
Y = "AGCTAA"
def self.solve
# 建立最优值表格
value_table = Table.new(X.size+1, Y.size+1)
# 建立回溯表格
# 其中，第三个分量表示沿着X和Y的位移量，可以为-1或0
# 例如trace_table[i,j,0] = -1,trace_table[i,j,1] = 0表示F[i][j]在
# F[i-1][j] - 1处达到最大值
trace_table = Table.new(X.size+1, Y.size+1, 2)
# 初始化
(0..X.size).each do |i|
value_table[i,0] = -i
trace_table[i,0,0] = -1
trace_table[i,0,1] = 0
end
(0..Y.size).each do |j|
value_table[0,j] = -j
trace_table[0,j,0] = 0
trace_table[0,j,1] = -1
end
# 迭代
(1..X.size).each do |i|
(1..Y.size).each do |j|
dij = X[i-1] == Y[j-1] ? 1 : -1
val1 = value_table[i-1,j] - 1
val2 = value_table[i,j-1] - 1
val3 = value_table[i-1,j-1] + dij
if val1 >= val2 && val1 >= val3
value_table[i,j] = val1
trace_table[i,j,0] = -1
trace_table[i,j,1] = 0
end
if val2 >= val1 && val2 >= val3
value_table[i,j] = val2
trace_table[i,j,0] = 0
trace_table[i,j,1] = -1
end
if val3 >= val1 && val3 >= val2
value_table[i,j] = val3
trace_table[i,j,0] = -1
trace_table[i,j,1] = -1
end
end
end
# 回溯
i = X.size
j = Y.size
result_x = ""
result_y = ""
until i == 0 && j == 0
cx = trace_table[i,j,0]
cy = trace_table[i,j,1]
if cx == -1
result_x = X[i-1].chr + result_x
else
result_x = "_" + result_x
end
if cy == -1
result_y = Y[j-1].chr + result_y
else
result_y = "_" + result_y
end
i += cx
j += cy
end
p value_table[X.size,Y.size],result_x,result_y
end
end

复制代码

姓名	第一大题得分	第二大题得分	第三大题得分	附加题得分	获得奖励
@丰聪耳神子	30+15+15+30+40	50+50+93	0(未做)	0(未做)	323EXP
@myownroc	30+15+15+20+55	50+30+100	75+75+95	98(2)	658EXP+2好人卡
@恐惧剑刃	30+15+15+25+50	50+40+30	75+75+90	50(1)	545EXP
@kuerlulu	0(未做)	0(未做)	75+40+100	50(1)	265EXP
@satgo1546	30+15+15+25+60	50+50+100	75+75+90	0(未做)	585EXP
@芯☆淡茹水	27+15+15+30+57	50+45+100	75+75+100	50(1)	639EXP+1好人卡
@无脑之人	0(未做)	0(未做)	0(未做)	100(2)	100EXP+1好人卡
@冰水金刚	30+15+15+25+58	50+50+100	65+75+60	50(3)	593EXP
@atom0520	25+15+15+30+58	50+50+100	75+75+100	0(1)	593EXP
@无忧谷主幻	30+15+15+30+55	50+50+90	75+60+100	0(未做)	570EXP