中科院面试题

[吕宗庭]

在N×N的矩阵中填入正整数，使得每一行每一列分别相加都得D。数字可以重复。计算一共有多少个这样的不同矩阵。不用输出所有矩阵，只要有多少种就
行。

计算N=5，D=8时的结果。算出来的同学发奖品。一件开源社区的T-shirt。

[Nemo]

我算法太烂，写了个计算时间都超过一分钟了- -!
而且结果让我很怀疑:153040

2009/11/26 吕宗庭 <lvzon...@gmail.com>

在N×N的矩阵中填入正整数，使得每一行每一列分别相加都得D。数字可以重复。计算一共有多少个这样的不同矩阵。不用输出所有矩阵，只要有多少种就
行。


计算N=5，D=8时的结果。算出来的同学发奖品。一件开源社区的T-shirt。

--
人生好比在树林中走路，有无数的岔路口，任你选择，但你永远只能选择其中一个。沿着你选择的岔路口走下去，你又会遇到无数的岔路口。当你做出了无数的选择—正确的或错误的，走到路的尽头，回头再看，所有的岔路口都不见了，你会发现，其实你只走了一条路—那就是你来时的路，那就是你唯一的命运。

[张龙攀]

我的结果也是153040

2009/11/26 Nemo <nemo...@gmail.com>

[吕宗庭]

咱能把算法贴出来吗。

On 11月26日, 下午4时17分, 张龙攀 <zhanglong...@gmail.com> wrote:
> 我的结果也是153040
> 2009/11/26 Nemo <nemo1...@gmail.com>

>
> > 我算法太烂，写了个计算时间都超过一分钟了- -!
> > 而且结果让我很怀疑:153040
>

> > 2009/11/26 吕宗庭 <lvzongt...@gmail.com>

>
> > 在N×N的矩阵中填入正整数，使得每一行每一列分别相加都得D。数字可以重复。计算一共有多少个这样的不同矩阵。不用输出所有矩阵，只要有多少种就
> >> 行。
>
> >> 计算N=5，D=8时的结果。算出来的同学发奖品。一件开源社区的T-shirt。
>
> > --
>

> > 人生好比在树林中走路，有无数的岔路口，任你选择，但你永远只能选择其中一个。沿着你选择的岔路口走下去，你又会遇到无数的岔路口。当你做出了无数的选择--正确的或错误的，走到路的尽头，回头再看，所有的岔路口都不见了，你会发现，其实你只走了一条路--那就是你来时的路，那就是你唯一的命运。

[张龙攀]

#include <iostream.h>
#include <string.h>
#include <fstream.h>
int a[100][100];
bool flag=0;
int count=0;
int n,d;
//ofstream out("result.txt");
int rsum(int i,int j)
{ 
 int sum=0;
 for(int k=1;k<=i;k++)
  sum+=a[k][j];
 return sum;
}
int csum(int i,int j)
{
 int sum=0;
 for(int k=1;k<=j;k++)
  sum+=a[i][k];
 return sum;
}
bool test()
{
 bool f=1;
 
 for(int i=1;i<=n;i++)
 {
  int sum1=0,sum2=0;
  for(int j=1;j<=n;j++)
  {
   sum1+=a[i][j];
   sum2+=a[j][i];
  }
  if(sum1==d && sum2==d)
   continue;
  else
  {
   f=0;
   break;
  }
 }
 return f;
}
void dfs(int i,int j)
{
 if(i==n && j==n)
 {
  for(int m=1;m<=d-n+1;m++)
  {
   a[n][n]=m;
   
   if(test())
   {
   /* for(int p=1;p<=n;p++)
    {
     cout<<endl;
     for(int q=1;q<=n;q++)
      cout<<a[p][q]<<" ";
    }
   */
    count++;
   }
   // else
   // cout<<"can not find the answer\n";
   
  }
  a[n][n]=0;
  return;
 }
 else
 {

  for(int m=1;m<=d-n+1;m++)
  {
   a[i][j]=m;
   if(rsum(i,j)>d || csum(i,j)>d)
    break;
   else
   {
    if(i==n && j<=n)
    {
      dfs(1,j+1);
    }
    else
    {
     dfs(i+1,j);
    }
   }
   
  }
 }
}
int main()
{

 while(cin>>n>>d)
 {
  memset(a,0,sizeof(a));
  dfs(1,1);
  cout<<count<<endl;
  count=0;

 }
 return 0;

}

 

