c - 我将如何使用递归来生成所有可能性？

Question

假设输入是 4，那么输出应该是所有可能的 4 字母单词，字母 a 到 f。一路从aaaa到ffff。我将如何通过使用递归来做到这一点？

我很抱歉在我最初的问题中没有包括我对这个问题的尝试。有些人想知道为什么我使用递归而不是使用更简单的方法（例如 for 循环），原因是我的教授希望我们使用 for 循环来解决这个问题。

这是我这样做的尝试：

void allPossiblilities(int n)
{
     char*result;
     if(Done(result))/*since the last possibility will be all f I am using that as my base case*/
     {
       printf("%s",result);
       return;
     }

 /*This is where the recursive part should go but I am totally lost as to what it should be*/
}

bool Done(result)/*This function just returns true if all the array's index are f*/
{
     int i;
     bool a=true;
     for(i=0;i<=n-1;i++)
        if(result[i]!='f')
           a=false;
}
     return a;
}

Answer 1

我会给你一个提示，让你思考：

4 位数字和 10 个可能的数字（0-9）有多少种可能性 base^digits = 10^4 = 10000 个可能的输出 0000-9999，在您的情况下，它们将 base = 6（AF）和 exp = 4（4 个位置） 6^4 = 1296 种组合。

递归函数是如何产生的？他们有两个步骤：

• 基本步骤：它是函数不调用自身时的条件或条件（最终条件）。

• Recursive Step：是函数调用自身的条件或条件，其结果应该更接近Basic Step。

比如著名的阶乘函数，基本步骤是返回1，递归步骤是第二个。

PD：我试图让你自己分析问题并得到解决方案，并给你一些工具。

编码：

#include <stdio.h>
#include <stdlib.h>

void recurs( int * s );
void print( int * s );

int main( void )
{
    int a[] = { 0, 0, 0, 0 };
    print( a );
    recurs( a );

}

void recurs( int * s )
{
    int i;

    /*Basic Case*/
    if( s[ 3 ] == 5 && s[ 2 ] == 5 && s[ 1 ] == 5 && s[ 0 ] == 5 ){
        print( s );
        printf( "\nAccomplisshed!\n" );
    }

    else{
        s[ 0 ] += 1;
        for( i = 0; i < 3; i++ ){
            if( s[ i ] == 6 ){
                s[ i ] = 0;
                s[ i + 1 ] += 1;
            }
        }
        print( s );
        recurs( s );
    }
}

/* This only prints. */
void print( int * s )
{
    int i; 
    printf( "    " );
    for( i = 3; i >= 0; i-- ){
        printf( "%c", ( s[ i ] + 65 ) );
    }
}

部分输出：

Answer 2

 int inc(char *c,char begin, char end){
    if(c[0]==0) return 0;
    if(c[0] == end){   // This make the algorithm to stop at char 'f'
        c[0]=begin;     // but you can put any other char            
        return inc(c+sizeof(char));
    }   
    c[0]++;
    return 1;
}

int all(int a, int n,char begin, char end){
    int i,j;
    char *c = malloc((n+1)*sizeof(char));
    for(i=a;i<=n;i++){
        for(j=0;j<i;j++) c[j]=begin;
        c[i]=0;
        do {
            printf("%s\n",c);
        } while(inc(c,begin,end));
    }
    free(c);
}


int main(void){
    all(4,4,'a','f'); // Generates from 4 letters words starting in aaaa to ffff
}

如果你调用 all(1,4,'a','f') 它将生成 a,b,c,d...ffff

如果你调用 all(4,4,'a','z') 它将从 aaaa 生成到 zzzz

Answer 3

只是为了使用十六进制表示法生成a-f字符：

#include <stdio.h>
int v(unsigned char* i, unsigned short n) {
  return !n || (*i>=0xa0 && (*i&0xf)>=10 && v(i+1,n-1));
}
void f(unsigned short i) {
  if(i) f(i-1);
  if(v((char*)&i,2)) printf("%x\n",i);
}
int main(){ f((1<<16)-1);}