current position:Home>C language beginners' doubts, no, require recursion

C language beginners' doubts, no, require recursion

2022-02-03 01:07:55 CSDN Q & A

For any positive integer n, You can always find positive integers and see k1、k2…, Make these numbers want to add up just equal to n, And each number does not exceed the specified number m.
ask : For a given n, Please find out how many such summations there are
Be careful ;
set up a,b It's not equal , Think a+b And b+a Is a different summation ;
n=n It's also a summation
for example :
n=4,m=2.
4=1+1+1+1
4=1+1+2
4=1+2+1
4=2+1+1
4=2+2




Refer to the answer 1:
#include <stdio.h>int cnt=0;void comb(int a[],int m,int k,int s) {    int i,j,t;    for(i=m;i>=k;i--)    {        a[k]=i;        if(k>1)            comb(a,i-1,k-1,s);        else        {            for(t=0,j=a[0];j>0;j--)                t=t+a[j];                        if(t==s)            {                cnt++;                printf("%d=", s);                for(j=a[0];j>1;j--)                printf("%d+", a[j]);                printf("%d\n", a[1]);            }        }    }}int main(){    int a[100],s,m,i;    while (1)    {        scanf("%d %d", &s, &m);        if (s == 0)        {            break;        }                cnt=0;        for (i=1;i<=m;i++)        {            a[0]=i;            comb(a,m,i,s);        }            printf("%d\n", cnt);    }    return 0;}

Running results :

img




Refer to the answer 2:



Refer to the answer 3:

“ Given a small point of input , Full single step tracking ( Press at the same time Alt+7 Key view Call Stack The corresponding function call history from the inner layer to the outer layer is listed from top to bottom ) Again .” Is the only way to understand the working principle of recursive functions !
Recursive functions focus on the following factors
· Exit conditions
· What are the parameters
· What is the return value
· What are the local variables
· What are the global variables
· When to output
· Will it cause stack overflow

For reference only :

#include <stdio.h>#include <stdlib.h>void print(int res[], int num) {    static int L=0;    L++;    printf("%8d:",L);    for (int i=0;i<num;++i) {        printf(" %d", res[i]);    }    printf("\n");}void split(int n, int m) {
   
   
   
   // n Represents the total number ,m Represents the maximum factor     static int res[100];//  Save results     static int num=-1;//  Current factor subscript     if (n<m || n<0 || m<1) return;    num++;    if (0==n) {
   
   
   
   //  Recursive termination condition , by 0 Can not be further divided , Direct output         print(res,num+1);        num--;        return;    } else {        if (n==m) {
   
   
   
   //  Don't dismantle , Direct output             res[num]=m;            print(res,num+1);            num--;        } else {            //  Split the first             res[num]=m;            n=n-m;            if (m>n) m = n; //  The maximum factor cannot be greater than the total             for (int i=m;i>=1;--i) {
   
   
   
   //  loop , The second factor can continue to split , And it can be divided into multiple according to the maximum factor                 split(n,i);            }            num--;        }    }}void Split(int n) {    if (n<=0) return;    if (100<n) {        printf("Up to 100\n");        return;    }    for (int i=n;i>=1;--i) {        split(n, i);    }}void main(int argc,char **argv) {         if (argc<=1) Split(5);    else if (argc>=3) split(atoi(argv[1]),atoi(argv[2]));    else              Split(atoi(argv[1]));}



Refer to the answer 4:

copyright notice
author[CSDN Q & A],Please bring the original link to reprint, thank you.
https://en.primo.wiki/2022/02/202202030107519801.html

Random recommended