Home Database Mysql Tutorial 程序员面试宝典8.2典型递归问题

程序员面试宝典8.2典型递归问题

Jun 07, 2016 pm 03:31 PM
look read a book programmer recursion question interview

今天看书看到8.2的递归问题,自己试了一下书上的代码,感觉尚有很多bug,于是自己写了一个。 主要是书中代码只是为了递归而递归,在递归的返回处理上做的不好。 贴上自己修改过的代码,仅作为日后复习之用。。 写程序时候发现几个问题,要注意: 1.一定要为v

今天看书看到8.2的递归问题,自己试了一下书上的代码,感觉尚有很多bug,于是自己写了一个。

主要是书中代码只是为了递归而递归,在递归的返回处理上做的不好。

贴上自己修改过的代码,仅作为日后复习之用。。

写程序时候发现几个问题,要注意:

1.一定要为vector**printarr=new vector*[slen];中申请的指针数组初始化,而初始化时,使用(*p+i)不能作为左值,改用p[i]即可。。

2.发现问题:使用*(*p+i)=i;赋值,调用时只能用指针+偏移值的方式,使用数组方式调用出错,如*p[i],而使用数组方式赋值,则只能使用数组方式调用。尚不明白是不是编译器的问题,留待学习。


#include
#include
#include
#include
using namespace std;

//建立比较串s在被比较串p中位置的vector。
void PrintfArrary(char* pstr,char* sstr,vector** printarr,int plen,int slen,int pstartnum,int sstartnum)
{


    for(int i=sstartnum;i         for(int j=pstartnum;j            if(*(sstr+i)==*(pstr+j))
            (*printarr[i]).push_back(j+1);
}

//递归调用,构建序列。
void printseq(vector** printarr,int slen,vector*out,int sum){
   if(slen==0){
     for(vector::iterator i((*out).begin());i!=(*out).end();i++)
        cout        cout    }


   else
     {
         int i=sum-slen;
         if(i){
            for(vector::iterator j((*printarr[i]).begin());j!=(*printarr[i]).end();j++){
                if(*j>*((*out).end()-1)){
                    (*out).push_back((*j));
                    printseq(printarr,slen-1,out,sum);
                    (*out).erase((*out).end()-1,(*out).end());
                }
            }
         }
         else
         for(vector::iterator j((*(*printarr)).begin());j!=(*(*printarr)).end();j++){
                    (*out).push_back((*j));
                    printseq(printarr,slen-1,out,sum);
                    (*out).erase((*out).end()-1,(*out).end());
         }
   }
}

//初始化及传递数据。
void  ConnectSequence(char* pstr,char* sstr)
{
    int plen=strlen(pstr);
    int slen=strlen(sstr);


    vector** printarr=new vector*[slen];
    for(int i=0;i

       printarr[i]=new vector;
   }
    vector*out=new vector;
    PrintfArrary(pstr,sstr,printarr,plen ,slen,0,0);
    printseq(printarr,slen,out,slen);
}


int main(){
 char* a="abdbccab";
 char* b="abc";
 ConnectSequence(a,b);
 return 0;
}

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Recursive implementation of C++ functions: Is there a limit to recursion depth? Recursive implementation of C++ functions: Is there a limit to recursion depth? Apr 23, 2024 am 09:30 AM

The recursion depth of C++ functions is limited, and exceeding this limit will result in a stack overflow error. The limit value varies between systems and compilers, but is usually between 1,000 and 10,000. Solutions include: 1. Tail recursion optimization; 2. Tail call; 3. Iterative implementation.

Do C++ lambda expressions support recursion? Do C++ lambda expressions support recursion? Apr 17, 2024 pm 09:06 PM

Yes, C++ Lambda expressions can support recursion by using std::function: Use std::function to capture a reference to a Lambda expression. With a captured reference, a Lambda expression can call itself recursively.

Recursive implementation of C++ functions: Comparative analysis of recursive and non-recursive algorithms? Recursive implementation of C++ functions: Comparative analysis of recursive and non-recursive algorithms? Apr 22, 2024 pm 03:18 PM

The recursive algorithm solves structured problems through function self-calling. The advantage is that it is simple and easy to understand, but the disadvantage is that it is less efficient and may cause stack overflow. The non-recursive algorithm avoids recursion by explicitly managing the stack data structure. The advantage is that it is more efficient and avoids the stack. Overflow, the disadvantage is that the code may be more complex. The choice of recursive or non-recursive depends on the problem and the specific constraints of the implementation.

Which AI programmer is the best? Explore the potential of Devin, Tongyi Lingma and SWE-agent Which AI programmer is the best? Explore the potential of Devin, Tongyi Lingma and SWE-agent Apr 07, 2024 am 09:10 AM

On March 3, 2022, less than a month after the birth of the world's first AI programmer Devin, the NLP team of Princeton University developed an open source AI programmer SWE-agent. It leverages the GPT-4 model to automatically resolve issues in GitHub repositories. SWE-agent's performance on the SWE-bench test set is similar to Devin, taking an average of 93 seconds and solving 12.29% of the problems. By interacting with a dedicated terminal, SWE-agent can open and search file contents, use automatic syntax checking, edit specific lines, and write and execute tests. (Note: The above content is a slight adjustment of the original content, but the key information in the original text is retained and does not exceed the specified word limit.) SWE-A

Revealing the appeal of C language: Uncovering the potential of programmers Revealing the appeal of C language: Uncovering the potential of programmers Feb 24, 2024 pm 11:21 PM

The Charm of Learning C Language: Unlocking the Potential of Programmers With the continuous development of technology, computer programming has become a field that has attracted much attention. Among many programming languages, C language has always been loved by programmers. Its simplicity, efficiency and wide application make learning C language the first step for many people to enter the field of programming. This article will discuss the charm of learning C language and how to unlock the potential of programmers by learning C language. First of all, the charm of learning C language lies in its simplicity. Compared with other programming languages, C language

C++ Recursion Advanced: Understanding Tail Recursion Optimization and Its Application C++ Recursion Advanced: Understanding Tail Recursion Optimization and Its Application Apr 30, 2024 am 10:45 AM

Tail recursion optimization (TRO) improves the efficiency of certain recursive calls. It converts tail-recursive calls into jump instructions and saves the context state in registers instead of on the stack, thereby eliminating extra calls and return operations to the stack and improving algorithm efficiency. Using TRO, we can optimize tail recursive functions (such as factorial calculations). By replacing the tail recursive call with a goto statement, the compiler will convert the goto jump into TRO and optimize the execution of the recursive algorithm.

Detailed explanation of C++ function recursion: application of recursion in string processing Detailed explanation of C++ function recursion: application of recursion in string processing Apr 30, 2024 am 10:30 AM

A recursive function is a technique that calls itself repeatedly to solve a problem in string processing. It requires a termination condition to prevent infinite recursion. Recursion is widely used in operations such as string reversal and palindrome checking.

Detailed explanation of C++ function recursion: tail recursion optimization Detailed explanation of C++ function recursion: tail recursion optimization May 03, 2024 pm 04:42 PM

Recursive definition and optimization: Recursive: A function calls itself internally to solve difficult problems that can be decomposed into smaller sub-problems. Tail recursion: The function performs all calculations before making a recursive call, which can be optimized into a loop. Tail recursion optimization condition: recursive call is the last operation. The recursive call parameters are the same as the original call parameters. Practical example: Calculate factorial: The auxiliary function factorial_helper implements tail recursion optimization, eliminates the call stack, and improves efficiency. Calculate Fibonacci numbers: The tail recursive function fibonacci_helper uses optimization to efficiently calculate Fibonacci numbers.

See all articles