成都.金山笔试题

#include <iostream>
#include <algorithm>
using namespace std;
/*
把一个自然数M分分解为N个不同自然数的和有几种分发方法
如:
输入 5 2
输出 2
原因:
    5=2+3
    5=1+4
思路:
    按从大到小排序
    (m-n_to_0+m%n)/n+n-1 至 min(m-n_to_0+1,前一个数)
*/

unsigned _sum_total(unsigned m,unsigned n,unsigned max_number){
    if(n==1)return (m<max_number?1:0);

    unsigned n_to_1=(n+1)*n/2;
    if(m<n_to_1)return 0;

    unsigned total=0,n_to_0=n_to_1-n;

    max_number=min(m-n_to_0+1,max_number);

    for(unsigned i=(m-n_to_0+m%n)/n+n-1;i<max_number;++i){
        total+=_sum_total(m-i,n-1,i);
    }
    return total;
}

unsigned sum_total(unsigned m,unsigned n){
    return _sum_total(m,n,m-(n-1)*n/2+1);
}

int main(int argc, char* argv[]) {

    cout<<sum_total(7,3)<<'\n';    //1+2+4
    cout<<sum_total(8,3)<<'\n';    //1+2+5 1+3+4
    cout<<sum_total(5,2)<<'\n';    //1+4 2+3
    cout<<sum_total(5,3)<<'\n';   
    system("pause");
    return 0;
}

,上一个想错了，这次这个应该没错了：

#include <stdio.h>
unsigned int get_count(unsigned int m,unsigned int n);
int main(int argc, char* argv[])
{
	unsigned int result=0;
	result=get_count(7,4);   
    printf("[%u]\n",result);   
    result=get_count(6,4);   
    printf("[%u]\n",result);  
	return (0);
}

unsigned int get_count(unsigned int m,unsigned int n)
{
	int result=0;
	if(n==2){
		return m/2;
	}
	else
	{
		for(unsigned int i=1;i<(m/n+1);i++)
		{
			result+=get_count(m-i,n-1);
		}
		return result;
	}
}