查人人中国名人网深圳哪里有玩赛车:c++ n-k集
来源：百度文库 编辑：查人人中国名人网 时间：2024/05/12 08:49:17
我们称一个自然数集合X为一个n-k集，如果它具有如下性质：（1）对于X中的每一个元素x有1=<x<=n；（2）X中的所有元素之和均大于k；（3）X中不包括连续自然数。
请写一个程序：读入两个整数n和k；计算所有不同的n-k集的数目。例如，n=5，k=6，则n-k集的数目是3。
分析1：设f(n,k)为n-k集的数目。
当n=1，
若k<0，则f(n,k)=1；
若k>=1，则f(n,k)=0；
当n=2，
若k<1，则有集合{2}、{1}符合要求，所以f(n,k)=2；
若k=1，则有集合{2}符合要求，所以f(n,k)=1；
若k>1，f(n,k)=0；
若n>2，X的非空子集可分为两类：
第一类集合含n，设A是这样的一个集合A={n}ÈB，其中B的元素来自1、2、…、n-2：
如果n>k，那么{n}本身也满足要求；另外，1、2、…、n-2中任何无相邻元素的集合子集C，因n-2>0，所以这样的集合至少有一个。于是{n}ÈC符合要求；C中的元素之和总大于0，这种集合个数有1+f(n-2,0)个。
如果n=k，A={n}ÈB，B中的元素之和总大于0，这样的B有f(n-2,0) 个；
如果n<k，A={n}ÈB，B中的元素之和应大于k-n，这样的B有f(n-2,k-n)个；
第二类集合D不含n，则D的元素来自1、2、…、n-1，且元素之和大于k；这种集合有f(n-1,k)个。
分析2：
设 为n-k集的数目。
当k<1时，
若n=1，则 =1；若n=2，则 =1；
当k=1时，
若n=1，则 =0；若n=2，则 =1；
当k=2时，
若n=1，则 =0；若n=2，则 =1；
若n>2，则 = + ；
当k>2时，
若n=1，则 =0；若n=2，则 =0；
若n>2，则 = + ；
请写一个程序：读入两个整数n和k；计算所有不同的n-k集的数目。例如，n=5，k=6，则n-k集的数目是3。
分析1：设f(n,k)为n-k集的数目。
当n=1，
若k<0，则f(n,k)=1；
若k>=1，则f(n,k)=0；
当n=2，
若k<1，则有集合{2}、{1}符合要求，所以f(n,k)=2；
若k=1，则有集合{2}符合要求，所以f(n,k)=1；
若k>1，f(n,k)=0；
若n>2，X的非空子集可分为两类：
第一类集合含n，设A是这样的一个集合A={n}ÈB，其中B的元素来自1、2、…、n-2：
如果n>k，那么{n}本身也满足要求；另外，1、2、…、n-2中任何无相邻元素的集合子集C，因n-2>0，所以这样的集合至少有一个。于是{n}ÈC符合要求；C中的元素之和总大于0，这种集合个数有1+f(n-2,0)个。
如果n=k，A={n}ÈB，B中的元素之和总大于0，这样的B有f(n-2,0) 个；
如果n<k，A={n}ÈB，B中的元素之和应大于k-n，这样的B有f(n-2,k-n)个；
第二类集合D不含n，则D的元素来自1、2、…、n-1，且元素之和大于k；这种集合有f(n-1,k)个。
分析2：
设 为n-k集的数目。
当k<1时，
若n=1，则 =1；若n=2，则 =1；
当k=1时，
若n=1，则 =0；若n=2，则 =1；
当k=2时，
若n=1，则 =0；若n=2，则 =1；
若n>2，则 = + ；
当k>2时，
若n=1，则 =0；若n=2，则 =0；
若n>2，则 = + ；
(2)X中的所有元素之和均大于k
什么意思，是所有元素之和大于k吧？
哇，楼主自己已经分析得这么清楚了，那就直接递归吧
q