第4题我觉得可以用递归回朔的方法。
这样比穷举计算次数要少些，但是因为递归会使效率下降。

所以综合起来就不知道哪个优了！

我试了啊，报错了，我理解的：静态数组大小只能是常量。

但是确实在某些编译器上允许这样。
我机器上有3个，所以就测试了3次，dev-cpp中可以，vc不可以。

所以我疑惑。根据我目前所了解，可以设置大小只能用动态数组！

我大致看了下HJin对这个问题的解法，我如果写，我也会有个同样的问题，不仅这个问题，一切有关类似这样的递归回溯的问题都存在，比如皇后，比如我在46楼写那个题。

我很想看看kai你是怎么处理当n很大时的情况。当然，不要让程序一直运行个几天才算出来，呵呵~（我想的话）。

第三题:(算法来自第69楼)

#include "iostream.h"
#include "stdio.h"
#include "iostream.h"
#include "conio.h"
main()
{
char ch[11]={'T','J','1','2','3','4','5','6','7','8','9'};
char output[21][21];
int i,j,m=0;
int x=1;
while (x)
{
while (!((m>=3&&m<=21)))
{
step: printf("输入一个3到20之间的数:");
scanf("%d",&m);
}

for(i=m;i>=0;i--)
{
for(j=i;j<=m-i;j++)
{
output[i][j]=ch[i];
output[j][i]=ch[i];
output[m-i][m-j]=ch[i];
output[m-j][m-i]=ch[i];
}
}
for (i=0;i<m;i++)
{
for (j=0;j<m;j++)
{
cout<<output[i][j];
}
cout<<"\n";
}
cout<<"输入任意数字继续，输入0退出！";
scanf("%d",&x);
if (x!=0) goto step;
}
}

aipb2007,
对于第四题,我个人认为用递归不可行,只能用iterative 的方法. 递归的一个根本的弱点是对内存空间的不必要的开销,因为递归的多层运算的顺利进行是建立在这么一个基础上,即多层次的中间状态需要保留以便回溯计算.而反观iterative 的方法就不是这样, 某个中间状态可以用一个变量来保留,当进入第2层的时候, 第一层已经不存在,其运算结果由某个变量来保留以便下一层的计算需要,当第二层计算完毕后,变量予以更新. 当进入再下一层的时候,只有那个变量被传递到下一层,所以内存开销被节约了.

lisp 和 scheme 都是建立在recursive 这样一个运算方法上的编程语言, 其基本数据结构就是list, 一个list 可以看成 first 和 rest 的一个组成. 那么一个对于一个list 可行的递归算法就是 f(list) = g(first, f(rest)); 我非常反感lisp 这种限制自由思想的编程语言. 但我也承认递归思想是非常有用的一种思想.

恩...

学习了..

说的很有道理，但是递归对内存的开销并不都是不必要啊。难道所有的递归算法都可以被迭代取代而不用到栈？
期待你的solution，这样说不好懂。

呵呵

aipb2007,
代码在书写中, 已经写了一个class MyCounter, 这个class 很简单, 用一个char array 来完成对递增的信息存储. 使用的是100进制, 为的是输出的方便和节约内存空间.
下一个正在写的class 就是 LatinMatrix, 我的算法是这样的. 首先根据N 的大小, 初始一个string array 并统统赋初值: 1234...N, 通过一个check 函数来判断属于LatinMatrix 的那些string array 的组合. 判断的方法是这样的. 在第一个str不动的情况下, 通过 next_permutation(...); 变动第二个str, 然后调用我事先写好的一个函数findSameChar(...); 如果没有发现相同的字符,那么还是通过 next_permutation(...); 变动第三个str, 然后还是调用findSameChar(...); 来判断在纵向所新形成的字符串中有没有相同的字符, 如果还是没有那么继续下一层, 如果发现相同, 那么当前这一层的运算退出, 回到上一层.

next_permutation 有一个非常方便的地方,那就是一个不拉的, 一个不重复的展现所有可能.

不错，是个值得学习的地方

我要睡觉了，今天还有自己的事，先将局部代码传上来，大家可以看看是否对你的开发有所启发：
[CODE]
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class MyCounter
{
private:
enum{N = 10800};
char counter[N];
public:
MyCounter()
{
reset();
}
void reset()
{
for(int i = 0; i<N; i++)
{
counter[i] = 0;
}
}
void display()
{
int i = 0;
while(i<N && (int)counter[i]==0)
{
i++;
}
int first = i;
if(first == N)
cout<<"0";
else
cout<<(int)counter[first];
for(i = first+1 ; i<N; i++)
{
int n = (int)counter[i];

if(n == 0)
cout<<"00";
else if(n<10)
cout<<'0'<<n;
else
cout<<n;
}
}
void operator++()
{
for(int i = N-1; i>=0; i--)
{
int num = (int)counter[i];
if(num<99)
{
counter[i] = ++num;
break;
}
else
{
counter[i] = 0;
continue;
}
}
}
};
class LatinMatrix
{
private:
int n; // to indicate how many numbers we have
string * lmStr; // an string array to save all the init numbers
vector<string *>strPerm; // to save the all combination of numbers
int * pos; // pos[0] indicates the current position of the first line,
// pos[1] indicates the current position of the second line, and so on
MyCounter myCounter; // to save the count of LatinMatrix
public:
static bool findSameChar(const char * t)
{
string temp;
int length = strlen(t);
for(int i = 0; i<length; i++)
temp += t[i];
for(i = 0; i<length; i++)
{
int pos = temp.find(t[i]);
if(pos != i)
return true;
}
return false;
}
static void integerToString(string & str, const int & t)
{
ostringstream oss;
oss << t;
str = oss.str();
}
LatinMatrix(int n)
{
this->n = n;
lmStr = new string[n];
pos = new int[n];
string temp;
for(int i = 0; i<n; i++)
{
pos[i] = 0; // init all line's current position to 0
integerToString(temp, i+1);
lmStr[i] = string(temp);
}
sort(lmStr, lmStr+n);
strPerm.push_back(lmStr);
while(next_permutation(lmStr, lmStr+n))
{
string * newLmStr = new string[n];

for(int j = 0; j<n; j++)
{
newLmStr[j] = lmStr[j];
}
strPerm.push_back(newLmStr);
}
}
void trytoFindLatinMatrix() // when I find a LatinMatrix, I print the matrix and increment the count
{
// the method to find the LatinMatrix is:
// first I get the first string array
// and then I get the second string array
// and then I check, whether this second string array is valid,
// when yes, then go with the third string array
// otherwise, I go a step back,
// something must be updated within this process, this is the pos value
// pos records the value of string array of permutation,
// so that I can follow the trace of the process

}
~LatinMatrix()
{
delete [] lmStr;
delete [] pos;
}
void display()
{
for(int i = 0; i<strPerm.size(); i++)
{
string * pStr = strPerm[i];
for(int j = 0; j<n; j++)
{
cout<<pStr[j]<<" ";
}
cout<<endl;
}
}
};
int main()
{
LatinMatrix lm(5);
lm.display();
return 0;
}
[/CODE]