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

523066680

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

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

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

语言不限

523066680

回复 2# Bella


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

523066680

回复 4# yangfengoo

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

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

523066680

回复 6# bailong360


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

523066680

参考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

523066680

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

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

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 ]