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

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

填数问题——2000年第15期擂台赛赛题解答

一、问题 设n为奇数,请将1,2,…至n~2共n×n个整数填入n×n的表格中,要求使该表格方阵每行、每列、从左上至右下角的主对角线以及从右上至左下角的辅对角线元素之和都相同。 例如,图1给出n=3时,将1,2,…9共9个数填入3×3表格,并满足所有行、列、主对角线与辅对角线     

确定最佳抽新股方案——2000年第19期擂台赛题分析

某投资者共有资金S元,用于某日抽新股,设该日共有n支新股发行,设第i支新股(1≤i≤n)发行价为P_i元,申购上限是m_i股,估计命中率为R_i,该新股上市后的价格是发行价的K_i倍。 同时按股市有关规定新股申购数必须是1000的整倍数,抽买新股没有手续费,但一般的股票交易有η=7‰     

如何安排最佳并行方案——2000年第11期擂台赛题目

一个工程可分为许多耗时不同的子步骤分步完成,每一步又需要几种不同的技术方式进行加工,而参与该项任务的几个技术工人可能会其中一种或几种加工技术,请编程给出一种工程完成工期最短的最佳工作分配方案。给出其中一种即可,给出所有最佳方案更好。 基本要求 实例1 首先假设每个子步骤所需要的时间是一样的,在     

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

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

工程安排问题——1999年第24期擂台赛赛题解答

(一)问题 某人要完成一项目,该项目由n项子项目构成,其中某些子项目存在依赖关系,必须先后执行,假设给出子项总数及子项间相互依赖的关系要求,请编程给出所有可能的工作安排方案。     

如何寻找最佳旅游路线——2000年第9期擂台赛题解

问题:给出某城市景点分布与交通路线图,并给出每一景点的评分与游玩所需时间,同时也给出通过每条道路所需的时间,那么某一游客在该城市玩n天并每天最多玩K小时后需回到一固定住所,请给出所游玩景点总评分最高的旅游路线方案。     

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

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

1998年第11期擂台赛点评

题目:多边形面积的计算 给出一个多边形各顶点的坐标,求这个多边形的面积。注意:这个多边形不一定是凸的。但是保证一定不自交。输入:多边形的顶点数N和按顺时针给出的顶点的坐标。输出:多边形的面积。     

如何寻找最短路径——兼评1999年第11期擂台赛

问题与背景 寻找无向图或有向图的最短路径是一个常会碰到的问题,有许许多多的实际应用背景。 例如,如图1所示是两城市V_0与V_7间的公路网图,其中每个点表示一个城镇或     

一种行棋游戏的编程：—2000年第22期擂台赛赛题解答

问题:一种棋盘如图1所示的行棋游戏,双方依次每步可且必须向有线段连接的邻点走一步。如黑子被围困在顶点则白棋胜,黑子走到了底线则黑棋胜,请编程与人对弈。实际上这是一种黑白不公平的游戏,除n=2层且黑先行外,白方都存在必胜策略。这里全文刊出擂主裴震权先生的参赛稿,这是一个很不错的参赛     

动态规划方法与矩阵连乘式的最小计算——2000年第13期擂台赛赛题评解

计算矩阵连乘式时有不同的运算次序，如ABCD就有5种计算方式（（AB）C）D，（A（BC））D，（AB）（CD），A（（BC）D）与A（B（CD）），其中每一种的运算量都不一定相同，请编一程序按最小运算量方案计算任意输入的矩阵连乘式。     

矩阵乘法——2000年第7期擂台赛题解

问 题 本期擂台赛题目是要求编一程序,从输入文件in-Put.dat中读入两矩阵的数据,然后输出计算出的乘积矩阵的结果。 这次的题目应该让大家感到很轻松,不过,在此基础上,本次擂台赛的赛题:如何高效率计算n个矩阵的连乘积,大家不妨再一显身手。 讲 评 矩阵乘法的基本规则:     

2000年第11期问题解答

本题作者在对电路工作原理的阐述中,错在对三极管VT1的工作状态认识不当,从而对灯的亮灭状态分析发生错误。正确的工作原理是: 接通220V电源后,由于VT1截止,经D1～D4整流后的直流电压由R2降压后,使可控硅VS触发导通,灯泡亮。VS导通后,其A、K端的正向压降约1.2V通过R3对C1充电,当C1的电压上升到0.7V时,VT1由截止变为导通,VS因控制极G失压而截止,灯熄灭。人体触摸金属片时,感应信号经R5使VT2导通,C1上的电压经三极管VT2迅速放电,VT1因失基极偏压变为截止,VS触发导通而灯亮。同时,C1又被充电,其缓慢上升的端电压经过一定时间后又使VT1导通、VS截止、灯熄灭。如此,完成一个灯亮灯灭的延时过程。在元件使用中,R5用10M阻值太大,将会影响     

如何安排任务获取最大利润——2000年第8期赛题解

本次赛题为已知m种产品,n台设备,设备i—周最多可用p_j小时,而生产每台产品i需用设备j加工q_(i,j)小时,还知道生产产品i的利润是r_i元,请编程给出获取总利润最高的方案。 这实际上是一个典型的线性规划问题,这里刊出     

如何编程解一元三次方程——2000年第2期擂台赛第1题评解

(一)问题 2000年第2期的擂台期试题1是求解一元三次方程,即设ax~3+bx~2+cx+d=0,输入一组双精度浮点系数的值,求出该方程的所有实根(但要注意考虑最高次项系数为0时的退化情况)。 对于一元n次方程的求解,历史上有过很多研究,也留下了许多有趣的故事,最后人们找到了一元最高     

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

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

2000年第22期擂台赛题目行棋游戏

一种棋盘如图1所示的棋。有两种颜色的棋子,一种为白色,共有两枚棋子,开局时放在底线;另一种为黑色,只有一枚,开局时放在顶点;棋盘共有n层(不包括顶点),图1是一个n=5的棋盘式样;开盘后一方先行,然后双方轮流行棋,每次可以且必     

快速分类问题算法分析——2000年第20期擂台赛解决方案评述

(一) 问题 本期的题目是一个研究中的实际问题,即报文的快速分类问题。常称流分类问题。 设1个报文的包头有n个整形变量x_1,x_2,…,x_n,那么可以设定一个规则库,利用规则库中的规则可以对报文进行分类,每条规则规定每个分量为某一特定值或可取介于某一上下限之间的值,符合某规则的报文将被分类为该规则指定的报文类型。 一般说,某一报文可能同时符合几条规则的要求,这时