之前遇见这个问题，非常费劲地理解了，并写出代码，然后过段时间，再遇见这个问题，又卡住了，如此反反复复两三次，才发现自己对递归的理解依然很肤浅。今天无聊，重温《算法：c语言实现》一书，又遇见了这个问题，心头一紧，担心要费些时间才能写出代码，没想到的是，再理解了书中对递归的定义，蒙住源代码动手写，发现很快就写出来了，甚至都没有费力去模拟整个汉诺塔移动过程，只是根据递归的要领（数学归纳法）分析了一下问题，便得出了一个递归形式，照此写代码，竟然没错。由此也醒悟到，很多时候，用递归写代码并不难，但却常常受困于一种恐惧和自惭的心理而畏葸不前。
下面是源代码，在此之前，阐述一下自己对递归的理解，&对于我们编写的每个递归函数，都必须能够进行有效的归纳证明。&这是《算法：c语言实现》中让我恍然大悟的一句话。这句话的意思是：根据数学归纳的形式，总是能够倒推出完整的递归形式的。数学归纳法的形式非常清晰，其过程通常为先试验初始条件n=1，验证某假设或公理是否成立，再设n=k，假设成立，由n=k推出n=k+1的时候，该假设是否成立。具体分析汉诺塔问题，其最原始的思想是：从某根桩移动N-1个盘子到后边桩上，接着以此类推，移动剩下的第N个盘到某一个桩，再将那N-1个盘移动到第N个盘所在的桩。
#include &stdio.h&
#include &stdlib.h&
#define ALL
enum DIRECT{left = 1, mid = 2, right = 3};
void hanoi(int N, int pos, int dst);
void shift(int N, int pos, int direct);
int main()
void hanoi(int N,
int pos, int dst)
if( 0 == N)
hanoi(N-1, pos, ALL-dst-pos);
shift(N, pos, dst);
hanoi(N-1, ALL-dst-pos, dst);
void shift(int N, int pos, int direct)
printf("move %d from pillar %d to pillar %d\n", N, pos, direct);
　众所周知，&递归程序总是可以转换成执行相同计算的非递归性程序。& 递归到非递归的转换，由堆栈来实现，此处不再赘述，感兴趣的可以看看这个网站：/posts/3.4.html
阅读(...) 评论()利用动态规划法求解旅行商问题（TSP）的C语言实现（一）
某推销员要从城市 出发，访问其它城市，，，各一次且仅一次，最后返回。为各城市间的距离矩阵。
问：该推销员应如何选择路线，才能使总的行程最短？
问题分析：记n个城市为1，2，，n.
对于给定的集合S属于{2,3,4,...n}
和元素k属于S，记C（S，k）是由城市1出发，遍历S中每个城市恰好一次，最后终止在城市k的最优费用.
则当S中只有一个元素k时，C（S，k）= D[1][k];
当S中有多于一个元素时， C（S，k）=
这一方程的求解要求对一切给定大小的集合S及S中的每个可能的元素k，计算 C（S，k）的值.
当S等于{2,3,4,...n}时，如果C（S，k）的值对任意属于S的元素k都已经通过计算得到，则最优环游的最费用为
算法复杂度分析：计算中所需的加法和比较的次数等于O(n^2*2^n)
空间复杂度：O(n*2^n)
算法改进：通过改进集合操作降低比较次数，利用二进制表示集合。确定元素k是否在集合S中的比较次数为1，从而降低了时间复杂度到O(n2^n)
#define MAX_N 10
(int)pow((double)x,(double)y);
//2 bits for vector
//struct path *lastN
path *lastN
struct path
struct path
*D[MAX_N];
if((mypow(2,i-1)&set)&0)
insertSet(int
if(inSet(i,set)==0)
set|mypow(2,i-1);
deleteSet(int
if(inSet(i,set))
~(mypow(2,i-1))&
print_path(struct path *p)
if(p==NULL)
printf("1");
print_path(p-&lastNode);
printf("-&%d",p-&current+1);
tsp(int n,
(*a)[MAX_N])
struct path
path *lastN
D[1] = NULL;
//当S中只有一个元素k时，C(S，k)=
temp = malloc(sizeof(struct path));
temp-&current =
temp-&cost = a[0][i];
temp-&lastNode = NULL;
temp-&next = D[1];
temp-&set = mypow(2,i-1);
//循环n-2遍,每次构造集合包含J个元素的子集
D[j] = NULL;//子集元素个数为J个的所有C(S,k)的链表的头
//利用address保存C(S,K)的信息。即保存相应struct
path结构的地址
address = malloc(sizeof(struct path
*)*mypow(2,n-1));
bzero(address,sizeof(&address));
p = D[j-1];
while(p!=NULL)
//判断元素i是否已经在p-&set集合中
//如果在这个集合中了不能利用元素i和p-&set构建新的子集了。
//因为每个子集中的元素是唯一
if(inSet(i,p-&set)==0)
//当S中有多于一个元素时,C(S，k)等于任意一个属于S-k集合的子集m，C(s-k,m)+d(m,k)中最小的一个，
set = insertSet(i,p-&set);
//判断C(S,k)是否已经计算过
//如果计算过，比较cost值，取小的
//不存在的话，就创建一个结构体struct
path保存C(S,k)的信息
if(address[set]!=NULL&&address[set]-&current==i)
cost = p-&cost + a[p-&current][i];
address[set]-&cost)
address[set]-&cost =
address[set]-&lastNode =
temp = malloc(sizeof(struct path));
temp-&current =
temp-&cost = p-&cost +
a[p-&current][i];
temp-&set =
temp-&lastNode =
temp-&next = D[j];
address[set]=
free(address);
//这一方程的求解要求对一切给定大小的集合S及S中的每个可能的元素k，计算 C(S，k）的值
//当S等于{2,3,...n}时，如果C(S，k)的值对k属于S都已经通过计算得到，则最优环游的最小费用为
//C(S,k)+d(k,1)中最小的一个。
mincost = -1;
p = D[n-1];
if(mincost==-1 ||
mincost & p-&cost + a[p-&current][0])
mincost = p-&cost + a[p-&current][0];
lastNode =
//打印计算结果
printf("mincost=%d\n",mincost);
//打印路径
print_path(lastNode);
printf("-&1\n");
argc, char
a[MAX_N][MAX_N]=
{ { 0, 10, 20, 30, 40, 50},
{12, 0, 18, 30, 25, 21},
{23, 19, 0, 5, 10, 15},
{34, 32, 4, 0, 8, 16},
{45, 27, 11, 10, 0, 18},
{56, 22, 16, 20, 12, 0}
EXIT_SUCCESS;
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。探讨一个C语言的问题_单片机吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：116,968贴子：
探讨一个C语言的问题收藏
连续几天，一个软I2C接口怎么都不动。昨天没办法就拿出示波器来看波形了。原先折腾这个I2C好多次了，软硬都弄过，没有这次这么讨厌。降速，把所有命令简化到只发启动，然后从机地址，然后停止。在示波器上看到了，本来应该是0XB8，却始终是0XF3。改程序语句，加入更多的延时，没效果。到更改一个IF语句，把if ((data&0x80)==1)修改为if (data&0x80)忽然间就不出错了，示波器上看到了0xb8的波形，从机也正常应答了。懊恼之余，我想明白了C语言在这款编译器上并非是绝对通用的。条件分支语句的条件是一个逻辑量，在片机上只有0和非0两种状态。data&0x80作为逻辑运算，一般C编译器都是直接把这东西当做逻辑量，然后非0就是1。那么，前面那个句子就不会出错。可我的编译器应该是把data&0x80当作数学运算了，按位与，得到的结果要么是0，要么是0x80。于是，这个结果永远不会等于1。后面那个语句即便是数学运算，按位与，可if条件分支的条件天然就是个逻辑量，只有0和非0两种状态，于是就不会出错了。这个教训拿出来跟各位分享。或许你不会碰到这样的问题，但是你若肯记下这件小事，将来或许就能免犯跟我一样的错误了。
刘备：军师，此次伐魏你有何妙计？
&&是逻辑与，&是按位与
或者data&0x80==0x80
不过按你修改的更好
本来就不等于1，是等于128
你写==1这结果当然结果逻辑是0，没什么问题
没玩过单片机，但是if语句里那个判断确实最好是0或非0 的判断
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或&&/&&&&/&&
文章列表：
推荐文章 TOP10后使用快捷导航没有帐号？
查看: 1362|回复: 9
求助一个C语言算法问题(类似于置换)
在线时间368 小时
威望398 分
芯币4060 枚
TA的帖子TA的资源
一粒金砂（高级）, 积分 398, 距离下一级还需 102 积分
一粒金砂（高级）, 积分 398, 距离下一级还需 102 积分
本帖最后由 cl17726 于
12:59 编辑
实现一个函数,函数的原型是这样的:
int conv(int b);
如果输入10,输出1,输入9,输出2,输入8,输出3,输入2,输出9,输入1,输出10.. 如此类推,不能用查表,因为数值范围很大,这个应该怎么做呢?求助
在线时间2 小时
TA的帖子TA的资源
一粒金砂（初级）, 积分 0, 距离下一级还需 5 积分
一粒金砂（初级）, 积分 0, 距离下一级还需 5 积分
输入一1，不是输出10？
是的,就是这样置换过来&
在线时间368 小时
威望398 分
芯币4060 枚
TA的帖子TA的资源
一粒金砂（高级）, 积分 398, 距离下一级还需 102 积分
一粒金砂（高级）, 积分 398, 距离下一级还需 102 积分
输入一1，不是输出10？
是的,就是这样置换过来
在线时间1250 小时
威望6087 分
芯币18904 枚
E金币300 枚
TA的帖子TA的资源
你这个要是完全没有规律就无法提出算法，逻辑化简可以让表小些但也要查表，别无它解，这不是C的问题。
在线时间1701 小时
威望416 分
芯币3251 枚
E金币174 枚
TA的帖子TA的资源
一粒金砂（高级）, 积分 416, 距离下一级还需 84 积分
一粒金砂（高级）, 积分 416, 距离下一级还需 84 积分
只看前三个还好说 他们的和都是11& & 输出=11-输入& & 后面的两个规律就不一样了 输出=10-输入
在线时间1109 小时
威望1952 分
芯币11243 枚
E金币716 枚
TA的帖子TA的资源
return ABS(a-11)
本帖子中包含更多资源
才可以下载或查看，没有帐号？
在线时间1109 小时
威望1952 分
芯币11243 枚
E金币716 枚
TA的帖子TA的资源
return -(a-11)?
本帖子中包含更多资源
才可以下载或查看，没有帐号？
在线时间885 小时
威望4179 分
芯币5101 枚
E金币327 枚
TA的帖子TA的资源
五彩晶圆（中级）, 积分 4179, 距离下一级还需 1821 积分
五彩晶圆（中级）, 积分 4179, 距离下一级还需 1821 积分
楼主，您主要这个是找到规律，才好设计您的算法，那么语句的实现也就简单了。现在白纸上找到规律哈，我建议。
在线时间971 小时
威望4106 分
芯币6516 枚
E金币1592 枚
TA的帖子TA的资源
五彩晶圆（中级）, 积分 4106, 距离下一级还需 1894 积分
五彩晶圆（中级）, 积分 4106, 距离下一级还需 1894 积分
恕我眼拙，我怎么看着你给出的输入输出，和都是11呢？&&输入的范围是多少啊。主要是找规律，和C语言算法没什么关系。
在线时间105 小时
威望243 分
芯币478 枚
TA的帖子TA的资源
一粒金砂（高级）, 积分 243, 距离下一级还需 257 积分
一粒金砂（高级）, 积分 243, 距离下一级还需 257 积分
6楼不是正解吗？6楼不是正解吗？6楼不是正解吗？6楼不是正解吗？6楼不是正解吗？
论坛测评队员
Powered by
逛了这许久，何不进去瞧瞧？