2011年度最变态的迷宫难题

    下面大家将会看到的是一个极其简单而又极其复杂的“迷宫”,这无疑是我在本年度见到的最变态的谜题:从左边入口处的 2011 进去,在迷宫里转悠,最后变成 2012 从右边出来。你可以在迷宫里转圈,可以重复之前走过的路,但不能往回退着走。

      

    你能成功走出来吗?


 
 
 
 
 
 
 
 
 
 
 
 
    放弃吧,答案是

2011 +7 ÷2 +7 ÷2 +7 -5 ×3 ÷2 +7 ÷2 +7 ×3 -5 ÷2 +7 ÷2 +7 -5 ×3 -5 ×3 ÷2 +7 -5 ×3 ÷2 +7 -5 = 2012

    这个变态的谜题来自 Holiday Puzzles 2011 ,作者是 Erich Friedman
    提前祝大家新年快乐。

82 条评论

  • matrix76

    haha,safa

  • ykzls

    没有考虑运算顺序。

  • qsort

    难得前排啊。
    不过这个答案和题目明显有歧义啊。

  • Draco

    用matlab又找了一个解
    2011+7+7+7+7+7/2+7*3-5+7/2/2+7*3*3/2+7*3-5/2+7/2/2+7+7/2+7*3-5-5=2012

  • w.vela

    matlab那个解不对吧,没法应用到这个迷宫中⋯⋯

  • Googler

    2 011 + (7 ÷ 2) + (7 ÷ 2) + 7 – ((5 × 3) ÷ 2) + (7 ÷ 2) + (7 × 3) – (5 ÷ 2) + (7 ÷ 2) + 7 – (5 × 3) – ((5 × 3) ÷ 2) + 7 – ((5 × 3) ÷ 2) + 7 – 5 = 2029

  • Draco

    步数比较短的几个解
    20:
    2011+7/2+7/2/2/2+7*3*3-5-5*3*3/2/2*3-5/2/2-5=2012
    2011+7-5-5/2/2-5-5/2+7-5-5-5-5-5*3-5-5*3-5-5=2012
    跑了半个小时貌似没有找到更少的。

  • Draco

    悲剧……没有看到不能往回退着走……

  • elfish

    test=2018;
    a=zeros(100000,3);
    for i=1:10000
    test
    if(test==2017)
    break;
    end
    if(mod(test,2)==1)
    if(a(test,1)==0)
    a(test,1)=1;
    test=(test+7)/2;
    continue;
    end
    if(a(test,2)==0)
    a(test,2)=1;
    test=(test-5)*3;
    continue;
    end
    if(a(test,3)==0)
    a(test,3)=1;
    test=(test*3)-5;
    continue;
    end
    else
    if(a(test,1)==0)
    a(test,1)=1;
    test=(test/2)+7;
    continue;
    end
    if(a(test,2)==0)
    a(test,2)=1;
    test=(test-5)*3;
    continue;
    end
    if(a(test,3)==0)
    a(test,3)=1;
    test=(test*3)-5;
    continue;
    end
    end
    end

  • calf

    考虑到加减乘除的运算优先级之后,结果明显是2029啊:http://www.wolframalpha.com/input/?i=2011+%2B7+%C3%B72+%2B7+%C3%B72+%2B7+-5+%C3%973+%C3%B72+%2B7+%C3%B72+%2B7+%C3%973+-5+%C3%B72+%2B7+%C3%B72+%2B7+-5+%C3%973+-5+%C3%973+%C3%B72+%2B7+-5+%C3%973+%C3%B72+%2B7+-5

  • zagfai

    楼上的. 就迷宫系按顺序 不考虑优先级 吧

  • 啪啦图

    可以用DPvis 做自动理论验证

  • a

    楼层: 10楼 | 2011-11-30 18:02 | calf
    楼层: 地基 | 2011-11-30 16:35 | Googler

    这显然不是算24点 问题。。。。

  • a

    楼层: 地壳 | 2011-11-30 16:50 | Draco 说: 从左边入口处的 2011 进去,在迷宫里转悠,最后变成 2012 从右边出来。你可以在迷宫里转圈,可以重复之前走过的路,但不能往回退着走。

  • andi

    var a,d,m,s;
    ac = [[d,m,s],[d]]
    dc = [[a,m,s],[a]]
    mc = [[],[s],[a,d,s]]
    sc = [[],[m],[a,m,d]]
    adp = [1,0]
    msp = [0,2,1]

    function a(o) { return {v:o.v+7, can:ac[o.p], p:adp[o.p]}; }
    function d(o) { return {v:o.v/2, can:dc[o.p], p:adp[o.p]}; }
    function m(o) { return {v:o.v*3, can:mc[o.p], p:msp[o.p]}; }
    function s(o) { return {v:o.v-5, can:sc[o.p], p:msp[o.p]}; }

    function print(a) {
    document.write(a+””);
    }

    function trace(x) {
    if (x == a) print(“+7”);
    if (x == d) print(“/2”);
    if (x == m) print(“*3”);
    if (x == s) print(“-5”);
    }

    function maze(o, level) {
    if (level > 40) return false;
    for (var i = 0; i < o.can.length; ++i) {
    if (o.v % 2 && o.can[i] == d) continue;
    var no = o.can[i](o);
    if (no.p == 2)
    if (no.p == 2 && no.v == 2012) {
    print(level + “<===”);
    return true;
    }
    if (maze(no, ++level)) {
    trace(o.can[i])
    return true;
    }
    }
    return false;
    }

    maze({v:2011, p:0, can:[a,d]}, 0);

  • elfish

    楼上js么

  • error 404

    提问:走法有没有限?如果有限,一共有几种?

  • elfish

    不限长度是有循环的

  • andi

    递归了40层找到答案
    递归50层扛不住,没有找到另一个答案。

  • biohu

    这个难度太大了!

  • Life Designer

    有没有通解???

  • liqiyu

    2011 +7/2+7/2+7-5*3/2+7/2+7*3-5/2+7/2+7-5*3-5*3/2+7-5*3/2+7-5 = 2012
    python 1s算出的结果,深度优先搜索,得限制深度; 广度优先没试 。

  • JJ

    所谓的回退指的是不能转身 还是不能以不同的方向走过同一条路径

  • liqiyu

    英文题目里说的更清楚:同一个操作可以经过多次,但是不能连续做两次。

  • Lois

    You may pass through an operation several times, but not twice in a row. 理解有点困难 解答里+7/2+7/2不就连着两次了么

  • 杨圣青

    @地板Draco,不能连着+7,规则里说了,不能往回退着走。

  • eniac

    什么叫回退,这个根本没解释清楚啊。

  • haipeng

    50步以内的所有解:
    44
    2011+7/2+7/2+7*3-5/2+7*3-5/2+7/2+7/2+7-5*3/2+7/2+7/2+7/2+7*3-5*3-5+7/2-5*3-5*3/2+7-5*3/2+7-5=2012
    44
    2011+7/2+7/2+7*3-5*3-5+7/2+7/2+7/2+7/2+7/2+7/2+7/2*3-5/2+7*3-5*3-5+7/2-5*3-5*3/2+7-5*3/2+7-5=2012
    28
    2011+7/2+7/2+7-5*3/2+7/2+7*3-5/2+7/2+7-5*3-5*3/2+7-5*3/2+7-5=2012
    44
    2011+7/2+7/2+7-5*3/2+7*3-5+7/2+7/2+7/2+7/2+7/2+7/2*3-5/2+7*3-5*3-5+7/2-5*3-5*3/2+7-5*3/2+7-5=2012

  • OMG

    那还不是算倒着走了……晕晕

  • Cielo

    手算的,先完全通过右侧倒推出:3到达中间位置即可,于是从左边出发希望得到3,结果不保证算对了……
    +7 ÷2 +7 ÷2 ÷2 ÷2 +7 ÷2 +7 ÷2 +7 ÷2 ÷2 +7 ÷2 -5 ×3 ÷2 ÷2 ×3 ×3 ×3 -5 ×3 ×3 -5 -5 ×3 -5 -5

  • Cielo

    好吧原来不能倒着走,晕死>_<

  • qing

    //对答案的注释

    ((((((((((((((((((((((((((2011+7)/2)+7)/2)+7)-5)*3)/2)+7)/2)+7)*3)-5)/2)+7)/2)+7)-5)*3)-5)*3)/2)+7)-5)*3)/2)+7-5
    自己拿笔算了半天没算出来

  • 六翼

    带括号的同学们,人家是要走一步就算一步的结果的吧……

  • 小灰

    这个。。好长一结果。。。。

  • ktx

    用有限状态机可以解决吗?

  • 梦半醒

    var numCal0 = [‘+7’, ‘/2’, ‘*3’, ‘-5’];
    var numCal = [[‘+7’, ‘/2’], [‘/2’, ‘+7’], [‘*3’, ‘-5’], [‘-5’, ‘*3’]];
    var iniNum = 2011, iniNum2 = iniNum + 7, resNum = 2012 + 5;

    var mig = function (arr) {
    var arrto = [];

    for (var j = 0; j < arr.length; j++) {
    var r = arr[j], r0 = parseInt(r.arr.charAt(r.arr.length – 1));

    for (var i = 0; i < numCal.length; i++) {
    if (i == r0) continue;
    if (r.num % 2 == i) continue;

    var rt = eval(‘(‘ + r.num + numCal[i][0] + ‘)’ + numCal[i][1]),
    arrx = r.arr + i + ” + ((i 0) arrto.push({ num: rt, arr: arrx });
    }
    }

    return mig(arrto);
    };

    var arr0 = mig([{ num: iniNum2, arr: ‘0’}]), s = iniNum;

    for (var i = 0; i < arr0.length; i++) {
    var x = parseInt(arr0.charAt(i));
    if (x == 0 || x == 3) s = ‘(‘ + s + numCal0[x] + ‘)’;
    else s += numCal0[x];
    }

    s += numCal0[3];

    alert(s);

  • BB霜

    这个用人脑能想出来吗?

  • xieranmaya

    手动逆推可以不..

  • LostAbaddon

    用JS写了个遗传算法的程序来跑,13个编码(也就是具体算符数-2后除2)是最容易得到的,其次是21个编码的,最长弄感到过44个编码的……
    平均1秒左右算完(看你具体参数设定),所以可以考虑点一次出个答案,应该很爽~
    https://plus.google.com/u/0/100539490303421499436/posts/BV8TRYtWrgt

  • claymore

    ((2012+7)/2 – 5x 67) x 3

  • Next Week

    js代码:

    function puzzle2011(initial, target) {
    var operations = {
    ‘left’:[‘+7′,’/2’],
    ‘right’:[‘*3’, ‘-5′]
    }
    function addstate(ops, pos, index) {
    for(var i=0; i<ops.length; i++) {
    var op = ops[i];
    if(op == state.op) continue;
    var num = eval(state.num + op);
    if(parseInt(num)!=num) continue;
    status.push({pos:pos, op:op, num:num, previous:index, step:state.step+1});
    if(status.length%10000==0) document.title = state.step +’ / ‘+ status.length;
    if(num==target && pos==’right’) {
    answer();
    return true;
    }
    }
    }
    function answer() {
    var state = status[status.length-1];
    var prefix = state.step +’ / ‘+ status.length + ‘:n’;
    var result = ‘= ‘ + target;
    do {
    result = (state.op||initial) + ‘ ‘ + result;
    } while(state = status[state.previous]);
    alert(prefix + result)
    }
    var status = [{num:initial, pos:’left’, step:0}];
    for(var i=0; i<status.length; i++) {
    var state = status[i];
    var ops = operations[state.pos];
    if(ops) {
    if(addstate(ops, ‘middle’, i)) return;
    } else {
    if(addstate(operations[‘left’], ‘left’, i)) return;
    if(addstate(operations[‘right’], ‘right’, i)) return;
    }
    }
    }
    puzzle2011(2011,2012);

  • Next Week

    算了下其它值, 所有运算符同优先级,严格按从左到右顺序计算
    2009 +7 /2 +7 -5 *3 /2 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 -5 *3 +7 /2 *3 -5 +7 /2 *3 = 2010
    2010 +7 *3 -5 /2 +7 /2 +7 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 /2 +7 *3 -5 /2 +7 *3 -5 /2 +7 -5 = 2011
    2011 +7 ÷2 +7 ÷2 +7 -5 ×3 ÷2 +7 ÷2 +7 ×3 -5 ÷2 +7 ÷2 +7 -5 ×3 -5 ×3 ÷2 +7 -5 ×3 ÷2 +7 -5 = 2012
    2012到2013算了37步也没结果
    2013 +7 /2 +7 *3 -5 /2 +7 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 *3 -5 /2 +7 /2 +7 /2 +7 -5 *3 -5 = 2014
    2014 /2 +7 /2 +7 /2 +7 /2 *3 -5 +7 /2 *3 -5 /2 +7 -5 *3 /2 +7 -5 *3 -5 *3 /2 +7 -5 = 2015

  • morrowind

    挺有意思的。在50步之前解都很稀疏,28步1个,44步3个,50步2个。
    但是之后解的个数突然爆发,52步有811个,54步有2053个,56步有5个,58步有305个,60步有382个。

  • morrowind

    算错了点,52步0个,54步有2051个,56步有5个,58步0个,60步有368个。
    2012到2013的最小解

  • 正月点灯笼

    哈哈,我也得到了这么几组解:
    解1:
    2011 +7 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 /2 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 /2 +7 /2 +7 *3 -5 *3 -5 +7 /2 -5 *3 -5 *3 /2 +7 -5 *3 /2 +7 -5 =2012

    解2:
    2011 +7 /2 +7 /2 +7 *3 -5 *3 -5 +7 /2 +7 /2 +7 /2 +7 /2 +7 /2 +7 /2 +7 /2 *3 -5 /2 +7 *3 -5 *3 -5 +7 /2 -5 *3 -5 *3 /2 +7 -5 *3 /2 +7 -5 =2012

    解3:
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 *3 -5 +7 /2 +7 /2 +7 /2 +7 /2 +7 /2 +7 /2 *3 -5 /2 +7 *3 -5 *3 -5 +7 /2 -5 *3 -5 *3 /2 +7 -5 *3 /2 +7 -5 =2012

    解4:
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 *3 -5 /2 +7 /2 +7 -5 *3 -5 *3 /2 +7 -5 *3 /2 +7 -5 =2012

    递归算的。

  • vibbow

    拿我的上网本用PHP递归中…
    递归到第17层已经要247秒了…

  • vibbow

    先用宽度优先结出一个结果:
    2011 +7 ÷2 +7 ÷2 ×3 -5 +7 ÷2 +7 ÷2 ×3 -5 ÷2 +7 ÷2 +7 ÷2 +7 -5 ×3 -5 ×3 -5 ×3 +7 ÷2 = 2012
    Execute time: 7s

  • vibbow

    擦,发现忽略了一个条件,蛋疼了,重算…

  • 正月点灯笼

    秀一下我的代码(C):

    #include
    #define PLUS7L 0
    #define PLUS7R 1
    #define DIVE2L 2
    #define DIVE2R 3
    #define MULT3L 4
    #define MULT3R 5
    #define MINU5L 6
    #define MINU5R 7

    int result[55];

    int trans[8][3] = {{MULT3L, MINU5L, DIVE2R},
    {DIVE2L, -1, -1},
    {MULT3L, MINU5L, PLUS7R},
    {PLUS7L, -1, -1},
    {MINU5R, -1, -1},
    {PLUS7R, DIVE2R, MINU5L},
    {MULT3R, -1, -1},
    {PLUS7R, DIVE2R, MULT3L},
    };

    int calc(int num, int state)
    {
    if (state==PLUS7L || state==PLUS7R) {
    return num+7;
    }
    else if (state==DIVE2L || state==DIVE2R) {
    return num/2;
    }
    else if (state==MULT3L || state==MULT3R) {
    return num*3;
    }
    else if (state==MINU5L || state==MINU5R) {
    return num-5;
    }
    }

    void print_arr(int length)
    {
    int i;
    for (i=0; i0) {
    int i;
    result[k] = state;
    int new_num = calc(num, state);
    if (new_num == 2012 && (state==MULT3L || state==MINU5L)) {
    printf(“%d步:n”, k+1);
    printf(“2011 “);
    print_arr(k);
    printf(“=2012n”);
    }
    for (i=0; i<3; i++) {
    if (trans[state][i]!=-1 && (trans[state][i]!=DIVE2L && trans[state][i]!=DIVE2R)) {
    int next_state = trans[state][i];
    solve(next_state, new_num, t-1, k+1);
    }
    else if (trans[state][i]!=-1 && (trans[state][i]==DIVE2L || trans[state][i]==DIVE2R)) {
    if (new_num%2==0) {
    int next_state = trans[state][i];
    solve(next_state, new_num, t-1, k+1);
    }
    }
    }
    }
    }

    int main()
    {
    solve(0, 2011, 52, 0);
    return 0;
    }

  • vibbow

    LS代码有问题吧,solve函数在哪里定义的?

  • vibbow

    运行无误了,秀一下我的代码,PHP版的:
    http://snipt.org/poNp6

    属于用硬盘空间换内存空间的典型。运行时内存占用不到10M,但是会生成数G的临时文件…

    在E5400上测,瓶颈依然是CPU,磁盘读写只维持在了7MB/s左右…

    算法很简单,代码读起来很纠结,属于笨办法去算的…

  • 古十长

    额。。。真的要那么多步么??
    2011+7*3-5*3-5=2012

  • 古十长

    2011十7×3一5X3一

  • 古十长

    2011+7×3一5×3一5

  • 古十长

    LZ我错了。。。刚刚因为网络原因才发那么多次。。。每次都显示发送失败。。而且刚刚的结果也是错的。。因为出口不对。。。现在改了代码。。
    12步:2011+7-5*3/2+7-5*3/2+7-5=2012

  • 大头龙仔

    这个不错,代码好像有些问题

  • vibbow

    @59楼:这个题不能遵守四则运算守则的,而应该是直接从左到右算的。

  • kshaoye

    自抢沙发!?还是山寨M67?
    评论中惊现大量CODE帝

  • smiletiger

    2011 + (7/2)*6 – 5 * 3 – 5 = 2012

  • smiletiger

    2011 + (7 / 2)*26 – (5 * 3)*6 = 2012

  • smiletiger

    2011 + (7/2)*4 + 7 – 5 * 3 – 5 = 2012

  • minglingmaster

    楼上几位,这题必须走一步算一步,不能按先乘除后加减算

  • Solstice

    搜到了另一个解
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 /2 +7 -5 *3 +7 /2 +7 /2 -5 *3 -5 *3 -5 *3 *3 -5 +7 /2 -5 = 2012
    https://gist.github.com/1723099

  • Solstice

    一共107组解:

    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 /2 +7 -5 *3 +7 /2 +7 /2 -5 *3 -5 *3 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 +7 /2 *3 -5 +7 /2 -5 *3 +7 /2 -5 *3 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 +7 /2 *3 -5 +7 /2 -5 *3 -5 *3 /2 +7 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 +7 /2 *3 -5 -5 *3 *3 -5 +7 /2 +7 /2 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 +7 /2 -5 *3 +7 /2 *3 -5 /2 +7 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 +7 /2 -5 *3 +7 /2 *3 -5 -5 *3 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 +7 /2 -5 *3 *3 -5 /2 +7 *3 -5 /2 +7 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 +7 /2 -5 *3 -5 *3 /2 +7 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 *3 -5 /2 +7 -5 *3 +7 /2 *3 -5 +7 /2 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 *3 -5 /2 +7 -5 *3 *3 -5 *3 -5 +7 /2 /2 +7 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 *3 -5 /2 +7 -5 *3 -5 *3 /2 +7 *3 -5 /2 +7 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 *3 -5 *3 -5 +7 /2 /2 +7 +7 /2 -5 *3 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 *3 -5 *3 -5 +7 /2 /2 +7 -5 *3 /2 +7 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 *3 -5 *3 -5 *3 -5 /2 +7 /2 +7 /2 +7 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 *3 -5 *3 -5 -5 *3 /2 +7 +7 /2 /2 +7 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 *3 -5 -5 *3 +7 /2 +7 /2 *3 -5 /2 +7 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 -5 *3 /2 +7 *3 -5 /2 +7 +7 /2 -5 *3 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 -5 *3 /2 +7 *3 -5 /2 +7 -5 *3 /2 +7 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 -5 *3 /2 +7 -5 *3 /2 +7 /2 +7 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 -5 *3 /2 +7 -5 *3 /2 +7 -5 *3 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 *3 -5 -5 *3 *3 -5 +7 /2 +7 /2 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 -5 *3 *3 -5 /2 +7 +7 /2 /2 +7 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 +7 /2 -5 *3 -5 *3 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 /2 +7 +7 /2 -5 *3 +7 /2 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 /2 +7 +7 /2 -5 *3 -5 *3 *3 -5 *3 -5 /2 +7 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 /2 +7 -5 *3 -5 *3 +7 /2 *3 -5 +7 /2 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 /2 +7 -5 *3 -5 *3 *3 -5 *3 -5 +7 /2 /2 +7 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 /2 +7 -5 *3 -5 *3 -5 *3 /2 +7 *3 -5 /2 +7 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 *3 -5 +7 /2 *3 -5 /2 +7 +7 /2 -5 *3 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 *3 -5 +7 /2 *3 -5 /2 +7 -5 *3 /2 +7 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 *3 -5 +7 /2 -5 *3 /2 +7 /2 +7 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 *3 -5 +7 /2 -5 *3 /2 +7 -5 *3 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 *3 -5 *3 -5 /2 +7 +7 /2 +7 /2 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 *3 -5 *3 -5 /2 +7 +7 /2 *3 -5 /2 +7 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 *3 -5 *3 -5 /2 +7 -5 *3 /2 +7 /2 +7 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 *3 -5 -5 *3 /2 +7 /2 +7 *3 -5 *3 -5 /2 +7 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 -5 *3 +7 /2 /2 +7 -5 *3 *3 -5 /2 +7 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 -5 *3 +7 /2 *3 -5 +7 /2 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 *3 -5 +7 /2 /2 +7 +7 /2 *3 -5 /2 +7 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 *3 -5 +7 /2 /2 +7 +7 /2 *3 -5 -5 *3 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 *3 -5 +7 /2 /2 +7 *3 -5 /2 +7 *3 -5 /2 +7 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 *3 -5 +7 /2 /2 +7 -5 *3 /2 +7 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 *3 -5 -5 *3 +7 /2 +7 /2 +7 /2 /2 +7 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 -5 *3 /2 +7 +7 /2 +7 /2 *3 -5 -5 *3 +7 /2 -5 *3 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 -5 *3 /2 +7 +7 /2 +7 /2 *3 -5 -5 *3 -5 *3 /2 +7 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 -5 *3 /2 +7 +7 /2 *3 -5 /2 +7 +7 /2 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 -5 *3 /2 +7 +7 /2 *3 -5 /2 +7 -5 *3 *3 -5 *3 -5 /2 +7 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 -5 *3 /2 +7 +7 /2 *3 -5 *3 -5 *3 -5 /2 +7 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 -5 *3 /2 +7 +7 /2 -5 *3 /2 +7 /2 +7 -5 *3 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 -5 *3 /2 +7 *3 -5 /2 +7 +7 /2 *3 -5 /2 +7 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 -5 *3 /2 +7 *3 -5 /2 +7 +7 /2 *3 -5 -5 *3 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 -5 *3 /2 +7 *3 -5 /2 +7 *3 -5 /2 +7 *3 -5 /2 +7 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 -5 *3 /2 +7 *3 -5 /2 +7 -5 *3 /2 +7 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 +7 /2 -5 *3 *3 -5 +7 /2 +7 /2 /2 +7 *3 -5 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 *3 -5 /2 +7 +7 /2 /2 +7 -5 *3 /2 +7 -5 *3 +7 /2 -5 *3 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 *3 -5 /2 +7 +7 /2 /2 +7 -5 *3 /2 +7 -5 *3 -5 *3 /2 +7 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 *3 -5 /2 +7 +7 /2 /2 +7 -5 *3 *3 -5 +7 /2 /2 +7 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 *3 -5 /2 +7 +7 /2 /2 +7 -5 *3 *3 -5 +7 /2 -5 *3 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 *3 -5 /2 +7 +7 /2 *3 -5 +7 /2 +7 /2 /2 +7 -5 *3 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 *3 -5 /2 +7 +7 /2 -5 *3 +7 /2 /2 +7 *3 -5 /2 +7 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 *3 -5 /2 +7 +7 /2 -5 *3 +7 /2 /2 +7 *3 -5 -5 *3 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 /2 +7 /2 +7 /2 +7 +7 /2 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 /2 +7 /2 +7 /2 +7 -5 *3 *3 -5 *3 -5 /2 +7 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 /2 +7 /2 +7 *3 -5 *3 -5 /2 +7 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 *3 -5 -5 *3 +7 /2 /2 +7 /2 +7 +7 /2 *3 -5 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 +7 /2 /2 +7 +7 /2 -5 *3 -5 *3 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 +7 /2 *3 -5 *3 -5 /2 +7 +7 /2 -5 *3 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 +7 /2 *3 -5 *3 -5 /2 +7 -5 *3 /2 +7 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 +7 /2 *3 -5 -5 *3 /2 +7 /2 +7 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 +7 /2 *3 -5 -5 *3 /2 +7 -5 *3 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 +7 /2 -5 *3 +7 /2 /2 +7 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 *3 -5 /2 +7 /2 +7 -5 *3 +7 /2 -5 *3 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 *3 -5 /2 +7 /2 +7 -5 *3 -5 *3 /2 +7 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 +7 /2 /2 +7 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 +7 /2 -5 *3 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 -5 *3 /2 +7 +7 /2 /2 +7 -5 *3 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 -5 *3 +7 /2 /2 +7 /2 +7 *3 -5 /2 +7 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 /2 +7 -5 *3 +7 /2 /2 +7 /2 +7 *3 -5 -5 *3 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 /2 +7 -5 *3 -5 *3 +7 /2 +7 /2 +7 /2 /2 +7 /2 +7 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 *3 -5 +7 /2 +7 /2 /2 +7 /2 +7 *3 -5 +7 /2 -5 *3 +7 /2 -5 *3 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 *3 -5 +7 /2 +7 /2 /2 +7 /2 +7 *3 -5 +7 /2 -5 *3 -5 *3 /2 +7 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 *3 -5 +7 /2 +7 /2 /2 +7 /2 +7 *3 -5 -5 *3 *3 -5 +7 /2 +7 /2 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 *3 -5 +7 /2 +7 /2 /2 +7 /2 +7 -5 *3 +7 /2 *3 -5 /2 +7 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 *3 -5 +7 /2 +7 /2 /2 +7 /2 +7 -5 *3 +7 /2 *3 -5 -5 *3 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 /2 +7 *3 -5 +7 /2 +7 /2 /2 +7 /2 +7 -5 *3 *3 -5 /2 +7 *3 -5 /2 +7 +7 /2 *3 -5 -5 = 2012
    2011 +7 /2 +7 *3 -5 +7 /2 +7 /2 /2 +7 /2 +7 -5 *3 -5 *3 /2 +7 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 *3 -5 +7 /2 +7 /2 *3 -5 +7 /2 /2 +7 /2 +7 /2 +7 -5 *3 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 *3 -5 +7 /2 *3 -5 /2 +7 /2 +7 +7 /2 /2 +7 *3 -5 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 -5 *3 +7 /2 /2 +7 +7 /2 *3 -5 /2 +7 +7 /2 /2 +7 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 -5 *3 +7 /2 /2 +7 +7 /2 -5 *3 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 -5 *3 +7 /2 /2 +7 -5 *3 /2 +7 /2 +7 /2 +7 /2 +7 -5 *3 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 /2 +7 -5 *3 *3 -5 /2 +7 /2 +7 /2 +7 +7 /2 /2 +7 /2 +7 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 /2 +7 -5 *3 -5 *3 /2 +7 +7 /2 /2 +7 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 *3 -5 +7 /2 /2 +7 +7 /2 /2 +7 +7 /2 /2 +7 -5 *3 +7 /2 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 *3 -5 +7 /2 /2 +7 +7 /2 /2 +7 +7 /2 /2 +7 -5 *3 -5 *3 *3 -5 *3 -5 /2 +7 /2 +7 -5 = 2012
    2011 +7 *3 -5 +7 /2 /2 +7 +7 /2 /2 +7 +7 /2 *3 -5 +7 /2 /2 +7 -5 *3 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 *3 -5 +7 /2 /2 +7 +7 /2 -5 *3 +7 /2 /2 +7 /2 +7 /2 +7 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 *3 -5 +7 /2 /2 +7 *3 -5 /2 +7 /2 +7 /2 +7 /2 +7 /2 +7 -5 *3 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 *3 -5 -5 *3 /2 +7 +7 /2 /2 +7 +7 /2 /2 +7 /2 +7 /2 +7 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 -5 *3 +7 /2 +7 /2 +7 /2 +7 /2 /2 +7 +7 /2 *3 -5 -5 *3 +7 /2 -5 *3 +7 /2 *3 -5 -5 = 2012
    2011 +7 -5 *3 +7 /2 +7 /2 +7 /2 +7 /2 /2 +7 +7 /2 *3 -5 -5 *3 -5 *3 /2 +7 -5 *3 /2 +7 -5 = 2012
    2011 +7 -5 *3 +7 /2 +7 /2 +7 /2 +7 /2 /2 +7 *3 -5 /2 +7 +7 /2 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 -5 *3 +7 /2 +7 /2 +7 /2 +7 /2 /2 +7 *3 -5 /2 +7 -5 *3 *3 -5 *3 -5 /2 +7 /2 +7 -5 = 2012
    2011 +7 -5 *3 +7 /2 +7 /2 +7 /2 +7 /2 /2 +7 *3 -5 *3 -5 *3 -5 /2 +7 +7 /2 /2 +7 *3 -5 -5 = 2012
    2011 +7 -5 *3 +7 /2 +7 /2 +7 /2 +7 /2 /2 +7 -5 *3 /2 +7 /2 +7 -5 *3 -5 *3 *3 -5 +7 /2 -5 = 2012
    2011 +7 -5 *3 +7 /2 +7 /2 +7 /2 *3 -5 /2 +7 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 -5 *3 /2 +7 -5 = 2012
    2011 +7 -5 *3 +7 /2 +7 /2 *3 -5 /2 +7 +7 /2 /2 +7 /2 +7 /2 +7 -5 *3 *3 -5 -5 *3 /2 +7 -5 = 2012

  • baohx

    目前比较确定的是有两个最优解(都是28步):
    2011 + 7 / 2 + 7 / 2 + 7 – 5 * 3 / 2 + 7 / 2 + 7 * 3 – 5 / 2 + 7 / 2 + 7 – 5 * 3 – 5 * 3 / 2 + 7 – 5 * 3 / 2 + 7 – 5 = 2012
    2011 + 7 – 5 * 3 + 7 / 2 + 7 / 2 + 7 / 2 * 3 – 5 / 2 + 7 / 2 + 7 / 2 + 7 * 3 – 5 / 2 + 7 * 3 – 5 – 5 * 3 / 2 + 7 – 5 = 2012
    其他的目前扫到的是:
    44步有3个解:
    2011 + 7 / 2 + 7 / 2 + 7 – 5 * 3 / 2 + 7 / 2 + 7 * 3 – 5 / 2 + 7 / 2 + 7 / 2 + 7 – 5 * 3 / 2 + 7 / 2 + 7 / 2 + 7 * 3 – 5 – 5 * 3 – 5 * 3 – 5 * 3 / 2 + 7 * 3 – 5 / 2 + 7 / 2 + 7 – 5 = 2012
    2011 + 7 / 2 + 7 / 2 + 7 * 3 – 5 / 2 + 7 * 3 – 5 / 2 + 7 / 2 + 7 / 2 + 7 – 5 * 3 / 2 + 7 / 2 + 7 / 2 + 7 / 2 + 7 – 5 * 3 / 2 + 7 * 3 – 5 – 5 * 3 – 5 * 3 / 2 + 7 – 5 * 3 / 2 + 7 – 5 = 2012
    2011 + 7 / 2 + 7 / 2 + 7 * 3 – 5 / 2 + 7 * 3 – 5 / 2 + 7 / 2 + 7 / 2 + 7 – 5 * 3 / 2 + 7 / 2 + 7 / 2 + 7 / 2 + 7 * 3 – 5 – 5 * 3 – 5 * 3 / 2 + 7 / 2 + 7 * 3 – 5 – 5 * 3 / 2 + 7 – 5 = 2012
    50步有一个解:
    2011 + 7 / 2 + 7 / 2 + 7 – 5 * 3 / 2 + 7 / 2 + 7 * 3 – 5 / 2 + 7 / 2 + 7 / 2 + 7 – 5 * 3 / 2 + 7 / 2 + 7 / 2 + 7 / 2 + 7 / 2 + 7 – 5 * 3 – 5 * 3 / 2 + 7 * 3 – 5 – 5 * 3 – 5 * 3 / 2 + 7 – 5 * 3 / 2 + 7 – 5 = 2012
    52步有一个解:
    2011 + 7 / 2 + 7 / 2 + 7 – 5 * 3 / 2 + 7 / 2 + 7 * 3 – 5 / 2 + 7 / 2 + 7 / 2 + 7 – 5 * 3 / 2 + 7 / 2 + 7 / 2 + 7 / 2 + 7 / 2 + 7 / 2 + 7 * 3 – 5 / 2 + 7 * 3 – 5 * 3 – 5 – 5 * 3 – 5 * 3 / 2 + 7 – 5 * 3 / 2 + 7 – 5 = 2012
    总体来说用递归比遍历快,深度遍历比广度遍历快。

  • Zealot

    20步的解 (代码 https://gist.github.com/1891936)

    Total step: 21, path below (reversed):
    step 21, year 2012, at 2
    step 20, year 2017, at 1
    step 19, year 2010, at 0
    step 18, year 2003, at 1
    step 17, year 1996, at 0
    step 16, year 1989, at 1
    step 15, year 663, at 2
    step 14, year 221, at 1
    step 13, year 214, at 0
    step 12, year 207, at 1
    step 11, year 69, at 2
    step 10, year 74, at 1
    step 9, year 67, at 0
    step 8, year 134, at 1
    step 7, year 127, at 0
    step 6, year 254, at 1
    step 5, year 508, at 0
    step 4, year 1016, at 1
    step 3, year 1009, at 0
    step 2, year 2018, at 1
    step 1, year 2011, at 0 (start position)

    real 0m0.005s
    user 0m0.000s
    sys 0m0.004s

  • Zealot

    竟然不能回退 看来要改代码

  • 混沌

    2011/2的话这样是算1005还是1005.5

  • 混沌

    #include
    struct q{
    long long n,x;
    char c[200];
    }h[100100];
    int l;
    int f(int n)
    {
    if (h[n].n * 3==2012)
    {
    printf(“%s *3”,h[n].c);
    return 1;
    }
    if (h[n].n – 5==2012)
    {
    printf(“%s -5″,h[n].c);
    return 1;
    }
    if (h[n].x!=1 && h[n].n&1)
    {
    if (++l == 100000) l=0;
    h[l].n=(h[n].n+7)>>1;
    h[l].x=2;
    sprintf(h[l].c,”%s +7 /2″,h[n].c);
    }
    if (h[n].x!=2 && !(h[n].n&1))
    {
    if (++l == 100000) l=0;
    h[l].n=(h[n].n>>1)+7;
    h[l].x=1;
    sprintf(h[l].c,”%s /2 +7″,h[n].c);
    }
    if (h[n].x!=3)
    {
    if (++l == 100000) l=0;
    h[l].n=(h[n].n * 3)-5;
    h[l].x=4;
    sprintf(h[l].c,”%s *3 -5″,h[n].c);
    }
    if (h[n].x!=4)
    {
    if (++l == 100000) l=0;
    h[l].n=(h[n].n -5)*3;
    h[l].x=3;
    sprintf(h[l].c,”%s -5 *3”,h[n].c);
    }
    return 0;
    }
    int main()
    {
    freopen(“out.txt”,”w”,stdout);
    l=0;
    h[0].n=2011+7;
    h[0].x=1;
    printf(“2011 “);
    for (int i=0;;i++)
    {
    if (i==100000) i=0;
    if (f(i)) break;
    }
    printf(” = 2012n”);
    return 0;
    }

    //out.txt:2011 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 *3 -5 /2 +7 /2 +7 -5 *3 +7 /2 -5 *3 +7 /2 *3 -5 -5 = 2012

  • 混沌

    囧 走最后一步的时候忘记考虑不能回退。。我说怎么错的。。。

    #include
    struct q{
    long long n,x;
    char c[200];
    }h[100100];
    int l;
    int f(int n)
    {
    if (h[n].n * 3==2012 && h[n].x!=3)
    {
    printf(“%s *3”,h[n].c);
    return 1;
    }
    if (h[n].n – 5==2012 && h[n].x!=4)
    {
    printf(“%s -5″,h[n].c);
    return 1;
    }
    if (h[n].x!=1 && h[n].n&1)
    {
    if (++l == 100000) l=0;
    h[l].n=(h[n].n+7)>>1;
    h[l].x=2;
    sprintf(h[l].c,”%s +7 /2″,h[n].c);
    }
    if (h[n].x!=2 && !(h[n].n&1))
    {
    if (++l == 100000) l=0;
    h[l].n=(h[n].n>>1)+7;
    h[l].x=1;
    sprintf(h[l].c,”%s /2 +7″,h[n].c);
    }
    if (h[n].x!=3)
    {
    if (++l == 100000) l=0;
    h[l].n=(h[n].n * 3)-5;
    h[l].x=4;
    sprintf(h[l].c,”%s *3 -5″,h[n].c);
    }
    if (h[n].x!=4)
    {
    if (++l == 100000) l=0;
    h[l].n=(h[n].n -5)*3;
    h[l].x=3;
    sprintf(h[l].c,”%s -5 *3”,h[n].c);
    }
    return 0;
    }
    int main()
    {
    freopen(“out.txt”,”w”,stdout);
    l=0;
    h[0].n=2011+7;
    h[0].x=1;
    printf(“2011 “);
    for (int i=0;;i++)
    {
    if (i==100000) i=0;
    if (f(i)) break;
    }
    printf(” = 2012n”);
    return 0;
    }
    //out.txt:2011 /2 +7 /2 +7 -5 *3 /2 +7 /2 +7 *3 -5 /2 +7 /2 +7 -5 *3 -5 *3 /2 +7 -5 *3 /2 +7 -5 = 2012

  • zaitian

    好像我的解跟大家不一样啊,也是28步
    2011 +7 /2 +7 /2 +7 *3 -5 /2 +7 *3 -5 /2 +7 *3 -5 *3 -5 /2 +7 /2 +7 /2 +7 /2 +7 *3 -5 +7 = 2012
    python递归一秒不到。

  • minglingmaster

    @75楼:最后一步+7能从右边出来么

  • 呵呵

    明显的 几步就可以搞定
    2011+7-5×3÷2+7-5×3÷2+7-5=2012

  • 勿扰

    有笔算的方法吗?

  • Ray

    Python代码也可以帖. BFS, 1秒内出解。
    |# +7 *3
    |# / /
    |#
    |# 2011 -> v0 v1 v2 -> 2012
    |#
    |# / /
    |# /2 -5
    |#
    |# state: (v, from, num)
    |
    |ef1 = lambda x:x+7
    |ef2 = lambda x:x/2 if x%2==0 else None
    |ef3 = lambda x:x*3
    |ef4 = lambda x:x-5
    |
    |adjs = [[(1, ef1, ‘+7’), (1, ef2, ‘/2’)],
    | [(0, ef1, ‘+7’), (0, ef2, ‘/2’), (2, ef3, ‘*3’), (2, ef4, ‘-5’)],
    | [(1, ef3, ‘*3’), (1, ef4, ‘-5’)]]
    |
    |def bfs():
    | start = 2011
    | dest = 2012
    | state0 = (0, None, start, None)
    | que = [state0]
    | head = 0
    | vis = {state0[:-1]}
    | found = False
    | while head < len(que) and not found:
    | s1 = v1, f1, num1, prev = que[head]
    | head += 1 # pop queue
    | for v2, f2, name2 in adjs[v1]:
    | if f2 != f1:
    | s2 = v2, f2, f2(num1), s1
    | if s2[2] != None and s2[:-1] not in vis:
    | vis.add(s2[:-1])
    | que.append(s2)
    | if v2 == 2 and s2[2] == dest:
    | found = True
    | break
    | assert found
    | # track the solution path
    | path = []
    | s2 = que[-1]
    | while 1:
    | v2, f2, num2, s1 = s2
    | if s1 is None: break
    | name2 = (name2 for v2p, f2p, name2 in adjs[s1[0]] if v2 == v2p and f2 == f2p).next()
    | path.append((name2, f2))
    | s2 = s1
    | # print the solution
    | num = start
    | print start,
    | for name, opr in reversed(path):
    | num = opr(num)
    | print ‘%s= %d’ %(name, num),
    | print ‘(%d steps, searched %d nodes)’ % (len(path), len(que))
    |bfs()

  • Ray

    为什么要将空格压缩掉?!
    ef1 = lambda x:x+7
    ef2 = lambda x:x/2 if x%2==0 else None
    ef3 = lambda x:x*3
    ef4 = lambda x:x-5

    adjs = [[(1, ef1, ‘+7’), (1, ef2, ‘/2’)],
    ___|___|[(0, ef1, ‘+7’), (0, ef2, ‘/2’), (2, ef3, ‘*3’), (2, ef4, ‘-5’)],
    ___|___|[(1, ef3, ‘*3’), (1, ef4, ‘-5’)]]

    def bfs():
    ___|start = 2011
    ___|dest = 2012
    ___|state0 = (0, None, start, None)
    ___|que = [state0]
    ___|head = 0
    ___|vis = {state0[:-1]}
    ___|found = False
    ___|while head < len(que) and not found:
    ___|___|s1 = v1, f1, num1, prev = que[head]
    ___|___|head += 1 # pop queue
    ___|___|for v2, f2, name2 in adjs[v1]:
    ___|___|___|if f2 != f1:
    ___|___|___|___|s2 = v2, f2, f2(num1), s1
    ___|___|___|___|if s2[2] != None and s2[:-1] not in vis:
    ___|___|___|___|___|vis.add(s2[:-1])
    ___|___|___|___|___|que.append(s2)
    ___|___|___|___|___|if v2 == 2 and s2[2] == dest:
    ___|___|___|___|___|___|found = True
    ___|___|___|___|___|___|break
    ___|assert found
    ___|# track the solution path
    ___|path = []
    ___|s2 = que[-1]
    ___|while 1:
    ___|___|v2, f2, num2, s1 = s2
    ___|___|if s1 is None: break
    ___|___|name2 = (name2 for v2p, f2p, name2 in adjs[s1[0]] if v2 == v2p and f2 == f2p).next()
    ___|___|path.append((name2, f2))
    ___|___|s2 = s1
    ___|# print the solution
    ___|num = start
    ___|print start,
    ___|for name, opr in reversed(path):
    ___|___|num = opr(num)
    ___|___|print ‘%s= %d’ %(name, num),
    ___|print ‘(%d steps, searched %d nodes)’ % (len(path), len(que))
    bfs()

  • cervelo

    这个难度太大了!

  • Hua Shao

    def dump(l):
    ____solution = []
    ____i = l
    ____paths = [“-5*3″,”+7/2″,”/2+7″,”*3-5”]
    ____while i>0:
    ________solution.append(paths[i%4])
    ________i = int((i-1)/4)
    ____print(“2011+7″,end=””)
    ____for i in range(len(solution)-1, -1, -1):
    ________print(solution[i], end=””)
    ____print(“-5 = 2012 (%d steps, searched %d nodes)”%(len(solution)*2+2, l))

    def search(onlyone = True):
    ____p1 = lambda x,i:(x+7)/2 if x%2==1 and i%4 != 2 and i!=0 else None
    ____p2 = lambda x,i:x/2+7 if x%2==0 and i%4 != 1 else None
    ____p3 = lambda x,i:x*3-5 if i%4 != 0 else None
    ____p4 = lambda x,i:(x-5)*3 if i%4 != 3 else None
    ____cursor = 0
    _____maze = [(2018,0)] # (node value, node idx)
    ____while 1:
    ________node,idx = _maze[cursor]
    ________cursor += 1
    ________children = [p1(node,idx),p2(node,idx),p3(node,idx),p4(node,idx)]
    ________for i in range(4):
    ____________if children[i]:
    _________________maze.append((children[i], idx*4+i+1))
    ________________if i!=2 and children[i] == 2017:
    ____________________dump3(idx*4+i+1)
    ____________________if onlyone:
    ________________________return

    search()

发表评论




Enter Captcha Here :