欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

凑数

程序员文章站 2022-05-08 22:12:50
...

凑数

啊啊啊啊我一遍过了好开心qwq

总时间限制: 1000ms 单个测试点时间限制: 100ms 内存限制: 65536kB

描述

我们希望利用不大于K的质数来凑出一个新的数M。

每个质数可以重复选择也可以不选择,需要使得选出来的数之和是M。

求总共有多少种不同的选法?

2 <= K <= 15,2 <= M <= 100。

//k很小,所以直接把2,3,5,7,11,13列出来就行

输入

输入两个整数,K和M,用空格隔开。

输出

输出一个整数,不同的选法的总数。

样例输入

5 20

样例输出

11

来源

2019心理信管计算概论期末

思路

  1. 首先找规律,发现用不大于5的质数分解8有三种方法:2+3+3,2+2+2+2,5+3。
    怎么区分2+2+2+2、3+3+2和5+3?
    最大的那个质数不同,所以就想要把结果按照“分解中最大的一个质数”分类,那么就需要定义一个“必须使用质数k分解m的方法数”,即d(k,m)
  2. 如果k比m要大,那么就说明“必须使用k”是不可行的,返回0;
    如果k和m相等,那么就说明分解方式就只有一种,即它本身,返回1;
    如果k比m要小,那么就说明“必须使用质数k”意味着我们可以从m中先拿出一个k来,然后剩下的部分使用不大于k的质数分解,即d(k,m)=ans(k,m-k)
  3. 至于ans(k,m),它等于∑d(zhishu[i],m),zhishu[i]<=k,所以k如果比m小或者大都没问题,都可以按这个方式表达
  4. 然后就按照这个想法把ans(5,8)试着表示了一遍
//装作是数学公式
ans(5,8)=d(5,8)+d(3,8)+d(2,8)
d(5,8)=ans(5,3)
	  =d(5,3)+d(3,3)+d(2,3)
	  =0+1+ans(2,1)
	  =1+d(2,1)
	  =1
d(3,8)=ans(3,5)
	  =d(3,5)+d(2,5)
	  =ans(3,2)+ans(2,3)
	  =d(3,2)+d(2,2)+d(2,1)
	  =0+1+0
	  =1
d(2,8)=ans(2,6)
	  =d(2,6)
	  =ans(2,4)
	  =d(2,4)
	  =ans(2,2)
	  =d(2,2)
	  =1

其实两个函数反应了在求解过程中对于k和m两个参量的消解,d主要是用来减小待分解的m,而ans则是为了把小于k的质数挑出来分别把它们当做分解结果中的最大的那个质数求解,这样就构成了两个函数的相互引用。

代码

#include <stdio.h>
#include <string.h>
#include <math.h>
int zhishu[6] = { 2,3,5,7,11,13 };
int d(int, int);
int ans(int, int);
int d(int k, int m)//必须包含k的分解方法数
{
	if (k == m)return 1;
	if (k < m)return ans(k, m - k);
	if (k > m)return 0;
}
int ans(int k, int m)//使用不小于k的分解方法数
{
	int y = 0;
	for (int i = 0; zhishu[i] <= k; i++)
	{
		y += d(zhishu[i], m);
	}
	return y;
}
int main()
{
	int k, m;
	scanf("%d%d", &k, &m);
	printf("%d", ans(k, m));
	return 0;
}
//这是当时的草稿
//15,2:2 15,3:3 15,4:2+2 15.5:2+3
//3,5:2+3 2,5:none
//5,7:2+2+3 5,8:2+3+3,2+2+2+2,5+3 d(2,8)+d(3,8)(d(3,5))+d(5,8)
//d(2,8)=d(2,6)=d(2,4)
//d(5,8)=d(5,3)=0
//d(k,m)是必须要包含k的一个分解
//ans(5,8)=d(5,8)+d(3,8)+d(2,8)
//d(5,8)=ans(5,3)=d(5,3)+d(3,3)+d(2,3)=0+1+ans(2,1)=1+0=1
//d(3,8)=ans(3,5)=d(3,5)+d(2,5)=ans(3,2)+ans(2,3)=d(3,2)+d(2,2)+d(2,1)=0+1+0=1
//d(2,8)=ans(2,6)=d(2,6)=ans(2,4)=d(2,4)=ans(2,2)=d(2,2)=1
//2,3,5,7,11,13
//d(2,7)
相关标签: 递归法