C趣味编程百例(32)

核心提示：96.选美比赛97.满足特异条件的数列98.八皇后问题96.选美比赛 在选美大奖赛的半决胜赛现场，有一批选手参加比赛，C趣味编程百例(32)，比赛的规则是最后得分越高，名次越低，不断地向前推就可以解决问题，下面的程序答应用户选定M和N，当半决决赛结束时，要在现场按照选手的出场顺序公布最后得分和最后名次

96.选美比赛
97.满足特异条件的数列
98.八皇后问题



96.选美比赛
　 在选美大奖赛的半决胜赛现场，有一批选手参加比赛，比赛的规则是最后得分越高，名次越低。当半决决赛结束时，要在现场按照选手的出场顺序公布最后得分和最后名次，获得相同分数的选手具有相同的名次，名次连续编号，不用考虑同名次的选手人数。例如：
　 选手序号：　　　　 1，2，3，4，5，6，7
　 选手得分：　　　　 5，3，4，7，3，5，6
　 则输出名次为：　　 3，1，2，5，1，3，4
　 请编程帮助大奖赛组委会完成半决赛的评分和排名工作。
*问题分析与算法设计
　 问题用程序设计语言加以表达的话，即为：将数组A中的整数从小到大进行连续编号，要求不改变数组中元素的顺序，且相同的整数要具有相同的编号。
　 普通的排序方法均要改变数组元素原来的顺序，显然不能满足要求。为此，引入一个专门存放名次的数组，再采用通常的算法：在尚未排出名次的元素中找出最小值，并对具有相同值的元素进行处理，重复这一过程，直到全部元素排好为止。
*程序与程序注释
#include<stdio.h>
#define NUM 7　　　 /*定义要处理的人数*/
int a[NUM+1]={0,5,3,4,7,3,5,6};　　　 /*为简单直接定义选手的分数*/
int m[NUM+1],l[NUM+1];　  /*m:已编名次的标记数组　 l:记录同名次元素的下标*/
void main()
{
　 int i,smallest,num,k,j;
　 num=1;　　　　　　　　　　　 /*名次*/
　 for(i=1;i<=NUM;i++)　　　 /*控制扫描整个数组，每次处理一个名次*/
　　  if(m[i]==0)　　 /*若尚未进行名次处理(即找到第一个尚未处理的元素)*/
　　　{
　　　　 smallest=a[i];　　 /*取第一个未处理的元素作为当前的最小值*/
　　　　 k=1;　　　　　  /*数组l的下标，同名次的人数*/
　　　　 l[k]=i;　　　  /*记录分值为smallest的同名次元素的下标*/
　　　　 for(j=i+1;j<=NUM;j++)　 /*从下一个元素开始对余下的元素进行处理*/
　　　　　  if(m[j]==0)　　　　　  /*若为尚未进行处理的元素*/
　　　　　　　 if(a[j]<smallest)　  /*分数小于当前最小值*/
　　　　　　　 {
　　　　　　　　  smallest=a[j];　  /*则重新设置当覵最小值*/
　　　　　　　　  k=0;　　　　　　  /*重新设置同名次人数*/
　　　　　　　　  l[++k]=j;　　　　 /*重新记录同名次元素下标*/
　　　　　　　 }
　　　　　　　 else if(a[j]==smallest)　　 /*若与当前最低分相同*/
　　　　　　　　  l[++k]=j;　　　　　　　 /*记录同名次的元素下标*/
　　　　 for(j=1;j<=k;j++)　　　 /*对同名次的元素进行名次处理*/
　　　　　  m[l[j>=num;
　　　　 num++;　　　　　　　　  /*名次加1*/
　　　　 i=0;　　　　  /*控制重新开始，找下一个没排名次的元素*/
　 }
　 PRintf("Player-No score Rank\n");
　 for(j=1;j<=NUM;j++)　　　　　　　　 /*控制输出*/
　　  printf(" %3d　　  %4d　　  %4d\n",j,a[j],m[j]);
}

*运行结果
　　　　 Player-No　　　　 Score　　　　 Rank
　　　　　  1　　　　　　　  5　　　　　　 3
　　　　　  2　　　　　　　  3　　　　　　 1
　　　　　  3　　　　　　　  4　　　　　　 2
　　　　　　5　　　　　　　　7　　　　　　 5
　　　　　  5　　　　　　　  3　　　　　　 1
　　　　　  3　　　　　　　　5　　　　　　 3
　　　　　  7　　　　　　　  6　　　　　　 4

*思考题
　 若将原题中的“名次连续编号，不用考虑同名次的选手人数”，改为”根据同名次的选手人数对选手的名次进行编号“，那么应该怎样修改程序。


97.满足特异条件的数列
　 输入m和n(20>=m>=n>0)求出满足以下方程的正整数数列 i1,i2,...,in，使得：i1+i1+...+in=m，且i1>=i2...>=in。例如：
　 当n=4, m=8时，将得到如下5 个数列：
　　　　 5 1 1 1　　  4 2 1 1　　  3 3 1 1　　  3 2 2 1　　  2 2 2 2
*问题分析与算法设计
　 可将原题抽象为：将M分解为N个整数，且N个整数的和为M，i1>=i2>=...>=in。分解整数的方法很低多，由于题目中有"i1>=i2>=.....>=in，提示我们可先确定最右边in元素的值为1，然后按照条件使前一个元素的值一定大于等于当前元素的值，不断地向前推就可以解决问题。下面的程序答应用户选定M和N，输出满足条件的所有数列。
*程序与程序注释
#include<stdio.h>
#define NUM 10　　  /*答应分解的最大元素数量*/
int i[NUM];