论坛 › 编程擂台 › 最小无法表达的正整数

mathe 发表于 2008-8-1 08:28:15

最小无法表达的正整数

求最小无法用1~n这n个数通过四则混合运算表达出来的正整数.
如n=1,那么显然只能表示1,所以结果是2.
而n=2,由于1=2-1,2=2*1,3=2+1,4无法表示所以结果是4
而n=3,由于1=(2+1)/3,2=3+1-2,3=3*(2-1),4=3+2-1,5=3*2-1,6=3*2*1,7=3*2+1,8=(3+1)*2,9=3*(2+1),10无法表示,所以结果为10
对不同的n分别求值,看谁能够达到最大的n

结果已添加到A060315

无心人 发表于 2008-8-1 14:22:24

有点复杂吧

mathe 发表于 2008-8-1 15:08:05

对于大一些的n应该挺复杂的.很多年前我做过,好像计算机运行两天左右才能够算出n=10的结果.不过那时候的代码应该还没有写得够好

无心人 发表于 2008-8-1 17:05:55

n = 4
1=(3+2-1)/4
2 = (2-1) + (4-3)
3 = 4 - (1 + 2) / 3
4 = (3 - 1) + (4 - 2)

无心人 发表于 2008-8-1 17:19:49

6 = 1 + 3 + 4 - 2
8 = 2 + 3 + 4 - 1
10 = 1 + 2 + 3 + 4

无心人 发表于 2008-8-1 17:21:13

7 = (1 + 2 + 4) * 1
5 = (2 - 3 + 4) * 1
9 = (2 + 3 + 4) * 1

无心人 发表于 2008-8-1 17:24:06

11 = 2 * 4 + 1 * 3
12 = 2 * 4 + 1 + 3
13 = 3 * 4 + 2 - 1
15 = 3 * 4 + 2 + 1
14 = 1 * 3 * 4 + 2

无心人 发表于 2008-8-1 17:28:06

16 = (1 + 3) * 4 + 2
17 = (1 + 4) * 3 + 2
18 = (4 - 1) * 3 * 2
19 = (4 + 2) * 3 + 1
20 = (3 * 2 - 1) * 4
21 = ( 4 + 2 + 1) * 3
22 = (4 * 3 - 1) * 2
23 = 4 * 3 * 2 - 1
24 = (4 + 2) * (1 + 3)
25 = (4 + 1) * (2 + 3)
26 = (4 * 3 + 1) * 2
27 = (4 * 2 + 1) * 3
28 = (2 * 3 + 1)* 4

n = 4的最小是29么？

无心人 发表于 2008-8-1 19:10:24

我想，似乎是个树状结构
叶子是n个数字，节点是四个运算符号

现在问题是我知道如何构造此树，但不知道如何计算，呵呵
哦，明白了
呵呵
计算左树，
计算右树
      输出结果
         是完整树？ 测试

无心人 发表于 2008-8-1 20:14:47

实际写程序
发现有点难
主要是无法找到递归的方式
呵呵

查看完整版本: 最小无法表达的正整数