电脑不够快

Posted on by
围棋

电脑围棋现在处于童年甚至婴儿时代

——陈志行　　

在一个论坛中有这样一个新手求助的帖子：

昨天，我用C语言写了一个程序，用来计算一个小学问题：在4*4的方格里填1~16，使横、竖、斜都相等。结果，计算机算了半天，没结果。而cpu使用为100%，我检查过了，不是死循环。我估算了一下，是计算次数太多了，我的电脑不够快。先将程序源代码贴出来，大家帮我想想办法。哪位有高级计算机，帮我算一下，谢谢！

#include<stdio .h>
int main(){
 int e2(int x);
 unsigned int 
a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,num1,term1,num2,term2;
 num1=term1=num2=term2=0;
 while(num1<2000000000){
 //translate num1 to a1~a8
 a1=num1%16+1;
 num1=(num1-num1%16)/16;
 a2=num1%16+1;
 num1=(num1-num1%16)/16;
 a3=num1%16+1;
 num1=(num1-num1%16)/16;
 a4=num1%16+1;
 num1=(num1-num1%16)/16;
 a5=num1%16+1;
 num1=(num1-num1%16)/16;
 a6=num1%16+1;
 num1=(num1-num1%16)/16;
 a7=num1%16+1;
 num1=(num1-num1%16)/16;
 a8=num1%16+1;
 num1=(num1-num1%16)/16;
 num1=term1=term1+1;
 while(num2<2000000000 && a1+a2+a3+a4==34 && a7+a5+a6+a8==34 && a8!=1 ){
  //translate num1 to a9~a16
  a9=num2%16+1;
  num2=(num2-num2%16)/16;
  a10=num2%16+1;
  num2=(num2-num2%16)/16;
  a11=num2%16+1;
  num2=(num2-num2%16)/16;
  a12=num2%16+1;
  num2=(num2-num2%16)/16;
  a13=num2%16+1;
  num2=(num2-num2%16)/16;
  a14=num2%16+1;
  num2=(num2-num2%16)/16;
  a15=num2%16+1;
  num2=(num2-num2%16)/16;
  a16=num2%16+1;
  num2=(num2-num2%16)/16;
  num2=term2=term2+1;
 
 
 
 //check  whether the translation works well. 
 
 //printf("%d %d %d %d %d %d %d %d   %d %d\n%d %d %d %d%d%d%d%d%d%d\n________________\n\n",
 // a1,a2,a3,a4,a5,a6,a7,a8,num1,term1,a9,a10,a11,a12,a13,a14,a15,a16,num2,term2);
 
 
 if(a9+a10+a11+a12==34 && a13+a14+a15+a16==34  &&
  a1+a5+a9+a13==34 && a2+a6+a10+a14==34 && a3+a7+a11+a15==34 && 
a4+a8+a12+a16==34 &&
  a9+a14+a3+a8==34 && a5+a2+a15+a12==34
  && e2(a1)+e2(a2)+e2(a3)+e2(a4)+e2(a5)+e2(a6)+e2(a7)+e2(a8)
  +e2(a9)+e2(a10)+e2(a11)+e2(a12)+e2(a13)+e2(a14)+e2(a15)+e2(a16)
==1022131070){
  printf(" %d %d %d %d\n %d %d %d %d\n %d %d %d %d\n %d %d %d %d\n %d %d\n%d %d\n", a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,num1,term1,num2,term2);
  getchar();
 }
  //check whether the circle work well 
  //if(term2%10000000==0)
  // printf("________2_________%d\n________1__________%d\n",term2/10000000,term1);
 if(term1%10000000==0)
   printf("________1__________%d\n",term1/10000000);  
 }
 num2=term2=0;
 }
 //getchar();
 return(0);
}
int e2(int x){
 int sum=1,n=0;
 while(n<x ){
  sum=sum*2;
  n++;
 }
 return(sum);
}

这段代码看着权当娱乐就好了，不过想一下，如果自己来写这样一个计算4阶幻方的程序，算出所有可能解，应该怎么做呢？

计算机的强大之处就是可以很快地重复执行很枯燥的工作，这一特性使得对于很多问题，只要把各种可能都试验一遍就可以了，比如像4阶幻方这样的问题。

虽然计算机可以算得很快，但是愚蠢的穷举方法会轻松导致失败，4阶幻方中，填好每行或者每列的前3个数后，第4个数只要用34减去前面3个数就好了。
这样只要关心9个格子的数字，再考虑两条对角线之后，只要关心7个格子的数字就行了，总共要考虑16!/(16-9)! = 4151347200种情况（考虑对称和旋转之后还可以少许多），用下面的程序就可以算了：

