试设计并实现一个就地的算法shift(int A[],int n,int k),在o(n)时间内将任一数组A[0,n)中的元素整体循环左移k位。例如,数组A[]=(1,2,3,4,5,6)经shift(A,6,2)之后,有A[]=(3,4,5,6,1,2)。
算法设计:对于给定的I和k,计算I的最大k乘积.
数据输入:由文件input.txt提供输入数据.文件的第1行中有2个正整数n和k.正整数n是序列的长度,正整数k是分割的段数.接下来的一行中是一个n位十进制整数(n≤10).
结果输出:将计算结果输出到文件output.txt.文件第1行中的数是计算出的最大k乘积.
算法设计:对任意给定的整数n和k,以及完成任务i需要的时间为ti(i=1,2,...,n).设计一个优先队列式分支限界法,计算完成这n个任务的最佳调度.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k.第2行的n个正整数是完成n个任务需要的时间.
结果输出:将计算的完成全部任务的最早时间输出到文件output.txt.
规则I:每次只能移动1个圆盘:
规则II:任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
规则III:任何时刻都不允许将同色圆盘叠放在一起:
规则IV:在满足移动规则I~III的前提下,可将圆盘移至A、B、C中任一塔座上.
试设计一个算法,用最少的移动次数将塔座A上的n个圆盘移到塔座B上,并仍按同样顺序叠置.
算法设计:对于给定的正整数n,计算最优移动方案.
数据输入:由文件input.txt给出输入数据.第1行是给定的正整数no.
结果输出:将计算出的最优移动方案输出到文件output.txt.文件的每行由一个正整数k
和2个字符c1和c2组成,表示将第k个圆盘从塔座c1移到塔座c2上.
问题描述:设磁盘上有n个文件每个文件占用磁盘上的1个磁道.这n个文件的检索概率分别是且磁头从当前磁道移到被检信息磁道所需的时间可用这两个磁道之间的径向距离来度量.如果文件fi存放在第i(1≤i≤n)道上,则检索这n个文件的期望时间是.式中,d(i,j)是第i道与第j道之间的径向距离|i-j|.
磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置,使期望检索时间达到最小.试设计一个解此问题的算法,并分析算法的正确性与计算复杂性.
算法设计:对于给定的文件检索概率,计算磁盘文件的最优存储方案.
数据输入:由文件input.txt给出输入数据.第1行是正整数n,表示文件个数.第2行有n个正整数a,表示文件的检索概率.实际上第k个文件的检索概率应为
结果输出:将计算的最小期望检索时间输出到文件output.txt.
设是一个d次多项式.假设已有一算法能在O(i)时间内计算一个i次多项式与一个一次多项式的乘积,以及一个算法能在O(ilogi)时间内计算两个i次多项式的乘积.对于任意给定的d个整数,用分治法设计一个有效算法,计算出满足且最高次项系数为1的d次多项式P(x),并分析算法的效率.
算法设计:对于给定的n件工作和n个人,计算最优分配方案和最差分配方案.
数据输入:由文件input.txt提供输入数据.文件的第1行有1个正整数n,表示有n件工作要分配给n个人做.接下来的n行中,每行有n个整数cij(1≤i≤n,1≤j≤n),表示第i个人做第j件工作产生的效益为cij.
结果输出:将计算的最小总效益和最大总效益输出到文件output.txt.
阅读以下说明和C++ 程序,将应填入(n)处的字句写在对应栏内。
[说明]
试从含有n个int 型数的数组中删去若干个成分,使剩下的全部成分构成一个不减的子序列。设计算法和编写程序求出数组的不减子序列的长。
[C++ 程序]
include<stdio.h>
define N 100
int b[]={9,8,5,4,3,2,7,6,8,7,5,3,4,5,9,1};
int a [N];
define n sizeofb/sizeofb[0]
void main ()
{
kit k,i,j;
(1)
(2)
for (i=1;i<n; i++ )
{
for (j=k;(3); j--);
(4); /*长为 j+1 的子序列的终元素存储在 a[j+1]*/
if ((5)k++; /*最长不减子序列长 k 增1*/
}
printf ("K = %d\n ",k );
}