[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
12
返回列表 发帖
523066680

Rank: 7Rank: 7Rank: 7

帖子
3151 
积分
6455 
技术
317  
捐助
70  
注册时间
2008-8-3 
1楼 跳转到 » 正序看帖
打印
tT
发表于 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以内

语言不限
收藏 分享
FuniCode 编程论坛

依山居

Rank: 5Rank: 5

帖子
593 
积分
935 
技术
49  
捐助
0  
注册时间
2008-1-3 
16楼
发表于 2015-11-26 17:10 | 只看该作者
感觉我并没有看懂这道题。
不过这道题的实际应用在玩牌类上似乎很实用吧？
下载安装python3 https://www.python.org/downloads/ 代码存为xx.py 双击运行或IDLE打开F5运行

TOP

aa77dd@163.com

帖子
548 
积分
1246 
技术
176  
捐助
0  
注册时间
2015-6-4 
15楼
发表于 2015-6-12 19:45 | 只看该作者
本帖最后由 aa77dd@163.com 于 2015-6-12 20:42 编辑

回复 15# 523066680

这些算法能不能遍历?

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

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

TOP

523066680

Rank: 7Rank: 7Rank: 7

帖子
3151 
积分
6455 
技术
317  
捐助
70  
注册时间
2008-8-3 
14楼
发表于 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 ]
FuniCode 编程论坛

TOP

523066680

Rank: 7Rank: 7Rank: 7

帖子
3151 
积分
6455 
技术
317  
捐助
70  
注册时间
2008-8-3 
13楼
发表于 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. 

  3. function arrays_equal(a,b)

  4. {

  5. 	return !(a<b || b<a);

  6. }

  7. 

  8. for(;;)

  9. {

  10. 	var tmparr = [0,0,0,0,0,0,0,0,0,0];

  11. 	for(var i = 0; i < 10; i++)

  12. 	{

  13. 		tmparr[i]++;

  14. 		var str = arr[i].toString(10);

  15. 		var slen = str.length;

  16. 		for(var j = 0; j < slen; j++)

  17. 		{

  18. 			var ch = str.charAt(j);

  19. 			var cint = parseInt(ch, 10);

  20. 			tmparr[cint]++;

  21. 		}

  22. 	}

  23. 	if(arrays_equal(arr, tmparr))

  24. 		break;

  25. 	arr = tmparr;

  26. }

  27. 

  28. for(var i = 0; i < 10; i++)

  29. {

  30. 	console.log(i + " : " + arr[i]);

  31. }
复制代码
运行结果：
1 11 2 1 1 1 1 1 1 1

也是js 保存为 htm
  1. <script>

  2. var starttime = Date.now();

  3. 

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

  5. var content = [0,0,0,0,0,0,0,0,0,0];

  6. 

  7. for(;;)

  8. {

  9. 	var bdiff = false;

  10. 	for(var k in keymaps)

  11. 	{

  12. 		var val = 1;

  13. 		var key = keymaps[k].toString(10);

  14. 		for(var i in content)

  15. 		{

  16. 			var str = content[i].toString(10);

  17. 			for(var j in str)

  18. 			{

  19. 				if(str[j] == key)

  20. 				{

  21. 					val++;

  22. 				}

  23. 			}

  24. 		}

  25. 		if(content[k] != val)

  26. 		{

  27. 			bdiff = true;

  28. 			content[k] = val;

  29. 		}

  30. 	}

  31. 	console.log(content);

  32. 	if(!bdiff)

  33. 		break;

  34. }

  35. 

  36. console.log("time: " + (Date.now() - starttime) / 1000);

  37. </script>
复制代码
运行结果
Array [ 1, 7, 3, 2, 1, 1, 1, 2, 1, 1 ]
"time: 0.006"
FuniCode 编程论坛

TOP

aa77dd@163.com

帖子
548 
积分
1246 
技术
176  
捐助
0  
注册时间
2015-6-4 
12楼
发表于 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

TOP

aa77dd@163.com

帖子
548 
积分
1246 
技术
176  
捐助
0  
注册时间
2015-6-4 
11楼
发表于 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>
复制代码
1

评分人数

TOP

tigerpower

Rank: 3Rank: 3

帖子
95 
积分
269 
技术
27  
捐助
0  
注册时间
2015-2-26 
10楼
发表于 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在这十六句话中出现的次数是______。

TOP

523066680

Rank: 7Rank: 7Rank: 7

帖子
3151 
积分
6455 
技术
317  
捐助
70  
注册时间
2008-8-3 
9楼
发表于 2015-6-8 11:05 | 只看该作者
本帖最后由 523066680 于 2015-6-9 19:51 编辑

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

  2. 

  3. my $max = 21;                 #理论次数合计

  4. my $maxIndex = 9;             #数组最大下标

  5. 

  6. deep($max);

  7. <STDIN>;

  8. 

  9. sub deep {

  10. 	my $max = shift;

  11. 	if ($#_ < $maxIndex) {

  12. 		for my $i ( 1..$max ) {

  13. 			deep( ($max-$i), @_, $i);

  14. 		}

  15. 	}  else {

  16. 		TestandPrint( @_ );

  17. 	}

  18. }

  19. 

  20. sub TestandPrint {

  21. 	my $str = join(",", @_);

  22. 	my $find;

  23. 	for my $i (0 .. $maxIndex) {

  24. 		$find = $str=~s/$i/$i/g + 1;

  25. 		if ($_[$i] != $find) {

  26. 			return -1;

  27. 		}

  28. 	}

  29. 	print $str,"\n";

  30. }
