会递推但是不会写代码，请教 - 编程论坛

#2

叶纤2020-03-21 20:34

这一题必须用递推吗？迭代法多简单呀

#3

自学的数学2020-03-21 21:02

程序代码：

#include<stdio.h>
#include<string.h>
#define max 256
int main()
{
    char a[max];
    gets(a);
    int length=strlen(a);
    for(int i=length-1;i>=0;i--)
    {
        printf("%c",*(a+i));
    }
    printf("\n");
    return 0;
}

#4

lidepeng19952020-03-21 21:09

回复 2楼叶纤

对，最近在练习递归，说要用递归把这题做出来

#5

lidepeng19952020-03-21 21:10

回复 3楼自学的数学

感谢，如果用递归该怎么做？

#6

叶纤2020-03-21 21:15

回复 4楼 lidepeng1995

我很想帮你，可是我递归并不是很熟悉，因为我最近在学基础

#7

叶纤2020-03-21 22:14

程序代码：

想了一会居然可以了，哈哈哈
#include<iostream>
/*输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

*/

#include<cstring>

using namespace std;

void weizhi(int length,char shuzi[][29])
{     if(length>=0)
{
         cout<<*(shuzi+length);
      weizhi(length-1, shuzi);

}
}
int main(){
    char shuzi[][29]={"h","e","l","l","o"};
  int length=size(shuzi);
  weizhi(length-1,&*(shuzi));

}

olleh

#8

wmf20142020-03-21 22:16

回答问题前首先搞清楚递归和递推的关系，百度如下：
递归：程序调用自身的编程技巧称为递归，是函数自己调用自己。
递推：它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定象的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复。
递归与递推区别：递归的步骤中包含递推，如一个规模为n的问题，递归首先通过回溯将问题回溯到n-1，n-2……，然后再通过递推从1的结果一直递推到n。
既然递归包含递推，我暂时理解一楼是要用递归解决问题吧：递归反显一个字符串很容易，但要原地反向修改该字符串稍微复杂些，但也能解决，如下：

程序代码：

#include <stdio.h>
void fun(char *a,char b,int s)
{
    int i;
    if(!a[s])return;
    b=a[s];
    a[s]=0;
    fun(a,b,s+1);
    if(b)
    {
        for(i=0;a[i];i++);
        a[i]=b;
    }
}
void main()
{
    char a[10]="abcdef",b;
    fun(a,b,0);
    printf("%s\n",a);
}

#9

lin51616782020-03-21 22:47

回复 7楼叶纤

从题目要求来看你的实现是错的
虽然逆序输出但是你没有实现原地翻转

#10

lin51616782020-03-21 22:49

回复楼主 lidepeng1995

结束条件是length-1-i不为负数

这个结束条件弄错了

你全部交换会导致每个元素交换2次
结果就是原来的字符串

#11

叶纤2020-03-21 23:16

回复 9楼 lin5161678

你写写让我参考参考啊，我一个新手哪懂什么原地翻不翻转的，写汉字还不如写代码来的明白

#12

lin51616782020-03-22 02:02

以下是引用叶纤在2020-3-21 23:16:14的发言：

你写写让我参考参考啊，我一个新手哪懂什么原地翻不翻转的，写汉字还不如写代码来的明白

程序代码：

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

void flip(char* str, int start, int end)
{
    while(start < end)
    {
        int tmp = str[start];
        str[start] = str[end];
        str[end] = tmp;
        ++start;
        --end;
    }
}

void flipInPlace(char* str)
{
    flip(str, 0, strlen(str)-1);
}

int main(int argc, char *argv[])
{
    char str[64];
    scanf("%[^\n]", str);
    flipInPlace(str);
    puts(str);
    return 0;
}

#13

叶纤2020-03-22 10:42

原来这叫原地翻转啊？
迭代法，另外还开了一个额外空间
递归?。。。，

#14

叶纤2020-03-22 10:45

以下是引用lin5161678在2020-3-21 22:47:02的发言：

从题目要求来看你的实现是错的
虽然逆序输出但是你没有实现原地翻转

你自己吐槽我的时候也说了从题目看，也说了要进行原地翻转

#15

lin51616782020-03-22 11:12

以下是引用叶纤在2020-3-22 10:45:40的发言：

你自己吐槽我的时候也说了从题目看，也说了要进行原地翻转

字符串存在 str
翻转结果存在str之后
输出str 是逆序字符串
这就叫做原地翻转

另外没递归不知道你怎么看的
空间复杂度是 O(1) 符合题目要求

断句不好可能造成误解
纠正

另外没递归
不知道你怎么看的
空间复杂度是 O(1) 符合题目要求

[此贴子已经被作者于2020-3-22 11:39编辑过]

#16

叶纤2020-03-22 11:23

回复 15楼 lin5161678

我接触递归没几天，希望有人给我展现的是正确的学习氛围，而不是故意的插入错误思想

#17

叶纤2020-03-22 11:26

迭代法和递归思想还没成型的时候，我并不想要的错误的思维，误导我

#18

lin51616782020-03-22 11:28

回复 16楼叶纤

题目编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

这是题目我没看到和递归有什么关系你来错地方了
顺便为什么符合题意的解答是错误的思想?

#19

叶纤2020-03-22 11:30

以下是引用lidepeng1995在2020-3-21 21:09:33的发言：

对，最近在练习递归，说要用递归把这题做出来

人家说题目要求递归

#20

lin51616782020-03-22 11:30

