挑战递归...

发信人: knuth (Knuth), 信区: Program 标题: [合集] 挑战递归… 发信站: 侏罗纪公园 (Fri Aug 1 17:27:37 2008), 站内

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Thu Nov 30 13:49:23 2006) 提到:

我想大家写程序到一定层度都会觉得递归很有意思。其实，我们接触很多算法都可以用递归实现的——虽然很多可能没有必要。

举个例子：

从数组顺序查找一个值应该很简单。但是，也可以从递归角度来实现！我们第一次先比较第一个，然后再递归查找剩下的数组。

下面我先给个小例子开个头：假设要把一个十进制的数逆序，119 -> 911

代码如下：

int fx(int n, int k)
{
    return (n)? fx(n/10, k*10+(n%10)): k;
}

main()
{
    printf("%d\n", fx(119, 0));
}

下面由大家来接啊_

char *reverse(char *str);是将str逆序后返回。要求用递归实现…

☆─────────────────────────────────────☆

IPconfig (readme.txt) 于 (Thu Nov 30 17:01:54 2006) 提到:

一直不喜欢用递归. 使用递归时,计算机做了什么,其实我们并不是很了解,也谈不上控制了. 我宁愿自己构造堆栈,用循环.

【在 knuth (Knuth) 的大作中提到: 】

我想大家写程序到一定层度都会觉得递归很有意思。

其实，我们接触很多算法都可以用递归实现的——虽然很多可能没有必要。

举个例子：

……………….

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Thu Nov 30 18:26:46 2006) 提到:

char *reverse(char *str);是将str逆序后返回。

要求用递归实现…

……………….

期待中…

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Thu Nov 30 18:37:17 2006) 提到:

【在 IPconfig (readme.txt) 的大作中提到: 】

一直不喜欢用递归.

使用递归时,计算机做了什么,其实我们并不是很了解,也谈不上控制了.

我宁愿自己构造堆栈,用循环.

递归其实是和函数调用的原理一样的（在C中）。函数调用参数要进栈，返回要出栈，因此，可以隐式地使用系统本身的栈…

关键是代码看起来简单明了…

☆─────────────────────────────────────☆

TomasMao (毛豆) 于 (Fri Dec 1 10:07:00 2006) 提到:

reverse(char *str,int left,int right)
{
    char tmp;
    tmp = str[left];
    str[left] = str[right];
    str[right] = tmp;
    left++;
    right--;
    if(right > left)
        reverse(str,left,right);
}

【在 knuth (Knuth) 的大作中提到: 】

我想大家写程序到一定层度都会觉得递归很有意思。

其实，我们接触很多算法都可以用递归实现的——虽然很多可能没有必要。

举个例子：

……………….

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Fri Dec 1 11:51:57 2006) 提到:

}

……………….

}

……………….

}

……………….

}

……………….

}

……………….

}

……………….

}

……………….

}

……………….
    reverse(str,left,right);
}

……………….

对ls的程序有个疑问：

left/right是str的下标还是str的内容？

如果left/right是下标，那么交换的时候怎么只交换left/right的值？如果left/right是内容，那传递str参数是否还有必要？

☆─────────────────────────────────────☆

TomasMao (毛豆) 于 (Fri Dec 1 14:22:15 2006) 提到:

下标，写错了

【在 knuth (Knuth) 的大作中提到: 】

reverse(char *str,int left,int right)

{

char tmp;

……………….

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Fri Dec 1 14:32:54 2006) 提到:

【在 TomasMao (毛豆) 的大作中提到: 】

下标，写错了

那现在继续增加挑战的难度^_^

函数的原形为：

char *reverse(char *str);

要求用递归实现该函数，但不能自行增加参数。

☆─────────────────────────────────────☆

TomasMao (毛豆) 于 (Fri Dec 1 14:45:11 2006) 提到:

可以有全局变量吗

【在 knuth (Knuth) 的大作中提到: 】

那现在继续增加挑战的难度^_^

函数的原形为：

char *reverse(char *str);

……………….

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Fri Dec 1 15:01:40 2006) 提到:

【在 TomasMao (毛豆) 的大作中提到: 】

可以有全局变量吗

那个不管，总之用户只是把它当作一个函数使用。