没有剪枝，跑的比较慢啊

[吕宗庭]

是算法不是代码。

[张龙攀]

代码不是很清晰么？DFS

2009/11/26 吕宗庭 <lvzon...@gmail.com>

[Nemo]

我是自己偷懒型的，事情大部分交给计算机，所以一直用for导致效率相当的低(罪过啊)：
［code］
#!/usr/bin/env python
List = []
count = 0
#5个1到8之间的数相加，当等于8时将的到的组合放入到一个列表中，这样的到了行相加为8的组合
for a in range(1, 8):
    for b in range(1, 8):
        for c in range(1, 8):
            for d in range(1, 8):
                for e in range(1, 8):
                    if a + b + c + d + e == 8:
                        List += [[a,b,c,d,e]]
#从之前的组合中取5个出来组成一个5x5矩阵
for La in List:
    for Lb in List:
        for Lc in List:
            for Ld in List:
                for Le in List:
                    #5列每列相加求和，直到最后一列求和亦为8时计数器加1
                    for i in range(5):
                        if La[i] + Lb[i] + Lc[i] + Ld[i] + Le[i] != 8:
                            break
                        if i == 4:
                            count += 1
print count
［code］

2009/11/26 吕宗庭 <lvzon...@gmail.com>

--

[Nemo]

我们宿舍的我和他说了他尝试用回溯法解决，我想应该更效率些，吕大给出你的想法？

2009/11/26 Nemo <nemo...@gmail.com>

[张龙攀]

我的那个更慢啊，盲目的枚举   脚本写起来就是简洁啊

[吕宗庭]

用状态转移写的 回逆，但是 还有更牛的 在 1ms内算出来的 我在想他怎么做的 他跟我说 用的是 翻转矩阵的方法 我还没搞明白 郁闷呀 比不过
人家了。人家 就没有 浪费的 直接 生成 字典序的 结果 。

On 11月26日, 下午5时24分, 张龙攀 <zhanglong...@gmail.com> wrote:
> 我的那个更慢啊，盲目的枚举[?][?][?] 脚本写起来就是简洁啊
>
> 331.gif
> < 1K查看下载

[吕宗庭]

我真没看出来 是 深度搜索 我连 结构都没看明白 。

On 11月26日, 下午5时17分, 张龙攀 <zhanglong...@gmail.com> wrote:
> 代码不是很清晰么？DFS
>
> 2009/11/26 吕宗庭 <lvzongt...@gmail.com>

[Nemo]

因为数字可以重复，所以翻转矩阵是不是就是矩阵翻转90度后又是一个新的矩阵，如果是的话这样能效率很多

2009/11/26 吕宗庭 <lvzon...@gmail.com>

[吕宗庭]

我们这些 都是 搜索法 他做出了 生成法。我已经想了 一天了。

On 11月26日, 下午6时15分, Nemo <nemo1...@gmail.com> wrote:
> 因为数字可以重复，所以翻转矩阵是不是就是矩阵翻转90度后又是一个新的矩阵，如果是的话这样能效率很多
>

> 2009/11/26 吕宗庭 <lvzongt...@gmail.com>

>
> > 用状态转移写的 回逆，但是 还有更牛的 在 1ms内算出来的 我在想他怎么做的 他跟我说 用的是 翻转矩阵的方法 我还没搞明白 郁闷呀 比不过
> > 人家了。人家 就没有 浪费的 直接 生成 字典序的 结果 。
>
> > On 11月26日, 下午5时24分, 张龙攀 <zhanglong...@gmail.com> wrote:
> > > 我的那个更慢啊，盲目的枚举[?][?][?] 脚本写起来就是简洁啊
>
> > > 331.gif
> > > < 1K查看下载
>
> --

