批处理之家's Archiver

523066680 发表于 2015-6-5 17:21

[思考题]0-9在这10句话中出现的次数

[i=s] 本帖最后由 523066680 于 2015-6-5 18:39 编辑 [/i]

十句话指的就是题目本身,你所填入的每一个数都会影响命题本身

0在这十句话中出现的次数是______。
1在这十句话中出现的次数是______。
2在这十句话中出现的次数是______。
3在这十句话中出现的次数是______。
4在这十句话中出现的次数是______。
5在这十句话中出现的次数是______。
6在这十句话中出现的次数是______。
7在这十句话中出现的次数是______。
8在这十句话中出现的次数是______。
9在这十句话中出现的次数是______。

(其实我发过,不过没什么回应,有一个回帖是暴力解法
(备注:填入的数值并不限制于10以内

语言不限

523066680 发表于 2015-6-5 20:46

[i=s] 本帖最后由 523066680 于 2015-6-5 20:49 编辑 [/i]

[b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=169684&ptid=35997]2#[/url] [i]Bella[/i] [/b]


    用黄色或者白色字体好不好嘛

yangfengoo 发表于 2015-6-5 21:36

这个题代码怎么写完全没思路。
只能初步推理,1应该出现最多;3后面的数字出现次数都应该很小。

523066680 发表于 2015-6-5 21:50

[i=s] 本帖最后由 523066680 于 2015-6-5 22:16 编辑 [/i]

[b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=169687&ptid=35997]4#[/url] [i]yangfengoo[/i] [/b]

模拟人为解题的过程,假设、判断、和排除,据说是分为深度优先和广度优先。

如果是暴力解则消耗巨大,比如设定每个空位都填1,轮流+1或者不加,
(或者直接假定答案数值的范围,像排列组合那样搞),对每个情况判断是否符合。

bailong360 发表于 2015-6-5 22:22

[i=s] 本帖最后由 bailong360 于 2015-6-7 19:06 编辑 [/i]

mark一下
数字可以大于10难度一下子就上去了

523066680 发表于 2015-6-5 22:44

[i=s] 本帖最后由 523066680 于 2015-6-5 22:45 编辑 [/i]

[b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=169690&ptid=35997]6#[/url] [i]bailong360[/i] [/b]


    恩但是希望其他看官不要被我的评论影响了,貌似是有快速解法的。
    我保留了一个python,一个js的代码,都是别人写的,各算出不同的结果(但是不能同时给出两个结果),速度较快,一直没去看思路

aa77dd@163.com 发表于 2015-6-6 19:19

以下代码 在 Windows 7 64-bit, 处理器: Core i3-3110M CPU @ 2.40GHz (4 CPUs), ~2.4GHz
chrome 42.0 环境运行, 耗时 < 100ms.

得结果
1,11,2,1,1,1,1,1,1,1
1,7,3,2,1,1,1,2,1,1[code]
<html>
    <body>
        结果<br>
        <textarea id="result" style="height: 100px; width: 300px;"></textarea><br/>
        运行时间从 <span id="start"></span>--<span id="end"></span><br>
        <button type="button" onclick="run();">运行</button>
    </body>
</html>
<script>
var g = new Array(10);
var f = new Array(10);
function run() {
  time_shot('start');
  init();
  f_search(9, 30);
  time_shot('end');
}

function init() {
  for (var i = 0; i <= 9; i++) {
    g[i] = 1;
  }
}

function f_search(ind, fsum_rem) {
  var t = ind - 2 >> 31;
  var fi_up = t & 21 | ~t & Math.floor((19 + ind) / (t | (ind - 1)));

  if (ind == 0 && fi_up > 3) {
    fi_up = 3;
  }

  t = fsum_rem - ind;
  var t1 = t - fi_up >> 31;
  fi_up = (t1 & t) | (~t1 & fi_up);

  if (ind < 0) {
    var test = true;
    for (var i = 0; i <= 9; i++) {
      if (g[i] != f[i]) {
        test = false;
        break;
      }
    }
    if (test) {
      var old = document.getElementById('result').innerHTML;
      document.getElementById('result').innerHTML = old + f.join() + '\n';
    }

    return;
  } else {
    var next = ind - 1;

    for (var i = g[ind]; i <= fi_up; i++) {
      f[ind] = i;

      fsum_rem -= f[ind];

      var a = Math.floor(f[ind] / 10);
      var b = f[ind] % 10;

      g[a] += (a == 0 ? 0 : 1);
      g[b] += 1;

      f_search(next, fsum_rem);

      g[a] -= (a == 0 ? 0 : 1);
      g[b] -= 1;

      fsum_rem += f[ind];
    }
  }
}

function time_shot(id) {
  var t_stamp = new Date();
  document.getElementById(id).innerHTML = t_stamp.getHours() + ':' + t_stamp.getMinutes() + ':' + t_stamp.getSeconds() + ':' + t_stamp.getMilliseconds();
}
</script>
[/code]分析:

频率为:
f0,f1,f2,f3,f4,f5,f6,f7,f8,f9
最大频率:
fmax = max(f0,f1,f2,f3,f4,f5,f6,f7,f8,f9)
频率总和:
fsum = f0+f1+f2+f3+f4+f5+f6+f7+f8+f9

假定 fmax 为 3 位数, 则 fsum <= 3 * 10 + 10 = 40, 而最小的 3 位数是 100, fsum > fmax >= 100, 所以无解;
假定 fmax 为 4 位数, 则 fsum <= 4 * 10 + 10 = 50, 而最小的 4 位数是 1000, fsum > fmax >= 1000, 所以无解;
...
fmax 的位数每增长 1 位, fsum 的上限只增长 +10, 而下限是以 10 倍增长, 所以断定 fmax 的位数不超过 2 位:
假定 fmax 为 2 位数, 则 fsum <= 2 * 10 + 10 = 30, 而最小的 2 位数是 10, fsum > fmax >= 10, 所以 fsum 属于 (10, 30];

任意一个频率 fi 有:
1 <= fi <= 30 - 9 = 21

所有 fi 中至多 2 个两位数

数字 i 在题面右侧 出现的总频率: (任意 i 题面左侧都已出现 1 次)
fi - 1
题面右侧 至少有 10 - (fi - 1) 行没有出现 i, 这些行右侧位置上频率数值总和至少是 10 - (fi - 1)
这些 i 对 fsum 的贡献至少为:
(fi - 1) * i

对数字 i , 其频率有上限:
(fi - 1) * i <= 30 - (10 - (fi - 1))
fi * i - i <= 20 + (fi - 1)
fi * i - i <= 19 + fi
fi * (i - 1) <= 19 + i
fi <= (19 + i) / (i - 1)

搜索算法以 f9,f8,f7,....f1,f0 的次序逐个设定,
在过程中, 所有尚未设定的 fi 的总和上限为:
fsum_rem

bailong360 发表于 2015-6-7 19:06

[code]#lang racket
(define (check guess)
  (define real (make-vector 10 1))
  (define mistake 0)
  (for-each (lambda (x)
              (for-each (lambda (y)
                          (vector-set! real y (+ 1 (vector-ref real y))))
                        (integer->list x)))
            (vector->list guess))
  (for-each (lambda (x)
              (when (eqv? x #f)
                (set! mistake 1)))
            (map = (vector->list guess) (vector->list real)))
  (when (= 0 mistake)
    (display guess)
    (newline)))

(define (integer->list num)
  (define index '(0 1 2 3 4 5 6 7 8 9))
  (define str '())
  (define (cc)
    (set! str (cons (list-ref index (modulo num 10)) str))
    (set! num (floor (/ num 10)))
    (if (= 0 num)
        str
        (cc)))
  (cc))

(define (main)
  (define guess (make-vector 10 1))
  (define max '((1 2) (1 2 3 4 5 6 7 8 9 10 11) (1 2 3) (1 2) (1 2) (1 2) (1 2) (1 2)))
  (define (loop index)
    (for-each (lambda (x)
                (vector-set! guess index x)
                (if (= index 7)
                    (check guess)
                    (loop (+ index 1))))
              (list-ref max index)))
  (loop 0))

(time (main))[/code]代码毫无技术含量可言,主要工作都是在草稿纸上完成的=_=
其实就是笔算把范围缩小,然后再穷举(汗)[code]
输出:
#(1 7 3 2 1 1 1 2 1 1)
#(1 11 2 1 1 1 1 1 1 1)
cpu time: 62 real time: 63 gc time: 0[/code]

523066680 发表于 2015-6-8 11:05

[i=s] 本帖最后由 523066680 于 2015-6-9 19:51 编辑 [/i]

[size=3]参考8楼的理论,对暴力解法进行了优化,10层的时候需要3-5秒
语言:Perl[/size][code]
use v5.16;

my $max = 21;                 #理论次数合计
my $maxIndex = 9;             #数组最大下标

deep($max);
<STDIN>;

sub deep {
        my $max = shift;
        if ($#_ < $maxIndex) {
                for my $i ( 1..$max ) {
                        deep( ($max-$i), @_, $i);
                }
        }  else {
                TestandPrint( @_ );
        }
}

sub TestandPrint {
        my $str = join(",", @_);
        my $find;
        for my $i (0 .. $maxIndex) {
                $find = $str=~s/$i/$i/g + 1;
                if ($_[$i] != $find) {
                        return -1;
                }
        }
        print $str,"\n";
}
[/code][size=3][color=Navy]代码备注:
test 函数核对结果,deep 函数递进排列,当前层的元素取值范围是 1 到 $max
优化方法是逐步缩小范围,例如当一个数字已经出现5次,则下一个数字出现的次数不会超过理论总次数-5次,
故有: deep( ($max-$i), @_, $i);
[/color][/size]
将 $maxIndex 改成其他数值(0-8),可以查看其他范围的结果:

9句话(0-8):
1,6,3,2,1,1,2,1,1
1,9,1,1,1,1,1,1,1
1,11,1,1,1,1,1,1,1

10句话(0-9):
1,7,3,2,1,1,1,2,1,1
1,11,2,1,1,1,1,1,1,1

tigerpower 发表于 2015-6-11 23:31

[i=s] 本帖最后由 tigerpower 于 2015-6-11 23:50 编辑 [/i]

如果换成十六进制,这题怎么解?

十六句话指的就是题目本身,你所填入的每一个数都会影响命题本身
0在这十六句话中出现的次数是______;
1在这十六句话中出现的次数是______;
2在这十六句话中出现的次数是______;
3在这十六句话中出现的次数是______;
4在这十六句话中出现的次数是______;
5在这十六句话中出现的次数是______;
6在这十六句话中出现的次数是______;
7在这十六句话中出现的次数是______;
8在这十六句话中出现的次数是______;
9在这十六句话中出现的次数是______;
A在这十六句话中出现的次数是______;
B在这十六句话中出现的次数是______;
C在这十六句话中出现的次数是______;
D在这十六句话中出现的次数是______;
E在这十六句话中出现的次数是______;
F在这十六句话中出现的次数是______。

aa77dd@163.com 发表于 2015-6-12 00:57

[i=s] 本帖最后由 aa77dd@163.com 于 2015-6-12 07:21 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=169980&ptid=35997]11#[/url] [i]tigerpower[/i] [/b]

分析方法和解题思路可以完全和 十进制时一样, 只是问题在计算上的规模更大了, 如果没有更高效的算法, 耗时会指数规律增长

仍采用 8 楼的分析方法和求解算法, 耗时从 < 100ms 增长到 > 3 min
结果(注意数值是十六进制意义上的了)
1,11,2,1,1,1,1,1,1,1,1,1,1,1,1,1
1,D,3,2,1,1,1,1,1,1,1,1,1,2,1,1

感觉可以做一个猜想, 这两个解似乎都有一个通项公式:
以 R0, R1, R2, ... 表示各个数字出现的频率:

A. 进制基数 >= 3 时, 下面解成立:
1,(进制基数+1),2,1,1,1,1,1,1,1,1,1,1,1,1,1
R1 = 进制基数+1
R2 = 2
其他频率都为 1

B. 进制基数 >= 7 时, 下面解成立:
1,(进制基数-3),3,2,1,1,1,1,1,1,1,1,1,2,1,1
R1 = 进制基数-3
R2 = 3
R3 = 2
R(进制基数-3) = 2
其他频率都为 1

当然以上只是猜测而已, 对其他进制是否成立未作验证, 也无任何推理.[code]<html>
<body>
  结果
  <br>
  <textarea id="result" style="height: 100px; width: 300px;"></textarea>
  <br /> 运行时间从
  <span id="start"></span>--
  <span id="end"></span>
  <br> cnt=
  <span id="cnt"></span>
  <br>
  <button type="button" onclick="run();">运行</button>
</body>
</html>
<script>
  var g = new Array(0x10);
  var R = new Array(0x10);
  var H = new Array(0x10);
  var cnt = 0;
  function run() {
    time_shot('start');
    init();
    f_search(0xF, 0x30);
    time_shot('end');
    document.getElementById('cnt').innerHTML = cnt;
  }
  function init() {
    for ( var i = 0; i <= 0xF; i++) {
      g[i] = 1;
    }
    cnt = 0;
  }
  function f_search(ind, fsum_rem) {
    if (ind < 0) {
      cnt++;
      var test = true;
      for ( var i = 0; i <= 0xF; i++) {
        if (g[i] != R[i]) {
          test = false;
          break;
        }
      }
      if (test) {
        var old = document.getElementById('result').value;
        for ( var i = 0; i <= 0xF; i++) {
          H[i] = R[i].toString(16).toUpperCase();
        }
        document.getElementById('result').value = old + H.join() + '\n';
      }
      return;
    } else {
      var t = ind - 2 >> 31;
      var fi_up = t & 0x21 | ~t
          & Math.floor((0x1F + ind) / (t | (ind - 1)));
      if (ind == 0 && fi_up > 3) {
        fi_up = 3;
      }
      t = fsum_rem - ind;
      var t1 = t - fi_up >> 31;
      fi_up = (t1 & t) | (~t1 & fi_up);
      for ( var i = g[ind]; i <= fi_up; i++) {
        R[ind] = i;
        var a = Math.floor(R[ind] / 0x10);
        var b = R[ind] % 0x10;
        var c = a == 0 ? 0 : 1;
        g[a] += c;
        g[b] += 1;
        f_search(ind - 1, fsum_rem - R[ind]);
        g[a] -= c;
        g[b] -= 1;
      }
    }
  }
  function time_shot(id) {
    var t_stamp = new Date();
    document.getElementById(id).innerHTML = t_stamp.getHours() + ':'
        + t_stamp.getMinutes() + ':' + t_stamp.getSeconds() + ':'
        + t_stamp.getMilliseconds();
  }
</script>[/code]

aa77dd@163.com 发表于 2015-6-12 01:50

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=169773&ptid=35997]10#[/url] [i]523066680[/i] [/b]

觉得这个题目使用的数字应该以进制来限制, 比如 9 句话时用 9 进制, 只能出现 0 -- 8 这些数字

那么, 下面两个结果在 9 进制意义上应该是不成立的
1,9,1,1,1,1,1,1,1
1,11,1,1,1,1,1,1,1

523066680 发表于 2015-6-12 10:29

我先把其他地方看到的解法发上来(作者不在论坛)

[i=s] 本帖最后由 523066680 于 2015-6-12 10:50 编辑 [/i]

js[code]var arr = [1,1,1,1,1,1,1,1,1,1];

function arrays_equal(a,b)
{
        return !(a<b || b<a);
}

for(;;)
{
        var tmparr = [0,0,0,0,0,0,0,0,0,0];
        for(var i = 0; i < 10; i++)
        {
                tmparr[i]++;
                var str = arr[i].toString(10);
                var slen = str.length;
                for(var j = 0; j < slen; j++)
                {
                        var ch = str.charAt(j);
                        var cint = parseInt(ch, 10);
                        tmparr[cint]++;
                }
        }
        if(arrays_equal(arr, tmparr))
                break;
        arr = tmparr;
}

for(var i = 0; i < 10; i++)
{
        console.log(i + " : " + arr[i]);
}[/code]运行结果:
1 11 2 1 1 1 1 1 1 1

也是js 保存为 htm[code]<script>
var starttime = Date.now();

var keymaps = [0,1,2,3,4,5,6,7,8,9];
var content = [0,0,0,0,0,0,0,0,0,0];

for(;;)
{
        var bdiff = false;
        for(var k in keymaps)
        {
                var val = 1;
                var key = keymaps[k].toString(10);
                for(var i in content)
                {
                        var str = content[i].toString(10);
                        for(var j in str)
                        {
                                if(str[j] == key)
                                {
                                        val++;
                                }
                        }
                }
                if(content[k] != val)
                {
                        bdiff = true;
                        content[k] = val;
                }
        }
        console.log(content);
        if(!bdiff)
                break;
}

console.log("time: " + (Date.now() - starttime) / 1000);
</script>[/code]运行结果
Array [ 1, 7, 3, 2, 1, 1, 1, 2, 1, 1 ]
"time: 0.006"

523066680 发表于 2015-6-12 12:53

[i=s] 本帖最后由 523066680 于 2015-6-12 18:41 编辑 [/i]

上面两段代码都是职业程序员解的。
啃了半晌发现都是:假设-> 计算对比 -> 调整答案 的方法逐步逼近
区别好像是广度优先 和 深度优先,效率好高,可惜各算出一种结果就结束了[code]Array [ 1, 11, 1, 1, 1, 1, 1, 1, 1, 1 ]
Array [ 1, 12, 1, 1, 1, 1, 1, 1, 1, 1 ]
Array [ 1, 11, 2, 1, 1, 1, 1, 1, 1, 1 ]
[/code][font=宋体]                 这种算法一开始假定结果是:[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
加上命题中的1一共11个1,其余数字各1,得到:[ 1, 11, 1, 1, 1, 1, 1, 1, 1, 1 ]
             重新统计,一共12个1,其余各1:[ 1, 12, 1, 1, 1, 1, 1, 1, 1, 1 ]
             重新统计,11个1,2个2,得   :[ 1, 11, 2, 1, 1, 1, 1, 1, 1, 1 ]
[/font]
=[code]Array [ 11, 3, 1, 2, 1, 1, 1, 1, 1, 1 ]
Array [ 1, 9, 2, 1, 1, 1, 1, 1, 1, 2 ]
Array [ 1, 8, 3, 2, 1, 1, 1, 1, 2, 1 ]
Array [ 1, 7, 3, 2, 1, 1, 1, 2, 1, 1 ]
Array [ 1, 7, 3, 2, 1, 1, 1, 2, 1, 1 ]
"time: 0.008"
[/code][font=宋体]这种是动态的进行逐个数字的统计:
                                  一开始假设 答案是:[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]  
有11个0,将11计入内,3个1,1个2,2个3,其余各1 得到:[ 11, 3, 1, 2, 1, 1, 1, 1, 1, 1 ]
   按上面的方式[/font][font=宋体][font=宋体]重新[/font]统计:1个0,9个1,2个2,... 2个9:[ 1, 9, 2, 1, 1, 1, 1, 1, 1, 2 ]

重复以上步骤N次后得到 [ 1, 7, 3, 2, 1, 1, 1, 2, 1, 1 ][/font]

aa77dd@163.com 发表于 2015-6-12 19:45

[i=s] 本帖最后由 aa77dd@163.com 于 2015-6-12 20:42 编辑 [/i]

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=170001&ptid=35997]15#[/url] [i]523066680[/i] [/b]

这些算法能不能遍历?

我初步理解是一种趋近算法, 但不知道能不能保证 收敛, 尽管两个算法事实上都得到了了一个解.

趋近的算法不能 收敛 时, 一种可能会未能遍历问题所有可能待测状态而跳出, 还有一种可能是无限循环, 但不能遍历所有可能待测状态也不能得到存在的解.

依山居 发表于 2015-11-26 17:10

感觉我并没有看懂这道题。
不过这道题的实际应用在玩牌类上似乎很实用吧?

页: [1]

Powered by Discuz! Archiver 7.2  © 2001-2009 Comsenz Inc.