main()
{
    char s1[] = "abc";
    char s2[] = "abc";
    printf("%s -> %s", s1, reverse(s2));
}

☆─────────────────────────────────────☆

debug (Leaving) 于 (Fri Dec 1 17:26:59 2006) 提到:

/*
 * reverse.cpp
 * IDE: DEV-CPP
 * <zmstone#gmail.com>
 */
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

void reverse(char* s, int k){
    if(k>1){
        reverse(s+1, k-2);
        swap(*s, s[k]);
    }
}

int main(){
    char str[] = "abcdefghijklmno";
    printf("%s\n", str);
    reverse(str, strlen(str)-1);
    printf("%s\n", str);
    while(1);
    return 0;
}

【在 IPconfig (readme.txt) 的大作中提到: 】

一直不喜欢用递归.

使用递归时,计算机做了什么,其实我们并不是很了解,也谈不上控制了.

我宁愿自己构造堆栈,用循环.

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Fri Dec 1 17:35:59 2006) 提到:

【在 debug (Leaving) 的大作中提到: 】

/*

* reverse.cpp

* IDE: DEV-CPP

}

……………….

}

……………….
 reverse(s+1, k-2);
      swap(*s, s[k]);
  }
}

……………….

楼上程序还没有完全达到要求哦_

char *reverse(char* str);

函数只有1个参数，且返回逆序后的字符串。

☆─────────────────────────────────────☆

debug (Leaving) 于 (Fri Dec 1 17:46:31 2006) 提到:

按你的要求来应该这样: /* * reverse.cpp * IDE: DEV-CPP * */ #include #include #include using namespace std;

void reverse(char *s, int k){
    if(k<0) return;
    reverse(s+1, k-2);
    swap(*s, s[k]);
}
char* reverse(char* s){
    char* ret = strdup(s);
    reverse(ret, strlen(ret)-1);
    return ret;
}
int main(){
    char *tmp, str[256];
    while(1 == scanf("%s", str)){
        printf("%s -> %s\n", str, tmp = reverse(str));
        if(strcmp(strrev(str), tmp)) printf("error!\n");
        delete []tmp;
    }
    return 0;
}

前面那个递归写错了… 直接调用

【在 knuth (Knuth) 的大作中提到: 】

我想大家写程序到一定层度都会觉得递归很有意思。

其实，我们接触很多算法都可以用递归实现的——虽然很多可能没有必要。

举个例子：

……………….

☆─────────────────────────────────────☆

leo (leo) 于 (Fri Dec 1 17:57:55 2006) 提到:

【在 knuth (Knuth) 的大作中提到: 】

我想大家写程序到一定层度都会觉得递归很有意思。

其实，我们接触很多算法都可以用递归实现的——虽然很多可能没有必要。

举个例子：

……………….

递归很好的,写出的代码简单又容易理解.

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Fri Dec 1 17:59:18 2006) 提到:

【在 debug (Leaving) 的大作中提到: 】

按你的要求来应该这样:

