![](https://static.youtibao.com/asksite/comm/h5/images/m_q_title.png)
给定两个大整数u和v,它们分别有m和n位数字,且m≤n.用通常的乘法求uv的值需要O(mn)时间.可以将u和v均看作有n位数字的大整数.用本章介绍的分治法,在O(mlog3)时间内计算iuv的值.当m比n小得多时,用这种方法就显得效率不够高.试设计一个算法,在上述情况下用O(nmlog3/2)时间求出uv的值.
![](https://static.youtibao.com/asksite/comm/h5/images/solist_ts.png)
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个整数wi、vi、di分别表示编号为i的顶点的权为wi,相应的有向边为(i,vi),其边长为di.
结果输出:将计算的最小服务转移费用输出到文件output.txt.
图的m着色问题描述如下:给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色.如果有一种着色法,使G中每条边的2个顶点着不同颜色,则称这个图是m可着色的.图的m着色问题是对于给定图G和m种颜色,找出所有不同的着色法.
算法设计:对于给定的无向连通图G和m种不同的颜色,计算图的所有不同的着色法.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n,k和m,表示给定的图G有n个项点和k条边,m种颜色.顶点编号为1,2,...,n接下来的k行中,每行有2个正整数u、v,表示图G的一条边(u,v).
结果输出:将计算的不同的着色方案数输出到文件output.txt.
在m维空间中任意给定n''+1个格点(各坐标均为整数的点,n≥2);求证:其中必定有两个格点P(X1,...,Xn),Q(y1,...,yn)使得点M(,...,
也是一个格点.
算法设计:对于给定的n个正整数,设计一个优先队列式分支限界法,用最少的无优先级运算次数产生整数m.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.第2行是给定的用于运算的n个正整数.
结果输出:将计算的产生整数m的最少无优先级运算次数以及最优无优先级运算表达式输出到文件output.txt.
为
而n阶微分为
输入2个整数,输出它们的最小公倍数和最大公约数。
#include<stdio.h>
void main()
{int m,n,gbs,gys;
scanf("%d,9/6d",m,n);
gbs=m;
while(______)/*第一空*/
gbs=______;/*第二空*/
gys=______;/*第三空*/
printf("%d %d\n",gbs,gys);
}