批处理之家 - Powered by Discuz! Board

标题: [思考题]0-9在这10句话中出现的次数 [打印本页]

作者: 523066680 时间: 2015-6-5 17:21 标题: [思考题]0-9在这10句话中出现的次数

本帖最后由 523066680 于 2015-6-5 18:39 编辑

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

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

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

语言不限

作者: 523066680 时间: 2015-6-5 20:46

本帖最后由 523066680 于 2015-6-5 20:49 编辑

回复 2# Bella

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

作者: yangfengoo 时间: 2015-6-5 21:36

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

作者: 523066680 时间: 2015-6-5 21:50

本帖最后由 523066680 于 2015-6-5 22:16 编辑

回复 4# yangfengoo

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

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

作者: bailong360 时间: 2015-6-5 22:22

本帖最后由 bailong360 于 2015-6-7 19:06 编辑

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

作者: 523066680 时间: 2015-6-5 22:44

本帖最后由 523066680 于 2015-6-5 22:45 编辑

回复 6# bailong360

恩但是希望其他看官不要被我的评论影响了，貌似是有快速解法的。
我保留了一个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

<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>
复制代码

分析:

频率为:
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

#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))
复制代码

代码毫无技术含量可言,主要工作都是在草稿纸上完成的=_=
其实就是笔算把范围缩小,然后再穷举(汗)

输出:
#(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
复制代码

作者: 523066680 时间: 2015-6-8 11:05

本帖最后由 523066680 于 2015-6-9 19:51 编辑

参考8楼的理论，对暴力解法进行了优化，10层的时候需要3-5秒
语言：Perl

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";
}
复制代码

代码备注：
test 函数核对结果，deep 函数递进排列，当前层的元素取值范围是 1 到 $max
优化方法是逐步缩小范围，例如当一个数字已经出现5次，则下一个数字出现的次数不会超过理论总次数-5次，
故有： deep( ($max-$i), @_, $i);

将 $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

本帖最后由 tigerpower 于 2015-6-11 23:50 编辑

如果换成十六进制，这题怎么解？

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

作者: aa77dd@163.com 时间: 2015-6-12 00:57

本帖最后由 aa77dd@163.com 于 2015-6-12 07:21 编辑

回复 11# tigerpower

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

仍采用 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

当然以上只是猜测而已, 对其他进制是否成立未作验证, 也无任何推理.

<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>
复制代码

作者: aa77dd@163.com 时间: 2015-6-12 01:50

回复 10# 523066680

觉得这个题目使用的数字应该以进制来限制, 比如 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 标题: 我先把其他地方看到的解法发上来（作者不在论坛）

本帖最后由 523066680 于 2015-6-12 10:50 编辑

js

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]);
}
复制代码

运行结果：
1 11 2 1 1 1 1 1 1 1

也是js 保存为 htm

<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>
复制代码

运行结果
Array [ 1, 7, 3, 2, 1, 1, 1, 2, 1, 1 ]
"time: 0.006"

作者: 523066680 时间: 2015-6-12 12:53

本帖最后由 523066680 于 2015-6-12 18:41 编辑

上面两段代码都是职业程序员解的。
啃了半晌发现都是：假设-> 计算对比 -> 调整答案的方法逐步逼近
区别好像是广度优先和深度优先，效率好高，可惜各算出一种结果就结束了

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 ]
复制代码

               这种算法一开始假定结果是：[ 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 ]

=

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"
复制代码

这种是动态的进行逐个数字的统计：
一开始假设答案是：[ 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 ]
按上面的方式重新统计：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 ]

作者: aa77dd@163.com 时间: 2015-6-12 19:45

本帖最后由 aa77dd@163.com 于 2015-6-12 20:42 编辑

回复 15# 523066680

这些算法能不能遍历?

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

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

作者: 依山居 时间: 2015-11-26 17:10

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

欢迎光临批处理之家 (http://bbs.bathome.net/)