[吕宗庭]

你这个 .........原题是这样的计算N从1到10，D从2到20的所有结果。

> 2009/11/26 吕宗庭 <lvzongt...@gmail.com>

[吕宗庭]

我写的可麻烦的一个 先生成一维的情况 然后 在这些 一维的基础上 构造二维的 结果 但是 还有很多 的多余解。

On 11月26日, 下午5时22分, Nemo <nemo1...@gmail.com> wrote:
> 我们宿舍的我和他说了他尝试用回溯法解决，我想应该更效率些，吕大给出你的想法？
>

> 2009/11/26 Nemo <nemo1...@gmail.com>

> > 2009/11/26 吕宗庭 <lvzongt...@gmail.com>

> > 人生好比在树林中走路，有无数的岔路口，任你选择，但你永远只能选择其中一个。沿着你选择的岔路口走下去，你又会遇到无数的岔路口。当你做出了无数的选择--正确的或错误的，走到路的尽头，回头再看，所有的岔路口都不见了，你会发现，其实你只走了一条路--那就是你来时的路，那就是你唯一的命运。
>
> --

[孙恭鑫]

xidian_linux，您好！

貌似是求这么一个东西是吧？||{A|A*ones(n,1)=d*ones(n,1), A'*ones(n,1)=d*ones(n,1), A∈N^+n*n}||
如果是这样可以考虑先对约束做个松弛处理，让A∈R^+n*n，然后割平面。


======================== 2009-11-26 18:44:38 您在来信中写道：========================

>我写的可麻烦的一个 先生成一维的情况 然后 在这些 一维的基础上 构造二维的 结果 但是 还有很多 的多余解。
>
>On 11月26日, 下午5时22分, Nemo <nemo1...@gmail.com> wrote:

>> 我们宿舍的我和他说了他尝试用回溯法解决，我想应该更效率些，吕大给出你的想法？
>>
>> 2009/11/26 Nemo <nemo1...@gmail.com>

>> > 2009/11/26 吕宗庭 <lvzongt...@gmail.com>

>> > 人生好比在树林中走路，有无数的岔路口，任你选择，但你永远只能选择其中一个。沿着你选择的岔路口走下去，你又会遇到无数的岔路口。当你做出了无数的选择--正确的或错误的，走到路的尽头，回头再看，所有的岔路口都不见了，你会发现，其实你只走了一条路--那就是你来时的路，那就是你唯一的命运。
>>
>> --

>> 人生好比在树林中走路，有无数的岔路口，任你选择，但你永远只能选择其中一个。沿着你选择的岔路口走下去，你又会遇到无数的岔路口。当你做出了无数的选择--正确的或错误的，走到路的尽头，回头再看，所有的岔路口都不见了，你会发现，其实你只走了一条路--那就是你来时的路，那就是你唯一的命运。
>>

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =



致
礼！


孙恭鑫
AlexS...@yahoo.com.cn
2009-11-26

[吕宗庭]

对，我这样做了，将其割成尽量连续的空间，但是 最后 变量就减了几个，而且解空间也不是很连续。效果不是很明显，你自己算一下就知道了。我校赛时就是
这样解的数独问题。求一个很容易。我找一下把我算的结果一会儿贴上来，真想知道 整数优化的函数是怎样迭代求点的(就对不是像书上讲的算法我试了没有这
么快但是我没找到最新的迭代算法)，效率真高。那样就快多了。

> AlexSun...@yahoo.com.cn
> 2009-11-26

[ggarlic]

你还是叫幻方问题的好~~

2009/11/26 吕宗庭 <lvzon...@gmail.com>

--
Welcome to World of Ggarlic
http://ggarlic.org

[吕宗庭]

不一样的 很多都不一样 幻方和这个的约束条件 不是很一样 这个更像 数独

On 11月26日, 下午8时44分, ggarlic <yangbo.ggar...@gmail.com> wrote:
> 你还是叫幻方问题的好~~
>
> 2009/11/26 吕宗庭 <lvzongt...@gmail.com>

[汪彧之]

我只能想到生成全排列判重……

矩阵旋转是个好方法，包括翻转、换行、换列

2009/11/26 吕宗庭 <lvzon...@gmail.com>

--
以上文本按GFDL发布
http://bigeagle.yo2.cn/

[吕宗庭]

扯了 题记错了
原题 ：

给定正整数N和D，生成所有行和、列和等于D的NxN的非负整数矩阵。给出 N <= 5, D <= 8 的所有计数值。

我找到邮件了。对不起大家。

答案：

N=5 D=4 结果:2224955 耗时109ms
N=5 D=5 结果:22069251 耗时1140ms
N=5 D=6 结果:164176640 耗时6531ms
N=5 D=7 结果:976395820 耗时34344ms
N=5 D=8 结果:4855258305 耗时172109ms

D D D D D D D D
1 2 3 4 5 6 7 8
N 1 1 1 1 1 1 1 1 1
N 2 2 3 4 5 6 7 8 9
N 3 6 21 55 120 231 406 666 1035
N 4 24 282 2008 10147 40176 132724 381424 981541
N 5 120 6210 153040

是要算零的。大家再改一下程序吧。我对不起大家。

On 11月26日, 下午11时03分, 汪彧之 <justin.w...@gmail.com> wrote:
> 我只能想到生成全排列判重......
>
> 矩阵旋转是个好方法，包括翻转、换行、换列
> 2009/11/26 吕宗庭 <lvzongt...@gmail.com>

[吕宗庭]

我 先写一个 慢的 给大家看看 他说了 他快的先不贴 一贴 就没人做了 所以我先 把我的 矬方法 贴出来吧《基于解不定方程组的搜索算法》但是
里面 有公式 所以 我贴到 我的校内上。

[MAT WETU]

先一维再二维…c实现…耗时居然是答案的三倍！校内那篇看不懂。。期待揭晓，希望到时看懂。。

在 09-11-27，吕宗庭<lvzon...@gmail.com> 写道：

[吕宗庭]

我今天晚上 会说的。我同学说：下周，他把更快的方法贴出来。然后他给大家讲一下。

On 11月28日, 上午1时19分, MAT WETU <matw...@gmail.com> wrote:
> 先一维再二维...c实现...耗时居然是答案的三倍！校内那篇看不懂。。期待揭晓，希望到时看懂。。
>
> 在 09-11-27，吕宗庭<lvzongt...@gmail.com> 写道：

[吕宗庭]

你把程序贴出来 我看一下。

On 11月28日, 上午1时19分, MAT WETU <matw...@gmail.com> wrote:

> 先一维再二维...c实现...耗时居然是答案的三倍！校内那篇看不懂。。期待揭晓，希望到时看懂。。
>
> 在 09-11-27，吕宗庭<lvzongt...@gmail.com> 写道：

[MAT WETU]

#include <stdio.h>
#include <time.h>
#define D 8
int part[500][5],np=0;
int tmp[5],tsum=0;
int way[5],wsum[5]={0,0,0,0,0};
unsigned int n=0;
void init(int x)
{
if(x==4){
tmp[4]=D-tsum;
memcpy(part[np],tmp,sizeof(tmp));
np++;
return;
}
int i;
for(i=0;i<=D;i++)
{
if(tsum+i<=D){
tsum+=i;
tmp[x]=i;
init(x+1);
tsum-=i;
}
}
}
void search(int x)
{
if(x==4){
n++;
return ;
}
int i;
for(i=0;i<np;i++)
{
int j;
for(j=0;j<5;j++)if(wsum[j]+part[i][j]>D)break;
if(j>=5)
{
for(j=0;j<5;j++)wsum[j]+=part[i][j];
way[x]=i;
search(x+1);
for(j=0;j<5;j++)wsum[j]-=part[i][j];
}
}
}
int main()
{
clock_t start, finish;
start = clock();
init(0);
printf("%d\n",np);
search(0);
finish = clock();
printf("%d %d",n,(int)((finish-start)));
}

/*有些习惯不大好。。可读性可能有点低。。

我用的编译器的int是4位的，N=5，D=8时会超出范围，这个没作处理*/

在 09-11-28，吕宗庭<lvzon...@gmail.com> 写道：

[张龙攀]

那人不是ACM基地的

[吕宗庭]

MAT WETU 这个人吗？我是链表实现的。要是acm基地的话就跟我联系一下，我可想去里面看看了，里面很多牛人呀。

On 11月28日, 下午9时48分, 张龙攀 <zhanglong...@gmail.com> wrote:
> 那人不是ACM基地的[?][?][?]
>
> 331.gif
> < 1K查看下载

[MAT WETU]

我不是啊…我才大一…刚才你讲的矩阵那个，没学过，完全不懂

在 09-11-28，吕宗庭<lvzon...@gmail.com> 写道：
>

[吕宗庭]

我当时就没凑出来 我给忘了怎么凑的了，后来我才想起来的。等你学了矩阵就会了。

On 11月29日, 上午12时10分, MAT WETU <matw...@gmail.com> wrote:
> 我不是啊...我才大一...刚才你讲的矩阵那个，没学过，完全不懂
>
> 在 09-11-28，吕宗庭<lvzongt...@gmail.com> 写道：

[张龙攀]

坐第一排的那个人不是ACM基地的…… 吕大讲得很好  ，很强大
ACM基地 的QQ群号68894580

[吕宗庭]

我知道了，那个人我以前没见过只见过照片还是低着头弹吉他的，没见过正脸昨天看错了。-_-|||!。群我已经加进去了，谢谢你。

On Nov 29, 3:07 pm, 张龙攀 <zhanglong...@gmail.com> wrote:
> 坐第一排的那个人不是ACM基地的...... 吕大讲得很好 ，很强大
> ACM基地 的QQ群号68894580

[MAT WETU]

是时候了…

在 09-11-28，吕宗庭<lvzon...@gmail.com> 写道：

[吕宗庭]

#include<iostream>
#include<ctime>
//#include<fstream>
using namespace std;

#define VERY_BIG 1<<16
#define N 5
#define D 5


struct Square
{
int num[5][5];
int rowcount[5];
int colcount[5];
//int N;
Square(int matrix_size)
{
//N=matrix_size;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
num[i][j]=0;
}
int get_grid(int row,int col)
{
return num[row][col];
}

int getcol(int col)
{
int res=0;
for(int i=0;i<N;i++)
{
res*=10;
res+=num[i][col];
}
return res;
}
int getrow(int row)
{
int ret=0;
for(int i=0;i<N;i++)
{
ret*=10;
ret+=num[row][i];
}
return ret;
}
void setrow(int row,int n)
{
for(int i=0;i<N;i++)
{
num[row][4-i]=n%10;
n/=10;
}
}
void setcol(int col,int n)
{
for(int i=0;i<N;i++)
{
num[4-i][col]=n%10;
n/=10;
}
}
void setgrid(int row,int col,int n)
{
num[row][col]=n;
}
void show()
{
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cout<<num[i][j];
}
cout<<endl;
}
cout<<endl;
}
};


