一周总结：11.8~11.14——递归，贪心（C++）

【问题描述】
　　找出 n个自然数中取 r 个数的组合。
【输入格式】
　　n 　　r
【输出格式】
　　枚举所有可能
【样例】
　　in：
5
3
　　out：
5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1

#include 
int a[100];
void combrecur(int n, int r)
{
    for(int i=n; i>=r; i--){
        a[r]=i;
        if(r>1){
            combrecur(i-1,r-1);
        }else{
            for(int j=a[0];j>0;j--){
                printf("%d",a[j]);
                printf(" ");
            }
            printf("n");
        }
    }
}
void main()
{
    int n,r;
    scanf("%d %d",&n,&r);
    if(n>r){
        a[0]=r;
        combrecur(n,r);
    }
}

【问题描述】
　　已知一些孩子和一些糖果，每个孩子有需求因子g，每个糖果有大小s，当某个糖果的大小s大于等于某个孩子的需求因子g时，代表该糖果能满足孩子；问用这些糖果，最多能满足多少孩子？（注意：每个孩子最多只能用一个糖果满足）
【输入格式】
　　第一、二行输入两个数n和m，分别代表g和s的个数
　　第三行为需求因子数组g
　　第四行为糖果大小数组s
【样例】
　　in:
6
5
5 10 2 9 15 9
6 1 20 3 8
　　out:
3
【解题思路】
　　贪心算法的经典例题。当糖果的大小“刚好”满足孩子的需求因子时（刚好就大一点），最“贪心”，因此，首先要让两个数组排序，这样才能通过比较得出较优解。通过比较，选出能满足孩子的糖果（遍历两个数组）。在这题中，我们只需要求出糖果最多能满足多少孩子即可。

#include 
#include 
#include 
using namespace std;

int findContentChildren(std::vector& g, std::vector& s){
	std::sort(g.begin(),g.end());
	std::sort(s.begin(),s.end());			//排序
	int child = 0;
	int cookie = 0;							//定义child和cookie变量，表示现在到第几个数
	while(child < g.size() && cookie < s.size()) {		//循环范围
		if(g[child] <= s[cookie]){
			child++;						//如果满足条件，意味着满足了一个孩子，child+1
		}
	    cookie++;							//cookie变量无论有无满足孩子都要+1
	}
	return child;							//返回满足的孩子数
}

int main(){
	std::vector g;
	std::vector s;
	int n,m;
	cin >> n >>m;
	int a,b;
	for(int i=0; i> a;
		g.push_back(a);
	}
	for(int j=0; j> b;
		s.push_back(b);
	}   
	
	cout< 
最大分解-贪心 
【问题描述】
 　　给出一个正整数n，求一个和最大的序列a0，a1，a2，……，ap，满足n=a0>a1>a2>……>ap且ai+1是ai的约数，输出a1+a2+……+ap的最大值
 【输入格式】
 　　输入仅一行，包含一个正整数n
 【输出格式】
 　　一个正整数，表示最大的序列和，即a1+a2+……+ap的最大值
 【样例】
 　　in：10
 　　out：6
 【样例说明】
 　　p=2
 　　a0=10，a1=5，a2=1，6=5+1
 【思路】
 　　这是一个对贪心的小练习，约数：当a能整除b，那么a就是b的约数（即：b>a）。题目要求是给定一个整数n，找出一组递减的数，里面的数都小于n并且前一个都能被后一个整除，因此能想到用for循环（while也可），遍历小于n的所有整数，看看它们是否能整除前一个数，如果可以，即符合题目要求，计算它们的总和。
 
#include 
using namespace std;

int fun(int n,int sum){

    for(int i=n-1; i!=0; i--){		 //一开始是用双重for，后来发现一层就可以解决了
    	if(n%i==0){
		   sum += i;			    //计算所有i的总和，i既是符合题目要求的数
		   n=i;                     //这里是重点，记得要把i赋值给n
        }
	}

	return sum;
}

int main(){
	int n,sum;
	sum=0;
	cin>>n;
	cout<