posts - 274, comments - 1258, trackbacks - 0

今日某ACM群上某君出了一道颇不寻常的题：“如何写一个递归函数reverse(char* s)来使s倒序？”
　　不寻常的题自然应该用不寻常的解法，我即兴写了一个：

char* reverse(char* s,int i=0){

char c=s[i];

return c ? &(*reverse(s,i+1)=c)+1 : s;

}

两行“搞掂”，是不是很好玩呢？

　你有没有更简洁或者更特别的算法？欢迎一齐探计~~
P.S.：本人觉得唯一的美中不足是它虽然可以按reverse(char* s)来调用，但毕竟实际上的原型是char* reverse(char* s,int i=0)，不过我基本可以肯定不可能使用单形参在O(n)时间内解决本问题。

posted on 2007-01-01 01:17 踏雪赤兔阅读(1626) 评论(9) 编辑收藏引用所属分类: 玩转编程

FeedBack:

# re: 递归实现倒序？

2007-11-21 15:23 | berry

/* reverse: reverse string s in place; exercise 4-13 */
我是这样想这个递归的
1、首先把s分为s[0]和rest
2、把rest reverse
3、交换s[0]和rest
的确很难在O(n)时间解决

void reverse(char s[])
{
char c;
int i;

if (s[0] == '\0' || s[1] == '\0')
return;
c = s[0];
reverse(s + 1);
for (i = 1; s[i] != '\0'; i++)
s[i - 1] = s[i];
s[i - 1] = c;
} 回复更多评论

# re: 递归实现倒序？

2007-11-23 18:14 | 踏雪赤兔

@berry
你的解法很有意思哦～

不过我想了一下，原来是可以Ｏ(n)解决的,不过需要三行:

char* reverse(char* s){

static int i=0;

char c=s[i++];

return c ? &(*reverse(s)=c)+1 : (i=0,s);

}

大家看得明我的算法吗?

回复更多评论

# re: 递归实现倒序？

2008-03-04 20:14 | 鹤峰

看看这个怎么样？
-----------------------------------
void reverse(const char* const sPtr)
{
if(sPtr[0]=='\0')
return;
else
reverse(&sPtr[1]);
}
-----------------------------------

回复更多评论

# re: 递归实现倒序？

2008-03-04 22:10 | 踏雪赤兔

楼上的不行吧……你都没有对字符串进行写操作，又怎样倒序呢？回复更多评论

# re: 递归实现倒序？

2008-03-05 11:38 | 鹤峰

一本书上这么写的，
我也是感到纳闷呢，
所以抄下来，给大家看下。回复更多评论

# re: 递归实现倒序？

2008-03-05 12:11 | 踏雪赤兔

呵呵~尽信书不如无书啊~ 回复更多评论

# re: 递归实现倒序？

2008-03-06 17:28 | richardxx

其实完全有办法只传一个参数在O(n)解决。

用一个queue T;

void reverse( char* s )
{
if ( *s == 0 ) return;

push_queue(*s, T )
reverse( s + 1 );
*s = pop_queue( T );
}
回复更多评论

# re: 递归实现倒序？

2008-03-06 17:30 | richardxx

ms 我方法犯规了....
不用理我回复更多评论

# re: 递归实现倒序？

2012-11-30 19:24 | 求答案

我说大哥，我就一大一的水平耶！看不懂，能用最笨的方法不？@踏雪赤兔
回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。