int valid_num[VERY_BIG];
int valid_count;

int cache3[9][1024];
int n_cache3[9];

int cache135[9][9][9][128];
int n_cache135[9][9][9];

int cache13[9][9][1024];
int n_cache13[9][9];

int n_cache12345[9][9][9][9][9];

int mark[9][9][9][9][9][9][9][9][9];

Square s(5);
void get_valid_num(int total,int deep,int pad)
{
deep--;
if(deep==0)
{
pad=pad*10+total;
valid_num[valid_count++]=pad;
return ;
}

for(int i=0;i<=total;i++)
{
get_valid_num(total-i,deep,pad*10+i);
}
}

void get_cache()
{
for(int i=0;i<valid_count;i++)
{
int digit=valid_num[i]%10;
int tens=valid_num[i]/10; tens%=10;//取得十位
int hundreds=valid_num[i]/100; hundreds%=10;//取得百位
int thousands=valid_num[i]/1000; thousands%=10;//取得千位
int myria=valid_num[i]/10000; myria%=10;//取得万位

int& i_cache3=n_cache3[hundreds];
cache3[hundreds][i_cache3++]=valid_num[i];

int& i_cache135=n_cache135[myria][hundreds][digit];
cache135[myria][hundreds][digit][i_cache135++]=valid_num[i];

int& i_cache13=n_cache13[myria][hundreds];
cache13[myria][hundreds][i_cache13++]=valid_num[i];

n_cache12345[myria][thousands][hundreds][tens][digit]++;
}
}