#include <stdio .h>
 
const int N = 4;
const int N2 = N * N;
const int M = N - 1;
const int S = (1 + N2) * N / 2 - N;
 
int a[N][N];
int u[N2];
 
int d;
 
bool updated(int d) {
    if (d < 0 || d >= N2 || u[d]) return false;
    if (::d >= 0) {
        return (::d == d);
    } else {
        ::d = d;
        return true;
    }
}
 
void printout() {
    puts("-----");
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) printf("%d ", a[j][k] + 1);
        putchar('\n');
    }
}
 
void f(int y, int x) {
    d = -1;
 
    if (y == M - 1) {
        if (x == 1) {
            int q = a[M - 1][0];
            for (int j = 0; j < M - 1; j++)
                q += a[j][0] - a[j][M - j];
            if (!updated(q)) return;
        } else if (x == M - 1) {
            int q = S;
            for (int j = 0; j < M - 1; j++)
                q -= -a[j][M] + a[j][j] + a[M - 1][j];
            if (q & 1) return;
            if (!updated(q / 2)) return;
        }
    } else if (y == M) {
        int q = S;
        for (int j = 0; j < M; j++) q -= a[j][x];
        if (!updated(q)) return;
        if (x == M) {
            a[M][M] = q;
            printout();
            return;
        }
    }
 
    if (x == M) {
        int q = S;
        for (int j = 0; j < M; j++) q -= a[y][j];
        if (!updated(q)) return;
    }
 
    int i = d;
    if (i >= 0) {
        u[i] = 1;
        a[y][x] = i;
        if (x == M) f(y + 1, 0);
        else f(y, x + 1);
        u[i] = 0;
    } else {
		for (i = 0; i < N2; i++) {
            if (!u[i]) {
                u[i] = 1;
                a[y][x] = i;
                if (x == M) f(y + 1, 0);
                else f(y, x + 1);
                u[i] = 0;
            }
        }
	}
}
 
int main() {
    f(0, 0);
    return 0;
}

半秒钟内就可以算出来全部的7040个解。上面的程序还可以处理其他阶的幻方，当N = 5时，算出来第一个解都要等待几分钟，实在太慢了。

上面的程序是一格一格地填，那么能不能一行一行地填呢？可以的，事先把一行的填法全部算出来，然后我采用这样的顺序：先填第一横行，再填第一竖行，再填第二横行，第二竖行…… 直到填完。

#include < stdio.h >
#include < string.h >
#include < algorithm >
#include < vector >
 
 
using namespace std;
 
const int N = 5;
const int N2 = N * N;
const int M = N - 1;
const int H = N / 2;
const int S = (1 + N2) * N / 2 - N;
 
int a[N][N];
int u[N2];
 
template< int T >
class Row {
    int a_[T];
public:
 
    Row() {
    }
 
    Row(const int a[]) {
        for (int i = 0; i < N; i++) a_[i] = a[i];
    }
 
    void set(int index, int value) {
        a_[index] = value;
    }
 
    int get(int index) {
        return a_[index];
    }
 
    bool operator<(const Row<T>& that) const {
        for (int i = 0; i < T; i++)
            if (a_[i] < that.a_[i]) return true;
            else if (a_[i] > that.a_[i]) return false;
        return false;
    }
 
    bool operator ==(const Row< t >& that) const {
        for (int i = 0; i < T; i++)
            if (a_[i] != that.a_[i]) return false;
        return true;
    }
 
    bool match(const int a[], const int l) const {
        for (int i = 0; i < l; i++) {
            if (a_[i] != a[i]) return false;
        }
        return true;
    }
};
 
vector< Row< N > > t;
int h[N];
int rl, rr;
 
void printout() {
    puts("-----");
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) printf("%d ", a[j][k] + 1);
        putchar('\n');
    }
}
 
