IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> 整数划分(C语言) -> 正文阅读

[C++知识库]整数划分(C语言)

整数划分(C语言)

参考博客:https://www.cnblogs.com/wkfvawl/p/11486992.html

思路整理

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划分的个数为q(n,m);

当n=6时我们可以获得以下这几种划分(注意,例子中m>=6)

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

  1. 当n=1时,不论m的值为多少(m>0),只有一种划分即{1}。因此 q(1,m) =1
  2. 当m=1时,不论n的值为多少,只有一种划分即n个1,{1,1,1,…,1}。 因此 q(n,1) =1。;
  3. 当n<m时,由于划分中不可能出现负数,因此就相当q(n,n),即q(n,m)=q(n,n),m>=n。
  4. 但n>m时,根据划分中是否包含最大值m,可以分为两种情况:
    (1) 划分中包含m的情况,即{m, {x1,x2,…xi}}, 其中{x1,x2,… xi} 的和为n-m,可能再次出现m,因此是(n-m)的m划分,因此这种划分个数为q(n-m, m)。
    (2) 划分中不包含m的情况,则划分中所有值都比m小,即n的(m-1)划分,个数为f(n,m-1)。因此 q(n, m) = q(n-m, m)+q(n,m-1)
  5. 当n=m时,根据划分中是否包含n,可以分为两种情况:
    (1) 划分中包含n的情况,只有一个即{n};
    (2) 划分中不包含n的情况,这时划分中最大的数字也一定比n小,即n的所有(n-1)划分。因此 q(n,n) =1 + q(n,n-1)

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 5
int mark[200];
int q2(int n,int m)
{
    if(n==1|| m==1) return 1;
    if(m==n)
    {
        return 1+q2(n,n-1);
    }
    if(m>n) return q2(n,n);
    if(m<n) return q2(n,m-1)+q2(n-m,m);
}


//输出划分的所有情况
void print(int sum, int k, int prio)
{
    if (sum > MAXSIZE)
        return;
    if (sum == MAXSIZE)
    {
        int i;
        for (i = 0; i < k - 1; i++)
        {
            printf("%d+",mark[i]);
        }
        printf("%d\n",mark[i]);
    }
    else {
        for (int j = prio; j > 0; j--)
        {
            mark[k] = j;
            sum += j;
            print(sum, k + 1, j);//递归调用
            sum -= j;//恢复现场
        }
    }
}
int main()
{
    int i;
    int num = q2(MAXSIZE,MAXSIZE);
    printf("%d有%d种分法:\n",MAXSIZE,num);
    print(0,0,MAXSIZE);
    return 0;
}

结果

  C++知识库 最新文章
【C++】友元、嵌套类、异常、RTTI、类型转换
通讯录的思路与实现(C语言)
C++PrimerPlus 第七章 函数-C++的编程模块(
Problem C: 算法9-9~9-12:平衡二叉树的基本
MSVC C++ UTF-8编程
C++进阶 多态原理
简单string类c++实现
我的年度总结
【C语言】以深厚地基筑伟岸高楼-基础篇(六
c语言常见错误合集
上一篇文章      下一篇文章      查看所有文章
加:2021-10-17 11:49:20  更:2021-10-17 11:51:41 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/14 14:58:54-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码