【挑战】批处理实现最大长方体问题、四色定理问题、导弹拦截问题

yslyxqysl

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

全部是Pascal书(来自我们学校图书馆)上的BT题...

batman

第二题:

@echo off&setlocal enabledelayedexpansion
for %%a in (red green yellow blue) do set /a n+=1&set "color!n!=%%a"
for /f "skip=2 delims=" %%a in (pic.txt) do (
    set "num="&set /a n=0
    for %%b in (%%a) do (
        if defined num (
           set /a n+=1&set "!num!-!n!=%%b"
           ) else (
           set "num=%%b"
        )
    )        
)
:begin
for /l %%a in (1,1,8) do (
    set /a a=!random!%%4+1
    for %%b in (!a!) do set "#%%a=!color%%b!"
)
for /l %%a in (1,1,8) do (
    set /a a=%%a-1
    if !a! neq 0 for /l %%b in (1,1,!a!) do if !%%a-%%b! equ 1 if !#%%a! equ !#%%b! goto begin 
)
for /l %%a in (1,1,8) do echo %%a:!#%%a!
pause>nul 
复制代码

[ 本帖最后由 batman 于 2009-10-30 22:48 编辑 ]

Seter

第三题...多谢freedom让我占尽优势啊...

@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

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

zqz0012005

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

真正能利用的批处理特性有哪些呢？
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

几个问题放在同一个帖子里面比较容易混乱

batman

@echo off&setlocal enabledelayedexpansion
set /p str=请按顺序输入导弹的高度,中间用空格格开:
:begin
set /a n=0,m=0
for /f "tokens=1*" %%a in ("%str%") do (
    for %%c in (%%b) do (
        if %%a gtr %%c (
           set /a n+=1
           ) else (
           set /a m+=1
        )
    ) 
    if !n! geq !m! (
       if not defined max set /a max=%%a,num+=1
       if !max! gtr %%a set /a max=%%a,num+=1
    )
    set "str=%%b"&goto begin
)
echo 最多能拦截%num%枚导弹
pause>nul
复制代码

[ 本帖最后由 batman 于 2009-10-31 00:31 编辑 ]

Seter

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

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

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