[计算机软件及应用]算法题目.docx

算法实验题1-1高精度整数问题
★问题描述：
、输出和四则运算
(+、一、X, 十).其中除法运算应其出所得的商和余数.
用」.述高粘度整数的模板类，计算大整数组合数和Cata s,和t姑合式公式
•如果W是合式公式，姑合式公式
•如果w和x是合式公式，Kwx, Awx, Cwx,和Ewx是合式公式。
个合式公式的含义定义如下：
•
.
,
P，q, r, s,和t是逻辑变最的值0 （假）或1 （真）.
K, A, N, C, E所定义在下面的真值表（其中w,x是2个合式公式）.
X
Definitions ol K, A, N, C, and E
Kmx
Amt
Nr
Cwx
Emt
1
1
1
1
0
1
1
1
0
0
1
0
0
0
0
1
0
1
1
1
0
0
0
0
0
1
1
1
现在要你判断，对于 个合式公式，无论p,q,r,s,t如何取值，它的运算是否结果均为 I.
★数据输入：
数据有多组，每组是一个合法的合式公式•” 0”时, 衣示数据输入完成。
★结果输出:
无论p,q,r,s,t如何取值，如果它的运算是否结果均为1,则输出1,否则输出
0.
例
输出示例
ApNp
ApNq 0
1
0
★问题描述：
将-个8*8的机盘迎行如卜分割：将原机盘割下-块矩形桃盘并使剩卜部分也姑 矩形，再将剩卜的部分继续如此分割，这样割了（n-1）次后，连同最后剩下的矩形棋盘 共有n块知形棋盘。（每次切割都只能沿着棋盘格子的边进行）
允许的分割方案 不允许的分割方案，
原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需 要把棋盘按上述规则分割成n块矩形机盘，并使各矩形机盘总分的均方差最小。
a H r）2 - = £括心
均方差 V U ,其中平均值“ » , xi为第i块矩形棋
盘的总分。
造编程对给出的棋盘及n,求出O'的最小值。°
★数据输入：
第1行为一个整数n（l < n < 16）.
第2行至第9行每行为8个小于100的非负整数，表示横盘上相应格子的分值。每
行相邻两数之间用一个空格分隔。
★结果输出：
输出一个浮点数，为0'（四舍五入精确到小数点后三位）.
输入示例 输出示例
3
11111113
11111111
11111111
11111111
11111111
11111111
11111110
1111110 3

★问题描述：
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种 不同的分法？(用K表示)5, I. 1和1, 5, 1是同一种分法。
^入：
数据的第一行是第一行是测试数据的数目t (0 <= t <= 20)。以下每行均包含二 个整数M和N,以空格分开。1<=M, N<=10o
★结果输出：
输对输入的每组数据M和N,用一行输出相应的K.
输入示例
输出示例
1
7 3
8
★问题描述：
鹏给 棵树， 条路径，权值和等T K,且边的数虽最小.
★数据输入：
第一行两个整数 n, k (K=n<=300000, 0<=k<2-31-l)
第一..n行每行工个整数表示一条无向边的两端和权值(注意点的编号从。开 始)
★^果输出：
一个整数表示最小边数虽如果不存在这样的路径输出-1。
输入示例
输出示例
4 3
2
算法实验题2-5最近点对问题
★问题描述：
给出平面上的N个二维点，求出距离最小的2个点对-本题中距离定义为他们的直 线距离。例如() (3,4)的距离为5.
★数据输入：
有多组数据，对于每组数据，第一行是一个数字N表示点的个数。N=0的时候说明 输入结束。之后N行，每行有2个浮点数乂_1, y_i表示第i个点的坐标=(1<=N<= 10000 0,0<=| x_i |, | y_i | <=10"9)
★结果输出：
输出一个浮点数，表示最近点对的距离除以2,保留2位小数(四舍五入八
输例
输出示例
2

0
0
0. 00
1
1
0. 75
2
1
1
1
1
3
- 0
0 0
0
0
算法实验作业3-4上升序列问题
★问息描述：
一个给定的 S={al,a2,a3,・・・.an},若有 P=fa_xl,a_x2,a_x3,・・・,a_xm},满足(xl < x2 < …< xm)K(