问题描述;设S是正整数集合.S是一个无和集,当且仅当 蕴含.对于任意正整数k,如果可将{1.2,...,k}

问题描述:子集和问题的一个实例为.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S₁,使得.试设计一个解子集和问题的回溯法.

算法设计:对于给定的正整数的集合和正整数c,计算S的一个了集S₁,使得

数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.

结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".

问题描述:具有截止时间和误时惩罚的任务安排问题可描述如下.

(1)给定n个任务的集合S={1,2,...,n};

(2)完成任务i需要t_i(1≤i≤n)时间;

(3)任务i的截止时间d_i(1≤i≤n),明要求任务i在时间di之前结束;

(4)任务i的误时惩罚w_i(1≤i≤n),即任务i末在时间di之前结束,将招致wi的惩罚;若按时完成,则无惩罚.

任务安排问题要求确定S的一个时间表(最优时间表)使得总误时惩罚达到最小.

算法设计:对于给定的n个任务,计算总误时惩罚最小的最优时间表.

数据输入:由文件input.txt给出输入数据.第1行是1个正整数n,表示任务数.接下来的n行中,每行有3个正整数a、b、c,表示完成相应任务需要时间a,截止时间为b,误时惩罚值为c.

结果输出:将计算的总误时惩罚输出到文件output.txt.

请编写一个函数unsigned short fun(unsigned short s)。其中s是一个大于10的无符号整数，若s是一个n(n≥2)位整数，函数求出s的n位数之和作为函数的返回值。

例如，s值为4315，则函数返回13。s值为13函数，则返回4。

注意：部分源程序已存在文件PROC15.cpp中。

请勿修改主函数和其他函数中的任何内容，仅在函数fun()的花括号中填写若干语句。

文件PROC15.cpp的内容如下：

//PROC15.cpp

include＜iostream＞

using namespace std；

unsigned short fun(unsigned short s)；

int main()

{

unsigned short a；

cout＜＜"Enter a unsigned short integer number：";

cin＞＞a；

if(a＜10)

cout＜＜"Data error!"；

else

cout＜＜"The result: "＜＜fun(a)＜＜end1；

return 0；

}

unsigned short fun(unsigned short s)

{

//* * * * * *

}

问题描述:最长公共子序列问题是生物信息学中序列比对问题的一个特例.这类问题在分子生物学和模式识别中有广泛应用.其中最主要的应用是测量基因序列的相似性.在演化分子生物学的研究中发现,某个重要的DNA序列片段常出现在不同的物种中.在测量基因序列的相似性时,如果需要特别关注一个具体的DNA序列片段,就要考察带有子串排斥约束的最长公共子序列问题.这个问题可以具体表述如下.

给定两个长度分别为n和m的序列x[0...n-1|]和y[0...m-1],以及一个长度为p的约束字符串s[0...p-1].带有子串排斥约束的最长公共子序列问题就是要找出x和y的不包含s为其子串的最长公共子序列.例如,如果给定的序列x和y分别为AATGCCTAGGC和CGATCTGGAC.字符串s=TG时,子序列ATCTGGC是x和y的一个无约束的最长公共子序列,而不包含s为其子串的最长公共子序列是ATCGGC.

算法设计:设计一个算法,找出给定序列x和y的不包含s为其子串的最长公共子序列.

数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x和y及约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.

结果输出:将计算出的x和y的不包含s为其子串的最长公共子序列的长度输出到文件output.txt中.

问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及一个长度为p的约束字符串S[0...p-1].带有子串包含约束的最长公共子序列问题就是要找出x和y的包含s为其子串的最长公共子序列.例如,如果给定的序列x和y分别为AATGCCTAGGC和CGATCTGGAC,字符串s=GTA时,子序列ATCTGGC是x和y的一个无约束的最长公共子序列,而包含s为其子串的最长公共子序列是GTAC.

算法设计:设计一个算法,找出给定序列x和y的包含s为其子串的最长公共子序列.

数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x、y和约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.

结果输出:将计算出的x和y的包含s为其子串的最长公共子序列的长度输出到文件output.txt中.

设某语言的语法规则用上下文无关文法G=(N，T，P，s)表示，其中N是非终结符号的集合，T是终结符号的集合，P是产生式集合，s是开始符号，令V=N∪T，那么符合该语言的句子是( )。

A．从s出发推导的、仅包含T中符号的符号串

B．从N中符号出发推导的、仅包含T中符号的符号串

C．从S出发推导的、包含V中符号的符号串

D．从N中符号出发推导的、包含V中符号的符号串

设某语言的语法规则用上下文无关文法G=(N，T，P，s)表示，其中N是非终结符号的集合，T是终结符号的集合，P是产生式集合，s是开始符号，令V=N∪T，那么符合该语言的句子是( )。

A．从s出发推导的、仅包含T中符号的符号串

B．从N中符号出发推导的、仅包含T中符号的符号串

C．从S出发推导的、包含V中符号的符号串

D．从N中符号出发推导的、包含V中符号的符号串