测试数据整数搜索——Ny 90 整数划分

在改章节中,我们主要介绍测试数据整数的内容,自我感觉有个不错的建议和大家分享下

1) 目题

整数分别

时光制限：3000 ms | 存内制限：65535 KB

难度：3

描述

将正整数n表现成一系列正整数之和：n=n1+n2+…+nk，
其中n1≥n2≥…≥nk≥1，k≥1。
正整数n的这类表现称为正整数n的分别。求正整数n的不
同分别个数。
例如正整数6有如下11种不同的分别：
6；
5+1；
4+2，4+1+1；
3+3，3+2+1，3+1+1+1；
2+2+2，2+2+1+1，2+1+1+1+1；
1+1+1+1+1+1。

输入

每日一道理
试试看——不是像企鹅那样静静的站在海边，翘首企盼机会的来临，而是如苍鹰一般不停的翻飞盘旋，执著的寻求。试试看——不是面对峰回路转、杂草丛生的前途枉自嗟叹，而是披荆斩棘，举步探索。试试看——不是拘泥于命运的禁锢，听凭命运的摆布，而是奋力敲击其神秘的门扉，使之洞开一个新的天地。微笑着，去唱生活的歌谣。

第一行是测试据数的数目M（1<=M<=10）。以下每行均包括一个整数n（1<=n<=10）。

输出

输出每组测试据数有多少种分法。

例样输入

例样输出

2) 题意

不再赘述。

3) 据数范围

测试据数数和n的值最大为10，据数量很小，手算都很轻易。

4) 算法

搜索法

为了免避搜索到重复的分别法方，定规：

分别序列a₁+a₂+…+a_n，a_i>=a_i+1, 1<=i<n。

如下图是分别整数6的一棵搜索树。两方格内的字数是分别出的两个数。如6可以分别为5+1,4+2,3+3。

图中以红色字数为根节点一棵树，即为该红色字数的分别搜索树。

5) 代码

#include <iostream>
#include <cstdio>
#include <ctime>

using namespace std;

int count;

//num为要分别的数，minn为许允分别出的最小数
void Backtrack(int num, int minn)
{
	//printf("%d %d\n", num, minn);
	count++;
	if (num > 1)
	{
		int left, right;
		for (left = num-minn, right = minn; left >= right; left--, right++)
		{
			Backtrack(left, right);
		}
	}
}

int main(void)
{
	int ncases;
	scanf("%d", &ncases);
	while (ncases-- != 0)
	{
		int num;
		scanf("%d", &num);
		count = 0;
		//clock_t start, finish;
		//start = clock();
		Backtrack(num, 1);
		//finish = clock();
		//printf("%lf\n",  (double)(finish - start) / CLOCKS_PER_SEC);
		printf("%d\n", count);
	}
	return 0;
}

/*
#include<iostream>
using namespace std;
int q(int n,int m)
{
	if((n<1)||(m<1) )return 0;
	if(n==1||m==1) return 1;
	if(n<m) return q(n,n);
	if(n==m)return q(n,m-1)+1;
	return q(n,m-1)+q(n-m,m);
}
int main()
{
	int a;
	cin>>a;
	while(a--)
	{
		int n;
		cin>>n;
		cout<<q(n,n)<<endl;
	}
	return 0;
}
*/

6) 测试据数

7) 提交结果

第一次，没有按输入式格来，心粗。

文章结束给大家分享下程序员的一些笑话语录：一位程序员去海边游泳，由于水性不佳，游不回岸了，于是他挥着手臂，大声求.救：“F1，F1！”