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

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

1999年第23期擂台赛题目

求电阻网络的等效电阻值 如图1是一个电阻网络,请编一程序输入5个电阻的电阻值,求出该电阻网络的等价电阻Rx的值。 提示:我们知道对这个电路,如果R1/R3=R2/R4则是一个平衡电桥,Rx=(R1+R3)(R2+R4)/(R1+R2+R3+R4),而对一般情况,只有     

擂台赛1999年第1期点评

这次擂台赛题目为:判断平面上给定坐标的n个点能否构成一个凸多边形。 来稿提到了10多种方法,有些朋友提出的算法很有特点,构思也很巧妙,但作为解决问题方法优劣的判断与评奖只能是效率、编程实现的简洁与清晰。 这里给出并讨论一种简洁的判断算法。 首先不能不讨论该算法的数学依据,同时以下的讨论都假设n个点中任意两个点都不重复。     

擂台赛1999年第16期点评

本次擂台赛有两个题目。 A题要求编一个求高精度的计算n~(1/2)、e或1g(n)的值的程序,擂主白炽贵设计与完成了一套很好的汇编程序,整个程序约三千程序行,这里无法刊出,有兴趣的读者可从本刊主页中下载。     

任意精度计算浅谈——兼评1999年第10期擂台赛

计算机编程语言中典型的数据类型长度或精度都是有限的。 例如典型的C语言中整型变量类型有 Short int、int与long int,在IBM PC上长度分别为16、16与32位,表示数的范围分别为-32768至32767(-2~(15)至 2~(15)-1)、-32768至32767与-2147483648至214783647(-2~(31)至 2~(31)-1)。如果用作无符号整数,可表示数的范围相应调整为0至2~(16)1、0至2~(16)-1与0至2~(32)-1。     

1998年第15期擂台赛点评

本次的题目是一个组合数学问题:输入1个屏幕及4个矩形的长与宽,编程判断,是否可通过这4个矩形在保持长宽比恒定的条件下进行缩放与拼合,使其不重复地完全覆盖屏幕。其中屏幕与缩放后矩形的长与宽必须是整数。可以则输入“Yes”,否则输入出“No”。     

探测断层位置问题——1999年第19期擂台赛点评

