1-29cm的尺子答案 — 编程爱好者社区

主题：1-29cm的尺子答案

幽灵密码 [专家分：3510] 发布于 2011-01-07 13:06:00

一条29cm的尺子，刻7个刻度，要求最多量一次能量出1-29cm所有长度。
解释一下，所谓只量一次是指两个刻度之间的长度可以量出1-29cm所有的长度，两个刻度相加是不允许的。
[color=FF0000]我想了一下，尺子最左边是0，最右边是29cm，所以29cm肯定不用刻。[/color]程序：
[color=0000FF]CLS
DIM s(28), m(7)
s = TIMER
FOR a = 1 TO 22
  FOR b = a + 1 TO 23
    FOR c = b + 1 TO 24
      FOR d = c + 1 TO 25
        FOR e = d + 1 TO 26
          FOR f = e + 1 TO 27
            FOR g = f + 1 TO 28
              n = 1
              m(1) = a
              m(2) = b: m(3) = c: m(4) = d: m(5) = e: m(6) = f: m(7) = g
              FOR j = 7 TO 1 STEP -1
                s(29 - m(j)) = 1
                FOR k = j - 1 TO 1 STEP -1
                  s(m(j) - m(k)) = 1
              NEXT k, j
              s(a) = 1
              s(b) = 1: s(c) = 1: s(d) = 1: s(e) = 1: s(f) = 1: s(g) = 1
              FOR i = 1 TO 28
                IF s(i) = 0 THEN n = 0: EXIT FOR
              NEXT i
              IF n <> 0 THEN PRINT a; b; c; d; e; f; g
              FOR i = 1 TO 28
                s(i) = 0
              NEXT i
NEXT g, f, e, d, c, b, a
PRINT "Use time"; TIMER - s; "seconds"
END[/color]
最后输出的是用时。大约16秒的样子。

运行结果：
1  2  14  18  21  24  27
1  3  6  13  20  24  28
1  4  10  16  22  24  27
1  5  9  16  23  26  28
2  5  7  13  19  25  28
2  5  8  11  15  27  28
Use time 16.87109 seconds '这里每次运行都不同

解释一下运行结果：
第一种方案：
1 3 6 13 20 24 28
1=1
2=3-1
3=3
4=18-14
5=6-1
6=6
7=20-13
8=28-20
9=24-13
10=13-3
11=24-13
12=13-1
13=13
14=20-6
15=28-13
16=29-13
17=20-3
18=24-6
19=20-1
20=20
21=24-3
22=28-6
23=24-1
24=24
25=28-3
26=29-3
27=28-1
28=28
29=29(尺子最边缘，不用刻)

第二种方案：
2 5 8 11 15 27 28
1=28-27
2=2
3=5-2
4=15-11
5=5
6=8-2
7=15-8
8=8
9=11-2
10=28-8
11=11
12=27-15
13=28-15
14=29-15
15=15
16=27-11
17=28-11
18=29-11
19=27-8
20=28-8
21=29-8
22=27-5
23=28-5
24=29-5
25=27-2
26=28-2
27=27
28=28
29=29

第三种方案：
1 2 14 18 21 24 27
1=1
2=2
3=24-21
4=18-14
5=29-24
6=27-21
7=21-14
8=29-21
9=27-18
10=24-14
11=29-18
12=14-2
13=14-1
14=14
15=29-14
16=18-6
17=18-1
18=18
19=21-2
20=21-1
21=21
22=24-2
23=24-1
24=24
25=27-2
26=27-1
27=27
28=29-1
29=29

第四种方案：
1 4 10 16 22 24 27
1=1
2=24-22
3=4-1
4=4
5=27-22
6=10-4
7=29-22
8=24-16
9=10-1
10=10
11=27-16
12=22-10
13=29-16
14=24-10
15=16-1
16=16
17=27-10
18=22-4
19=29-10
20=24-4
21=22-1
22=22
23=24-1
24=24
25=29-4
26=27-1
27=27
28=29-1
29=29

第五种方案：
1 5 9 16 23 26 28
1=1
2=28-26
3=26-23
4=5-1
5=5
6=29-23
7=23-16
8=9-1
9=9
10=26-16
11=16-5
12=28-16
13=29-16
14=23-9
15=16-1
16=16
17=26-9
18=23-5
19=28-9
20=29-9
21=26-5
22=23-1
23=23
24=29-5
25=26-1
26=26
27=28-1
28=28
29=29

第六种方案：
2 5 7 13 19 25 28
1=29-28
2=2
3=5-2
4=29-25
5=5
6=19-13
7=7
8=13-5
9=28-19
10=29-19
11=13-2
12=19-7
13=13
14=19-5
15=28-13
16=29-13
17=19-2
18=25-7
19=19
20=25-5
21=28-7
22=29-7
23=28-5
24=29-5
25=25
26=28-2
27=29-2
28=28
29=29