复制代码
代码备注：
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
FuniCode 编程论坛

TOP

bailong360

Rank: 5Rank: 5

帖子
578 
积分
1235 
技术
170  
捐助
60  
注册时间
2012-8-5 
8楼
发表于 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. 

  18. (define (integer->list num)

  19.   (define index '(0 1 2 3 4 5 6 7 8 9))

  20.   (define str '())

  21.   (define (cc)

  22.     (set! str (cons (list-ref index (modulo num 10)) str))

  23.     (set! num (floor (/ num 10)))

  24.     (if (= 0 num)

  25.         str

  26.         (cc)))

  27.   (cc))

  28. 

  29. (define (main)

  30.   (define guess (make-vector 10 1))

  31.   (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)))

  32.   (define (loop index)

  33.     (for-each (lambda (x)

  34.                 (vector-set! guess index x)

  35.                 (if (= index 7)

  36.                     (check guess)

  37.                     (loop (+ index 1))))

  38.               (list-ref max index)))

  39.   (loop 0))

  40. 

  41. (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
复制代码
2

评分人数

TOP

aa77dd@163.com

帖子
548 
积分
1246 
技术
176  
捐助
0  
注册时间
2015-6-4 
7楼
发表于 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. 

  19. function init() {

  20.   for (var i = 0; i <= 9; i++) {

  21.     g[i] = 1;

  22.   }

  23. }

  24. 

  25. function f_search(ind, fsum_rem) {

  26.   var t = ind - 2 >> 31;

  27.   var fi_up = t & 21 | ~t & Math.floor((19 + ind) / (t | (ind - 1)));

  28. 

  29.   if (ind == 0 && fi_up > 3) {

  30.     fi_up = 3;

  31.   }

  32. 

  33.   t = fsum_rem - ind;

  34.   var t1 = t - fi_up >> 31;

  35.   fi_up = (t1 & t) | (~t1 & fi_up);

  36. 

  37.   if (ind < 0) {

  38.     var test = true;

  39.     for (var i = 0; i <= 9; i++) {

  40.       if (g[i] != f[i]) {

  41.         test = false;

  42.         break;

  43.       }

  44.     }

  45.     if (test) {

  46.       var old = document.getElementById('result').innerHTML;

  47.       document.getElementById('result').innerHTML = old + f.join() + '\n';

  48.     }

  49. 

  50.     return;

  51.   } else {

  52.     var next = ind - 1;

  53. 

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

  55.       f[ind] = i;

  56. 

  57.       fsum_rem -= f[ind];

  58. 

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

  60.       var b = f[ind] % 10;

  61. 

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

  63.       g[b] += 1;

  64. 

  65.       f_search(next, fsum_rem);

  66. 

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

  68.       g[b] -= 1;

  69. 

  70.       fsum_rem += f[ind];

  71.     }

  72.   }

  73. }

  74. 

  75. function time_shot(id) {

  76.   var t_stamp = new Date();

  77.   document.getElementById(id).innerHTML = t_stamp.getHours() + ':' + t_stamp.getMinutes() + ':' + t_stamp.getSeconds() + ':' + t_stamp.getMilliseconds();

  78. }

  79. </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
3

评分人数

TOP

523066680

Rank: 7Rank: 7Rank: 7

帖子
3151 
积分
6455 
技术
317  
捐助
70  
注册时间
2008-8-3 
6楼
发表于 2015-6-5 22:44 | 只看该作者
本帖最后由 523066680 于 2015-6-5 22:45 编辑

回复 6# bailong360


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

TOP

bailong360

Rank: 5Rank: 5

帖子
578 
积分
1235 
技术
170  
捐助
60  
注册时间
2012-8-5 
5楼
发表于 2015-6-5 22:22 | 只看该作者
本帖最后由 bailong360 于 2015-6-7 19:06 编辑

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

TOP

523066680

Rank: 7Rank: 7Rank: 7

帖子
3151 
积分
6455 
技术
317  
捐助
70  
注册时间
2008-8-3 
4楼
发表于 2015-6-5 21:50 | 只看该作者
本帖最后由 523066680 于 2015-6-5 22:16 编辑

回复 4# yangfengoo

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

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

TOP

yangfengoo

Rank: 5Rank: 5

帖子
441 
积分
1312 
技术
39  
捐助
0  
注册时间
2009-4-26 
3楼
发表于 2015-6-5 21:36 | 只看该作者
这个题代码怎么写完全没思路。
只能初步推理，1应该出现最多；3后面的数字出现次数都应该很小。

TOP

12
返回列表