Board logo

标题: [思考题]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
  1. <html>
  2.     <body>
  3.         结果<br>
  4.         <textarea id="result" style="height: 100px; width: 300px;"></textarea><br/>
  5.         运行时间从 <span id="start"></span>--<span id="end"></span><br>
  6.         <button type="button" onclick="run();">运行</button>
  7.     </body>
  8. </html>
  9. <script>
  10. var g = new Array(10);
  11. var f = new Array(10);
  12. function run() {
  13.   time_shot('start');
  14.   init();
  15.   f_search(9, 30);
  16.   time_shot('end');
  17. }
  18. function init() {
  19.   for (var i = 0; i <= 9; i++) {
  20.     g[i] = 1;
  21.   }
  22. }
  23. function f_search(ind, fsum_rem) {
  24.   var t = ind - 2 >> 31;
  25.   var fi_up = t & 21 | ~t & Math.floor((19 + ind) / (t | (ind - 1)));
  26.   if (ind == 0 && fi_up > 3) {
  27.     fi_up = 3;
  28.   }
  29.   t = fsum_rem - ind;
  30.   var t1 = t - fi_up >> 31;
  31.   fi_up = (t1 & t) | (~t1 & fi_up);
  32.   if (ind < 0) {
  33.     var test = true;
  34.     for (var i = 0; i <= 9; i++) {
  35.       if (g[i] != f[i]) {
  36.         test = false;
  37.         break;
  38.       }
  39.     }
  40.     if (test) {
  41.       var old = document.getElementById('result').innerHTML;
  42.       document.getElementById('result').innerHTML = old + f.join() + '\n';
  43.     }
  44.     return;
  45.   } else {
  46.     var next = ind - 1;
  47.     for (var i = g[ind]; i <= fi_up; i++) {
  48.       f[ind] = i;
  49.       fsum_rem -= f[ind];
  50.       var a = Math.floor(f[ind] / 10);
  51.       var b = f[ind] % 10;
  52.       g[a] += (a == 0 ? 0 : 1);
  53.       g[b] += 1;
  54.       f_search(next, fsum_rem);
  55.       g[a] -= (a == 0 ? 0 : 1);
  56.       g[b] -= 1;
  57.       fsum_rem += f[ind];
  58.     }
  59.   }
  60. }
  61. function time_shot(id) {
  62.   var t_stamp = new Date();
  63.   document.getElementById(id).innerHTML = t_stamp.getHours() + ':' + t_stamp.getMinutes() + ':' + t_stamp.getSeconds() + ':' + t_stamp.getMilliseconds();
  64. }
  65. </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

  1. #lang racket
  2. (define (check guess)
  3.   (define real (make-vector 10 1))
  4.   (define mistake 0)
  5.   (for-each (lambda (x)
  6.               (for-each (lambda (y)
  7.                           (vector-set! real y (+ 1 (vector-ref real y))))
  8.                         (integer->list x)))
  9.             (vector->list guess))
  10.   (for-each (lambda (x)
  11.               (when (eqv? x #f)
  12.                 (set! mistake 1)))
  13.             (map = (vector->list guess) (vector->list real)))
  14.   (when (= 0 mistake)
  15.     (display guess)
  16.     (newline)))
  17. (define (integer->list num)
  18.   (define index '(0 1 2 3 4 5 6 7 8 9))
  19.   (define str '())
  20.   (define (cc)
  21.     (set! str (cons (list-ref index (modulo num 10)) str))
  22.     (set! num (floor (/ num 10)))
  23.     (if (= 0 num)
  24.         str
  25.         (cc)))
  26.   (cc))
  27. (define (main)
  28.   (define guess (make-vector 10 1))
  29.   (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)))
  30.   (define (loop index)
  31.     (for-each (lambda (x)
  32.                 (vector-set! guess index x)
  33.                 (if (= index 7)
  34.                     (check guess)
  35.                     (loop (+ index 1))))
  36.               (list-ref max index)))
  37.   (loop 0))
  38. (time (main))
复制代码
代码毫无技术含量可言,主要工作都是在草稿纸上完成的=_=
其实就是笔算把范围缩小,然后再穷举(汗)
  1. 输出:
  2. #(1 7 3 2 1 1 1 2 1 1)
  3. #(1 11 2 1 1 1 1 1 1 1)
  4. 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
  1. use v5.16;
  2. my $max = 21;                 #理论次数合计
  3. my $maxIndex = 9;             #数组最大下标
  4. deep($max);
  5. <STDIN>;
  6. sub deep {
  7. my $max = shift;
  8. if ($#_ < $maxIndex) {
  9. for my $i ( 1..$max ) {
  10. deep( ($max-$i), @_, $i);
  11. }
  12. }  else {
  13. TestandPrint( @_ );
  14. }
  15. }
  16. sub TestandPrint {
  17. my $str = join(",", @_);
  18. my $find;
  19. for my $i (0 .. $maxIndex) {
  20. $find = $str=~s/$i/$i/g + 1;
  21. if ($_[$i] != $find) {
  22. return -1;
  23. }
  24. }
  25. print $str,"\n";
  26. }
复制代码
代码备注:
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

当然以上只是猜测而已, 对其他进制是否成立未作验证, 也无任何推理.
  1. <html>
  2. <body>
  3.   结果
  4.   <br>
  5.   <textarea id="result" style="height: 100px; width: 300px;"></textarea>
  6.   <br /> 运行时间从
  7.   <span id="start"></span>--
  8.   <span id="end"></span>
  9.   <br> cnt=
  10.   <span id="cnt"></span>
  11.   <br>
  12.   <button type="button" onclick="run();">运行</button>
  13. </body>
  14. </html>
  15. <script>
  16.   var g = new Array(0x10);
  17.   var R = new Array(0x10);
  18.   var H = new Array(0x10);
  19.   var cnt = 0;
  20.   function run() {
  21.     time_shot('start');
  22.     init();
  23.     f_search(0xF, 0x30);
  24.     time_shot('end');
  25.     document.getElementById('cnt').innerHTML = cnt;
  26.   }
  27.   function init() {
  28.     for ( var i = 0; i <= 0xF; i++) {
  29.       g[i] = 1;
  30.     }
  31.     cnt = 0;
  32.   }
  33.   function f_search(ind, fsum_rem) {
  34.     if (ind < 0) {
  35.       cnt++;
  36.       var test = true;
  37.       for ( var i = 0; i <= 0xF; i++) {
  38.         if (g[i] != R[i]) {
  39.           test = false;
  40.           break;
  41.         }
  42.       }
  43.       if (test) {
  44.         var old = document.getElementById('result').value;
  45.         for ( var i = 0; i <= 0xF; i++) {
  46.           H[i] = R[i].toString(16).toUpperCase();
  47.         }
  48.         document.getElementById('result').value = old + H.join() + '\n';
  49.       }
  50.       return;
  51.     } else {
  52.       var t = ind - 2 >> 31;
  53.       var fi_up = t & 0x21 | ~t
  54.           & Math.floor((0x1F + ind) / (t | (ind - 1)));
  55.       if (ind == 0 && fi_up > 3) {
  56.         fi_up = 3;
  57.       }
  58.       t = fsum_rem - ind;
  59.       var t1 = t - fi_up >> 31;
  60.       fi_up = (t1 & t) | (~t1 & fi_up);
  61.       for ( var i = g[ind]; i <= fi_up; i++) {
  62.         R[ind] = i;
  63.         var a = Math.floor(R[ind] / 0x10);
  64.         var b = R[ind] % 0x10;
  65.         var c = a == 0 ? 0 : 1;
  66.         g[a] += c;
  67.         g[b] += 1;
  68.         f_search(ind - 1, fsum_rem - R[ind]);
  69.         g[a] -= c;
  70.         g[b] -= 1;
  71.       }
  72.     }
  73.   }
  74.   function time_shot(id) {
  75.     var t_stamp = new Date();
  76.     document.getElementById(id).innerHTML = t_stamp.getHours() + ':'
  77.         + t_stamp.getMinutes() + ':' + t_stamp.getSeconds() + ':'
  78.         + t_stamp.getMilliseconds();
  79.   }
  80. </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
  1. var arr = [1,1,1,1,1,1,1,1,1,1];
  2. function arrays_equal(a,b)
  3. {
  4. return !(a<b || b<a);
  5. }
  6. for(;;)
  7. {
  8. var tmparr = [0,0,0,0,0,0,0,0,0,0];
  9. for(var i = 0; i < 10; i++)
  10. {
  11. tmparr[i]++;
  12. var str = arr[i].toString(10);
  13. var slen = str.length;
  14. for(var j = 0; j < slen; j++)
  15. {
  16. var ch = str.charAt(j);
  17. var cint = parseInt(ch, 10);
  18. tmparr[cint]++;
  19. }
  20. }
  21. if(arrays_equal(arr, tmparr))
  22. break;
  23. arr = tmparr;
  24. }
  25. for(var i = 0; i < 10; i++)
  26. {
  27. console.log(i + " : " + arr[i]);
  28. }
复制代码
运行结果:
1 11 2 1 1 1 1 1 1 1

也是js 保存为 htm
  1. <script>
  2. var starttime = Date.now();
  3. var keymaps = [0,1,2,3,4,5,6,7,8,9];
  4. var content = [0,0,0,0,0,0,0,0,0,0];
  5. for(;;)
  6. {
  7. var bdiff = false;
  8. for(var k in keymaps)
  9. {
  10. var val = 1;
  11. var key = keymaps[k].toString(10);
  12. for(var i in content)
  13. {
  14. var str = content[i].toString(10);
  15. for(var j in str)
  16. {
  17. if(str[j] == key)
  18. {
  19. val++;
  20. }
  21. }
  22. }
  23. if(content[k] != val)
  24. {
  25. bdiff = true;
  26. content[k] = val;
  27. }
  28. }
  29. console.log(content);
  30. if(!bdiff)
  31. break;
  32. }
  33. console.log("time: " + (Date.now() - starttime) / 1000);
  34. </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 编辑

上面两段代码都是职业程序员解的。
啃了半晌发现都是:假设-> 计算对比 -> 调整答案 的方法逐步逼近
区别好像是广度优先 和 深度优先,效率好高,可惜各算出一种结果就结束了
  1. Array [ 1, 11, 1, 1, 1, 1, 1, 1, 1, 1 ]
  2. Array [ 1, 12, 1, 1, 1, 1, 1, 1, 1, 1 ]
  3. 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 ]

=
  1. Array [ 11, 3, 1, 2, 1, 1, 1, 1, 1, 1 ]
  2. Array [ 1, 9, 2, 1, 1, 1, 1, 1, 1, 2 ]
  3. Array [ 1, 8, 3, 2, 1, 1, 1, 1, 2, 1 ]
  4. Array [ 1, 7, 3, 2, 1, 1, 1, 2, 1, 1 ]
  5. Array [ 1, 7, 3, 2, 1, 1, 1, 2, 1, 1 ]
  6. "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://bathome.net./) Powered by Discuz! 7.2