问题 本次擂台赛的题目属于一个科学与工程的计算问题。 在地下有一断层平面,在地面上n个同一水平面的不同位置分别用声学方法测量到测量点到断层的点面距离d_i及相应的测量值的标准误差σ_i,请编程给出该断层的平面方程(即Ax+By+Cz+D=0的一组系数)。 该问题是一个工程技术问题,对应许多实际工程技术问题的一种简化情况,例如雷达测目标、声呐系统测量,超高能宇宙线的地面广延大气簇射测向(目     

移数问题解答——1999年第22期擂台赛解答

本期擂台赛是:将4×4方格内任意填写了1至15的数字与一个空格的状态(如图1),要求通过移动(空格可与上下左右数字交换位置)将数字排列到指定的位置(如图2),例如要求由图1移动到图2的状态,编程给出移动方案。 如将每一种填数状态看成一结点,如结点A可通过移动成为结点B的状态,则认为有A至B的有向边,于是问题可看成由初始点在有向图中找一条至指定要求状态的通路(或最短通路)。 由于其中结点数高达161≈2.1×10~(13)个,简单采用回溯法工作量很大,可以针对问题状态空间树的搜寻采取一些策略,如考虑最小耗费搜寻法、限界剪枝等等。 这里刊出擂主李建平先生的程序设计稿供大家参考。     

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

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

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

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

求命题逻辑公式的真值表——1999年第18期擂台赛点评

一、问题 请编一程序,输入一命题逻辑的公式,给出该公式的真值表。 其中原子命题用符号P_1、P_2……表示,联结词包括:否定(?)(用!字符代替,(?)P_1表示非P_1)、合取Λ(用&字符代替,P_1ΛP_2表示P_1并且P_2)、析取(?)(用I字符代替,P_1(?)P_2表示P_1或者P_2)、蕴涵→(用>字符代替,P_1→P_2表示如P_1则P_2)、等价(?)(用=字符代替,P_1(?)P_2表示,P_1当且仅当P_2),公式中还可含有小括号“()”。 二、算法 该问题实际上就是一个表达式的求值问题,今年第2期本栏目的1998年第20期点评中已介绍与讨论了用程序输入一个算术表达式的表达式求值问题,将     

如何排循环赛赛程表?——1999年第21期擂台赛点评

(一) 问题 有n=2~k(K为正整数)个运动员参加某乒乓球循环赛,请编一程序,排出满足如下条件的赛程表: (1) 每个选手必须与其它所有n-1个选手比赛且仅赛一场; (2) 每个选手一日必赛且只赛一场; (3) 比赛必须在n-1日内完成。 (二) 赛程安排实例 这里首先对n=2~1,n=2~2,n=2~3三种情况作出     

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

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

如何实现窗口对线段的快速裁剪?——1999年第8期擂台赛述评

本次擂台赛的题目是编程实现矩形窗口对线段快速裁剪的程序。从input.dat文件读入矩形窗口4个顶点与待判断线段两端点的X与Y坐标,判断该线段在该窗口内是否有可见部分,结果输出到文件output.dat中。完全不可见输出0;如有可见部分输出1,并输出可见部分两端点的X与Y坐标。由于矩形窗口大量应用,该问题实际上已是一个普遍而经典的问题了。 首先讨论解决问题的主要依据,对矩形窗口的4条边所在的直线,其每条直线将平面划分为两个共域,     

配平化学反应方程式问题——2000年第16期擂台赛题解

第16期擂台赛的赛题是:编一程序。输入一化学反应的反应物与生成物分子式(格式可自定义),输出配平后的化学反应方程式。 例如,输入:H_2O→H_2+O_2; 则输出:2H_2O=2H_2+O_2 实际上,该问题可用下述数学方式描述。 假设反应物与生成物共有n种,则可设相应配平后的化学反应方程式系数为x_1,x_2,…,x_n,都必须是大或于等于1的正整数。 再设该反应中共含m种原子,则依次对每种原子,化学反应中原子不发生改变,即原个数守恒,故可得到m个关于x_1,x_2,…,x_n的方程。 配平问题就是求解该方程组得到所有大于等于1且不存在公因子的一组整数解(x_1,x_2,…,x_n)。 例如对H_2O→H_2+O_2 可设x_1(H_2O)=x_2(H_2)+x_3(O_2)则对H原子有:2x_1=2x_2 对O原子有:x_1=2x_2 该方程正好有惟一一组无公因子的正整数解x_1=2,x_2=2,x_3=1。 实际上,解方程时可用不同方法,但一些细节应该注意。 如:应是正整数解,不能有小数、负数或0; 当n=m+1且各个方程互相独立时,该方程有惟一的解,那么对更一般情况,可能出现无解或多解的情况又请作何考虑呢? 这里给出获奖选手李铮的参赛稿,一方面供大家学习借鉴,另一方面也希望大家对它进行分析讨论,看看有什么不足的地方,并将您的分析寄给本栏目(信封或E-mail主题请注明2000年第22期程序分析稿),本栏     

n!右边有多少个0?——1999年第20期擂台赛点评

本次擂台赛的题目是:输入一整数n(n≤65000),编程求出n!的值从右往左数有多少个连续的零。 相对而言,前几期的编程任务不是太容易完成,而本次的题目让大家轻松了一把,或许只是一个在计算机上花几分钟的编辑智力操而已。     

2001年第9期擂台赛题目——如何破坏交通网中两点间的通迅最省事之二

设一个通信网络可以用一个无向图表示,现在需要通过破坏一些线路的手段,也就是对应删去有向图中的一组边,达到使其中两指定点间无法通迅的目的(也就是使两点间不再存在通路)。请编一程序,给出其中需删除边数最少的一种方案。 如图1所示,是一个表示8个站点间通迅网情况的无向图,要通过破坏线路的办法破坏点0与点1间的通迅,有很多     

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

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

编程中的动态规划方法——兼评第7期擂台赛

常会碰到这样的一类问题:需要从所有可能的解空间中找出某一需要的解(一般情况下为使某一目标函数取最大或最小值的解)。 解空间可取值的数目可能无限也可能有限。对有限的情况,最简单的方法便是穷举法:遍历解空间的     

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

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