最后更新于：2011-01-25 17:08:00

本帖地址： http://bbs.pfan.cn/post/360861.html

回复列表（共9个回复）

沙发

moz [专家分：37620] 发布于 2011-01-08 01:54:00

果然是后生可畏，我按照你的理论，写了一个程序，结果......落后你太多太多了，用了三分钟。
171.6558     82694

代码如下：

t1 = Timer
Sum = 0
a$ = "123456789:;<=>?@ABCDEFGHIJKL"
b$ = "FGHIJKL"
Do
    Sum = Sum + checkisright(b$)
    b$ = nextzh$(a$, b$)
Loop Until b$ = "FGHIJKL"
Print Timer - t1,Sum

Function nextzh$(a$, b$)
For i = 1 To Len(b$)
  If InStr(1, a$, Mid$(b$, i, 1)) > i Then
     Mid$(b$, 1, i) = Mid$(a$, InStr(1, a$, Mid$(b$, i, 1)) - i, i)
     Exit For
  End If
Next
If i > Len(b$) Then b$ = Right$(a$, Len(b$))
nextzh$ = b$
End Function

Function checkisright(x$)
y$ = x$
z$ = Right$(y$, 2)
zz$ = z$
s$ = Space$(28)
For i = 1 To Len(x$)
    p = Asc(Mid$(x$, i, 1)) - 48
    mid$(s$,p,1)="1"
    If p + p < 29 Then Mid$(s$, p + p, 1) = 1
Next
Do
    p = Asc(Left$(z$, 1)) - 48
    q = Asc(Right$(z$, 1)) - 48
    If p + q < 29 Then Mid$(s$, p + q, 1) = "1"
    Mid$(s$, Abs(p - q), 1) = "1"
    z$ = nextzh$(y$, z$)
Loop Until z$ = zz$
If InStr(s$, Chr$(32)) = 0 Then
    For i = 1 To Len(x$)
        Print Asc(Mid$(x$, i, 1)) - 48;
    Next
    Print
    checkisright = 1
End If
End Function

板凳

moz [专家分：37620] 发布于 2011-01-08 02:15:00

你帮我把最后的几个结果验证一下，看看有什么问题。
1  2  3  6  10  11  14
2  3  5  8  9  11  14
2  3  5  7  9  11  14
2  3  5  6  8  11  14
2  3  5  6  7  11  14
2  3  4  8  9  10  14
2  3  4  7  9  10  14
2  3  4  6  8  10  14
2  3  4  6  7  10  14
2  3  4  5  8  9  14
2  3  4  5  7  9  14
2  3  4  5  6  8  14
2  3  4  5  6  7  14
1  2  8  10  11  12  13
1  2  7  10  11  12  13
1  2  6  10  11  12  13
1  2  5  10  11  12  13
1  2  4  10  11  12  13
1  2  3  10  11  12  13
1  2  8  9  11  12  13
1  2  7  9  11  12  13
1  2  6  9  11  12  13
1  2  7  8  11  12  13
1  2  6  8  11  12  13
1  2  5  8  11  12  13
1  2  4  8  11  12  13
1  2  3  8  11  12  13
1  2  8  9  10  12  13
1  2  7  9  10  12  13
1  2  6  9  10  12  13
1  2  5  9  10  12  13
1  2  4  9  10  12  13
1  2  3  9  10  12  13
1  2  7  8  10  12  13
1  2  6  8  10  12  13
1  2  5  8  10  12  13
1  2  4  8  10  12  13
1  2  3  8  10  12  13
1  2  6  8  9  12  13
1  2  6  7  9  12  13
1  2  5  6  9  12  13
1  2  4  6  9  12  13
1  2  3  6  9  12  13
1  2  6  7  8  12  13
1  2  4  9  10  11  13
1  2  4  8  10  11  13
1  2  4  7  10  11  13
1  2  4  6  10  11  13
1  2  4  5  10  11  13
1  2  3  4  10  11  13
1  2  3  4  10  11  12
1  2  3  4  8  11  12

3 楼

yuan067 [专家分：60] 发布于 2011-01-08 03:09:00

这个计算时间改得不错

4 楼

幽灵密码 [专家分：3510] 发布于 2011-01-10 22:03:00

最多量一次

5 楼

幽灵密码 [专家分：3510] 发布于 2011-01-10 22:04:00

Moz的方法有误啊

6 楼

小败家子 [专家分：0] 发布于 2011-02-22 22:14:00

C++版的运行结果：
1 2 14 18 21 24 27
1 3 6 13 20 24 28
1 4 10 16 22 24 27
1 5 9 16 23 26 28
2 5 7 13 19 25 28
2 5 8 11 15 27 28

