动态规划法解最佳三角剖分凸多边形问题——2000年第18期擂台赛题解

不知道大家还记得本年度第19期本栏目对第13期赛题(矩阵连来式如何用最小运算量计算方案计算)的分析与动态规划方法的求解吗?一个代数问题与本期的一个几何问题,实际上可以用相同方法很漂亮地解决……     

2000年第24期擂台赛题目——有向图的连通性质判断

一个有向图的连通性包括弱连通性、单向连通性以及强连通性。     

如何安排工程方案——2000年第6期擂台赛赛题评解

题 目 一项n个子项的工程,n个子项在执行的时间上有以下几种依赖关系:①某子项需接着另一子项相继完成;②某子项需在另一子项完成后才允许进行;③某子项需在某两子项中先完成的一项完成后即刻接着执行;④某子项需在某两子项先完成的一项完成之后才可完成。     

如何在点阵中快速画圆?——2000年第3期擂台赛赛题评解

题目 已知m行×n列由灯泡组成的象素阵, 请编程快速高效地画出以(x_c,y_c)为圆心,R为半径的圆。 实际上,大量的图形显示设备都可归结为象素点表示,如显示器、点阵打印机等等(当然不是所有图形设备都用点阵表示,如类似人用笔写字的笔划式绘图仪就不用点阵而用轨迹矢量作图)。 其中画线与画圆是最基本的作图问题,快速画线与画图就自然成为整个图形设备效率的关键问题。自     

高效率计算矩阵连乘积——2000年第13期擂台赛题目

设有n个矩阵,A_1A_2…A_iA_(i+1)…A_n,设其中任意两个相邻矩阵A_iA_(i+1)都是可以相乘的(i=1,2,…,n-1),显然可以定义并计算出矩阵的连乘积A_1A_2…A_n。 由于矩阵乘法满足结合律,因此计算次序除对n-1次矩阵乘法依次相乘外,还可以以不同的次序进行计算,也就是通过不同方式的加括号得到不同的运算次序。     

如果寻找最快完成任务的方案——2000年第11期擂台赛赛题解法分析

问题 本次擂台赛赛题是要求给出解决一个任务的最佳并行方案。 具体讲,基本要求就是给出了一项大任务的各项子任务间的先后次序关系,以及每一项子任务所需加工的方式,同时还给出n个工作人员每人所掌握的加工方式情况。     

如何事后估计股票的最佳买卖策略——2000年第5期擂台赛赛题简析

基本问题是:如果n只股票,m天内的K线行情数据(主要包括每日最高价、最低价与收盘价)已知,事后分析时,编程给出理论上存在的最佳的炒股策略。 首先应说明,仅知道日K线数据并不足以得出真实情况下的最佳策略,因为每日的最高价与最低价谁先出现,谁后出现,相应策略可能不同,我国现行的股票交易规则规定一只股票一天内卖出后可买回,而当     

计算任意电阻网络等效电阻的程序设计——1999年第23期擂台赛赛题解答

(一)问题 1999年第23期擂台赛赛题的基本要求是求电桥的等效电阻; 进一步的高一级要求是求任意电阻网络任意指定两点间的等效电阻。 (二)电桥等效电阻求解