主题：分正方形问题，我用贪心算法做不出来，请各位帮帮我
Mato完整版
[专家分：1270] 发布于 2008-04-09 21:09:00
【题目】
分正方形问题
有一个M×N（单位：厘米）的长方形（M,N都不大于100），要求把它分成边长是整数厘米的正方形，要求正好分完，并且使分出的正方形个数最少。
我本想用贪心算法做这道题，即每次都分出能分成的最大的正方形，可我发现有些情况就不对。
比如5×6的：
—— —— —— —— —— —— —— —— —— —— —— ——
| | 1×1 |
| | |
—— ——
| | 1×1 |
| | |
—— ——
| 5×5 | 1×1 |
| | |
—— ——
| | 1×1 |
| | |
—— ——
| | 1×1 |
| | |
—— —— —— —— —— —— —— —— —— —— —— ——
按我的算法应该分成上图的形状，共6个正方形，可是下图：
—— —— —— —— —— —— —— —— —— —— —— ——
| | |
| | |
| 3×3 | 3×3 |
| | |
| | |
| | |
—— —— —— —— —— —— —— —— —— —— —— ——
| | | |
| | | |
2×2 2×2 2×2
| | | |
| | | |
—— —— —— —— —— —— —— —— —— —— —— ——
却只需要5个正方形。
到底怎么做啊？请各位帮帮我。
最后更新于：2008-04-10 22:29:00
回复列表 （共13个回复）
沙发
Mato完整版 [专家分：1270] 发布于 2008-04-10 22:29:00
这道题对于各位来说是非常简单的，
怎么谁都不帮我啊！
要是复赛考到了类似的题，我找你们算账！
板凳
moz [专家分：37620] 发布于 2008-04-10 23:39:00
不好意思,我有点笨,还没想到好一点的办法.
3 楼
moz [专家分：37620] 发布于 2008-04-20 17:27:00
我想了很久,终于才想到这个办法,实在是有愧于Mato啊,
得数是有了,至于怎么分,呵呵,自己想想.
DefLng A-Z
Print F4F(5,6)
Function F4F(a, b)
If a = 1 Or b = 1 Then
F4F = a * b
Exit Function
ElseIf a < b Then
z = b
b = a
a = z
End If
If a Mod b = 0 Then
F4F = a \ b
Exit Function
ElseIf a \ b > 1 Then
F4F = a \ b + F4F(a Mod b, b)
Exit Function
End If
ss = a * b
For i = b To (b + 1) \ 2 Step -1
s = 1
If a <> i Then j1 = i \ (a - i)
If b <> i Then j2 = i \ (b - i)
s = s + j1 + j2
If s < ss Then s = s + Fabcd(a - i, b - i, a - (b - i) * j2, b - (a - i) * j1)
If s < ss Then ss = s
Next
F4F = ss
End Function
Function Fabcd(a, b, c, d)
If b = 0 Then
If d > 0 Then Fabcd = F4F(a, d)
ElseIf a = c And b = d And a = b Then
Fabcd = 1
ElseIf a = c Or b = d Then
If a < c Then a = c
If b < d Then b = d
Fabcd = F4F(a, b)
Else
If a = b And a = 1 Then
Fabcd = c + d + 1
Else
ss = a * d + b * c - a * b
If a = d Then
S1 = 1 + F4F(b, c - a)
ElseIf a > d Then
S1 = 1 + Fabcd(a - d, b, c - d, d)
ElseIf a < d Then
S1 = 1 + Fabcd(d - a, c - a, b, c)
End If
If S1 < ss Then ss = S1
If b = c Then
S1 = 1 + F4F(a, d - b)
ElseIf b > c Then
S1 = 1 + Fabcd(a, b - c, c, d - c)
ElseIf b < c Then
S1 = 1 + Fabcd(d - b, c - b, d, a)
End If
If S1 < ss Then ss = S1
Fabcd = ss
End If
End If
End Function
4 楼
Mato完整版 [专家分：1270] 发布于 2008-04-20 17:45:00
谢谢moz，你的算法很好，不过我输入11，10它就栈溢出了，这也许就是递归算法的缺陷。
总之，这算法还是很不错的。
5 楼
moz [专家分：37620] 发布于 2008-04-20 20:58:00
惭愧惭愧,我再追踪调试一下先.
6 楼
moz [专家分：37620] 发布于 2008-04-23 20:15:00
DECLARE FUNCTION KP1& (s$, K&, L&, LL&())
DECLARE FUNCTION Replace1& (s$, A&, N&, M&, L&, X&)
DECLARE SUB Replaces (s$, A$)
DEFLNG A-Z
INPUT "Input N, M: ", N, M
s$ = SPACE$(N * M)
IF N < M THEN J = N ELSE J = M
Min = 1 + ABS(M - N) * J
DIM LL(Min)
DO
i = INSTR(s$, " ")
IF i = 0 THEN
IF K < Min THEN
COLOR , 0
CLS
COLOR 7, 1
FOR zzz = 1 TO LEN(s$) STEP M
PRINT MID$(s$, zzz, M)
NEXT
Min = K
PRINT K
'zz2$ = INPUT$(1)
END IF
Replaces s$, CHR$(K + 48)
IF KP1(s$, K, L, LL()) THEN EXIT DO
ELSE
K = K + 1
IF K >= Min THEN
IF KP1(s$, K, L, LL()) THEN EXIT DO
ELSE
L = M - (i - 1) MOD M
IF L > J THEN L = J
IF (i + M - 1) \ M + L - 1 > N THEN L = N - ((i + M - 1) \ M - 1)
END IF
END IF
DO UNTIL Replace1(s$, INSTR(s$, " "), N, M, L, K)
IF L > 1 THEN
L = L - 1
ELSE
IF KP1(s$, K, L, LL()) THEN EXIT DO
END IF
LOOP
LL(K) = L
'COLOR , 0: CLS : COLOR 7, 1: FOR zzz = 1 TO LEN(s$) STEP M: PRINT MID$(s$, zzz, M): NEXT
'z2$ = INPUT$(1)
LOOP UNTIL K < 1
PRINT Min
FUNCTION KP1 (s$, K, L, LL())
DO
K = K - 1
IF K < 1 THEN EXIT DO
Replaces s$, CHR$(K + 48)
L = LL(K) - 1
LOOP UNTIL L > 1
END FUNCTION
FUNCTION Replace1 (s$, A, N, M, L, X)
J = A
FOR i = 1 TO L
IF MID$(s$, J, L) <> SPACE$(L) THEN
Replaces s$, STRING$(L, X + 48)
EXIT FUNCTION
ELSE
MID$(s$, J, L) = STRING$(L, X + 48)
END IF
J = J + M
NEXT
Replace1 = -1
END FUNCTION
SUB Replaces (s$, A$)
L = LEN(A$)
DO
i = INSTR(s$, A$)
IF i = 0 THEN EXIT DO
MID$(s$, i, L) = SPACE$(L)
LOOP
END SUB
仍然很慢。
7 楼
Mato完整版 [专家分：1270] 发布于 2008-04-23 22:04:00
一点都不慢！
比我的那破程序快多了。
比如输入10，20
你的程序很快就能出结果，但我的却要等10分钟。
8 楼
moz [专家分：37620] 发布于 2008-04-23 23:24:00
DECLARE SUB cc (ss!(), k!)
OPTION BASE 1
CLS
DIM SHARED m, n, f '全局变量
INPUT m, n
IF m < 1 OR n < 1 OR m > 50 OR n > 50 OR m <> INT(m) OR n <> INT(n) THEN PRINT "ERROR!": END
IF m = n THEN PRINT 1: END
IF m < n THEN x = m ELSE x = n
DIM s(m * n), t(x)
FOR i = 1 TO x
t(i) = (x + 1 - i) * (x + 1 - i) 'X为最大的边长, t( ) 储存所有可能的正方形面积
NEXT i
min = m * n '未开始时的最小个数,其实就是最大的可能值,极限值
p = 0
i = 0
lspc = m * n
v = 1
DO
i = i + 1
IF i <= x THEN
IF lspc >= t(i) THEN
p = p + 1
s(p) = t(i)
lspc = lspc - t(i)
i = i - 1
IF lspc = 0 THEN '如果某些数的平方和等于总面积,尝试拼凑正方形,并得出正方形个数.
CALL cc(s(), p)
IF f AND p < min THEN min = p
END IF
END IF
ELSE
IF p = 1 AND s(p) = 1 THEN v = 0
i = x + 1 - SQR(s(p))
lspc = lspc + s(p)
s(p) = 0
p = p - 1
END IF
LOOP UNTIL v = 0
PRINT min
END
SUB cc (ss(), k)
DIM a(m, n)
f = 1
FOR i = 1 TO k
xxx = m + 1 - SQR(ss(i))
yyy = n + 1 - SQR(ss(i))
ff = 0
FOR ii = 1 TO xxx
FOR jj = 1 TO yyy
fff = 0
IF a(ii, jj) = 0 THEN
FOR iii = ii TO ii + SQR(ss(i)) - 1
FOR jjj = jj TO jj + SQR(ss(i)) - 1
IF a(iii, jjj) THEN fff = 0:GOTO nf
a(iii, jjj) = 1
NEXT jjj, iii
fff = 1
END IF
IF fff THEN ff = 1: GOTO sf
nf: NEXT jj, ii
sf:
IF ff = 0 THEN f = 0: EXIT SUB
NEXT i
f = 1
END SUB
Mato其实你用不着过于担心,
就算别人冰雪聪明,
也不一定能看得明白你的代码,
就算给他抄去,也不见得能抢去你的劳动成果.
互相学习才会有进步,
在你这个年龄谈成绩未免太早了.
你的代码具体有没有漏洞或者优化的可能,我没有办法回答你,
因为我也只能是看得出个大概来.
你大概是在穷举所有平方和的可能性,并看它们能不能拼凑成原大正方形,而且个数是否最少的.
但我有一些很哆嗦的建议:
1.因为程序中用不着小数,所以有必要把所有变量弄成整形,在某种程度上可以加快一点运行的效率.
2.虽然说不上反对Goto的使用,但我仍然希望你能避免使用它,因为很多时候你甚至不会知道该怎么修改.
9 楼
moz [专家分：37620] 发布于 2008-04-23 23:31:00
我再来说说我的一些想法:
解释一下3楼的代码先:
其实这个程序没经过检查,应该有不少漏洞,我的想法是原来的矩形切去一个正方形后,
将会得到以下一个图形:
a
_____
| |
_____| |
b| |d
|_________|
c
我的程序里是使用了函数来计算a,b,c,d这个形状的最少正方形的,
但事实上出现了很多的问题,我却没有足够的时间和精力去解决.
而6楼的代码,却是使用字符串来做的.
空格符为没划分的空白,填了字符的为已划分的正方形.
用Instr( )来找到最前面的一个空格,在这个位置上从大到小的测试正方形,
并不断的得到更少的正方形数.
程序是正确的,但当N,M越来越大的时候就显得力不从心了.
10 楼
Mato完整版 [专家分：1270] 发布于 2008-04-24 12:43:00
moz:
我发现你6楼的程序算法是跟我原来的一样的。
Replace1：将第i个正方形的数据放入s$里
Replaces：清除第i个正方形的数据。
不过我不知道KP1函有什么用，而且这个函数没有返回值，怎么搞的？
我来回复
您所在位置：