首页 > 公需科目

题目内容（请给出正确答案）

[主观题]

给定两个大整数u和v,它们分别有m和n位数字,且m≤n.用通常的乘法求uv的值需要O（mn)时间.可以将u和v均看作有n位数字的大整数.用本章介绍的分治法,在O（m^log3)时间内计算iuv的值.当m比n小得多时,用这种方法就显得效率不够高.试设计一个算法,在上述情况下用O（nm^log3/2)时间求出uv的值.

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装优题宝APP，拍照搜题省时又省心！

更多“给定两个大整数u和v,它们分别有m和n位数字,且m≤n.用通…”相关的问题

第1题

证明:任意给定的52个整数中,总存在两个数,它们的和或差能被100整除.

点击查看答案

第2题

问题描述:给定一个赋权无向图G=（V,E),每个顶点都有权值w（v).如果,且对任意（u,V)∈E有u∈U或v∈U,

问题描述:给定一个赋权无向图G=(V,E),每个顶点都有权值w(v).如果,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.

算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).

结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.

点击查看答案

第3题

问题描述:给定一棵有向树T;树T中每个顶点u都有权值w(u),树的每条边(u,v)都有一个非负边长d(u,

问题描述:给定一棵有向树T;树T中每个顶点u都有权值w（u),树的每条边（u,v)都有一个非负边长d（u,

v).有向树T的每个顶点u可以看作客户,其服务需求量为w(u).每条边(u,v)的边长d(u,v)可以看作运输费用.如果在顶点u处未设置服务机构,则将顶点u处的服务需求沿有向树的边(u,v)转移到顶点v处服务机构需付出的服务转移费用为w(u)×d(u,v).树根处已设置了服务机构,现在要在树T中增设k处独立服务机构,使得整棵树T的服务转移费用最小.服务机构的独立性是指任例两个服务机构之间都不存在有向路径.

算法设计:对于给定的有向树T:计算在树T中增设k处独立服务机构的最小服务转移费用.

数据输入:由文件input.txt.给出输入数据.第1行有2个正整数n和k.n表示有向树T的边数:k是要增设的服务机构数.有向树T的顶点编号为0,1,...,n.根结点编号为0.接下来的n行中,每行存表示有向树T的一条有向边的3个整数.第i+1行的3个整数w_i、v_i、d_i分别表示编号为i的顶点的权为w_i,相应的有向边为(i,v_i),其边长为d_i.

结果输出:将计算的最小服务转移费用输出到文件output.txt.

点击查看答案

第4题

对任意的整数x、y、u、v,有gcd(a,b)≤gcd(xa+yb,ua+vb).

对任意的整数x、y、u、v,有gcd（a,b)≤gcd（xa+yb,ua+vb).

点击查看答案

第5题

问题描述:设I是一个n位十进制整数.如果将I划分为k段,则可得到k个整数.这k个整数的乘积称为I的

一个k乘积.试设计一个算法,对于给定的I和k,求出I的最大k乘积.

算法设计:对于给定的I和k,计算I的最大k乘积.

数据输入:由文件input.txt提供输入数据.文件的第1行中有2个正整数n和k.正整数n是序列的长度,正整数k是分割的段数.接下来的一行中是一个n位十进制整数(n≤10).

结果输出:将计算结果输出到文件output.txt.文件第1行中的数是计算出的最大k乘积.

点击查看答案

第6题

整数集I上的一元运算定义如下:（m)=m'（modk)其中r,k为给定正整数,又定义I上的关系~:X~y当且

整数集I上的一元运算定义如下:

(m)=m'(modk)

其中r,k为给定正整数,又定义I上的关系~:

X~y当且仅当x=y(modk)

问一是否是代数结构＜l,＞上的同余关系.

点击查看答案

第7题

数字电路可分为哪两大类？它们的基本单元和常用电路分别有哪些？

点击查看答案

第8题

已知广义表为L(A(u，v，(x，y)，z)，C(m，()，(k，1，n)，(()))，((()))，(e，(f，g)，h))，则它的深度是()。

已知广义表为L（A（u，v，（x，y)，z)，C（m，（)，（k，1，n)，（（)))，（（（)))，（e，（f，g)，h))，则它的深度是（)。

A、2

B、3

C、4

D、5

点击查看答案

第9题

已知广义表为L(A(u，v，(x，y)，z)，C(m，()，(k，l，n)，(()))，((()))，(e，(f，g)，h))，则它的长度是()。

已知广义表为L（A（u，v，（x，y)，z)，C（m，（)，（k，l，n)，（（)))，（（（)))，（e，（f，g)，h))，则它的长度是（)。

A、2

B、3

C、4

D、5

点击查看答案

第10题

合成数（composite number)法，是消除图算法岐义性的一种通用方法。首先，在顶点的标识之间约定

合成数(composite number)法，是消除图算法岐义性的一种通用方法。首先，在顶点的标识之间约定某一次序。比如，顶点标识为整数或字符时，可直接以整数或字符为序;对于字符串等标识，不妨按字典序排列。于是，若边(v，u)权重为w，则对应的合成数取作向量：(w，min(v，u)，max(v，u))。如此，任何两条边总能明确地依照字典序比较出大小。

试在6.11.5节Prim算法和6.12.2节Dijkstra算法中引入这一方法，以消除其中的歧义性。

点击查看答案