回复 17楼叶纤

顺便按照题目要求空间复杂度 O(1)
如果要递归实现必须借助全局变量
是一个很丑陋的实现
本身就不应该考虑递归

#21

lin51616782020-03-22 11:31

回复 19楼叶纤

他理解错而已
题目根本没提到递归2个字

#22

叶纤2020-03-22 11:32

现在你告诉我你写的是递归，深感疑惑

#23

叶纤2020-03-22 11:34

以下是引用lin5161678在2020-3-22 11:31:01的发言：

他理解错而已
题目根本没提到递归2个字

你问人家了吗？怎么知道人家是不是截得完整的题目

#24

lin51616782020-03-22 11:36

回复 22楼叶纤

我说我写的不是递归

#25

lin51616782020-03-22 11:38

回复 23楼叶纤

题目不完整那是发帖人的过错
完整题目如果包括递归实现是出题人的过错
这个题目用递归实现属于残废代码
要么空间复杂度 O(N)
要么不可重入

#26

叶纤2020-03-22 11:59

以下是引用lin5161678在2020-3-22 11:38:16的发言：

题目不完整那是发帖人的过错
完整题目如果包括递归实现是出题人的过错
这个题目用递归实现属于残废代码
要么空间复杂度 O(N)
要么不可重入

在那个质疑帖人家那么帮你说话，你这么吐槽人家，你怎么想的啊？
2，人家正题已经说了用 递推不会做
3，人家已经说了，人家在 练习递归，刚开始学习递归，并没有考虑残废代码的问题
4如果从题目角度来看，已经说了 不要给另外的数组分配额外空间
5我是请教你如何原地不翻转的，让你用代码写出来，不是和你进行骂架的我也不喜欢和别人的帖子讨论这些有的没的
6人家版主也说了一堆话而且，用了递归做这题，你不看偏偏看我的想认徒吗？就算认徒也是徒弟主动去认的，也不用这么明显的我回答一个帖就吐槽一个帖，这样想想我也能体会你很铁不成钢的心情了
7不过人家暂时不想认师傅呢，师傅不要这么主动嘛，我只想安静的看别人的代码，看别人的思维
8 之后我就不回帖了，你怎么开心怎么聊
9最后说一句，玩的开心哈

#27

lin51616782020-03-22 12:14

以下是引用叶纤在2020-3-22 11:59:11的发言：

在那个质疑帖人家那么帮你说话，你这么吐槽人家，你怎么想的啊？
2，人家正题已经说了用递推不会做
3，人家已经说了，人家在练习递归，刚开始学习递归，并没有考虑残废代码的问题
4如果从题目角度来看，已经说了不要给另外的数组分配额外空间
5我是请教你如何原地不翻转的，让你用代码写出来，不是和你进行骂架的我也不喜欢和别人的帖子讨论这些有的没的
6人家版主也说了一堆话而且，用了递归做这题，你不看偏偏看我的想认徒吗？就算认徒也是徒弟主动去认的，也不用这么明显的我回答一个帖就吐槽一个帖，这样想想我也能体会你很铁不成钢的心情了
7不过人家暂时不想认师傅呢，师傅不要这么主动嘛，我只想安静的看别人的代码，看别人的思维
8 之后我就不回帖了，你怎么开心怎么聊
9最后说一句，玩的开心哈

递推不是递归
练习递归换一个题目这个题目练习递归效果不好
从题目的角度请问我的实现怎么另外分配额外空间了说了空间复杂度是O(1)
原地翻转的代码不是早就写出来了吗你是不是没看懂?
认你做徒弟? 你这是自作多情了我没这个想法看到错误我就纠正
这个论坛不能纠正错误?

#28

lidepeng19952020-03-22 12:53

仔细的看来一下你们的评论
我确实在练习递归，可能我把递推也当成递归了，造成了误解
残废代码？虽然听着不好听，但是因该指的是效率吧，可是不练习就学不会递归的，请谅解我的残废题目
题目要求是用递归写，我把它作为主体就希望更能清楚的看见
7楼用了c++写的看着有些吃力，不过大体可以看懂，7楼应该是按照3楼的代码思路进行写的吧，

#29

lin51616782020-03-22 12:58

以下是引用lidepeng1995在2020-3-22 12:53:03的发言：

仔细的看来一下你们的评论
我确实在练习递归，可能我把递推也当成递归了，造成了误解
残废代码？虽然听着不好听，但是因该指的是效率吧，可是不练习就学不会递归的，请谅解我的残废题目
题目要求是用递归写，我把它作为主体就希望更能清楚的看见
7楼用了c++写的看着有些吃力，不过大体可以看懂，7楼应该是按照3楼的代码思路进行写的吧，

残废代码倒不是效率问题
递归实现每次递归需要变量记录交换元素的下标
如果下标通过参数传递空间复杂度是O(N) 不符合题目要求
如果是通过全局变量传递则不可重入
不可重入的意思是 2个线程同时调用这个函数会造成错误
这里全局变量会被2个线程读写变成脏数据
从结果错误到运行崩溃都是有可能的

所以这个题目根本不应该考虑用递归实现
适合递归练习的简单题目还有很多
计算连续整数和
简单的动态规划
把循环改成递归

#30

lidepeng19952020-03-22 13:10

谢谢大佬的点拨了解了，
计算连续整数和是1+2+3+4...这样的吗
简单的动态规划我不明白
把循环改成递归？是不是像7楼把3楼的循环代码改成递归，一样呢？