bool test (_int64 &total)
{
int grid22=s.get_grid (2,2);
int grid21=s.get_grid (2,1);
int grid20=s.get_grid (2,0);
int grid23=s.get_grid (2,3);
int grid24=s.get_grid (2,4);

int grid02=s.get_grid (0,2);
int grid12=s.get_grid (1,2);
int grid32=s.get_grid (3,2);
int grid42=s.get_grid (4,2);

int &value=mark[grid22][grid20][grid21][grid23][grid24][grid02]
[grid12][grid32][grid42];
if(mark[grid22][grid20][grid21][grid23][grid24][grid42][grid32]
[grid12][grid02]>0)
{
value=mark[grid22][grid20][grid21][grid23][grid24][grid42][grid32]
[grid12][grid02];
total+=value;
return true;
}
if(mark[grid22][grid24][grid23][grid21][grid20][grid02][grid12]
[grid32][grid42]>0)
{
value=mark[grid22][grid24][grid23][grid21][grid20][grid02][grid12]
[grid32][grid42];
total+=value;
return true;
}
if(mark[grid22][grid24][grid23][grid21][grid20][grid02][grid12]
[grid32][grid42]>0)
{
value=mark[grid22][grid24][grid23][grid21][grid20][grid02][grid12]
[grid32][grid42];
total+=value;
return true;
}

if(mark[grid22][grid02][grid12][grid32][grid42][grid20][grid21]
[grid23][grid24]>0)
{
value=mark[grid22][grid02][grid12][grid32][grid42][grid20][grid21]
[grid23][grid24];
total+=value;
return true;
}
if(mark[grid22][grid42][grid32][grid12][grid02][grid20][grid21]
[grid23][grid24]>0)
{
value=mark[grid22][grid42][grid32][grid12][grid02][grid20][grid21]
[grid23][grid24];
total+=value;
return true;
}
if(mark[grid22][grid02][grid12][grid32][grid42][grid24][grid23]
[grid21][grid20]>0)
{
value=mark[grid22][grid02][grid12][grid32][grid42][grid24][grid23]
[grid21][grid20];
total+=value;
return true;
}
if(mark[grid22][grid42][grid32][grid12][grid02][grid24][grid23]
[grid21][grid20]>0)
{
value=mark[grid22][grid42][grid32][grid12][grid02][grid24][grid23]
[grid21][grid20];
total+=value;
return true;
}

return false;
}