void f(int n, int d) {
    if (n == N) {
        //check '\'
        int s = 0;
        for (int i = 0; i < N; i++) s += a[i][i];
        if (s == S) printout();
        return;
    }
    int h[N];
    switch (d) {
        case 0:
            // Direction: Hor --
            for (int i = 0; i < N; i++) h[i] = i >= n ? 0 : a[n][i];
 
            for (vector< Row< N > >::iterator l = lower_bound(t.begin(), t.end(), Row< N > (h));
                    l != t.end() && l -> match(h, n); l++) {
                //check unused
                bool flag = true;
                for (int i = n; i < N; i++) {
                    if (u[l->get(i)]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    //try it
                    for (int i = n; i < N; i++) u[a[n][i] = l -> get(i)] = 1;
                    //check /
                    if ((N & 1) && n == H) {
                        int s = 0;
                        for (int k = 0; k < N; k++) s += a[M - k][k];
                        flag = (s == S);
                    }
 
                    if (flag) f(n + 1, 1);
                    for (int i = n; i < N; i++) u[l -> get(i)] = 0;
                }
            }
            break;
        case 1:
            // Direction: Ver |
            for (int i = 0; i < N; i++) h[i] = i >= n ? 0 : a[i][n - 1];
 
            for (vector< Row< N > >::iterator l = lower_bound(t.begin(), t.end(), Row< N > (h));
                    l != t.end() && l->match(h, n); l++) {
                //check unused
                bool flag = true;
                for (int i = n; i < N; i++) {
                    if (u[l -> get(i)]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    //try it
                    for (int i = n; i < N; i++)
                        u[a[i][n - 1] = l -> get(i)] = 1;
                    //check /
                    if (!(N & 1) && n == H) {
                        int s = 0;
                        for (int k = 0; k < N; k++) s += a[M - k][k];
                        flag = (s == S);
                    }
                    if (flag) f(n, 0);
 
                    for (int i = n; i < N; i++)
                        u[l -> get(i)] = 0;
                }
            }
    }
}
 
void gen(int i, int l) {
    if (i == M) {
        if (l >= 0 && l < N2 && !u[l]) {
            h[M] = l;
            t.push_back(Row< N > (h));
        }
    } else {
        for (int j = 0; j < N2; j++) {
            if (!u[j]) {
                if (l >= j) {
                    u[j] = 1;
                    if (i >= 0) h[i] = j;
                    gen(i + 1, l - j);
                    u[j] = 0;
                }
            }
        }
    }
}
 
int main() {
    gen(0, S);
    f(0, 0);
    return 0;
}

这里实际上用空间换取了时间，事先计算出来的一行的所有排法需要占用空间，而后可以算得快一些。而并不是所有时候都可以用空间换时间，必须要在有重复或类似的状态出现时才有可能用空间换取时间。

实际用这个程序算五阶幻方，几秒钟内就可以算出来第一个解，剩下的解也可以源源不断地算出来，但是要算出所有解，看起来要用很多个小时，还是很慢。

还可以考虑一次填一横行和一竖行，这样需要更多的空间，更复杂的程序，也不一定会快到哪里，我并没有去实现它。

5阶幻方，这个看起来很简单的事情，实际上用电脑来算，却是十分的不容易，即便程序已经优化得复杂度降了一维又一维，但是仍然慢得无法忍受，而且伴随着速度加快，还有内存不够用的危险。

高中的时候，我曾经在自己的电脑上想算出3阶魔方的所有状态，但是没有算完第4步就遇到了内存不够和速度不能忍的问题：

program magic_square;
{$APPTYPE CONSOLE}
 
const debug=1;
      MAX_PERMUTATION_ELEMENTS_COUNT=20;
      MAX_PERMUTATION_COUNT=50000;
type
     TInt=longword;
     TPermutation=array [1..MAX_PERMUTATION_ELEMENTS_COUNT] of word;
     TLink=record prev,next:TInt; end;
     ECompare=(Bigger,Smaller,Equal);
var
  Pers:packed array [1..MAX_PERMUTATION_COUNT] of TPermutation;
  PersIndex:packed array [1..MAX_PERMUTATION_COUNT] of TInt;
  PersCount:TInt;
 
  PerTemp:TPermutation;
  {PersLinkTable:array [0..MAX_PERMUTATION_COUNT] of TLink;}
 
  {
   Data struct:
     PersLinkTable[i].next  : (Element Pers[i])'s next element's index, 0 : Tail
                     .prev  : (Element Pers[i])'s previous element's index, 0 : Tail
     PersLinkTable[0].next  : Head index
     ->Use binary search, not use PersLinkTable
  }
 
//Permutation functions//////////////////////////
{
procedure PersLinkTableInit;
begin
  PersCount:=0;
  fillchar(PersLinkTable,sizeof(PersLinkTable),0);
  PersLinkTable[0].next:=1;
end;
}
 
function PersCompare(var a,b:TPermutation):ECompare;
var i:TInt;
begin
  for i:=1 to MAX_PERMUTATION_ELEMENTS_COUNT do
    if a[i] > b[i] then begin result:=Bigger;exit end else
    if a[i] < b[i] then begin result:=Smaller;exit end;
  Result:=Equal;
end;
 
function PersBinarySearch(var a:TPermutation):TInt;
var l,r,m:TInt;
begin
  l:=1;r:=PersCount;
  while l<=r do begin
    m:=(l+r) div 2;
    case PersCompare(a,Pers[PersIndex[m]]) of
    Equal:
      //本应该返回mid, 但是直接处理掉重复，返回0
      begin result:=0;exit;end;
    Bigger:
      l:=m+1;
    Smaller:
      r:=m-1;
    end;
  end;
  //此时，l= (>a的第一个元素)
  Result:=l;
end;
 
procedure PersInsert(var a:TPermutation);
var i,p:TInt;
begin
  p:=PersBinarySearch(a);
  if p>0 then begin
    if PersCount>=MAX_PERMUTATION_COUNT then begin
       writeln('Over flow!');
       readln;
       halt;
    end;
 
    //Move Pers[p..PersCount] to Pers[p+1..PersCount+1]
    inc(PersCount);
    if PersCount mod 1000=0 then writeln('  Count: ',PersCount);
    Move(PersIndex[p],PersIndex[p+1],(PersCount-p)*sizeof(PersCount));
 
    Pers[PersCount]:=a;
    PersIndex[p]:=PersCount;
  end;
 
end;
 
procedure PersCreat(var a:TPermutation;ProvidedLength:Word;Content:array of Word);
var i:word;
begin
     for i:=1 to MAX_PERMUTATION_ELEMENTS_COUNT do a[i]:=i;
     //注意:Content array 下标从0开始
     for i:=0 to ProvidedLength-1 do
         a[Content[i]]:=Content[ProvidedLength+i];
end;
 
procedure PersMultiply(var MulResult,a,b:TPermutation);
var i:word;
begin
     for i:=1 to MAX_PERMUTATION_ELEMENTS_COUNT do
         MulResult[i]:=b[a[i]];
end;
/////////////////////////////////////////////////
 
var
    LastPersCount:TInt;
    i,j,k:word;
begin
  PersCount:=0;
  LastPersCount:=PersCount;
{
                 +--------+
                 |13 14 15|
                 |16    17|
                 |18 19 20|
         +-------+--------+
         |9    10|
         |       |
         |11   12|
 +-------+-------+
 |1  2  3|
 |4     5|
 |6  7  8|
 +-------+
 注意:每个面的面心固定住，
 因为无论怎么转，都可得到本质相同的情况（考虑一步即可）
}
  PersCreat(PerTemp,8,
  [1,2,3,4,5,6,7,8,
   3,5,8,2,7,1,4,6]);PersInsert(PerTemp); //Front side
 
  PersCreat(PerTemp,8,
  [13,14,15,16,17,18,19,20,
   15,17,20,14,19,13,16,18]);PersInsert(PerTemp); //Back side
 
  PersCreat(PerTemp,8,
  [1,9,13,4,16,6,11,18,
   13,16,18,9,11,1,4,6]);PersInsert(PerTemp); //Left side
 
  PersCreat(PerTemp,8,
  [3,10,15,5,17,8,12,20,
  15,17,20,10,12,3,5,8]);PersInsert(PerTemp); //Right side
 
  PersCreat(PerTemp,8,
  [1,2,3,9,10,13,14,15,
  3,10,15,2,14,1,9,13]);PersInsert(PerTemp); //Top side
 
  PersCreat(PerTemp,8,
  [6,7,8,11,12,18,19,20,
  8,12,20,7,19,6,11,18]);PersInsert(PerTemp); //Bottom side
 
  for i:=1 to 10 do begin
      writeln('#',i,':');
      LastPersCount:=PersCount;
      for j:=1 to LastPersCount do for k:=1 to LastPersCount do begin
          PersMultiply(PerTemp,Pers[j],Pers[k]);
          PersInsert(PerTemp);
      end;
      writeln('Now Count: ',Perscount);
      readln;
  end;
 
  if debug=1 then readln;
end.

现在的CPU和内存和上面这个程序运行时已经有了很大进步，但执行上面的程序一定还没有希望获得结果。

目前的电脑还很慢……

2 thoughts on “电脑不够快”

  1. 怎么连 pascal 都出来了？
    幻方搜索解的话，是相互独立的吧，应该可以很容易并行或者分布式一下哦！不过得要有硬件资源才能玩。

    Reply

  2. @pluskid: 最后那个程序是以前写的, 现在回过头看pascal语法,都有点不熟悉了 – –
    分布式也不一定够用,计算量增长得太快了…

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>