8

【分析】“動態規劃”問題，此題情境與“將一個整數m分成n個整數之和”類似。

        設f[m][n]為將m分成最多n份的方案數，且其中的方案不重復，即每個方案前一個份的值一定不會比后面的大。則有：f[m][n] = f[m][n - 1] + f[m - n][n]，其中f[m][1]=1、f[0][n]=1。其中的含義是：分的方案包含兩種，一是方案中不含有空的情況，則從每個盤子里面拿出一個來也不影響最終的結果，即f[m][n] = f[m - n][n]，二是方案中含有的空的情況，至于含有幾個空暫時不考慮，只用考慮一個空的就行，即f[m][n] = f[m][n - 1]，在這種遞歸調用中會重復調用含有空的情況，也就是最終包含了各種可能為空的情況。

源代碼：

#include <stdio.h>int fun(int m,int n){	if(m==0 || n==1)		return 1;	if(n>m)        return fun(m,m);  	else		return fun(m,n-1)+fun(m-n,n);	} int main(){	int t;	int K,M,N;	scanf("%d",&t);	while(t--)	{		scanf("%d %d",&M,&N);		K=fun(M,N);		PRintf("%d/n",K);		} 	return 0;}程序截圖：
2. （2010年北京郵電大學網院研究生機試真題）查找第K小數題目描述：查找一個數組的第K小的數，注意同樣大小算一樣大。 如  2 1 3 4 5 2 第三小數為3。輸入：輸入有多組數據。每組輸入n，然后輸入n個整數(1<=n<=1000)，再輸入k。輸出：輸出第k小的整數。樣例輸入：62 1 3 5 2 23樣例輸出：3
源代碼：
#include <stdio.h>#include <iostream>                //按C++類型提交 #include <algorithm>using namespace std;#define maxn 1010int main(){	int i,j,t,flag;	int n,k;	int a[maxn],b[maxn];           //ab兩數組分別保存輸入數據與刪除輸入數據中重復元素后的數據 	while(scanf("%d",&n)!=EOF)	{		for(i=0;i<n;i++)			scanf("%d",&a[i]);		scanf("%d",&k);		sort(a,a+n);               //直接使用排序模板對輸入的n個數排序 		t=1;		b[0]=a[0];                 //首先保存a數組第一個數據 		for(i=1;i<n;i++)           //保存輸入數據（不保存重復） 		{			flag=1;			for(j=0;j<t;j++)			{				if(a[i]==b[j])				{					flag=0;					break;				}			}			if(flag==1)				b[t++]=a[i];		}		printf("%d/n",b[k-1]);     //直接根據下標完成查找 	}	return 0;}程序截圖：
3. （2005年華中科技大學計算機保研機試真題）找位置
題目描述：對給定的一個字符串，找出有重復的字符，并給出其位置，如：abcaaAB12ab12輸出：a，1；a，4；a，5；a，10，b，2；b，11，1，8；1，12， 2，9；2，13。輸入：輸入包括一個由字母和數字組成的字符串，其長度不超過100。輸出：可能有多組測試數據，對于每組數據，按照樣例輸出的格式將字符出現的位置標出。樣例輸入：abcaaAB12ab12樣例輸出：a:0,a:3,a:4,a:9b:1,b:101:7,1:112:8,2:12提示：1、下標從0開始。2、相同的字母在一行表示出其出現過的位置。
【分析】注意查找有重復的字符，在輸出時通過設定一些特殊變量控制輸出格式。
源代碼：
#include <stdio.h>#include <string.h>#define maxlen 110void FindRepetation(char str[],int len)          //查重并輸出 {	int i,j;	int first;                                   //first記錄重復字符是否第一次訪問，1-否 0-是 	int visited[maxlen]={0};                     //visited數組記錄字符串中每個字符的訪問情況，1-已訪問 0-未訪問 	for(i=0;i<len;i++)	{		first=1;		for(j=i+1;j<len;j++)                     //查找重復出現的字符 		{			if(str[i]==str[j] && visited[i]==0)  //第i+1個字符重復出現，且之前未被訪問 			{				if(first==1)                     //是第一次訪問這個字符，前面不輸出逗號，并置first=0 				{					printf("%c:%d",str[i],i);					first=0;				}				printf(",%c:%d",str[j],j);       //后面發現該字符繼續出現，前面輸出逗號 				visited[j]=1;                    //這些字符的訪問標記置為1 			}		}		if(first==0)                             //每組重復字符及位置輸出完成后換行 			printf("/n");	}}int main(){	int len;	char str[maxlen];	while(scanf("%s",str)!=EOF)                  //獲得輸入字符串的長度后開始查找重復字符并按格式輸出 	{		len=strlen(str);		FindRepetation(str,len);	}	return 0;}程序截圖：