用C语言写这样一个程序

楼主你好。

代码如下：

#include <stdioh>

#include <mathh>

void output(int array, int n)

{

int i;

for(i=0;i<n;i++)

printf("%3d",array[i]);

printf("\n");

}

void swap(int a,int b)

{

int t;

t=a;

a=b;

b=t;

}

int is_square_number(int array){

int num=0, i;

for(i=0;i<3;i++){

num=10;

num+=array[i];

}

if(num == pow((int)sqrt(num),2))

return 1;

return 0;

}

void permutate(int array, int n, int t)

{

int i;

if(t > 0 && t % 3 == 0 && !is_square_number(array + t - 3)){

return;//回溯

}

if(t==n)   //输出

{

output(array, n);

return ;

}

for(i=t;i<n;i++)

{

swap(&array[i],&array[t]);   //交换

permutate(array, n, t+1);

swap(&array[t],&array[i]);   //换回

}

}

int main(){

int num[]={1,2,3,4,5,6,7,8,9};

permutate(num, sizeof(num)/sizeof(int), 0);

return 0;

}

运行结果：

如果你把9删去，只留8个数字，结果如下最后两位就不判断是否是平方数了，如果你还想判断，稍作修改即可：

为了描述问题的某一状态，必须用到该状态的上一状态，而描述上一状态，又必须用到上一状态的上一状态……这种用自已来定义自己的方法，称为递归定义。形式如 f(n) = n f(n - 1), if n = 0, f(n) = 1

从问题的某一种可能出发，搜索从这种情况出发所能达到的所有可能，当这一条路走到“尽头”的时候，再倒回出发点，从另一个可能出发，继续搜索。这种不断“反悔”寻找解的方法，称作“回溯法”。

递归法好比是一个军队要通过一个迷宫，到了第一个分岔口，有 3 条路，将军命令 3 个小队分别去探哪条路能到出口，3 个小队沿着 3 条路分别前进，各自到达了路上的下一个分岔口，于是小队长再分派人手各自去探路——只要人手足够（对照而言，就是计算机的堆栈足够），最后必将有人找到出口，从这人开始只要层层上报直属领导，最后，将军将得到一条通路。所不同的是，计算机的递归法是把这个并行过程串行化了。

而回溯法则是一个人走迷宫的思维模拟，其实是一种试探，走错了倒回来，继续走。该方法放弃关于问题规模大小的限制，并将问题的方案按某种顺序逐一枚举和试验。发现当前方案不可能有解时，就选择下一个方案，倘若当前方案不满足问题的要求时，继续扩大当前方案的规模，并继续试探。如果当前方案满足所有要求时，该方案就是问题的一个解。 放弃当前方案，寻找下一方案的过程称为回溯。

递归算法依赖与前一步的结果，它的结果来源于一条主线，是确定的，而不是试探的结果，这就是其与回溯的区别，而在很多情况下，回溯与递归算法是在一起使用的。

递归会出现在子程序中自己调用自己或间接地自己调用自己。最直接的递归应用就是计算连续数的阶乘，计算规律：n! = (n - 1)! n。观察阶乘计算的规律，前一个数结成的结果可以直接被应用到后一个数结成的计算中。

回溯是一种算法思想，可以用递归实现。通俗点讲回溯就是一种试探，类似于穷举，但回溯有“剪枝”功能，比如求和问题。给定 7 个数字，1 2 3 4 5 6 7 求和等于 7 的组合，从小到大搜索，选择 1 + 2 + 3 + 4 = 10 > 7，已经超过了 7，之后的 5 6 7 就没必要在继续了，这就是一种搜索过程的优化。比如 8 皇后问题。

之前读过《算法导论》（常被简称为CLRS，下同），读这本是想换个角度来研究下算法。虽然很多东西已经通过前者有所了解，这里就谈谈二者的不同之处。 一方面，数学性的推导和证明还是CLRS比较擅长，后者大多数情况只是尽量做到让读者能够理解而已，这一点在上面的评论“可以作为浅显易懂的入门教材”一文也指出了，我就不再细谈了。 另一方面，本书对于实践是非常重视的，在介绍算法的同时不停留在代码和思路本身，同时也会讲一些实践细节，甚至通过专门的章节，也即书中的War Story来加深读者对算法的理解。不过很惭愧的是，由于时间有限，War Story我基本没读几篇，浅尝辄止而已。 更有指导意义的是，书中的第二部分收集和归类大量的算法问题，并对这些问题的求解做出了分析。这个所谓的分析就是，把问题具体化，在不同情况下都选择相应的最优算法。尽管没有给出可以直接用来“复制-粘贴”的代码，但这样做明显比“笼统地写出一个问题—给出一个唯一答案”的做法强得多。当然，通过对于第一部分算法介绍的阅读，第二部分可以先做泛读，遇到具体问题时再来查阅对应的解决方案的指导，此时还能根据给出的参考文献进行深入的阅读。这种细致全面的安排可以看出作者的用心之处。 再谈谈一些其他的读书收获吧，下面是我印象比较深的地方： 1CLRS在介绍DFS时写成了一个子程序，后面的拓扑排序、强联通分支等使用到DFS的算法将其调用；而本书的DFS是直接写成了一个框架（这种做法你还会在回溯法、近似字符串匹配等地方看到），通过修改其不同的子函数来完成不同的功能如拓扑排序、强联通分支。我不评价哪种更好，只是CLRS版的DFS先入为主，我以CLRS版为准。 2在读完《算法设计手册》的第7章回溯法之前，我对回溯法的认知完全是云里雾里。虽然也写过不少回溯法的程序，甚至做过剪枝处理，但它们都局限于具体问题的求解，完全没有一个全局性的概念。这本书向我展示了回溯法的框架，可以套用至很多回溯法程序（然后再进行简化），一举心中的廓清迷雾，这个章节很建议阅读。 3本书第一部分每个章节的练习题中包含了面试题部分，起初还不怎么注意，直到被有些难住时，google其解法发现居然是货真价实的google、ms、amazon面试题！如果即将进行参加招聘面试笔试，这部分题目还是值得做做的。虽然通过作者的网页和google、stackoverflow等可以找到大部分的解答，不过我还是抽空亲自把这部分全部题目做完并进行了总结，有兴趣的读者可以参照文末链接。 下面是几个相关链接： 原书勘误表：>

以上就是关于用C语言写这样一个程序全部的内容，包括:用C语言写这样一个程序、递归与回溯、THE ALGORITHM DESIGN MANUAL怎么样等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！