Board logo

标题: 【挑战】批处理实现最大长方体问题、四色定理问题、导弹拦截问题 [打印本页]

作者: yslyxqysl    时间: 2009-10-26 22:11     标题: 【挑战】批处理实现最大长方体问题、四色定理问题、导弹拦截问题

1.最大长方体问题
有一个文本a.txt,里面有n(不定)个n*n的矩阵,
矩阵之间用“#层数”分开,
这些矩阵代表一个n*n*n的正方体,
正方体中的每一个1*1*1的单位上都标有一个数字,例如:
示例:
#1
-1 3 -2
8 -2 2
0 -4 -4
#2
2 15 7
12 5 2
-1 0 10
#3
-4 -4 -4
-2 3 -1
-128 -13 3


这就代表一个正方体,其中
(1,2,3)是-4(第一个,第二行,第三层),
(3,2,1)是2(第三个,第二行,第一层)。

现在要从这个正方体中“切”出一个长方体,
使得这个长方体中所有数的和最大。
当有多个答案时取体积最大(数的个数最多)的那个
要求输出数的和以及数的个数。

例子的答案(可能是吧):
52
18

参考分数:满分70分,2技术,1声望。

2.四色定理问题
A公司要给一幅很大的图涂上颜色,要用四种颜色把n(不定)块图案分开
他们给你这个计算机专家一个文本pic.txt,示例如下:
# 1 2 3 4 5 6 7 8
1
2 1
3 0 1
4 0 0 1
5 0 1 0 1
6 0 0 0 1 0
7 0 0 0 0 1 1
8 1 1 0 0 0 0 1
这个文本说明了块与块之间是有边相连(1)还是无边相连(0)
例如(2,5)的值为1,就说明2和5是有相连的;
(4,7)的值为0,就说明4和7是无相连的。
请注意,图案中的块的个数是不定的,
可能8块也可能更多或更少。

试输出一种涂色方案,今假设用红黄蓝绿四种颜色。
例子的其中一种答案:
1:red
2:yellow
3:red
4:yellow
5:green
6:green
7:blue
8:green

实际图形(一种可能的情况)


参考分数:满分50分,1技术。

3.导弹拦截问题
Y国自主研发了一套导弹拦截系统,可惜这套系统有一个缺点,
就是一套系统发射了一枚拦截导弹后就会产生磨损,下一发
拦截导弹就不能比前一发射得高或和前一发一样高了。
不巧Y国只完成一套系统之后,就与X国发生了战争,
X国陆续投来一些(不定)不同高度的导弹,试问Y国仅有的一套拦截系统最
多能拦住几枚导弹?假设每一枚拦截导弹都能准确击中目标。

示例输入:
10 7 8 3 7 4 2 11 9

示例输出:
5

参考分数:满分30分。
作者: yslyxqysl    时间: 2009-10-30 20:52

全部是Pascal书(来自我们学校图书馆)上的BT题...
作者: batman    时间: 2009-10-30 22:32

第二题:
  1. @echo off&setlocal enabledelayedexpansion
  2. for %%a in (red green yellow blue) do set /a n+=1&set "color!n!=%%a"
  3. for /f "skip=2 delims=" %%a in (pic.txt) do (
  4.     set "num="&set /a n=0
  5.     for %%b in (%%a) do (
  6.         if defined num (
  7.            set /a n+=1&set "!num!-!n!=%%b"
  8.            ) else (
  9.            set "num=%%b"
  10.         )
  11.     )        
  12. )
  13. :begin
  14. for /l %%a in (1,1,8) do (
  15.     set /a a=!random!%%4+1
  16.     for %%b in (!a!) do set "#%%a=!color%%b!"
  17. )
  18. for /l %%a in (1,1,8) do (
  19.     set /a a=%%a-1
  20.     if !a! neq 0 for /l %%b in (1,1,!a!) do if !%%a-%%b! equ 1 if !#%%a! equ !#%%b! goto begin
  21. )
  22. for /l %%a in (1,1,8) do echo %%a:!#%%a!
  23. pause>nul
复制代码

