设 A是n个不相等的正整数构成的集合,其中,n=2k,k为正整数.考虑下述在A中找最大和最小的算法
设x(n)是一个M点(0≤n≤M-1)的有限长序列,其z变换为
令X(z)在单位圆上N个等间隔点上的抽样X(zk)为
这里M和N都是较大的正整数,问如何用CZT算法快速算出全部N点X(zk)值来。
问题描述:子集和问题的一个实例为.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S1,使得.试设计一个解子集和问题的回溯法.
算法设计:对于给定的正整数的集合和正整数c,计算S的一个了集S1,使得
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.
结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".
对以下定义的集合和运算判别它们能否构成代数系统?如果能,请说明是构成哪一种代数系统?
(1)S1={0,±1,±2,...,±n},+为普通加法,则S1是Ⓐ。
(2)S2={1/2,0,,2},*为普通乘法,则S2是Ⓑ。
(3)S3={0,1,...,n-1},n为任意给定的正整数且n≥2,*为模1乘法,°为模n加法,则S3是Ⓒ。
(4)S4={0,1,2,3},≤为小于等于关系,则S4是Ⓓ。
(5)S5=Mn(R),+为矩阵加法,则S5是Ⓔ。
其中,集合{{1,2,3,4)}由1个子集组成:集合{{1{,2},{3,4}},{{1,3},{2,4},{{1,4},{2,3}},{{1,2,3},{4}},{{1,2,4},{3}},{{1,3,4},{2}},{2,3,4},{1}}由2个子集组成:集合{{1,2},{3},{4}},({1,3},{2},{4},{{1,4},{2},{3}},{{2,3},{1},{4)},{{2.4},{1},{3}},{{3,4},{1},{2}}由3个子集组成:集合{{1},{2},{3},{4}}由4个子集组成.
算法设计;给定正整数n和m,计算出n个元素的集合{1,2,...,n}可以划分为多少个不同的由m个非空子集组成的集合.
数据输入:由文件input.txt提供输入数据.文件的第1行是元素个数n和非空子集数m.
结果输出:将计算出的不同的由m个非空子集组成的集合数输出到文件output.txt.
算法设计:对于给定的开区间集合I和正整数k,计算开区间集合I的最长k可重区间集的长度.
数据输入:由文件input.txt提供输入数据.文件的第1行有2个正整数n和k,分别表示开区间的个数和开区间的可重叠数.接下来的n行,每行有2个整数,表示开区间的左、右端点坐标.
结果输出:将计算的最长k可重区间集的长度输出到文件output.txt.
若有两位候选人参选,并争夺n·51个选举人团(50个州和1个特区)的共计2m=538张选举人票,是否可能因两人恰好各得m=269张,而不得不重新选举?
a)试设计并实现一个对应的算法,并分析其时间复杂度;
b)若没有其它(诸如限定整数取值范围等)附加条件,该问题可否在多项式时间内求解?
A.①能被23整除的正整数,②6的因子,③10以内的正整数
B.①20的因子,②40以内的正整数,③能被43整除的正整数
C.①50以内的正整数,②能被4 1整除的正整数,③49的因子
D.①100以内的正整数,②87的因子,③能被73整除的正整数
问题描述:给定一个无向图G=(V.E),设是G的顶点集.对任意,若u∈U且v∈V-U,就称(u,1)为关于顶点集U的条割边.顶点集U的所有割边构成图G的一个割.G的最大割是指G中所含边数最多的割.
算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最大割.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.接下来的m行中,每行有2个正整数u和y,表示图G的一条边(u,v).
结果输出:将计算的最大割的边数和顶点集U输出到文件output.txt.文件的第1行是最大割的边数;第2行是表示顶点集U的向量x(1≤i≤n),x=0表示顶点i不在项点集U中,x=1表示顶点i在顶点集U中.