Process returned 0 (0x0)   execution time : 2.484 s
Press any key to continue.
代码：
#include<iostream>
using namespace std;
int f[9];
bool d[30];
int main()
{
    bool flag;
    f[0] = 0;f[8] = 29;
    for(f[1] = 1; f[1] <= 22; ++f[1])
        for(f[2] = f[1]+1; f[2] <= 23; ++f[2])
            for(f[3] = f[2]+1; f[3] <= 24; ++f[3])
                for(f[4] = f[3]+1; f[4] <= 25; ++f[4])
                    for(f[5] = f[4]+1; f[5] <= 26; ++f[5])
                        for(f[6] = f[5]+1; f[6] <= 27; ++f[6])
                            for(f[7] = f[6]+1; f[7] <= 28; ++f[7]){
                                flag = true;
                                for(int i = 0; i <= 29; ++i)
                                    d[i] = false;
                                for(int i = 0; i <= 7; ++i){
                                    for(int j = i+1; j <= 8; ++j){
                                        d[f[j] - f[i]] = true;
                                    }
                                }
                                for(int i = 1; i <= 29; ++i){
                                    if(d[i] == false){
                                        flag = false;
                                        break;
                                    }
                                }
                                if(flag){
                                    for(int i = 1; i <= 7; ++i)
                                        cout<<f[i]<<" ";
                                    cout<<endl;
                                }
                            }
    return 0;
}

7 楼

imjohnzj [专家分：1490] 发布于 2011-12-03 20:43:00

MOZ 用字符串哦，会不会是这里慢了？

8 楼

moz [专家分：37620] 发布于 2011-12-04 00:16:00

我的记忆力不是很好，也不想跟小孩子计较太多。
但如果我不提醒一下我自己的话，我会害怕是不是因为我老的太快了。
所以你改了题目，再回头来说我做的不对的话，是否有考虑过会不会对我是一种伤害或是打击？

DefInt A-Z
t1# = Timer
Sum = 0
a$ = "123456789:;<=>?@ABCDEFGHIJKL"
b$ = "FGHIJKL"
s$ = b$ + "M                            "
i = 7
c = 1
Do
    y = 8
    For j = 1 To i
        For k = j + 1 To 8
            y = y + 1
            Mid$(s$, y, 1) = Chr$(48 + Asc(Mid$(s$, k, 1)) - Asc(Mid$(s$, j, 1)))
        Next
    Next
    If InStr(s$, Chr$(48 + c)) > 0 Then
    For c = 1 To 28
        If InStr(s$, Chr$(48 + c)) = 0 Then Exit For
    Next
    End If
    If c > 28 Then
        Sum = Sum + 1
        For d = 1 To 7
            Print Asc(Mid$(b$, d, 1)) - 48;
        Next
        Print
    End If
    For i = 1 To 7
      If InStr(1, a$, Mid$(b$, i, 1)) > i Then
         Mid$(b$, 1, i) = Mid$(a$, InStr(1, a$, Mid$(b$, i, 1)) - i, i)
         Exit For
      End If
    Next
    Mid$(s$, 1, 8) = b$ + "M"
Loop Until i > 7
Print Timer - t1#, Sum

9 楼

幽灵密码 [专家分：3510] 发布于 2011-12-09 21:30:00

[quote]我的记忆力不是很好，也不想跟小孩子计较太多。
但如果我不提醒一下我自己的话，我会害怕是不是因为我老的太快了。
所以你改了题目，再回头来说我做的不对的话，是否有考虑过会不会对我是一种伤害或是打击？

DefInt A-Z
t1# = Timer
Sum = 0
a$ = "123456789:;<=>?@ABCDEFGHIJKL"
b$ = "FGHIJKL"
s$ = b$ + "M                            "
i = 7
c = 1
Do
    y = 8
    For j = 1 To i
        For k = j + 1 To 8
            y = y + 1
            Mid$(s$, y, 1) = Chr$(48 + Asc(Mid$(s$, k, 1)) - Asc(Mid$(s$, j, 1)))
        Next
    Next
    If InStr(s$, Chr$(48 + c)) > 0 Then
    For c = 1 To 28
        If InStr(s$, Chr$(48 + c)) = 0 Then Exit For
    Next
    End If
    If c > 28 Then
        Sum = Sum + 1
        For d = 1 To 7
            Print Asc(Mid$(b$, d, 1)) - 48;
        Next
        Print
    End If
    For i = 1 To 7
      If InStr(1, a$, Mid$(b$, i, 1)) > i Then
         Mid$(b$, 1, i) = Mid$(a$, InStr(1, a$, Mid$(b$, i, 1)) - i, i)
         Exit For
      End If
    Next
    Mid$(s$, 1, 8) = b$ + "M"
Loop Until i > 7
Print Timer - t1#, Sum[/quote]
我没改题目= =。

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：1-29cm的尺子答案

回复列表（共9个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：1-29cm的尺子 答案

回复列表 （共9个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：1-29cm的尺子答案

回复列表（共9个回复）