[ 本帖最后由 batman 于 2009-10-30 22:48 编辑 ]
作者: Seter    时间: 2009-10-30 23:02

第三题...多谢freedom让我占尽优势啊...
  1. @echo off&setlocal enabledelayedexpansion&set/pk=&set i=1&(for %%i in (!k!) do (set m=0&for /l %%j in (1,1,!i!) do if !e%%j! gtr %%i if !m! lss !l%%j! set m=!l%%j!)&set/al!i!=m+1&set e!i!=%%i&set/ai+=1)&set m=!l1!&set r=!r1!&(for /l %%i in (2,1,!i!) do if !m! lss !l%%i! set m=!l%%i!)&echo !m!&pause
复制代码
http://www.bathome.net/viewthread.php?tid=5959&extra=&highlight=%CA%FD%D7%D6%B4%AE&page=3
还需要我拆不~?
作者: batman    时间: 2009-10-30 23:16

对第二题暂时没有好的思路,至于不定块的问题,可以在我3楼的代码中在:begin前加入set /a n+=1,然后把后面的8全改成%n%,但这种判断返回法应该是不支持n为大数值的情况的...
作者: zqz0012005    时间: 2009-10-30 23:33

说实话,用批处理做算法分析显然是不合适的,因为它本身就不是程序设计语言。

真正能利用的批处理特性有哪些呢?
1、不用临时变量交换两个变量的值(预处理机制),C有位运算(当然如果值是非数字还得使用临时变量,那也不过是多设置一个指针而已)。而且对于数字,bat不能预处理特性也能实现:a=a+b, b=a-b, a=a-b
2、预处理机制是有一些地方可以利用,但预处理也是bat不足之处的表现。而且跟C的宏和预编译相比,bat的预处理完全是微不足道。
3、字符串处理、特殊符号、数值计算,一直是bat天生的软肋。
4、便捷的文件操作与系统管理,这才是bat的正道。
5、预处理还有哪些可以利用的优势,大家来补充(不要提bat的胶水功能,它不是bat独有的)
除此之外,用bat设计的“程序”其他部分都是通用性的算法。

第3题有点问题吧?敌方导弹如果是同时来的,只能拦截一枚。如果是分先后来的,如何得知后来的导弹的高度?所以没有选择的机会。第一枚来,射!第二枚,高了干瞪眼,低就射!后面的同理,只与前一个比较大小。

你的本意应该是seter给的链接中的那个问题吧,但这个实际例子不太好。

[ 本帖最后由 zqz0012005 于 2009-10-30 23:44 编辑 ]
作者: Batcher    时间: 2009-10-30 23:51

几个问题放在同一个帖子里面比较容易混乱
作者: batman    时间: 2009-10-31 00:20     标题: 第三题的解

  1. @echo off&setlocal enabledelayedexpansion
  2. set /p str=请按顺序输入导弹的高度,中间用空格格开:
  3. :begin
  4. set /a n=0,m=0
  5. for /f "tokens=1*" %%a in ("%str%") do (
  6.     for %%c in (%%b) do (
  7.         if %%a gtr %%c (
  8.            set /a n+=1
  9.            ) else (
  10.            set /a m+=1
  11.         )
  12.     )
  13.     if !n! geq !m! (
  14.        if not defined max set /a max=%%a,num+=1
  15.        if !max! gtr %%a set /a max=%%a,num+=1
  16.     )
  17.     set "str=%%b"&goto begin
  18. )
  19. echo 最多能拦截%num%枚导弹
  20. pause>nul
复制代码

[ 本帖最后由 batman 于 2009-10-31 00:31 编辑 ]
作者: Seter    时间: 2009-10-31 12:32

第三题必须怪YSL没说清楚...原题有这样一句话..

...某天,雷达捕捉到敌国的导弹来袭...  
...样例:
    INPUT                                                 OUTPUT
    389 207 155 300 299 170 158 65     6(最多能拦截的导弹数)

看看,这可是雷达啊,别说高度了,连速度都能知道!




欢迎光临 批处理之家 (http://bathome.net./) Powered by Discuz! 7.2