C语言之整数划分问题（递归法）实例代码

C语言之整数划分问题（递归法）实例代码

整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分，是指把一个正整数n写成如下形式：

n=m1+m2+...+mi; （其中mi为正整数，并且1 <= mi <= n），则{m1,m2,...,mi}为n的一个划分。

如果{m1,m2,...,mi}中的最大值不超过m，即max(m1,m2,...,mi)<=m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);

例如但n=4时，他有5个划分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};

注意4=1+3 和 4=3+1被认为是同一个划分。

该问题是求出n的所有划分个数，即f(n, n)。下面我们考虑求f(n,m)的方法;

1.递归法：

根据n和m的关系，考虑以下几种情况：

(1)当n=1时，不论m的值为多少（m>0)，只有一种划分即{1};

(2)当m=1时，不论n的值为多少，只有一种划分即n个1，{1,1,1,...,1};

(3)当n=m时，根据划分中是否包含n，可以分为两种情况：

(a)划分中包含n的情况，只有一个即{n}；

(b)划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分。

因此 f(n,n) =1 + f(n,n-1);

(4)当n<m时，由于划分中不可能出现负数，因此就相当于f(n,n);

(5)但n>m时，根据划分中是否包含最大值m，可以分为两种情况：

(a)划分中包含m的情况，即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m，因此这情况下

为f(n-m,m)

(b)划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为f(n,m-1);

因此 f(n, m) = f(n-m, m)+f(n,m-1);

综上所述：

       f(n, m)=  1;       (n=1 or m=1)

        f(n,m)  =  f(n, n);          (n<m)

               1+ f(n, m-1);       (n=m)

               f(n-m,m)+f(n,m-1);     (n>m)

#include<iostream>
using namespace std;

int equationCount(int n,int m)
{
  if(n==1||m==1)
    return 1;
  else if(n<m)
    return equationCount(n,n);
  else if(n==m)
    return 1+equationCount(n,n-1);
  else
    return equationCount(n,m-1)+equationCount(n-m,m);
}

int main(void)
{
  int n;
  while(scanf("%d",&n)!=EOF&&(n>=1&&n<=120))
  {
    printf("%d\n",equationCount(n,n));
  }
  return 0;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • C语言使用普通循环方法和递归求斐波那契序列示例代码

    复制代码 代码如下: #include <stdio.h> int fac(int x); int main(void){    int n;    scanf("%d", &n);    if (n == 1 || n == 2)        printf("1\n");    else if (n == 3)        printf("2\n");    else    {        int last = 1; 

  • 纯C语言:递归最大数源码分享

    复制代码 代码如下: #include<stdio.h>int Getmax(int arr[n]){ for(int i=0;i<n,i++) {  if(n==0)   return arr[0];  else  {   arr[0]=arr[0]>Getmax(arr[]+1,n-1)?arr[0]:Getmax(arr[]+1,n-1);   return arr[0];   } }}void main(){ printf("请输入一组整数(用空格隔开):\n&q

  • 纯C语言:递归二进制转十进制源码分享

    复制代码 代码如下: #include<stdio.h>#include<math.h>int change(int n,int *sum,int *m)//n为第n位,m总位数{    char c;    if(c!='#')    {        *m=*m+1;        change(n+1,sum,m);    }    if(c=='#')    {        return *sum=int(*sum+pow(2,*m-n));    }}void main

  • C语言的递归思想实例分析

    本文实例分析C语言的递归思想,分享给大家供大家参考之用.具体方法如下: 通俗点来说,递归就是自己调用自己. 递归的难点一是理解递归的执行调用过程,二是设置一个合理的递归结束条件. 下面来看一段摘自书中的简单程序: #include <STDIO.H> long fact(int n); long rfact(int n); int main(void) { int num; printf("This program calculates factorials.\n"); p

  • 使用C语言递归与非递归实现字符串反转函数char *reverse(char *str)的方法

    代码如下所示: 复制代码 代码如下: // 递归实现字符串反转   char *reverse(char *str)   {    if( !str )    {     return NULL; } int len = strlen(str);       if( len > 1 )       {           char ctemp =str[0];           str[0] = str[len-1];              str[len-1] = '/0';// 最后一

  • 纯C语言:递归组合数源码分享

    复制代码 代码如下: #include<stdio.h>int sum(int m,int n){ if(n==m||n==0)  return 1; else  return sum(m-1,n)+sum(m-1,n-1);}void main(){ int m,n; printf("请输入组合数中的m:"); scanf("%d",&m); printf("\n请输入组合数中的n:"); scanf("%d&qu

  • C语言二叉树的非递归遍历实例分析

    本文以实例形式讲述了C语言实现二叉树的非递归遍历方法.是数据结构与算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.pus

  • c语言版本二叉树基本操作示例(先序 递归 非递归)

    c语言版本二叉树基本操作示例(先序 递归 非递归)

    复制代码 代码如下: 请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):ABD==E==CF==G== 先序递归遍历:A B D E C F G中序递归遍历:D B E A F C G后序递归遍历:D E B F G C A层序递归遍历:ABCDEFG先序非递归遍历:A B D E C F G中序非递归遍历:D B E A F C G后序非递归遍历:D E B F G C A深度:请按任意键继续. . . 复制代码 代码如下: #include<stdio.h>#include&

  • C语言函数的递归和调用实例分析

    一.基本内容: C语言中的函数可以递归调用,即:可以直接(简单递归)或间接(间接递归)地自己调自己. 要点: 1.C语言函数可以递归调用. 2.可以通过直接或间接两种方式调用.目前只讨论直接递归调用. 二.递归条件 采用递归方法来解决问题,必须符合以下三个条件: 1.可以把要解决的问题转化为一个新问题,而这个新的问题的解决方法仍与原来的解决方法相同,只是所处理的对象有规律地递增或递减. 说明:解决问题的方法相同,调用函数的参数每次不同(有规律的递增或递减),如果没有规律也就不能适用递归调用. 2

  • 对C语言中递归算法的深入解析

    对C语言中递归算法的深入解析

    许多教科书都把计算机阶乘和菲波那契数列用来说明递归,非常不幸我们可爱的著名的老潭老师的<C语言程序设计>一书中就是从阶乘的计算开始的函数递归.导致读过这本经书的同学们,看到阶乘计算第一个想法就是递归.但是在阶乘的计算里,递归并没有提供任何优越之处.在菲波那契数列中,它的效率更是低的非常恐怖. 这里有一个简单的程序,可用于说明递归.程序的目的是把一个整数从二进制形式转换为可打印的字符形式.例如:给出一个值4267,我们需要依次产生字符'4','2','6',和'7'.就如在printf函数中使用

随机推荐