First, question raising

Question: How many ways can I put m apples into n plates and allow some plates to be empty?

Note:

5,1,1 and 1, 5,1 belong to the same method

M and n are both less than 10

Second, algorithm analysis

Let f(m,n) be the number of apples and n plates, then discuss n first,

When n>m: there must be n-m plates that are always empty, removing them has no effect on the number of ways to place apples. If (n>m) f(m,n) = f(m,m)

When n<=m: The different methods can be divided into two categories:

If at least one plate is empty, that is, f(m,n) = f(m,n-1);

All the plates have apples, which is equivalent to removing an apple from each plate without affecting the number of different ways to put it, that is, f(m,n) = F (m-n,n). And the total number of ways to put apples is the sum of the two, which is f(m,n) =f(m,n-1)+f(m-n,n).

Recursive export condition description:

When n=1, all the apples have to be on the same plate, so return 1;

When m==0(there are no apples to put), it is defined as 1 way to put;

Third, program design

#include <stdio.h> #include <stdlib.h> int appledivide(m,n); int main() { int m,n; Printf (" Please enter the number of apples and plates (both less than 10) :\n"); scanf("%d%d",&m,&n); if(m<10&&n<10) { int result = appledivide(m,n); Printf (" place %d apples, into %d plates, total method in %d ",m,n,result); } else printf(" Apples or plates should be less than 10"); return 0; {} int appledivide (m, n) / / if only one dish, no matter how many apples are there is only one put method if (m = = 0 | | n = = 1) {return 1; } // If (n>m) {return appledivide(m,m); } else { return appledivide(m,n-1) + appledivide(m-n,n); }}Copy the code

Fourth, program results display

Example: 9 apples and 9 plates

If you also like programming and want to learn C/C++! If you want to become a great programmer with real stuff, start now!

Wechat official account: C language programming Learning base

Organize and share (years of learning source code, project actual combat video, project notes, basic introduction tutorial)