int main()
{
// int N=5;

_int64 total=0;


time_t old_time=clock();
get_valid_num(D,N,0);
get_cache();

for(int m=0;m<valid_count;m++)
{
s.setrow(2,valid_num[m]);
int grid22=s.get_grid (2,2);
for(int n=0;n<n_cache3[grid22];n++)
{
s.setcol(2,cache3[grid22][n]);
if(test(total)==true)
continue;
int grid20=s.get_grid (2,0);
int grid24=s.get_grid (2,4);
for(int i=0;i<n_cache3[grid20];i++)
{
s.setcol (0,cache3[grid20][i]);
if(n_cache13[s.get_grid (0,0)][s.get_grid (0,2)]==0||
n_cache13[s.get_grid (1,0)][s.get_grid (1,2)]==0||
n_cache13[s.get_grid (3,0)][s.get_grid (3,2)]==0||
n_cache13[s.get_grid (4,0)][s.get_grid (4,2)]==0)
continue;
for(int j=0;j<n_cache3[grid24];j++)
{
s.setcol (4,cache3[grid24][j]);
if(n_cache135[s.get_grid (0,0)][s.get_grid (0,2)][s.get_grid
(0,4)]==0)
break;
if(n_cache135[s.get_grid (4,0)][s.get_grid (4,2)][s.get_grid
(4,4)]==0)
continue;
for(int p=0;p<n_cache135[s.get_grid (0,0)][s.get_grid (0,2)]
[s.get_grid (0,4)];p++)
{
s.setrow (0,cache135[s.get_grid (0,0)][s.get_grid (0,2)]
[s.get_grid (0,4)][p]);
if(n_cache13[s.get_grid (0,1)][s.get_grid (2,1)]==0||
n_cache13[s.get_grid (0,3)][s.get_grid (2,3)]==0)
continue;
for(int q=0;q<n_cache135[s.get_grid (4,0)][s.get_grid(4,2)]
[s.get_grid (4,4)];q++)
{
s.setrow (4,cache135[s.get_grid (4,0)][s.get_grid(4,2)]
[s.get_grid (4,4)][q]);
if(n_cache135[s.get_grid (0,1)][s.get_grid (2,1)][s.get_grid
(4,1)]==0||
n_cache135[s.get_grid (0,3)][s.get_grid (2,3)][s.get_grid
(4,3)]==0||
n_cache135[s.get_grid (1,0)][s.get_grid (1,2)][s.get_grid
(1,4)]==0||
n_cache135[s.get_grid (3,0)][s.get_grid (3,2)][s.get_grid
(3,4)]==0)
continue;
for(int r=0;r<n_cache135[s.get_grid (1,0)][s.get_grid (1,2)]
[s.get_grid (1,4)];r++)
{

s.setrow (1,cache135[s.get_grid (1,0)][s.get_grid (1,2)]
[s.get_grid (1,4)][r]);
int grid31=D-s.get_grid (0,1)-s.get_grid (1,1)-s.get_grid
(2,1)-s.get_grid (4,1);
if(grid31<0) continue;
int grid33=D-s.get_grid (0,3)-s.get_grid (1,3)-s.get_grid
(2,3)-s.get_grid (4,3);
if(grid33<0) continue;

if(grid33+grid31+s.get_grid (3,0)+s.get_grid (3,2)+s.get_grid
(3,4)!=D)
continue;
s.setgrid (3,1,grid31);
s.setgrid (3,3,grid33);
// s.show ();
total++;
mark[s.get_grid (2,2)][s.get_grid (2,0)][s.get_grid (2,1)]
[s.get_grid (2,3)]
[s.get_grid (2,4)][s.get_grid (0,2)][s.get_grid (1,2)]
[s.get_grid (3,2)][s.get_grid (4,2)]++;
}
}
}
}
}
}
}

printf("%d\n",total);
printf("耗时：%d\n",clock()-old_time);
return 0;
}

[吕宗庭]

我没看懂，同学们自己看一下吧，上次忘了让我同学给大家讲一下，上周六讲的我都晕了，很多事情都忘了。

[吕宗庭]

对了，我记性实在不好，谢谢MAT WETU提醒。

On 12月8日, 上午10时26分, MAT WETU <matw...@gmail.com> wrote:
> 是时候了...
>
> 在 09-11-28，吕宗庭<lvzongt...@gmail.com> 写道：

> ...
>
> 阅读更多 >>

[MAT WETU]

辛苦了 吕大！
。。这样大的数组 足以秒杀 内存。。周四 拿 学校 机子 试试。。

在 09-12-8，吕宗庭<lvzon...@gmail.com> 写道：

[吕宗庭]

他懒得建 数据结构 你有兴趣可以 改写一下 他的程序

On 12月8日, 下午3时42分, MAT WETU <matw...@gmail.com> wrote:
> 辛苦了 吕大！
> 。。这样大的数组 足以秒杀 内存。。周四 拿 学校 机子 试试。。
>

> 在 09-12-8，吕宗庭<lvzongt...@gmail.com> 写道：

> ...
>
> 阅读更多 >>