/*

* reverse.cpp

……………….

楼上使用了C++的重载功能。本质上发生递归的是reverse(char *s, int k)函数，还是2个参数。

提高的要求是用1个参数实现递归^_^

☆─────────────────────────────────────☆

TomasMao (毛豆) 于 (Fri Dec 1 18:33:29 2006) 提到:

我觉得这个如果用递归不划算,我倒是想到了用分治来实现一个参数的,递归.就是让前面一半的字符串和后面一半的分别reverse,然后整个再reverse.不过时空复杂度都比不递归大的多.不知道,有没有别的简单的递归算法.

【在 knuth (Knuth) 的大作中提到: 】

楼上使用了C++的重载功能。

本质上发生递归的是reverse(char *s, int k)函数，

还是2个参数。

……………….

☆─────────────────────────────────────☆

TomasMao (毛豆) 于 (Fri Dec 1 18:35:29 2006) 提到:

如果有全局变量和没有全局变量思路完全不一样.如果有全局变量相当于传递了参数,那么把有多个参数的程序稍微改下就可以了.如果没有全局变量用分治可以实现一个参数.

【在 knuth (Knuth) 的大作中提到: 】

那个不管，总之用户只是把它当作一个函数使用。

main()

{

……………….

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Fri Dec 1 18:41:09 2006) 提到:

【在 TomasMao (毛豆) 的大作中提到: 】

我觉得这个如果用递归不划算,我倒是想到了用分治来实现一个参数的,递归.就是让?..

一半的字符串和后面一半的分别reverse,然后整个再reverse.不过时空复杂度都比不递

归大的多.不知道,有没有别的简单的递归算法.

贴个代码出来吧_

不过这里用递归实现并不是要使用，只是想大家能更深入些了解递归…

☆─────────────────────────────────────☆

TomasMao (毛豆) 于 (Fri Dec 1 18:53:27 2006) 提到:

reverse(char *str)
{
    int len;
    char *tmp;
    len = strlen(str);
    if(len&1)
    {
        tmp=str+len/2+1;
        reverse(tmp);
    }
    else
    {
        tmp=str+len/2;
        reverse(tmp);
    }
    int i;
    for(i=0;i<len/2;i++)
    {
        swap(str[i],str[i+len/2]);
    }
    reverse(tmp);
}

【在 knuth (Knuth) 的大作中提到: 】

贴个代码出来吧_

不过这里用递归实现并不是要使用，

只是想大家能更深入些了解递归…

……………….

☆─────────────────────────────────────☆

TomasMao (毛豆) 于 (Fri Dec 1 18:55:42 2006) 提到:

把if else里面的reverse()提出来代码更简洁点

【在 TomasMao (毛豆) 的大作中提到: 】

reverse(char *str)

{

int len;

……………….

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Fri Dec 1 19:12:22 2006) 提到:

【在 TomasMao (毛豆) 的大作中提到: 】

reverse(char *str)

{

int len;

……………….

看了你的代码，觉得结果不对, 而且实际运行的时候错误错误。

☆─────────────────────────────────────☆

TomasMao (毛豆) 于 (Fri Dec 1 19:16:47 2006) 提到:

思路应该没问题 ,自己改改吧

【在 knuth (Knuth) 的大作中提到: 】

看了你的代码，觉得结果不对,

而且实际运行的时候错误错误。

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Fri Dec 1 19:18:08 2006) 提到:

从软件安全和维护的角度来讲,我认为提醒程序员自己做了什么很重要. 所以,我认为不应该设计一个返回变量等待程序员释放. 我的想法是让程序员自己new字符串.这样也许更能提醒程序员注意自己使用的系统资源.

void reverse(char *str)
{
    static int begin = -1;
    static int end = -1;

    if (begin == -1)
    {
        begin = 0;
        end = strlen(str)-1;
    }

    if ( (end-begin) >= 1 )
    {
        str[begin] = str[begin] ^ str[end];
        str[end]   = str[end]   ^ str[begin];
        str[begin] = str[begin] ^ str[end];
        begin++;
        end--;
        return reverse(str);
    }
    else
    {
        begin  = -1;
        end = -1;
        return str;
    }
}

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Fri Dec 1 19:25:42 2006) 提到:

本来有了这么多的解决方法,自己不应该再多此一举.但是,呵呵,发现自己还是和大一初学编程的时候一样会为这样的”挑战”而狂热…

“编程为什么有趣？作为回报，它的从业者期望得到什么样的快乐？首先是一种创建事物的纯粹快乐。如同小孩在玩泥巴时感到愉快一样，成年人喜欢创建事物，特别是自己进行设计。我想这种快乐是上帝创造世界的折射，一种呈现在每片独特、崭新的树叶和雪花上的喜悦1。 ……… 1. Ershov认为编程是一种乐趣和苦恼共存的活动。A.P. Ershov, “Aesthetics and the human factor in programming,” CACM, 15,7(July,1972), pp. 501-505.”

摘自《人月神话》作者：FREDERICK P. BROOKS, JR. 翻译：Adams Wang

☆─────────────────────────────────────☆

TomasMao (毛豆) 于 (Fri Dec 1 19:30:04 2006) 提到:

#include <stdio.h>
#include <conio.h>
#include <string.h>

void reverse(char *str)
{
    char *tmp;
    int i;
    int len;
    char c;
    int add;
    len = strlen(str);
    if(len < 1)
        return;
    if(len&1)
    {
        add = len/2+1;
    }
    else
    {
        add = len/2;
    }
    tmp = str + add;
    reverse(tmp);
    for(i=0;i<len/2;i++)
    {
        c = str[i];
        str[i] = str[i+add];
        str[i+add] = c;
    }
    reverse(tmp);
}

void main()
{
    char str[10] = "abcdef";
    printf("%s\n",str);
    reverse(str);
    printf("%s",str);
}

【在 knuth (Knuth) 的大作中提到: 】

看了你的代码，觉得结果不对,

而且实际运行的时候错误错误。

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Fri Dec 1 19:34:38 2006) 提到:

【在 TomasMao (毛豆) 的大作中提到: 】

思路应该没问题 ,自己改改吧

刚才又看了一下，觉得似乎可以…

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Fri Dec 1 19:36:06 2006) 提到:

还有一个问题，我刚刚也暗示了。这个：

#include <iostream>
using namespace std;
int main()
{
char* s="12";
s[0] = '1';
return 0;
}

我想大家知道我要说什么。

也许大家强调题目并没有明确指出这一点，但是knuth函数原型的返回值暗示了：参数也许指向常量。

【在 knuth (Knuth) 的大作中提到: 】

reverse(char *str,int left,int right)

{

char tmp;

……………….

☆─────────────────────────────────────☆

TomasMao (毛豆) 于 (Fri Dec 1 19:37:35 2006) 提到:

你说什么呢? 我一直没看懂

【在 magicGG (magicGG) 的大作中提到: 】

还有一个问题，我刚刚也暗示了。

这个：

#include

……………….

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Fri Dec 1 19:45:53 2006) 提到:

你运行一下我那段小代码，常量不能访问的问题。

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Fri Dec 1 19:49:06 2006) 提到:

【在 magicGG (magicGG) 的大作中提到: 】

本来有了这么多的解决方法,自己不应该再多此一举.但是,呵呵,发现自己还是和..

初学编程的时候一样会为这样的”挑战”而狂热…

“编程为什么有趣？作为回报，它的从业者期望得到什么样的快乐？

……………….

地大bbs在外网访问太慢了！！！根本大不开帖子！现在才看到已经回了好多。

magicGG的方法和我的有些相似_

char *reverse(char *str)
{
    static int stk;
    static char *s;

    if(!stk) s = str+strlen(str)-1;

    stk++;
    if(str < s)
    {
        char c = *s; *s = *str; *str = c;
        s--; reverse(str+1);
    }
    stk--;

    return str;
}

都用到了static变量！

发了这个回去就回去了，下周再看。要是现在看，估计得等到10点…

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Fri Dec 1 19:57:22 2006) 提到:

不好意思：

void reverse(char *str)
{
    static int begin = -1;
    static int end = -1;

    if (begin == -1)
    {
        begin = 0;
        end = strlen(str)-1;
    }

    if ( (end-begin) >= 1 )
    {
        str[begin] = str[begin] ^ str[end];
        str[end]   = str[end]   ^ str[begin];
        str[begin] = str[begin] ^ str[end];
        begin++;
        end--;
        //return
        reverse(str);
    }
    else
    {
        begin  = -1;
        end = -1;
        //return str;
    }
}

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Fri Dec 1 20:16:06 2006) 提到:

我认为 TomasMao (毛豆) 是最“递归”的解法。相比之下，我和knuth过多依赖了语言元素。

【在 TomasMao (毛豆) 的大作中提到: 】

#include

#include

#include

……………….

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Fri Dec 1 20:28:49 2006) 提到:

我来尝试解释：TomasMao (毛豆)的方法： 1.首先反转串的后半部分。 2.把反转后的后半子串平移到前半部分来。这样以后就把结果串的前半部分弄好了。此时，原来串的前半部分已经被移动到了后面。对它的移动已经完成了，它现在需要被反转。 3.反转它。

☆─────────────────────────────────────☆

TomasMao (毛豆) 于 (Fri Dec 1 20:39:52 2006) 提到:

呵呵,谢谢啊

【在 magicGG (magicGG) 的大作中提到: 】

我来尝试解释：TomasMao (毛豆)的方法：

1.首先反转串的后半部分。

2.把反转后的后半子串平移到前半部分来。这样以后就把结果串的前半部分弄好了。

……………….

☆─────────────────────────────────────☆

Superren (西门飘雪) 于 (Fri Dec 1 22:57:12 2006) 提到:

【在 TomasMao (毛豆) 的大作中提到: 】

#include

#include

#include

……………….

TomasMao (毛豆)方法不错,但是”if else”代码段还可精简add = (len+1)/2; 该语句把奇偶情况全包含了.

☆─────────────────────────────────────☆

ray (小平) 于 (Fri Dec 1 23:13:41 2006) 提到:

【在 knuth (Knuth) 的大作中提到: 】

我想大家写程序到一定层度都会觉得递归很有意思。

其实，我们接触很多算法都可以用递归实现的——虽然很多可能没有必要。

举个例子：

……………….

阅，抄送家宝！

☆─────────────────────────────────────☆

Superren (西门飘雪) 于 (Sat Dec 2 00:16:43 2006) 提到:

【在 knuth (Knuth) 的大作中提到: 】

我想大家写程序到一定层度都会觉得递归很有意思。

其实，我们接触很多算法都可以用递归实现的——虽然很多可能没有必要。

举个例子：

……………….

大家方法都不错不过对比一下还是算”毛豆”先生是真正的为了解决问题而递归的. 其它的递归都是为了递归而递归的,与其这样,直接整个翻转就OK了,还费那么大劲哈哈,不过都有收获

☆─────────────────────────────────────☆

C9456 (C9456) 于 (Sat Dec 2 14:10:19 2006) 提到:

【在 Superren (西门飘雪) 的大作中提到: 】

大家方法都不错

不过对比一下

还是算”毛豆”先生是真正的为了解决问题而递归的.

……………….

递归代价比较大，一般不能不用递归就不要使用递归。递归花费了大量的内存空间（系统栈空间和应用堆参数表空间）和函数调用时环境切换的时间。

从理论上来说，递归可以使用递推来完成，相比之下，递推代码书写量要大些，但代码的可控制性更高！

☆─────────────────────────────────────☆

C9456 (C9456) 于 (Sat Dec 2 14:19:09 2006) 提到:

【在 C9456 (C9456) 的大作中提到: 】

递归代价比较大，一般不能不用递归就不要使用递归。

递归花费了大量的内存空间（系统栈空间和应用堆参数表空间）和函数调用时环境切..

时间。

……………….

我也发个：

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <windows.h>
#include <winbase.h>

char* reverse(char *str)
{
    static char* rev_buf = NULL;
    static char* Str_Error ="ERROR";
    char* ret_buf;
    int str_len;
    static int str_count = 0;

    str_len = (int)strlen(str) - str_count;
    if(str_len < 0)        //递归出口判断条件
        goto End;

    //分配全局静态空间
    if(rev_buf == NULL){
        if((rev_buf = (char*)malloc( sizeof(char)*strlen(str))) != NULL)
            ZeroMemory(rev_buf, strlen(rev_buf));
        else
            return Str_Error;
    }

    //将返回值，拷贝到全局静态空间中
    str_count++ ;
    sprintf(rev_buf,"%s%c", rev_buf, *reverse(str));
    str_count --;

End:
    if(str_count == 0){
        sprintf(rev_buf,"%s%c", rev_buf, *(str));        //最后返回，差一个字节，此处补上
        if((ret_buf = malloc(sizeof(char)*strlen(str))) != NULL){
            strcpy(ret_buf, rev_buf);                    //静态缓冲空间不便作返回值
        //    ZeroMemory(rev_buf, strlen(rev_buf));      //清空内存数据，再次使用不用malloc
            rev_buf = NULL;                              //清空指针，以便下次该函数使用，之后使用要malloc
            return ret_buf;                              //返回字符串
        }
        return Str_Error;                                //返回出错信息
    }
    else
        return str + str_count;
}

void main(void)
{
    char* str = "123456";
    char* str1 = "123456789";
    char str2[20];
    strcpy(str2, reverse(str1));
    printf("%s\n%s\n", reverse(str), reverse(str1));
    printf("%s\n", str2);
}

☆─────────────────────────────────────☆

steam (少上bbs,多读书) 于 (Sat Dec 2 14:31:05 2006) 提到:

也原创一下

void reverse(char *buf)
{
    static char *pBuf=buf;

    char ch=*buf;
    if(*(++buf)!='\0')
        reverse(buf);
    *(pBuf++)=ch;
}

【在 knuth (Knuth) 的大作中提到: 】

我想大家写程序到一定层度都会觉得递归很有意思。

其实，我们接触很多算法都可以用递归实现的——虽然很多可能没有必要。

举个例子：

……………….

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Sat Dec 2 15:02:33 2006) 提到:

逻辑好像不对.

【在 steam (少上bbs,多读书) 的大作中提到: 】

也原创一下

void reverse(char *buf)

{

……………….

☆─────────────────────────────────────☆

steam (javaing) 于 (Sat Dec 2 15:10:56 2006) 提到:

为啥不对？你试了没

【在 magicGG (magicGG) 的大作中提到: 】

逻辑好像不对.

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Sat Dec 2 15:15:22 2006) 提到:

steam的算法也很简单.但只是忘记考虑static初始化只能执行一次的问题.

【在 magicGG (magicGG) 的大作中提到: 】

逻辑好像不对.

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Sat Dec 2 15:35:30 2006) 提到:

好复杂啊.

【在 C9456 (C9456) 的大作中提到: 】

我也发个：

#include

#include

……………….

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Sat Dec 2 15:36:55 2006) 提到:

我试了.

【在 steam (javaing) 的大作中提到: 】

为啥不对？

你试了没

☆─────────────────────────────────────☆

steam (javaing) 于 (Sat Dec 2 15:38:10 2006) 提到:

void reverse(char *buf)
{
    static char *pBuf=0;
    static int n=0;
    if(n==0)
        pBuf=buf;
    n++;
    char ch=*buf;
    if(*(++buf)!='\0')
        reverse(buf);
    *(pBuf++)=ch;
    n--;
}

【在 magicGG (magicGG) 的大作中提到: 】

好复杂啊.

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Sun Dec 3 09:58:17 2006) 提到:

【在 knuth (Knuth) 的大作中提到: 】

我想大家写程序到一定层度都会觉得递归很有意思。

其实，我们接触很多算法都可以用递归实现的——虽然很多可能没有必要。

举个例子：

……………….

一天没看，已经回了这么多拉，哈哈

想必大家都对reverse有了较深入的了解，

现在让我们再回到原点…

开始我给了一个逆序十进制数的程序

int fx(int n, int k) { return (n)? fx(n/10, k*10+(n%10)): k; }

main() { printf(“%d\n”, fx(119, 0)); }

fx也是设置了一个辅助参数k。参考reverse的方法，我们也可以把k去掉。

int fx(int n)
{
    static int stk;
    static int k;

    if(!stk) k = 0;

    stk++;
    if(n) { k = k*10 + n%10; fx(n/10); }
    stk--;

    return k;
}

当然这种修改没什么特别之处。我的目的是要进一步考察它们的联系…

fx把十进制119逆序为911，reverse则是把字符串逆序。

那么我们是否可以把reverse要逆序的字符串也看作是一个数呢？

当然可以了，一个char占一个字节8个二进制位，因此权值为256…

从这个角度看的话，fx的方法同样也可以用于实现reverse。

和二进制相似，reverse的str/256和str%256我们可以利用左移来实现。

char *reverse(char *str)
{
    static int stk;
    static char *s;

    if(!stk) s = str + strlen(str) - 1;

    stk++;
    if(str < s)
    {
        char *p = s - 1;
        char c = *p;

        while(*(p+1))
        {
            *p = *(p+1); p++;
        }
        *p = c;

        s--; reverse(str);
    }
    stk--;

    return str;
}

其中str-s对应fx中当前的n，s到末尾对应fx中的k。

今天还有事情，先写这些了_

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Sun Dec 3 10:44:03 2006) 提到:

确实精巧,深刻.

【在 knuth (Knuth) 的大作中提到: 】

一天没看，已经回了这么多拉，哈哈

想必大家都对reverse有了较深入的了解，

现在让我们再回到原点…

……………….

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Mon Dec 4 08:49:44 2006) 提到:

【在 knuth (Knuth) 的大作中提到: 】

一天没看，已经回了这么多拉，哈哈

想必大家都对reverse有了较深入的了解，

现在让我们再回到原点…

……………….

现在再把算法左右对称一下：

char *reverse(char *str)
{
    static int stk;
    static char *s;

    if(!stk) s = str;

    stk++;
    if(*str)
    {
        char *p = str, t = *p;
        while(p > s) { *p = *(p-1); p--; }
        *p = t;

        reverse(str+1);
    }
    stk--;

    return str;
}

这样我们就得到另一种完整的方法…

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Mon Dec 4 09:21:09 2006) 提到:

恩.

☆─────────────────────────────────────☆

C9456 (C9456) 于 (Mon Dec 4 09:32:27 2006) 提到:

【在 knuth (Knuth) 的大作中提到: 】

一天没看，已经回了这么多拉，哈哈

想必大家都对reverse有了较深入的了解，

现在让我们再回到原点…

……………….

呵呵，思想不错，可惜我没有完全看懂！

不知道你分析了下其空间复杂度和时间复杂度没有？

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Mon Dec 4 09:35:15 2006) 提到:

我想,如果从你的思路出发,继续向前,还是有路可走的.

那就是TomasMao(毛豆)的思路.

他的算法思想如果非要找到一个和你一样的思路的话,到是可以这样解释:

每次不是除以256,然后取余.而是动态的除以当前串长的一半所代表的权值,然后把另一半(也就是余数),赋给K.和你的思想的最大的不同还有一点,就是他的算法就此没有迭代得使用算术思想,而是每个递归都仅此一步算术.我想表达的意思是他的算法中的算术不具有连续性,不知道说清楚没…

steam的算法好像是迄今效率最高的.

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Mon Dec 4 09:49:52 2006) 提到:

【在 magicGG (magicGG) 的大作中提到: 】

我想,如果从你的思路出发,继续向前,还是有路可走的.

那就是TomasMao(毛豆)的思路.

他的算法思想如果非要找到一个和你一样的思路的话,到是可以这样解释:

……………….

哈哈，现在问题终于被展开了_ 看来我开始的目的已经达到了…

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Mon Dec 4 10:12:43 2006) 提到:

我发现一规律:就是knuth用三个点(…)的时候一定是笑里藏刀,绵里藏针…醉翁之意不在酒…更大的还在后头…

哈哈…^_^

☆─────────────────────────────────────☆

TomasMao (毛豆) 于 (Mon Dec 4 10:44:22 2006) 提到:

递归问题没必要弄得这么复杂吧？我觉得递归就是将一个问题和子问题的相似性利用起来这样使程序看起来非常简洁

我想当初那些做编译器的人支持递归也是发现了很多程序问题，子问题跟原问题有相似性如果让人为的实现这些相似性比如自己构造堆栈来实现递归非常麻烦那么我们就让编译器帮我们实现，于是开始支持递归我是这么想的，反正就是为了方便程序员处理问题像算法里面的动态规划和分治这两个最常用最重要的算法都用到了递归，可见递归的重要性。

还有一点就是程序就是为了帮助程序员解决问题所以我觉得还是把精力放到解决问题上比较好不用拿一些解决问题方法例如递归，或者一些语言的特性研究半天其实语言为什么有那么多种？就是因为要解决不同的问题，写脚步用脚本语言perl python shell 开发大规模现实应用程序需要接近人类思维需要面向对象c++ java，底层开发要接近硬件思维c语言，汇编语言。还有数据库查询也需要自己的SQL语言。总之一句话什么方便用什么，什么让程序员能快速解决问题用什么。任何语言都有它存在的道理。大家不但要学习这些语言还要明白为什么要学习使用这些语言不要只学习知识而忘记学习知识的目的其实递归好像也没什么好研究的

【在 knuth (Knuth) 的大作中提到: 】

哈哈，现在问题终于被展开了_

看来我开始的目的已经达到了…

☆─────────────────────────────────────☆

C9456 (C9456) 于 (Mon Dec 4 12:00:21 2006) 提到:

【在 TomasMao (毛豆) 的大作中提到: 】

递归问题没必要弄得这么复杂吧？

我觉得递归就是将一个问题和子问题的相似性利用起来

这样使程序看起来非常简洁

……………….

说得极是！

能不用递归就不要用递归！空间复杂度问题始终是递归使用者忽略的问题。

对于程序员来说，递归是简单了编程的过程，但对计算机来说是个挑战！

☆─────────────────────────────────────☆

kusa (时代青年) 于 (Mon Dec 4 13:30:43 2006) 提到:

【在 TomasMao (毛豆) 的大作中提到: 】

递归问题没必要弄得这么复杂吧？

我觉得递归就是将一个问题和子问题的相似性利用起来

这样使程序看起来非常简洁

……………….

递归遍历的效率一般是比较低的!

☆─────────────────────────────────────☆

steam (javaing) 于 (Mon Dec 4 15:42:23 2006) 提到:

效率暂时不谈，考虑堆栈可能溢出的问题，很多时候对递归没安全感,虽然用它来描述思想和编写程序比较简单。

【在 TomasMao (毛豆) 的大作中提到: 】

递归问题没必要弄得这么复杂吧？

我觉得递归就是将一个问题和子问题的相似性利用起来

这样使程序看起来非常简洁

……………….

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Mon Dec 4 16:03:15 2006) 提到:

我同意的你部分观点,但不同意另外一部分.

首先,一个小概念的澄清.编译器设计和程序设计语言的设计不是等同的.语言递归特征的出现我想当初是人的求解思路的直接要求.像菲波那楔数列的定义和其他某些事物的定义本身就引导我们使用一种叫递归的东西去求解,所以在”语言设计”中加入了这个特征.我印象中是有语言不支持函数直接调用自身的的,但我们可以用两个函数互相调用来解决这个问题,我想.

其次,每个人研究的层次不同,这个层次有高低之分,但没有贵贱之分.这个贵贱不是人的,而是问题的—-没有.我的意思是说不论是对语言特征应用的讨论还是问题建模的讨论还是对思路的讨论都很重要.不同的语言对思维有不一样的反作用,“解决问题”总要使用语言,总要被它的特征所拓展和限制—-无论是自然语言,数学语言,亦或计算机程序设计语言 .(关于语言与思维的关系的讨论详见我发在数学工具版的).

最后,这次讨论我受到很多启发.

☆─────────────────────────────────────☆

C9456 (C9456) 于 (Mon Dec 4 16:19:07 2006) 提到:

【在 magicGG (magicGG) 的大作中提到: 】

我同意的你部分观点,但不同意另外一部分.

首先,一个小概念的澄清.编译器设计和程序设计语言的设计不是等同的.语言递?..

的出现我想当初是人的求解思路的直接要求.像菲波那楔数列的定义和其他某些事物?..

……………….

呵呵，多搞这样的讨论才好啊！讨论是个让我们进步很快的方法！

强烈建议大家多讨论。

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Mon Dec 4 18:52:13 2006) 提到:

【在 C9456 (C9456) 的大作中提到: 】

呵呵，

多搞这样的讨论才好啊！

讨论是个让我们进步很快的方法！

……………….

看来大家讨论的还是很激烈啊_

本来还想继续深入的，但刚才看了帖子已经到60楼了…

因此，就先告一段落吧。

#include <stdlib.h>

void main(void)
{
    unsigned n = 1;
    while(malloc(n <<= 1));
    main();
}

不过不知道这个程序是否能停止得了…

☆─────────────────────────────────────☆

magicGG (magicGG) 于 (Mon Dec 4 19:16:05 2006) 提到:

三个点,注意到没?

☆─────────────────────────────────────☆

knuth (Knuth) 于 (Mon Dec 4 19:17:36 2006) 提到:

【在 magicGG (magicGG) 的大作中提到: 】

三个点,注意到没?

哈哈，觉得magicGG兄很幽默啊。

☆─────────────────────────────────────☆

C9456 (C9456) 于 (Mon Dec 4 20:28:24 2006) 提到:

【在 knuth (Knuth) 的大作中提到: 】

看来大家讨论的还是很激烈啊_

本来还想继续深入的，

但刚才看了帖子已经到60楼了…

……………….

内存完了就会异常结束！

文章目录