编程沙龙（19）

IT商界

PALADIN

　　已知一辆汽车要从A地前往B地，而旅途中有M个加油站。已知这M个加油站分别到A地距离为S1、S2 ……Sm。该车加满油后可行驶N公里(可以确定该车一定能到达B地)，车从A地地开出时已加满了油。设计一个程序，输入N以及S1、S2 ……Sm，输出该车应在哪些加油站停靠加油，使沿途加油次数最少。并证明该方法获得的是最优解。

　　读者朋友可以用你最擅长的语言和编程工具来完成这道题，答题方式为：把你的答案发送到software@cpcw.com，邮件主题写上“算法演义答题”。我们会从中选出答题最好的参赛者，并发送精美奖品。

　　首先特别要感谢的是辽宁抚顺的刘金义朋友，他发现了我们上期有奖征答活动中的一位获奖者的程序存在缺陷并给出了一组反例。他还同时提出上期任务分配的问题是NP难问题并给出了详细的证明。他在信中提到：“……该问题只能用穷举法来解决，任何多项式时间的算法是不存在的。因此给出的动态规划算法肯定是错误的。……”

　　答：关于什么是NP难问题，该问题是不是NP难问题，是否只能用穷举法来解决，作为我们下期算法演义讨论的内容，我会在网上发布刘金义朋友的证明内容(http://paladin.nease.net/cpcw/work.zip)，欢迎大家下载并给出你的见解。

　　王皓玉提到：“信息学奥赛的复赛中，主要的题目是按照问题编写程序。每道题在‘判卷子’的时候，采用黑箱测试。测试人员会用一组叫做‘测试数据’的数据测试这些程序。我希望你们在给出题目的同时也能给出两组测试数据，以方便我们检测程序的正确性”。

　　答：我们现在的评判是采取了黑盒加白盒的测试方法。开始由于考虑对于不同的题目，黑盒法测试数据的数目要求不同，如果完全给出测试数据可能会使题目显得冗长，所以未给出测试数据。我们会在以后注意这方面问题，尽可能地提供测试数据。当然在此前的编程沙龙中我也提到过读者朋友可以试着对自己的程序进行一下测试，这对编程的学习有很大帮助。

　　zzx问：“在C语言中，在图形界面下，如何显示放大了的汉字？为什么用outtextxy(midx, midy, "这是几个汉字")；显示出的是乱码？”

　　答：如果我没记错的话，在MSDOS的图形界面下显示汉字有两个途径，一是有像UCDOS那样的平台支持，二是自己创建显示汉字的函数并自带字库的文件。第二种途径实现起来比较费劲，所以建议你先装上UCDOS试一下。