本帖最后由 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>
|
发表于 2015-6-6 19:19
| 